Chapter 02 of 30

Propositional Logic

Every if statement you have ever written is a small piece of logic. if (marks >= 40 && attendance >= 75) combines two true/false facts with "and"; while (!found || retries < 3) uses "not" and "or". Propositional logic is the mathematics behind exactly these expressions. It tells us precisely when a combined statement is true, how to translate English sentences without ambiguity, and how to spot reasoning that only looks correct.

In Introduction to Discrete Mathematics we said logic is the foundation of the whole subject. In this chapter we define propositions, the six logical connectives and their truth tables, the conditional statement and its relatives (converse, inverse, contrapositive), the many English forms of "if ... then", and the classification of formulas into tautologies, contradictions and contingencies. Every truth table here was generated and checked by a program.


Propositions

A proposition (or statement) is a declarative sentence that is either true or false, but not both. Its truth or falsehood is called its truth value, written T (or 1) and F (or 0).

Sentence

Proposition?

Why

New Delhi is the capital of India.

Yes (T)

Declarative, has a definite truth value

2 + 3 = 7

Yes (F)

False is still a truth value

Every even number greater than 2 is a sum of two primes.

Yes

Goldbach's conjecture: nobody knows its value yet, but it is definitely either true or false

Close the door.

No

A command, not a statement

What time is it?

No

A question

x + 1 = 5

No

Its truth depends on x. (It becomes a proposition once x is given a value; such sentences are handled in Predicate Logic & Quantifiers.)

This sentence is false.

No

If true, it is false; if false, it is true. It cannot consistently have a truth value (the liar paradox).

We name propositions with lowercase letters p, q, r, s, ... called propositional variables. A proposition with no connective (like "It is raining") is atomic; one built from others with connectives is compound.


The Logical Connectives

Connectives build compound propositions. The truth value of the result depends only on the truth values of the parts, and a truth table lists the result for every possible combination.

Negation (¬p, "not p")

¬p is true exactly when p is false. If p is "the server is running", ¬p is "the server is not running" (or "it is not the case that the server is running"). Other notations: ~p, p′, p̄.

Conjunction (p ∧ q, "p and q")

True only when both p and q are true. English words like "but", "although", "yet" and "while" also usually mean ∧: "The phone is cheap but slow" is c ∧ s.

Disjunction (p ∨ q, "p or q")

True when at least one of p, q is true. This is the inclusive or: "p or q or both".

Exclusive Or (p ⊕ q, "p xor q")

True when exactly one of p, q is true. A restaurant's "the thali comes with rice or roti" usually means you cannot have both; that is ⊕. In logic, plain "or" always means ∨ unless the problem says "but not both".

The Full Table

p

q

¬p

p ∧ q

p ∨ q

p ⊕ q

p → q

p ↔ q

T

T

F

T

T

F

T

T

T

F

F

F

T

T

F

F

F

T

T

F

T

T

T

F

F

F

T

F

F

F

T

T

The last two columns, the conditional and the biconditional, need the most care, so we study them separately.


The Conditional p → q

The conditional (or implication) p → q, read "if p then q", is false only when p is true and q is false. In every other case it is true. p is called the hypothesis (antecedent, premise) and q the conclusion (consequent).

Why is "false → anything" true? Think of p → q as a promise. A teacher says: "If you submit the assignment, then you will get 10 marks." When has the teacher broken the promise?

  • You submitted and got 10 marks (T → T): promise kept. True.

  • You submitted but did not get 10 marks (T → F): promise broken. False.

  • You did not submit, and still got 10 marks (F → T): the teacher was generous, but no promise was broken. True.

  • You did not submit and did not get the marks (F → F): promise kept. True.

The promise can only be broken when its condition is met and its outcome fails. When the hypothesis is false we say the conditional is vacuously true. So "If 2 + 2 = 5, then the moon is made of cheese" is a true proposition.

