References: Rosen 8e §1.1–1.3, 1.6; Velleman 3e ch. 1; Mendelson 6e ch. 1; Cori & Lascar vol. 1 ch. 1–2; Lalement Logique, réduction, résolution.
2 / 35
1.1 Proposition — formal definition
A proposition is a declarative sentence that is either true ($\mathtt T$) or false ($\mathtt F$), but never both and never neither. We denote propositions by lowercase letters $p, q, r, \ldots$ and use the set $\mathbb{B} = \{\mathtt T, \mathtt F\}$ of truth values.
Examples (and non-examples):
Sentence
Proposition?
Why
"$2 + 2 = 4$"
Yes (True)
Declarative, definite truth value.
"It will rain tomorrow."
Yes
Declarative; truth value is fixed by the future fact.
"Close the door."
No
Imperative — no truth value.
"What time is it?"
No
Interrogative.
"$x + 1 = 0$"
No (yet)
Contains a free variable — it is a predicate.
"This sentence is false."
No
Paradoxical — violates the bivalence principle.
Rosen 8e, §1.1, p. 4; Mendelson 6e, §1.1.
3 / 35
1.2 Atomic vs compound propositions
An atomic proposition is one that cannot be further decomposed using logical connectives — symbolised by a single letter $p, q, \dots$.
A compound proposition is built from atomic propositions and connectives ($\neg, \wedge, \vee, \to, \leftrightarrow, \dots$).
Let $p$ = "It is raining" and $q$ = "I take an umbrella".
$p$ — atomic.
$\neg p$, $p \wedge q$, $p \to q$ — compound.
$\bigl(p \to q\bigr) \wedge \bigl(\neg p \to \neg q\bigr)$ — compound (built from two implications).
Propositional logic studies only the structure of compound propositions in terms of their atoms; it does not look inside an atomic letter $p$. Looking inside is the job of predicate logic (Lesson 4).
Rosen 8e, §1.1; Cori & Lascar vol. 1, §1.1.
4 / 35
1.3 Formal grammar of well-formed formulas
Fix a countable set $\mathcal{P} = \{p_1, p_2, \dots\}$ of propositional variables and the two constants $\top$ (top, always true) and $\bot$ (bottom, always false). The set of well-formed formulas ($\mathrm{wff}$) is defined inductively by the Backus–Naur form:
Equivalently, every wff is one of: a propositional variable, a constant, a negation, or a binary connective applied to two wffs. Parentheses are eliminated in practice via operator precedence (§5).
Mendelson 6e, §1.2; Lalement, ch. 1.
5 / 35
1.4 Truth assignment (valuation)
A truth assignment (or valuation) is a function $v : \mathcal{P} \to \mathbb{B}$ mapping each propositional variable to a truth value. Each valuation extends uniquely to a function $\widehat{v}$ on all wffs by the recursive rules:
$$\widehat{v}(\top) = \mathtt T,\;\; \widehat{v}(\bot) = \mathtt F,\;\; \widehat{v}(\neg \varphi) = \neg \widehat{v}(\varphi),$$
$$\widehat{v}(\varphi \wedge \psi) = \widehat{v}(\varphi) \wedge \widehat{v}(\psi),\;\; \text{etc.}$$
Two valuations that agree on the propositional variables appearing in a formula $\varphi$ produce the same truth value for $\varphi$ — only the relevant variables matter.
A formula with $n$ distinct propositional variables admits exactly $2^n$ distinct relevant valuations — this is exactly the number of rows in its truth table.
Mendelson 6e, §1.2; Cori & Lascar vol. 1, §2.1.
6 / 35
2.1 Negation $\neg$
$\neg p$ — "not $p$" — is the unique unary connective that flips the truth value of $p$.
$p$
$\neg p$
$\mathtt T$
$\mathtt F$
$\mathtt F$
$\mathtt T$
Python — SymPy imports (run once)from sympy import symbols, Not, And, Or, Implies, Equivalent, Xor, simplify
from sympy.logic.boolalg import truth_table, to_cnf, to_dnf
from sympy.logic.inference import satisfiable
p, q, r = symbols('p q r')
$p \wedge q$ — "$p$ and $q$" — is true iff both $p$ and $q$ are true.
$p \vee q$ — "$p$ or $q$" (inclusive or) — is true iff at least one of $p$, $q$ is true.
$p$
$q$
$p \wedge q$
$p \vee q$
T
T
T
T
T
F
F
T
F
T
F
T
F
F
F
F
Python — SymPyAnd(p, q) # p ∧ q — also written p & q
Or(p, q) # p ∨ q — also written p | q
for row in truth_table(And(p, q), [p, q]):
print(row) # ([0,0],False), ([0,1],False), ([1,0],False), ([1,1],True)
Rosen 8e, §1.1, pp. 6–7.
8 / 35
2.3 Exclusive or $\oplus$ (XOR)
$p \oplus q$ — "$p$ exclusive-or $q$" — is true iff exactly one of $p$, $q$ is true (but not both).
English "or" is ambiguous: "You may have coffee or tea" is usually exclusive; "Students taking French or Italian" is inclusive. Logic fixes $\vee$ as inclusive; XOR is reserved for exclusive intent.
Rosen 8e, §1.1, p. 7; Velleman 3e, §1.1.
9 / 35
2.4 Conditional $\to$ — material implication
$p \to q$ — "if $p$ then $q$" — is false in exactly one case: $p$ true and $q$ false. In all other cases it is true.
$p$
$q$
$p \to q$
T
T
T
T
F
F
F
T
T
F
F
T
All of the following English phrases mean $p \to q$:
"If $p$, then $q$" · "$p$ implies $q$" · "$q$ if $p$".
"$p$ only if $q$" · "$p$ is sufficient for $q$".
"$q$ is necessary for $p$" · "$q$ whenever $p$".
"$q$ unless $\neg p$".
Vacuous truth. When $p$ is false, $p \to q$ is true regardless of $q$. This is the same vacuous-truth phenomenon as $\forall x \in \varnothing\,P(x)$ in predicate logic.
Rosen 8e, §1.1, pp. 8–11.
10 / 35
2.5 Biconditional $\leftrightarrow$ (iff)
$p \leftrightarrow q$ — "$p$ if and only if $q$" — is true iff $p$ and $q$ have the same truth value.
$p$
$q$
$p \leftrightarrow q$
T
T
T
T
F
F
F
T
F
F
F
T
$p \leftrightarrow q$ is the conjunction of the two implications:
Each of $\{\uparrow\}$ and $\{\downarrow\}$ alone is functionally complete (§12) — every truth function can be expressed using just NAND, or just NOR. Hence the popularity of NAND/NOR in hardware: a chip can be built using a single gate type.
Mendelson 6e, §1.4; Rosen 8e, §1.3 Ex. 41.
12 / 35
3. Building truth tables systematically
For a formula $\varphi$ with $n$ distinct propositional variables, list all $2^n$ valuations as rows. Standard convention: variables in alphabetical order, value $\mathtt T$ before $\mathtt F$ in each column (or in binary-counting order — pick one and stay consistent). Then fill in one column per sub-formula bottom-up.
Truth table of $\varphi := (p \to q) \wedge (\neg p \vee r)$ — three variables, $2^3 = 8$ rows.
$p$
$q$
$r$
$\neg p$
$p \to q$
$\neg p \vee r$
$\varphi$
T
T
T
F
T
T
T
T
T
F
F
T
F
F
T
F
T
F
F
T
F
T
F
F
F
F
F
F
F
T
T
T
T
T
T
F
T
F
T
T
T
T
F
F
T
T
T
T
T
F
F
F
T
T
T
T
Python — automate itexpr = And(Implies(p, q), Or(Not(p), r))
for vals, val in truth_table(expr, [p, q, r]):
print(vals, '→', val)
Rosen 8e, §1.1, p. 12.
13 / 35
4. Precedence and parenthesization
Standard precedence (highest first): $\;( \cdot ) \;>\; \neg \;>\; \wedge \;>\; \vee \;>\; \to \;>\; \leftrightarrow$.
Binary connectives associate to the right by default: $p \to q \to r$ means $p \to (q \to r)$.
Mnemonic — P N A O I BParentheses · Not · And · Or · Implies · Biconditional.
Written
Means
$\neg p \wedge q$
$(\neg p) \wedge q$ — not $\neg(p \wedge q)$.
$p \vee q \wedge r$
$p \vee (q \wedge r)$.
$p \to q \vee r$
$p \to (q \vee r)$.
$p \to q \to r$
$p \to (q \to r)$ (right-associative).
$\neg p \to q \leftrightarrow r$
$((\neg p) \to q) \leftrightarrow r$.
When in doubt, parenthesise. Code uses operator precedence too — but Python's bitwise ~, &, | bind differently from $\neg, \wedge, \vee$. Always wrap SymPy expressions with parentheses.
Verify by truth table — the four rows of $p \to q$ and $\neg q \to \neg p$ agree column-wise. Equivalently, $p \to q \equiv \neg p \vee q \equiv q \vee \neg p \equiv \neg(\neg q) \vee \neg p \equiv \neg q \to \neg p$. $\square$
Converse and inverse are equivalent to each other: $q \to p \equiv \neg p \to \neg q$ (each is the contrapositive of the other).
Rosen 8e, §1.1, p. 9; Velleman 3e, §1.2.
15 / 35
5.2 Two classical fallacies
Affirming the consequent. From $p \to q$ and $q$ one cannot conclude $p$.
Example: "If it rains, the ground is wet. The ground is wet. Therefore it rained." False — a sprinkler could have made the ground wet.
Denying the antecedent. From $p \to q$ and $\neg p$ one cannot conclude $\neg q$.
Example: "If you study, you pass. You did not study. Therefore you do not pass." False — you might pass anyway.
The two valid patterns are the converse of these:
Modus ponens: from $p \to q$ and $p$, conclude $q$. (See §9.1)
Modus tollens: from $p \to q$ and $\neg q$, conclude $\neg p$. (See §9.1)
Rosen 8e, §1.6; Velleman 3e, §1.2.
16 / 35
6. Tautology, contradiction, contingency
A formula $\varphi$ is a tautology if it is true under every valuation. Notation $\models \varphi$.
A formula is a contradiction (or unsatisfiable) if it is false under every valuation.
A formula is contingent if it is true in some valuation and false in another.
Formula
Classification
$p \vee \neg p$
Tautology (law of excluded middle).
$p \wedge \neg p$
Contradiction (law of non-contradiction, negated).
$(p \to q) \leftrightarrow (\neg q \to \neg p)$
Tautology.
$p \to (p \wedge q)$
Contingent (true when $q$ true, false when $p$ true and $q$ false).
Python — test by SATsatisfiable(p | ~p) # always satisfiable, hence not a contradiction
satisfiable(~(p | ~p)) # False — its negation is unsat, so original is a tautology
satisfiable(p & ~p) # False — contradiction
Rosen 8e, §1.3, p. 28; Mendelson 6e, §1.3.
17 / 35
7. Satisfiability and the SAT problem
A formula $\varphi$ is satisfiable if at least one valuation makes it true. Otherwise it is unsatisfiable. The decision problem "is this Boolean formula satisfiable?" is called SAT.
Naïve algorithm: enumerate $2^n$ valuations — exponential in $n$.
2-SAT (each clause has at most 2 literals) is in $\mathcal{P}$.
3-SAT is NP-complete (Cook–Levin, 1971) — the canonical NP-complete problem.
Modern SAT-solvers (e.g. Z3, MiniSAT) handle formulas with millions of variables via DPLL/CDCL heuristics — they are the backbone of modern verification, planning and combinatorial search.
Two formulas $\varphi$ and $\psi$ are logically equivalent, written $\varphi \equiv \psi$, iff they take the same truth value under every valuation. Equivalently: $\models \varphi \leftrightarrow \psi$.
Compare the two symbols:
Symbol
Type
Status
$\leftrightarrow$
Connective (a formula)
$\varphi \leftrightarrow \psi$ is itself a formula with its own truth value in each valuation.
$\equiv$
Meta-symbol (an assertion)
$\varphi \equiv \psi$ asserts the formula $\varphi \leftrightarrow \psi$ is a tautology.
Substitution theorem. If $\varphi \equiv \psi$, then for any formula $\chi$ obtained by replacing some occurrence of $\varphi$ by $\psi$: $\chi[\varphi] \equiv \chi[\psi]$.
Rosen 8e, §1.3, p. 27; Mendelson 6e, §1.3.
19 / 35
8.2 Major equivalence laws
Name
Law
Identity
$p \wedge \top \equiv p,\quad p \vee \bot \equiv p$
Domination
$p \vee \top \equiv \top,\quad p \wedge \bot \equiv \bot$
Python — verify any identitysimplify(Equivalent(Implies(p, q), Or(Not(p), q))) # True
Rosen 8e, §1.3, Tables 7–8.
22 / 35
9. Logical consequence (entailment)
Let $\Gamma$ be a set of formulas and $\varphi$ a formula. We say $\varphi$ is a logical consequence (or that $\Gamma$ entails $\varphi$), written $\;\Gamma \models \varphi\;$, iff every valuation that makes all formulas in $\Gamma$ true also makes $\varphi$ true.
Take $\Gamma = \{\,p \to q,\; p\,\}$ and $\varphi = q$. Every valuation satisfying both $p \to q$ and $p$ must have $p = \mathtt T$ and (since $p \to q$ holds) $q = \mathtt T$. Hence $\Gamma \models q$ — this is the soundness of modus ponens (next slide).
Distinguish: $\Gamma \models \varphi$ is a semantic claim (about valuations); the analogous syntactic claim $\Gamma \vdash \varphi$ is "$\varphi$ can be derived from $\Gamma$ by inference rules". Soundness and completeness of propositional logic ensure $\models$ and $\vdash$ coincide.
Mendelson 6e, §1.5; Cori & Lascar vol. 1, ch. 2.
23 / 35
10.1 Modus ponens and modus tollens
Modus Ponens (MP). $\;\{\,p,\; p \to q\,\} \models q.$
$p \to q,\;\; p$$\therefore\; q$
A valuation in which $p$ and $p \to q$ are both true cannot make $q$ false — that would make $p \to q$ false. So every model of the premises is a model of $q$. $\square$
"Either I left my keys in the car or in the office. They are not in the car. Therefore they are in the office."
Rosen 8e, §1.6, Table 1, p. 75.
25 / 35
10.3 More inference rules
Name
Rule
Addition
$p \;\therefore\; p \vee q$
Simplification
$p \wedge q \;\therefore\; p$
Conjunction
$p,\; q \;\therefore\; p \wedge q$
Resolution
$p \vee q,\; \neg p \vee r \;\therefore\; q \vee r$
Resolution. If two clauses $C_1 = p \vee q$ and $C_2 = \neg p \vee r$ are both true, then $q \vee r$ must be true.
Consider any valuation satisfying $C_1$ and $C_2$. If $p$ is true, $C_2$ forces $r$ to be true, hence $q \vee r$. If $p$ is false, $C_1$ forces $q$ to be true, hence $q \vee r$. Either way, $q \vee r$ holds. $\square$
Resolution is the single inference rule used by resolution refutation, the algorithmic core of most SAT-solvers and automated theorem provers.
Rosen 8e, §1.6, Table 1; Lalement, ch. 3.
26 / 35
11. Proof methods in propositional reasoning
Direct proof of $p \to q$. Assume $p$, derive $q$ via known inference rules.
Proof by contrapositive. To prove $p \to q$, equivalently prove $\neg q \to \neg p$.
Proof by contradiction (reductio). To prove $\varphi$, assume $\neg \varphi$ and derive $\bot$. Justification: $\neg \varphi \to \bot \;\equiv\; \varphi$.
Proof by cases. To prove $(p_1 \vee p_2 \vee \dots \vee p_k) \to q$, prove each $p_i \to q$ separately.
Truth-table proof. For a propositional tautology, exhibit every row of the truth table.
(Contrapositive.) Prove: if $n^2$ is odd, then $n$ is odd. Contrapositive: if $n$ is even, then $n^2$ is even. Assume $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$ is even. $\square$
(Cases.) Prove $\forall n \in \mathbb{Z},\; n^2 \geq n$ for $n \neq 0$. Case $n \geq 1$: multiply $n \geq 1$ by $n \geq 0$ to get $n^2 \geq n$. Case $n \leq -1$: $n^2 \geq 1 \geq 0 \geq n$. $\square$
Velleman 3e, ch. 3; Rosen 8e, §1.7.
27 / 35
12.1 Normal forms — NNF, CNF, DNF
A literal is a propositional variable $p$ or its negation $\neg p$.
A clause is a disjunction of literals; a cube is a conjunction of literals. Negation Normal Form (NNF): negations apply only to atoms; the formula uses only $\neg, \wedge, \vee$. Conjunctive Normal Form (CNF): a conjunction of clauses — $\bigwedge_i \bigvee_j \ell_{ij}$. Disjunctive Normal Form (DNF): a disjunction of cubes — $\bigvee_i \bigwedge_j \ell_{ij}$.
Every propositional formula is equivalent to one in NNF, one in CNF, and one in DNF.
$\;p \leftrightarrow q\;$ in DNF: $\;(p \wedge q) \vee (\neg p \wedge \neg q)$.
$\;p \leftrightarrow q\;$ in CNF: $\;(\neg p \vee q) \wedge (p \vee \neg q)$.
Rosen 8e, §1.3, p. 31; Mendelson 6e, §1.4.
28 / 35
12.2 CNF conversion — algorithm & worked example
Eliminate $\leftrightarrow$ and $\to$ in favour of $\neg, \wedge, \vee$:
$$\alpha \leftrightarrow \beta \;\rightsquigarrow\; (\neg\alpha \vee \beta) \wedge (\alpha \vee \neg\beta), \qquad \alpha \to \beta \;\rightsquigarrow\; \neg\alpha \vee \beta.$$
Push $\neg$ inward by De Morgan until it appears only on atoms (formula now in NNF).
Python — automate itexpr = Not(And(Implies(p, q), Implies(q, r)))
print(to_cnf(expr, simplify=True)) # CNF form
print(to_dnf(expr, simplify=True)) # DNF form
Lalement, ch. 2; Rosen 8e, §1.3 Ex. 49.
29 / 35
13. Functional completeness
A set $S$ of connectives is functionally complete if every Boolean function $f : \mathbb{B}^n \to \mathbb{B}$ can be expressed using only connectives from $S$.
Each of the following sets is functionally complete:
$\;\{\neg, \wedge, \vee\},\;\{\neg, \wedge\},\;\{\neg, \vee\},\;\{\neg, \to\},\;\{\uparrow\},\;\{\downarrow\}.$
Sketch: any Boolean function can be read off its truth table as a DNF over $\{\neg, \wedge, \vee\}$. From there, De Morgan eliminates $\vee$ (giving $\{\neg, \wedge\}$) or $\wedge$ (giving $\{\neg, \vee\}$). Finally,
$$\neg p \equiv p \uparrow p, \qquad p \wedge q \equiv (p \uparrow q) \uparrow (p \uparrow q),$$
$$\neg p \equiv p \downarrow p, \qquad p \vee q \equiv (p \downarrow q) \downarrow (p \downarrow q),$$
which gives $\{\uparrow\}$ and $\{\downarrow\}$ completeness.
$\{\wedge, \vee\}$ alone is not complete — both connectives are monotone: any formula built from them returns true at the all-true valuation, so $\neg p$ is not expressible.
Mendelson 6e, §1.4; Rosen 8e, §1.3 Ex. 41.
30 / 35
14. Logic gates and digital circuits
A logic gate is a physical realisation of a Boolean function on electrical signals (high voltage = $\mathtt T$, low = $\mathtt F$). The basic gates correspond directly to connectives:
Gate
Symbol
Connective
NOT (inverter)
$\neg$
$\neg p$
AND
$\wedge$
$p \wedge q$
OR
$\vee$
$p \vee q$
NAND
$\uparrow$
$\neg(p \wedge q)$
NOR
$\downarrow$
$\neg(p \vee q)$
XOR
$\oplus$
$(p \vee q) \wedge \neg(p \wedge q)$
Half-adder circuit
Given two bits $a, b$, the sum $s = a \oplus b$ and the carry $c = a \wedge b$ together compute the binary sum $a + b \in \{00, 01, 10\}$.
$a$
$b$
sum $s = a \oplus b$
carry $c = a \wedge b$
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Chaining $n$ full-adders (which also accept a carry-in) gives the ripple-carry adder, the heart of every CPU's arithmetic unit.
Rosen 8e, §12.3; Mendelson 6e, §1.4.
31 / 35
15. Translation examples — English to logic
Let $p$ = "you study", $q$ = "you do exercises", $r$ = "you pass the course".
#
English
Formal
1
You pass the course only if you study.
$r \to p$
2
Studying and doing exercises is sufficient to pass.
$(p \wedge q) \to r$
3
You will not pass unless you study or do exercises.
You pass if and only if you study and do exercises.
$r \leftrightarrow (p \wedge q)$
5
Either you study and pass, or you do not study and fail.
$(p \wedge r) \vee (\neg p \wedge \neg r)\;\equiv\; p \leftrightarrow r$
Let $a$ = "the alarm rings", $b$ = "the door is open", $c$ = "the cat escapes".
#
English
Formal
6
If the alarm rings and the door is open, the cat escapes.
$(a \wedge b) \to c$
7
The cat escapes only when the door is open.
$c \to b$
8
The cat does not escape and the alarm does not ring.
$\neg c \wedge \neg a$
9
It is not the case that the alarm rings without the door being open.
$\neg(a \wedge \neg b)\;\equiv\; a \to b$
Rosen 8e, §1.1, pp. 8–10.
32 / 35
16. Summary
A proposition is a truth-bearer; propositional logic studies how compound propositions are built from atoms via the connectives $\neg, \wedge, \vee, \to, \leftrightarrow$ (and derived ones $\oplus, \uparrow, \downarrow$).
A valuation $v : \mathcal{P} \to \mathbb{B}$ extends uniquely to a truth value for every wff; for $n$ atoms there are $2^n$ valuations — the rows of a truth table.
The classes are: tautology (true everywhere), contradiction (false everywhere), contingent (sometimes true, sometimes false), satisfiable (true somewhere).
$\equiv$ is logical equivalence (a tautological $\leftrightarrow$); the Substitution Theorem allows replacement of equivalent sub-formulas.
$\Gamma \models \varphi$ is semantic entailment; the four most-used inference rules are MP, MT, HS, DS; resolution powers automated theorem proving.
Every formula has a CNF and a DNF; $\{\uparrow\}$ and $\{\downarrow\}$ are functionally complete.
Logic gates physically realise these connectives — propositional logic is the language of digital computing.
33 / 35
17. Wolfram → Python quick reference
Wolfram
SymPy
Python operator
Not[p]
Not(p)
~p
And[p,q]
And(p, q)
p & q
Or[p,q]
Or(p, q)
p | q
Xor[p,q]
Xor(p, q)
p ^ q
Implies[p,q]
Implies(p, q)
—
Equivalent[p,q]
Equivalent(p, q)
—
Nand[p,q]
Nand(p, q)
—
Nor[p,q]
Nor(p, q)
—
TautologyQ[expr]
not satisfiable(Not(expr))
—
SatisfiableQ[expr]
satisfiable(expr)
—
BooleanConvert[e,"CNF"]
to_cnf(e, simplify=True)
—
BooleanConvert[e,"DNF"]
to_dnf(e, simplify=True)
—
FullSimplify[e]
simplify(e)
—
BooleanTable[e,{p,q}]
truth_table(e, [p, q])
—
34 / 35
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §§1.1–1.3 (connectives, equivalences, normal forms), §1.6 (inference rules), §1.7 (proof methods), §12.3 (logic gates).
D. J. Velleman. How To Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019 — ch. 1 (logical operators), §3.1 (proof strategies).
E. Mendelson. Introduction to Mathematical Logic, 6th ed., CRC Press, 2015 — ch. 1 (propositional logic, NNF, completeness).
R. Cori & D. Lascar. Mathematical Logic, vol. 1: Propositional Calculus, Boolean Algebras, Predicate Calculus, Oxford University Press, 2000 — ch. 1–2.