Unit 2: Logic Calculus

I. Orientation: The Logic of Propositions

Propositional logic (developed formally by George Boole, 1847, and refined by Frege and others) is the study of how the truth of statements combines. It treats declarative sentences as atomic values — true or false — and asks how compound statements built from them behave. In discrete structures it supplies the reasoning engine behind proofs, circuit design and Boolean algebra.

• Object of study: the proposition — a declarative sentence with exactly one truth value, T (true) or F (false).
• Bivalence assumption: every proposition is either true or false, never both, never neither.
• Truth-functionality: the truth value of a compound depends only on the truth values of its parts, not on meaning or context.
• Symbols used throughout: variables p, q, r for propositions; connectives ¬, ∧, ∨, →, ↔; values T, F (sometimes 1, 0).
• Precedence convention: ¬ binds tightest, then ∧, then ∨, then →, then ↔; parentheses override this.

II. Introduction to Logic

The formal treatment of valid reasoning.

Logic isolates the form of an argument from its content so that validity can be judged mechanically.

A. What logic studies

• Reasoning, not truth of premises: logic checks whether a conclusion follows from premises, e.g. "All primes > 2 are odd; 7 is prime; therefore 7 is odd."
• Form over content: replacing subjects with symbols exposes structure — "If p then q; p; therefore q" is valid whatever p, q mean.
• Propositional vs predicate logic: propositional logic handles whole statements as units; predicate logic (later) breaks them into subjects and predicates with quantifiers.

B. Why it matters in discrete structures

• Proof construction: every theorem proof is a chain of logically valid steps.
• Digital hardware: logic gates (AND, OR, NOT) are physical realisations of connectives.
• Program correctness: conditions in if/while statements are propositions evaluated at runtime.

III. Propositions and Compound Propositions

Atomic statements and the structures built from them.

A proposition is the smallest unit that carries a truth value; compound propositions are assembled from these using connectives.

A. Propositions

Definition: a proposition is a declarative sentence that is definitely true or definitely false.

• Valid propositions: "2 + 2 = 4" (T); "The Moon is a star" (F).
• Non-propositions: questions ("Is it raining?"), commands ("Close the door"), and paradoxes ("This sentence is false") — none has a fixed truth value.
• Open sentences: "x > 3" is not a proposition until x is fixed, since its value depends on the variable.

B. Compound propositions

Definition: a compound proposition is formed by combining one or more propositions with logical connectives.

• Atomic vs compound: p = "It is cold" is atomic; "It is cold and windy" is compound.
• Well-formed formulae: only expressions built by the grammar of connectives count, e.g. (p ∧ q) → ¬r is well-formed; p ∧ ∨ q is not.
• Component count sets table size: a formula with n distinct variables has 2ⁿ possible assignments.

IV. Basic Logical Operations

The three primitive connectives.

All compound propositions reduce to combinations of negation, conjunction and disjunction.

A. Conjunction

Definition: p ∧ q ("p and q") is true only when both operands are true.

p q | p ∧ q
T T |   T
T F |   F
F T |   F
F F |   F

• English cues: "and", "but", "moreover" — "It is raining but warm" is p ∧ q.
• Restrictive: conjunction only ever weakens truth; adding a conjunct can never make a false compound true.

B. Disjunction

Definition: p ∨ q ("p or q") is true when at least one operand is true (inclusive or).

p q | p ∨ q
T T |   T
T F |   T
F T |   T
F F |   F

1. Inclusive or (∨): true even when both hold — "coffee or tea" allows both.
2. Exclusive or (⊕): true only when exactly one holds — "you may have soup ⊕ salad" excludes both; T ⊕ T = F.

C. Negation

Definition: ¬p ("not p") reverses the truth value of p.

p | ¬p
T |  F
F |  T

• English cues: "not", "it is false that" — ¬p for "It is not cold".
• Involution: applying negation twice restores the original, ¬¬p ≡ p.

V. Propositions and Truth Tables

The exhaustive method for evaluating compounds.

A truth table lists every combination of operand values and the resulting value of the compound, making truth-functional behaviour fully explicit.

A. Constructing a truth table

• Row count: 2ⁿ rows for n variables — two variables give 4 rows, three give 8.
• Column order: list variables, then sub-expressions in order of precedence, then the whole formula.
• Filling variables: conventionally alternate T/F in a halving pattern so all combinations appear once.

B. Worked example

Evaluate (p ∧ q) ∨ ¬p:

p q | p ∧ q | ¬p | (p ∧ q) ∨ ¬p
T T |   T   |  F |      T
T F |   F   |  F |      F
F T |   F   |  T |      T
F F |   F   |  T |      T

• Reading the result: the compound is false only when p is true and q is false, giving a full behavioural specification.

VI. Tautologies and Contradiction

Formulae whose value is fixed regardless of inputs.

Some compounds carry the same truth value in every row; these anchor logical laws.

A. Tautology

Definition: a compound that is true in every row of its truth table.

• Canonical example: p ∨ ¬p (law of excluded middle) is T for both p = T and p = F.
• Notation: often written ⊤; a valid argument form corresponds to a tautology.

B. Contradiction

Definition: a compound that is false in every row.

• Canonical example: p ∧ ¬p (law of non-contradiction) is F for all values.
• Notation: often written ⊥; ¬(tautology) is always a contradiction.

C. Contingency

• Middle case: a formula true in some rows and false in others, e.g. p ∧ q. Most formulae are contingent; tautologies and contradictions are the extremes.

VII. Logical Equivalence

When two formulae behave identically.

Two propositions are logically equivalent when they have the same truth value under every assignment.

A. Definition and test

Definition: p ≡ q (also p ⇔ q) holds iff p ↔ q is a tautology.

• Table test: build both columns; if they match row-for-row, the formulae are equivalent.
• Example: ¬(p ∧ q) and ¬p ∨ ¬q share the column F,T,T,T, so ¬(p ∧ q) ≡ ¬p ∨ ¬q.

B. Key equivalence laws

• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q.
• Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
• Identity and domination: p ∧ T ≡ p; p ∨ T ≡ T.
• Idempotent: p ∨ p ≡ p; p ∧ p ≡ p.
• Double negation: ¬¬p ≡ p.

VIII. Conditional and Biconditional Statements

Implication and mutual implication.

These connectives express dependence and equivalence between propositions.

A. Conditional statement

Definition: p → q ("if p then q") is false only when the antecedent p is true and the consequent q is false.

p q | p → q
T T |   T
T F |   F
F T |   T
F F |   T

• Vacuous truth: when p is false the conditional is true regardless of q — "If 2 is odd, then 3 = 3" is T.
• Terminology: p is the hypothesis/antecedent, q the conclusion/consequent.
• Related forms:
  • Converse: q → p — not equivalent to the original.
  • Inverse: ¬p → ¬q — not equivalent to the original.
  • Contrapositive: ¬q → ¬p — logically equivalent to p → q.
• Equivalence: p → q ≡ ¬p ∨ q.

B. Biconditional statement

Definition: p ↔ q ("p if and only if q") is true exactly when p and q have the same truth value.

p q | p ↔ q
T T |   T
T F |   F
F T |   F
F F |   T

• Decomposition: p ↔ q ≡ (p → q) ∧ (q → p) — both directions must hold.
• English cues: "if and only if", "iff", "is necessary and sufficient for".
• Link to equivalence: p ↔ q is a tautology precisely when p ≡ q, tying this connective back to Section VII.