Also note that in logic, p → q does not claim that p causes q, or that p and q are related at all. "If 7 is prime, then Mumbai is in India" is true simply because both parts are true.

Ways to Say p → q in English

This is one of the most tested skills in exams. All of these mean p → q:

English form

Example (p: "you pass", q: "you scored at least 40")

if p, then q

If you pass, then you scored at least 40.

q if p

You scored at least 40 if you passed.

p only if q

You pass only if you score at least 40.

p is sufficient for q

Knowing that you passed is sufficient to conclude that you scored at least 40.

q is necessary for p

Scoring at least 40 is necessary for passing.

q whenever p; q when p

You scored at least 40 whenever you passed.

p implies q

Passing implies scoring at least 40.

q unless ¬p (that is, ¬p ∨ q)

You scored at least 40 unless you did not pass.

The trap is "only if". "p only if q" means p → q, not q → p. Scoring 40 does not guarantee passing (there may be other conditions, like attendance), but you cannot pass without it. "Only if" introduces a necessary condition; plain "if" introduces a sufficient one.

The word "unless" means "if not": "p unless q" means ¬q → p, which is equivalent to p ∨ q. Example: "The build fails unless the tests pass" is ¬t → f, or t ∨ f.


Converse, Inverse and Contrapositive

From one conditional p → q we can form three related ones:

Name

Form

Example (r: "it rains", c: "the match is cancelled")

Original

p → q

If it rains, the match is cancelled.

Converse

q → p

If the match is cancelled, it rained.

Inverse

¬p → ¬q

If it does not rain, the match is not cancelled.

Contrapositive

¬q → ¬p

If the match is not cancelled, it did not rain.

Here are the four truth tables side by side:

p

q

p → q

q → p (converse)

¬p → ¬q (inverse)

¬q → ¬p (contrapositive)

T

T

T

T

T

T

T

F

F

T

T

F

F

T

T

F

F

T

F

F

T

T

T

T

A conditional and its contrapositive always have the same truth value. The converse and the inverse have the same truth value as each other, but in general not as the original.

In the cricket example: the match could be cancelled because of a power failure without rain, so the converse can be false while the original is true. The contrapositive, however, says the same thing as the original: if the match went ahead, it cannot have rained. This fact is the basis of "proof by contrapositive" in Proof Techniques.


The Biconditional p ↔ q

p ↔ q, read "p if and only if q" (often written "p iff q"), is true exactly when p and q have the same truth value.

p ↔ q means (p → q) ∧ (q → p): "p if q" and "p only if q" together. Other English forms: "p is necessary and sufficient for q", "p exactly when q". Notice that ↔ is the negation of ⊕: p ↔ q is true exactly when p ⊕ q is false.

Example: "An integer n is even if and only if n mod 2 = 0." Both directions hold, so this is a biconditional, and it is exactly the kind of sentence used in definitions.


Precedence and Building Truth Tables

To avoid writing too many brackets, connectives have a standard precedence (highest first):

Precedence

Operator

Example

1 (highest)

¬

¬p ∧ q means (¬p) ∧ q

2

∧

p ∨ q ∧ r means p ∨ (q ∧ r)

3

∨ (and ⊕)

p ∨ q → r means (p ∨ q) → r

4

→

p → q ↔ r means (p → q) ↔ r

5 (lowest)

↔

Books disagree on chains like p → q → r, and it matters: (p → q) → r and p → (q → r) are different formulas (we prove this in Logical Equivalences & Normal Forms). Always use brackets for repeated →.

Worked Example: Truth Table of (p ∨ ¬q) → (p ∧ q)

With n variables there are 2n rows (each variable is T or F independently). Here n = 2, so 4 rows. Build helper columns from the inside out:

p

q

¬q

p ∨ ¬q

p ∧ q

(p ∨ ¬q) → (p ∧ q)

T

T

F

T

T

T

T

F

T

T

F

F

F

T

F

F

F

T

F

F

T

T

F

F

