13  Propositional Logic

14 Propositional Logic

Week 6, Session 1. CSS 342.

14.1 Warmup

Write a function that takes two booleans a and b and returns !(a && b). Now write a different expression that produces the same result using only || and !. (Answer below; do not peek.)

// !(a && b) ≡ !a || !b   (De Morgan)
bool nand(bool a, bool b) { return !a || !b; }

This is the kind of equivalence we will formalize this chapter.

14.2 Learning objectives

  1. Construct and evaluate truth tables for compound propositions.
  2. Distinguish between the contrapositive (logically equivalent) and the converse (not equivalent).
  3. Identify tautologies and contradictions in propositional formulas.
  4. Translate C++ if conditions into propositional logic and vice versa.
  5. Apply logical equivalences to simplify boolean conditions in code.

14.3 Propositions and connectives

A proposition is a statement that is either true or false. “It is raining” is a proposition. “What time is it?” is not.

We name propositions with letters: P, Q, R. Then we combine them with connectives:

Symbol Read as C++ Meaning
¬P not P !P true if P is false
P ∧ Q P and Q P && Q true if both true
P ∨ Q P or Q P \|\| Q true if at least one true
P → Q if P then Q (no direct) false only when P true, Q false
P ↔︎ Q P iff Q P == Q true if P and Q match

14.4 Truth tables

A truth table enumerates all combinations of inputs and shows the output.

P Q P ∧ Q P ∨ Q P → Q P ↔︎ Q
T T T T T T
T F F T F F
F T F T T F
F F F F T T

The implication row that confuses students: F → T = T. “If pigs fly, then it is Tuesday” is vacuously true because the hypothesis is false. The implication is only false when you have a true premise leading to a false conclusion.

14.5 De Morgan’s laws

The two equivalences that show up most in code:

\[ \neg(P \wedge Q) \equiv \neg P \vee \neg Q \]

\[ \neg(P \vee Q) \equiv \neg P \wedge \neg Q \]

In C++:

if (!(a && b))      // is the same as
if (!a || !b)

if (!(a || b))      // is the same as
if (!a && !b)

The first equivalence is the one I use to clean up code. If I see if (!(x.empty() && y.empty())) I rewrite it as if (!x.empty() || !y.empty()) — same logic, easier to read.

14.6 Contrapositive, converse, inverse

Starting from “if P then Q”:

  • Contrapositive: “if not Q then not P” — logically equivalent to the original.
  • Converse: “if Q then P” — not equivalent. Easy mistake.
  • Inverse: “if not P then not Q” — not equivalent.

Example. Original: “if it rains, the ground is wet.”

  • Contrapositive: “if the ground is not wet, it is not raining.” Always true if the original is true.
  • Converse: “if the ground is wet, it is raining.” Could be false — sprinklers exist.
  • Inverse: “if it does not rain, the ground is not wet.” Could be false — sprinklers.

In code, this matters when reasoning about preconditions. “If n > 0, f(n) returns a positive number” lets you conclude “if f(n) returns ≤ 0, then n ≤ 0” (contrapositive). It does not let you conclude “if f(n) returns positive, then n > 0” (converse).

14.7 Tautology and contradiction

A tautology is true in every row of the truth table. Example: P ∨ ¬P (“the law of excluded middle”). Always true.

A contradiction is false in every row. Example: P ∧ ¬P. Always false.

If you compile if (x > 0 || x <= 0) — the body always runs. The compiler probably warns. That is a tautology in disguise.

14.8 Application: simplifying conditions

// Before:
if (!(a >= 10) && !(b >= 10)) { ... }

// Use De Morgan:
if (!((a >= 10) || (b >= 10))) { ... }

// Simplify the negations:
if (a < 10 && b < 10) { ... }

Three forms, all equivalent. The third is the clearest.

14.9 assert as propositional logic

assert(condition) in C++ formalizes a runtime check of a propositional statement. If the condition is false, the program aborts.

#include <cassert>

int divide(int a, int b) {
  assert(b != 0);    // precondition: b is nonzero
  return a / b;
}

The assertion is the formal precondition: “this function may only be called when b != 0.” It documents AND enforces.

14.10 Try it

Write the truth table for (P → Q) → (¬Q → ¬P). What kind of expression is it?

Hint: it is the equivalence of an implication and its contrapositive. The truth table is all T. It is a tautology.

14.11 Self-check

1. Which is logically equivalent to !(x > 0 && y > 0)?
b. De Morgan + careful negation: !(x > 0) is x <= 0, not x < 0.
2. The contrapositive of "if it compiles, then it works" is:
c. Contrapositive negates and swaps. (The statement is false, but the contrapositive is the correct logical form.)

14.12 Challenges

  1. Build a truth table for (P ∨ Q) ∧ (¬P ∨ R). Identify when it is true.
  2. Simplify !(!a || !b) || (!a && !b) using De Morgan. (Answer: a && b || (!a && !b) = a == b.)
  3. Translate “every student who passed has score ≥ 60” into propositional form using passed(s) and score(s).

14.13 Where this fits

Logic underpins reasoning about programs: invariants, preconditions, complexity proofs. The next chapter generalizes from propositions to predicates (quantified statements).

You are here Coming up
Propositions, connectives, De Morgan, contrapositive vs. converse Chapter 12: predicate logic and Boolean algebra