Discrete Math: Logic, Truth Tables & Proofs

Only when both p and q are true.

Only when both p and q are false. Logical OR is inclusive.

Only when p is true and q is false.

When p and q have the same truth value (both true or both false).

When exactly one of p and q is true.

Converse: q \to p Inverse: \neg p \to \neg q Contrapositive: \neg q \to \neg p

\neg p \vee q

p \wedge \neg q

\neg(p \wedge q) \equiv \neg p \vee \neg q \neg(p \vee q) \equiv \neg p \wedge \neg q

Tautology: always true (p ∨ ¬p). Contradiction: always false (p ∧ ¬p). Contingency: sometimes true, sometimes false.

16

\neg\forall x\, P(x) \equiv \exists x\, \neg P(x) \neg\exists x\, P(x) \equiv \forall x\, \neg P(x)

Modus ponens: p \to q , p , therefore q . Modus tollens: p \to q , \neg q , therefore \neg p .

Hypothetical: p \to q , q \to r , therefore p \to r . Disjunctive: p \vee q , \neg p , therefore q .

Invalid. From p \to q and q you cannot conclude p .

Direct: assume p , derive q . Contrapositive: assume \neg q , derive \neg p . Contradiction: assume the statement is false and derive something impossible.

Proof by contradiction: assume \sqrt{2} = a/b in lowest terms, then show a and b are both even.

1. Base case: show P(1) (or the first value). 2. Inductive step: assume P(k) (the inductive hypothesis) and prove P(k + 1) .