Row 3 is true vacuously (the hypothesis p ∨ ¬q is false). Rows 2 and 4 are false because the hypothesis is true and the conclusion false.

Since each of the 2n rows can independently be T or F in the result column, there are 22n different truth tables (Boolean functions) of n variables: 16 for n = 2, and 256 for n = 3.


Tautology, Contradiction, Contingency

A compound proposition is a
tautology if it is true in every row of its truth table;
contradiction if it is false in every row;
contingency if it is neither (true in some rows, false in others).
It is satisfiable if it is true in at least one row (so tautologies and contingencies are satisfiable; contradictions are not).

Simple examples: p ∨ ¬p is a tautology (law of excluded middle), p ∧ ¬p is a contradiction, and p → q is a contingency.

Note the relationship: A is a tautology if and only if ¬A is a contradiction, and A is satisfiable if and only if ¬A is not a tautology.

Checking with a Program

Truth tables are perfect for computers: just try every row. This program prints the table and classifies the formula.

from itertools import product

def implies(a, b):
    return (not a) or b

def truth_table(names, formula):
    rows = list(product([True, False], repeat=len(names)))
    results = []
    print(' '.join(names), '| result')
    for values in rows:
        value = formula(*values)
        results.append(value)
        cells = ' '.join('T' if v else 'F' for v in values)
        print(cells, '|', 'T' if value else 'F')
    if all(results):
        print('=> tautology')
    elif not any(results):
        print('=> contradiction')
    else:
        print('=> contingency')
    print()

# (p -> q) and (q -> r)  implies  (p -> r)
truth_table(['p', 'q', 'r'],
            lambda p, q, r: implies(implies(p, q) and implies(q, r), implies(p, r)))

# (p -> q) -> p
truth_table(['p', 'q'], lambda p, q: implies(implies(p, q), p))

# p and not p
truth_table(['p'], lambda p: p and not p)

Output:

p q r | result
T T T | T
T T F | T
T F T | T
T F F | T
F T T | T
F T F | T
F F T | T
F F F | T
=> tautology

p q | result
T T | T
T F | T
F T | F
F F | F
=> contingency

p | result
T | F
F | F
=> contradiction

The first formula, ((p → q) ∧ (q → r)) → (p → r), is a tautology: "implication is transitive". It will reappear as the rule hypothetical syllogism in Rules of Inference.

A truth table has 2n rows, so this brute-force method doubles in cost with every new variable. Deciding whether a formula is satisfiable (the SAT problem) was the first problem proved NP-complete, and no algorithm is known that is fast on every input. Modern SAT solvers are nonetheless very good in practice and are used in chip verification and planning.


Translating English into Logic

Steps: (1) identify the atomic propositions and give each a letter; (2) find the connective words; (3) watch for "only if", "unless", "necessary" and "sufficient"; (4) add brackets.

Example 1. "Students can apply for the scholarship only if their CGPA is at least 8 and they have no backlogs." Let a: can apply, g: CGPA ≥ 8, b: has backlogs. Answer: a → (g ∧ ¬b). ("Only if" puts a on the left.)

Example 2. "The website loads quickly if the cache is warm, unless the database is down." Let l: loads quickly, c: cache warm, d: database down. "X unless d" is ¬d → X, where X is c → l. Answer: ¬d → (c → l), which is equivalent to (c ∧ ¬d) → l.

Example 3. "A valid password is necessary and sufficient to log in." Let v: valid password, l: log in. Answer: v ↔ l.

Example 4 (a logic puzzle). On an island, knights always tell the truth and knaves always lie. A says "B is a knave." B says "A and I are both knights." Let a: "A is a knight", b: "B is a knight". A person's statement is true exactly when that person is a knight, so a ↔ ¬b and b ↔ (a ∧ b). Try the cases: if b is T, then a ∧ b must be T, so a is T; but then a ↔ ¬b gives T ↔ F, impossible. So b is F. Then b ↔ (a ∧ b) is F ↔ F, fine, and a ↔ ¬b gives a = T. A is a knight and B is a knave, and a check of all four cases confirms this is the only solution.


