# Propositional and Predicate Logic — Truth Tables, Implications, Equivalences and Quantifiers

Source: https://skills101.in/learn/discrete-math/propositional-predicate-logic — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

Every `if` statement is logic. So is every database query, every circuit and every security rule. This lesson makes logic precise — and shows how it turns into code.

## 1. Propositions and connectives

A **proposition** is a statement that is either true or false: "7 is prime" (T), "2 + 2 = 5" (F).

| Connective | Symbol | Python | True when |
|---|---|---|---|
| NOT | ¬p | `not p` | p is false |
| AND | p ∧ q | `p and q` | both true |
| OR | p ∨ q | `p or q` | at least one true |
| XOR | p ⊕ q | `p != q` | exactly one true |
| Implication | p → q | `(not p) or q` | **false only when p true and q false** |
| Biconditional | p ↔ q | `p == q` | both same |

## 2. Truth tables

Let Python generate them — no mistakes, any number of variables:

```python
from itertools import product

def table(expr, names):
    print(" ".join(names), "| result")
    for values in product([True, False], repeat=len(names)):
        env = dict(zip(names, values))
        row = " ".join("T" if v else "F" for v in values)
        print(row, "|", "T" if expr(**env) else "F")

print("p -> q")
table(lambda p, q: (not p) or q, ["p", "q"])
```

```text
p -> q
p q | result
T T | T
T F | F
F T | T
F F | T
```

## 3. Understanding implication

p → q ("if p then q") is a **promise**. It's broken only when p happens and q doesn't.

> "If you score 90+, you get a scholarship."
> You scored 85 and got a scholarship anyway — the promise isn't broken (p false ⇒ implication true).

![Implication and its relatives: the statement p implies q, its converse q implies p, its inverse not p implies not q, and its contrapositive not q implies not p; only the contrapositive is always equivalent to the original](https://skills101.in/learn-img/discrete-math/implication-family.svg)

| Form | Statement | Equivalent to p → q? |
|---|---|---|
| **Converse** | q → p | no |
| **Inverse** | ¬p → ¬q | no |
| **Contrapositive** | ¬q → ¬p | **yes** |

Check by brute force:

```python
from itertools import product

implies = lambda a, b: (not a) or b
rows = list(product([True, False], repeat=2))
print("p->q == contrapositive:", all(implies(p, q) == implies(not q, not p) for p, q in rows))
print("p->q == converse      :", all(implies(p, q) == implies(q, p) for p, q in rows))
print("p->q == not p or q    :", all(implies(p, q) == ((not p) or q) for p, q in rows))
```

```text
p->q == contrapositive: True
p->q == converse      : False
p->q == not p or q    : True
```

## 4. Tautology, contradiction, contingency

- **Tautology**: true in every row — e.g. p ∨ ¬p.
- **Contradiction**: false in every row — e.g. p ∧ ¬p.
- **Contingency**: sometimes true, sometimes false.
- Two formulas are **logically equivalent** (≡) if their biconditional is a tautology.

```python
from itertools import product

def kind(expr, n):
    vals = [expr(*v) for v in product([True, False], repeat=n)]
    return "tautology" if all(vals) else "contradiction" if not any(vals) else "contingency"

print("p or not p           :", kind(lambda p: p or not p, 1))
print("p and not p          :", kind(lambda p: p and not p, 1))
print("(p->q) and p -> q    :", kind(lambda p, q: (not (((not p) or q) and p)) or q, 2))
print("p -> (p and q)       :", kind(lambda p, q: (not p) or (p and q), 2))
```

```text
p or not p           : tautology
p and not p          : contradiction
(p->q) and p -> q    : tautology
p -> (p and q)       : contingency
```

The third one is **modus ponens** ("if p then q; p; therefore q") — a tautology, which is why it's a valid rule of reasoning.

## 5. Laws you'll use constantly

| Law | Statement |
|---|---|
| **De Morgan** | ¬(p ∧ q) ≡ ¬p ∨ ¬q ; ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Double negation | ¬¬p ≡ p |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Absorption | p ∨ (p ∧ q) ≡ p |
| Implication | p → q ≡ ¬p ∨ q |

**De Morgan in code** — simplifying a condition:

```python
# "not (has_paid and is_verified)" is the same as "not has_paid or not is_verified"
from itertools import product
print(all((not (a and b)) == ((not a) or (not b)) for a, b in product([True, False], repeat=2)))
```

```text
True
```

## 6. Predicates and quantifiers

A **predicate** has variables: P(x) = "x is prime". It becomes a proposition when x is given or quantified:

- **∀x P(x)** — "for all x, P(x)" — like Python `all(...)`
- **∃x P(x)** — "there exists x with P(x)" — like `any(...)`

**Negating quantifiers** (the exam trap):

- ¬∀x P(x) ≡ ∃x ¬P(x) — "not all are prime" = "some is not prime"
- ¬∃x P(x) ≡ ∀x ¬P(x) — "none is prime" = "all are non-prime"

```python
marks = [72, 45, 88, 91, 39]
passed = lambda m: m >= 40

print("everyone passed (∀)       :", all(passed(m) for m in marks))
print("someone failed  (∃ not)   :", any(not passed(m) for m in marks))
print("negation law holds        :", (not all(passed(m) for m in marks)) == any(not passed(m) for m in marks))
```

```text
everyone passed (∀)       : False
someone failed  (∃ not)   : True
negation law holds        : True
```

**Nested quantifiers — order matters:** ∀x ∃y (y > x) "for every number there's a bigger one" is true on integers; ∃y ∀x (y > x) "there's a number bigger than all numbers" is false.

## Common mistakes

- Thinking p → q is false when p is false.
- Confusing converse with contrapositive.
- Negating "all students passed" as "all students failed" (correct: "some student failed").
- Swapping the order of nested quantifiers.

## Quick recap

- Connectives: ¬, ∧, ∨, ⊕, →, ↔; p → q ≡ ¬p ∨ q (false only for T → F).
- Contrapositive ≡ original; converse and inverse are not.
- Tautology / contradiction / contingency; use truth tables (or Python) to check.
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
- ∀ ↔ `all`, ∃ ↔ `any`; ¬∀ = ∃¬, ¬∃ = ∀¬; quantifier order matters.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/propositional-predicate-logic