Hello class! As we approach the Mid Term on October 18th, I have put together this study guide to help you structure your revision. We will be going through these questions in detail during class, but please review the concepts below beforehand to make the most of our discussion.

1. Propositional Logic (Sections 1.1 - 1.3)

Make sure you are comfortable with translating English sentences into logical notation. Remember that a proposition must have a truth value (true or false).

  • Key Connectives: Conjunction ($p \land q$), Disjunction ($p \lor q$), and Implication ($p \rightarrow q$).
  • Variations of the Conditional: For a statement $p \rightarrow q$:
    • Converse: $q \rightarrow p$
    • Inverse: $\neg p \rightarrow \neg q$
    • Contrapositive: $\neg q \rightarrow \neg p$ (Remember: a statement is logically equivalent to its contrapositive!)
  • Logic Puzzles: Review the "Knights and Knaves" problems (Section 1.2). These are excellent for practicing consistency in truth values.
  • Logical Equivalences: Be ready to use De Morgan's Laws to negate compound propositions:
    $$\neg(p \land q) \equiv \neg p \lor \neg q$$
    $$\neg(p \lor q) \equiv \neg p \land \neg q$$

2. Predicates and Quantifiers (Sections 1.4 - 1.5)

We move from simple propositions to statements involving variables. Pay close attention to the domain (universe) of discourse.

  • Universal Quantifier ($\forall$): "For all" or "Every".
  • Existential Quantifier ($\exists$): "There exists" or "Some".
  • Negating Quantifiers: This is a common stumbling block. Remember to flip the quantifier and negate the predicate:
    $$\neg \forall x P(x) \equiv \exists x \neg P(x)$$
    $$\neg \exists x P(x) \equiv \forall x \neg P(x)$$
  • Nested Quantifiers: Order matters! $\forall x \exists y P(x, y)$ is not the same as $\exists y \forall x P(x, y)$. Review the examples in Section 1.5 regarding the "Loves" predicate $L(x,y)$ to understand the difference.

3. Methods of Proof (Sections 1.6 - 1.8)

The exam will test your ability to construct valid arguments.

  • Rules of Inference: Be familiar with Modus Ponens, Modus Tollens, and Hypothetical Syllogism.
  • Direct Proof: Assume $p$ is true, use definitions (like $n = 2k$ for even integers), and show $q$ is true.
  • Proof by Contraposition: To prove $p \rightarrow q$, assume $\neg q$ and prove $\neg p$. This is often easier for statements like "If $3n + 2$ is odd, then $n$ is odd."
  • Proof by Contradiction: Assume the statement is false and derive a logical contradiction (e.g., $1 = 0$ or $r \land \neg r$).
  • Counterexamples: To disprove a universal statement like "Every integer is less than its cube," you only need to find one specific case where it fails (e.g., consider negative integers).

Practice Materials

Please download and review the extra examples and solutions for each section below. We will solve selected problems from these files in class.

Study hard, and see you on the 18th!