Logic in Hardware and Code: Bit Operations

A computer word is a string of bits, and the bitwise operators apply a connective to each pair of bits in the same position: & is ∧, | is ∨, ^ is ⊕, ~ is ¬.

    01101          01101          01101
  & 11011        | 11011        ^ 11011
  -------        -------        -------
    01001          11111          10110

The same connectives, built from transistors, are the logic gates (AND, OR, NOT, XOR) of the Digital Logic tutorial. In C, C++, Java and Python, the logical operators (&&, ||, or and, or in Python) also use short-circuit evaluation: in p && q, if p is false, q is never evaluated, because the result is already F. Logically the value is the same; only the side effects differ.


Common Mistakes

  • Treating "p only if q" as q → p. It is p → q. "Only if" marks the necessary condition, which goes on the right of the arrow.

  • Thinking F → F (or F → T) is false. A conditional is false only in the row T → F.

  • Confusing converse with contrapositive. Only the contrapositive ¬q → ¬p is equivalent to p → q. Believing the converse is the fallacy of affirming the consequent.

  • Reading English "or" as exclusive. In logic, "or" is inclusive unless the problem explicitly says "but not both".

  • Calling sentences with free variables propositions. "x > 3" has no truth value until x is fixed or quantified.

  • Wrong number of rows. n variables need 2n rows, not 2n. Four variables need 16 rows.

  • Assuming → means causation. Logical implication is defined by the truth table alone.


Interview and GATE-Style Questions

When is p → q false?

Only when p is true and q is false. In all other three cases it is true.

Which of these is a tautology? (a) (p → q) → (q → p) (b) (p ∧ (p → q)) → q (c) (p ∨ q) → (p ∧ q)

(b). If p and p → q are both true, q must be true, so the implication never fails. (a) is false when p = F, q = T; (c) is false when exactly one of p, q is true.

How many rows does the truth table of a formula with 5 variables have, and how many different Boolean functions of 3 variables exist?

25 = 32 rows. Boolean functions of 3 variables: 223 = 28 = 256.

Write the converse, inverse and contrapositive of "If n2 is even, then n is even." Which of them is equivalent to the original?

Converse: if n is even, then n2 is even. Inverse: if n2 is odd, then n is odd. Contrapositive: if n is odd, then n2 is odd. The contrapositive is equivalent to the original. (Here all four happen to be true, but that is a property of this example, not a general rule.)

Translate: "You will not get a refund unless you return the product within 7 days." (r: refund, w: return within 7 days)

"¬r unless w" means ¬w → ¬r, which is equivalent (contrapositive) to r → w: a refund only if you return within 7 days.

Is p → (q → p) a tautology? Justify without a full table.

Yes. The formula can only be false if p is T and q → p is F. But q → p is F only when p is F. Both cannot happen, so the formula is never false.

If p ↔ q is false, what is the value of p ⊕ q?

True. p ↔ q is false exactly when p and q differ, which is exactly when p ⊕ q is true.


Summary

  • A proposition is a declarative sentence that is either true or false, not both.

  • Connectives: ¬ (not), ∧ (and), ∨ (inclusive or), ⊕ (exclusive or), → (if then), ↔ (if and only if).

  • p → q is false only when p is T and q is F. "p only if q", "q is necessary for p" and "p is sufficient for q" all mean p → q.

  • A conditional is equivalent to its contrapositive; the converse is equivalent to the inverse, not to the original.

  • n variables give 2n truth-table rows and 22n possible Boolean functions.

  • Formulas are tautologies (always T), contradictions (always F) or contingencies; satisfiable means "true in at least one row".

  • Next, in Logical Equivalences & Normal Forms, we learn to transform formulas algebraically instead of always building truth tables.