Lesson 2 — Exercises: Propositional Logic

Ex 1 Basic Propositions SymPy

Use sympy.symbols to declare boolean variables $p$ and $q$. Build the compound expression $p \land (q \lor \neg p)$ and evaluate it for all four combinations of truth values.

Use .subs({p: True, q: False}) to evaluate.
Print one line per combination in the form p=..., q=... → ....

Ex 2 NOT, AND, OR connectives

Using SymPy's Not, And, Or, compute $\neg p$, $p \land q$, and $p \lor q$ for all four assignments of $(p, q)$.

Print a single row per assignment showing all three results side by side.
Confirm that $\neg p$ flips the truth value of $p$ in every row.

Ex 3 Implication Truth Table Implies

Build the expression $p \to q$ using sympy.Implies(p, q) and print its complete truth table using sympy.logic.boolalg.truth_table.

Format the output as a table with columns $p$, $q$, $p \to q$.
Identify the one row where $p \to q$ is False and explain why.

Reminder: $p \to q$ is False only when $p$ is True and $q$ is False.

Ex 4 Biconditional (↔) Equivalent

Build $p \leftrightarrow q$ using sympy.Equivalent(p, q) and print its full truth table.

Format output with columns $p$, $q$, $p \leftrightarrow q$.
On which rows is the biconditional True? What do those rows have in common?

Ex 5 Operator Precedence precedence

Evaluate two different parenthesisations of $\neg p \land q \lor r$ for the assignment $p = \text{True},\; q = \text{False},\; r = \text{True}$:

Expression A: $(\neg p \land q) \lor r$
Expression B: $\neg p \land (q \lor r)$

Show that A and B give different results and explain the standard precedence order: $\neg > \land > \lor > {\to} > {\leftrightarrow}$.

Ex 6 Converse, Contrapositive, Inverse implication

Given the implication $p \to q$, define and simplify (using simplify_logic) each of the following:

Name	Formula
Original	$p \to q$
Converse	$q \to p$
Contrapositive	$\neg q \to \neg p$
Inverse	$\neg p \to \neg q$

Verify that the original and contrapositive simplify to the same expression.
Verify that the converse and inverse simplify to the same expression.

Ex 7 Tautology Detection satisfiable

Write a helper is_tautology(expr) -> bool that returns True when an expression is a tautology (True for every assignment).

Hint: A formula is a tautology iff its negation is unsatisfiable — use not satisfiable(Not(expr)).

Apply it to each formula below and report the result:

$p \lor \neg p$
$(p \to q) \to (\neg q \to \neg p)$
$p \land \neg p$
$(p \lor q) \to p$

Ex 8 Contradiction Detection satisfiable

Write is_contradiction(expr) -> bool that returns True when a formula is False for every assignment.

Hint: A formula is a contradiction iff it is not satisfiable — use not satisfiable(expr).

Test it on:

$p \land \neg p$
$p \lor \neg p$
$(p \to q) \land p \land \neg q$

Ex 9 Exclusive OR (XOR) Xor

Use SymPy's Xor(p, q) and verify the equivalence:

$$p \oplus q \;\equiv\; (p \lor q) \land \neg(p \land q)$$

Use is_tautology(Equivalent(xor_direct, xor_expanded)) to confirm.
Print the full truth table for $p \oplus q$.
On which rows is XOR True? How does it differ from OR?

Ex 10 Logic Gates — NAND and NOR gates

Define Python functions NAND(a, b) and NOR(a, b) using SymPy's Not, And, Or.

Then show that NAND is functionally complete by expressing NOT, AND, and OR using only NAND:

$\neg p \;\equiv\; p \;\text{NAND}\; p$
$p \land q \;\equiv\; (p \;\text{NAND}\; q) \;\text{NAND}\; (p \;\text{NAND}\; q)$
$p \lor q \;\equiv\; \text{NOR}(\text{NOR}(p,p),\, \text{NOR}(q,q))$

Verify each equivalence using is_tautology(Equivalent(...)).

Ex 11 Three-Variable Truth Table truth_table

Consider the formula representing Hypothetical Syllogism:

$$\bigl((p \to q) \land (q \to r)\bigr) \to (p \to r)$$

Build this formula with SymPy and print its complete truth table over $p, q, r$ (8 rows).
Is the formula a tautology? Verify using is_tautology.
How many rows are there for $n = 3$ boolean variables? Why?

Lesson 2 — Propositional Logic