DISCRETE MATHEMATICS

Unit 2: Propositional Logic & Rules of Inference

Statement / Proposition

A declarative sentence that is either true or false, but not both.

Argument

A list of statements called premises followed by a final statement called the conclusion.

Tautology

A statement form that is always true regardless of the truth values of its variables (e.g., p ∨ ¬p).

Contradiction

A statement form that is always false regardless of its variables (e.g., p ∧ ¬p).

Contingency

A statement that is neither a tautology nor a contradiction.

Conjunction (p ∧ q)

True ONLY if both p and q are true. (AND gate)

Disjunction (p ∨ q)

True if at least one of p or q is true. (OR gate)

Exclusive OR / XOR (p ⊕ q)

True ONLY if exactly one of p or q is true.

NAND (p ↑ q) / NOR (p ↓ q)

NAND is False ONLY when both inputs are True. NOR is True ONLY when both inputs are False.

Conditional / Implication (p → q)

False ONLY when hypothesis p is True and conclusion q is False.

Conditional Variations

Given p → q, the Converse is q → p, the Inverse is ¬p → ¬q, and the Contrapositive is ¬q → ¬p. (Note: A conditional is logically equivalent to its contrapositive).

Proof by Contradiction (Indirect Proof)

Assuming the negation of the conclusion is true, and showing that it leads to a logical impossibility.

Modus Ponens

Modus Tollens

Hypothetical Syllogism

Disjunctive Syllogism

Resolution