Logical Thinking Beginner

A statement (or proposition) is a sentence that is either true (⊤) or false (⊥) — never both, never neither. Examples of statements: The sky is blue. (true), 2 + 2 = 5. (false). Non-statements include questions (Is it raining?) and commands (Close the door.), because they have no truth value.

• Statements are the atoms of logical reasoning.
• We use letters like p, q, r to represent them.
• The law of excluded middle: every statement is either true or false.
• The law of non-contradiction: no statement can be both true and false at once.

p = "It is raining."    q = "The ground is wet."
p can be ⊤ or ⊥; q can be ⊤ or ⊥ — independently.

The negation of a statement p is written ¬p (read "not p"). It flips the truth value: if p is true, ¬p is false, and vice versa.

Truth table for ¬p:
  p   | ¬p
  ----+----
  ⊤   | ⊥
  ⊥   | ⊤

Examples: If p = "It is raining," then ¬p = "It is not raining." Double negation restores the original: ¬(¬p) ≡ p.

The conjunction of p and q is written p ∧ q (read "p and q"). It is true only when both operands are true.

Truth table for p ∧ q:
  p   | q   | p ∧ q
  ----+-----+-------
  ⊤   | ⊤   | ⊤
  ⊤   | ⊥   | ⊥
  ⊥   | ⊤   | ⊥
  ⊥   | ⊥   | ⊥

Example: "It is sunny and warm" is only true on a day that is both sunny and warm. A single false component makes the whole conjunction false.

The disjunction of p and q is written p ∨ q (read "p or q"). In logic the default OR is inclusive: it is true when at least one operand is true.

Truth table for p ∨ q:
  p   | q   | p ∨ q
  ----+-----+-------
  ⊤   | ⊤   | ⊤
  ⊤   | ⊥   | ⊤
  ⊥   | ⊤   | ⊤
  ⊥   | ⊥   | ⊥

The only row that makes p ∨ q false is when both p and q are false. Compare: "You need a pen or a pencil" — having both is fine.

Exclusive-or, written p ⊕ q, is true when exactly one operand is true, but not both. It differs from inclusive-OR in the case where both inputs are true.

Truth table for p ⊕ q:
  p   | q   | p ⊕ q
  ----+-----+-------
  ⊤   | ⊤   | ⊥
  ⊤   | ⊥   | ⊤
  ⊥   | ⊤   | ⊤
  ⊥   | ⊥   | ⊥

Example: "You may have cake or ice cream (but not both)" is an exclusive-or. XOR is fundamental in digital circuits and cryptography.

The conditional (implication) p → q reads "if p then q." p is the hypothesis (antecedent) and q is the conclusion (consequent). The conditional is false only when the hypothesis is true but the conclusion is false.

Truth table for p → q:
  p   | q   | p → q
  ----+-----+-------
  ⊤   | ⊤   | ⊤
  ⊤   | ⊥   | ⊥
  ⊥   | ⊤   | ⊤
  ⊥   | ⊥   | ⊤

A promise "If it rains, I will bring an umbrella" is only broken if it rains and you do not bring an umbrella. A false hypothesis makes the implication vacuously true.

Logical connectives can be combined to form compound statements. Precedence (highest to lowest): ¬, then ∧, then ∨, then →. Parentheses override precedence.

• ¬p ∧ q means (¬p) ∧ q, not ¬(p ∧ q).
• To evaluate a compound statement, build a truth table row by row.

Evaluate ¬p ∨ q for p = ⊤, q = ⊥:
  ¬p = ⊥
  ⊥ ∨ ⊥ = ⊥
So the compound statement is false.

Truth tables always have 2ⁿ rows for n variables.