Lesson 3 — Exercises: Equivalence of Propositions

Ex 1 De Morgan's First Law equivalence

Verify the equivalence $\neg(p \land q) \equiv \neg p \lor \neg q$ by comparing truth table outputs row by row.

Write a helper are_equivalent(expr1, expr2, variables) -> bool using truth_table.
Apply it to confirm De Morgan's first law for all four assignments of $(p, q)$.

Ex 2 De Morgan's Second Law equivalence

Verify the equivalence $\neg(p \lor q) \equiv \neg p \land \neg q$ using the same are_equivalent helper from Exercise 1.

Confirm the result for all four assignments of $(p, q)$.
State in plain English what De Morgan's laws say about negating compound statements.

Ex 3 Double Negation simplify_logic

Use simplify_logic(Not(Not(p))) and verify that the result equals $p$.

Assert simplify_logic(Not(Not(p))) == p.
What does the double negation law $\neg\neg p \equiv p$ mean intuitively?

Ex 4 Absorption Laws simplify_logic

Verify both absorption laws using simplify_logic:

$p \lor (p \land q) \equiv p$ (OR absorption)
$p \land (p \lor q) \equiv p$ (AND absorption)

Assert that both expressions simplify to the symbol $p$ alone. Why is this called an "absorption" law?

Ex 5 Distributive Laws equivalence

Verify both distributive laws using are_equivalent over three variables $(p, q, r)$:

$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

How many rows does a truth table with 3 variables have?

Ex 6 Simplification with simplify_logic simplify_logic

Simplify the following compound formulas using simplify_logic and verify each result equals $p$:

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

Hint: Both expressions can be simplified by factoring out $p$ using the distributive law, then applying the tautology $q \lor \neg q \equiv \top$.

Ex 7 Conjunctive Normal Form (CNF) to_cnf

Convert each of the following formulas to CNF using sympy.to_cnf. A CNF is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals.

$p \to q$
$p \leftrightarrow q$
$(p \lor q) \land (p \to r)$

Print the CNF form of each and verify it is logically equivalent to the original using are_equivalent.

Ex 8 Disjunctive Normal Form (DNF) to_dnf

Convert each formula to DNF using sympy.to_dnf. A DNF is a disjunction (OR) of terms, where each term is a conjunction (AND) of literals.

$(p \lor q) \land \neg r$
$p \leftrightarrow (q \land r)$

Print the DNF form and verify equivalence with the original formula.

Ex 9 Satisfiability satisfiable

Use sympy.logic.inference.satisfiable to determine whether each formula below is satisfiable, unsatisfiable, or a tautology. satisfiable returns a model (dictionary) if satisfiable, or False if not.

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

For each satisfiable formula, print the model (assignment that makes it True).

Ex 10 Counting Function — At Least $k$ of $n$ combinations

Implement at_least_k_of(variables, k) that returns a SymPy formula which is True iff at least $k$ of the given variables are True.

Hint: Use itertools.combinations — "at least $k$ variables are True" iff some $k$-element subset is simultaneously True: Or(*[And(*combo) for combo in combinations(variables, k)]).

Declare variables $a, b, c, d, e$ and build at_least_2_of_5.
Verify: the formula is True when $a=b=\text{True},\; c=d=e=\text{False}$.
Verify: the formula is False when only $a=\text{True}$ and all others False.
Print the simplified form using simplify_logic.

Ex 11 Implication Equivalences equivalence

Verify each of the following equivalences using are_equivalent:

Name	Equivalence
Implication as disjunction	$p \to q \;\equiv\; \neg p \lor q$
Contrapositive	$p \to q \;\equiv\; \neg q \to \neg p$
Negation of implication	$\neg(p \to q) \;\equiv\; p \land \neg q$

For each equivalence, assert the result and print a confirmation message.

Lesson 3 — Equivalence of Propositions