Log in
MODULE 01

Propositional Logic

Enter expressions using AND, OR, NOT, XOR, IMPLIES (->), IFF (<->), or symbols & | ~ ^ -> <->. Example: (P AND Q) -> R

Understanding Propositional Logic

Propositional logic is the branch of mathematical logic that deals with statements (propositions) that are either true or false, and the ways these statements combine using logical connectives. Every argument, computer program condition, and digital circuit ultimately reduces to combinations of true/false statements linked by AND, OR, NOT, implication, and biconditional operators. Learning to build and read truth tables is the foundation for everything else in discrete mathematics, since more advanced topics like predicate logic, proofs, and boolean algebra all build directly on these rules.

Key Definitions & Formulas

  • Negation (¬P): true when P is false, and vice versa.
  • Conjunction (P ∧ Q): true only when both P and Q are true.
  • Disjunction (P ∨ Q): true when at least one of P, Q is true.
  • Implication (P → Q): false only when P is true and Q is false; otherwise true.
  • Biconditional (P ↔ Q): true when P and Q have the same truth value.
  • Tautology: a formula that is true in every row of its truth table (e.g. P ∨ ¬P).
  • Contradiction: a formula that is false in every row (e.g. P ∧ ¬P).

Worked Example

Consider the formula (P → Q) ↔ (¬P ∨ Q). Building the truth table across all 4 combinations of P and Q shows both sides always match — this identity is exactly why implication can always be rewritten as a disjunction, a rule used constantly when simplifying logical circuits and program conditions.

Where This Is Used

  • Writing correct if conditions and boolean expressions in programming.
  • Designing digital logic gates and circuits in computer engineering.
  • Formal verification of algorithms and mathematical proofs.
  • Database query conditions (SQL WHERE clauses are propositional formulas).