Equivalence of Propositions

Discrete Mathematics — Lesson 3

Notes By Pr. El Hadiq Zouhair

1 / 15

Overview

Propositional equivalences are the primary tool of simplification in Boolean algebra.
Using equivalences allows the analysis of satisfiability.
Philosophy and reasoning are full of puzzles that can be simplified using equivalences.

You will learn about propositional equivalences, satisfiability, and normal forms.

2 / 15

Satisfiability — Tautology & Contradiction

A tautology is a logical statement that is always true: $p \lor \lnot p \equiv \top$

Wolfram TautologyQ[p || !p] (* Out: True *)

SymPy from sympy import symbols, Or, Not from sympy.logic.inference import satisfiable p = symbols('p') not satisfiable(Not(Or(p, Not(p)))) # True

A formula is satisfiable if in at least one case it takes a true value.
A contradiction is always false: $p \land \lnot p \equiv \bot$

Wolfram SatisfiableQ[p && !p] (* Out: False *)

SymPy from sympy import And bool(satisfiable(And(p, Not(p)))) # False

3 / 15

Satisfiability — Contingency

A contingency may be true or false: $p \land q$ is satisfiable but not a tautology.

Wolfram SatisfiableQ[p && q] (* True *) TautologyQ[p && q] (* False *)

SymPy q = symbols('q') bool(satisfiable(And(p, q))) # True not satisfiable(Not(And(p, q))) # False

	Satisfiable	Tautology
Tautology	✔	✔
Contingency	✔	✘
Contradiction	✘	✘

4 / 15

Main Equivalences

Two propositions $p$ and $q$ are equivalent if and only if $p \Leftrightarrow q$ is a tautology.

Law	Equivalence 1	Equivalence 2
Identity	$p \land \top \Leftrightarrow p$	$p \lor \bot \Leftrightarrow p$
Domination	$p \lor \top \Leftrightarrow \top$	$p \land \bot \Leftrightarrow \bot$
Idempotency	$p \lor p \Leftrightarrow p$	$p \land p \Leftrightarrow p$
Double Negation	$\lnot(\lnot p) \Leftrightarrow p$
Commutativity	$p \lor q \Leftrightarrow q \lor p$	$p \land q \Leftrightarrow q \land p$
Associativity	$p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r$	$p \land (q \land r) \Leftrightarrow (p \land q) \land r$
Distributivity	$p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$	$p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$
De Morgan's	$\lnot(p \land q) \Leftrightarrow \lnot p \lor \lnot q$	$\lnot(p \lor q) \Leftrightarrow \lnot p \land \lnot q$
Absorption	$p \lor (p \land q) \Leftrightarrow p$	$p \land (p \lor q) \Leftrightarrow p$
Negation	$p \lor \lnot p \Leftrightarrow \top$	$p \land \lnot p \Leftrightarrow \bot$

5 / 15

Example: Simplifying a Proposition

Simplify: "These potatoes are sweet and salty or they are salty, spicy and (salty or spicy)."

$(\textit{sweet} \land \textit{salty}) \lor \bigl(\textit{salty} \land \textit{spicy} \land (\textit{salty} \lor \textit{spicy})\bigr)$

$\Leftrightarrow\;(\textit{sweet} \land \textit{salty}) \lor (\textit{salty} \land \textit{spicy} \land \textit{salty}) \lor (\textit{salty} \land \textit{spicy} \land \textit{spicy})$Distributivity

$\Leftrightarrow\;(\textit{sweet} \land \textit{salty}) \lor (\textit{salty} \land \textit{spicy}) \lor (\textit{salty} \land \textit{spicy})$Idempotency

$\Leftrightarrow\;(\textit{salty} \land \textit{spicy}) \lor (\textit{salty} \land \textit{sweet})$Idempotency

Result: "These potatoes are salty and spicy, or salty and sweet."

6 / 15

Automated Simplification

Wolfram — BooleanMinimize BooleanMinimize[ (sweet && salty) || (salty && spicy && (salty || spicy))] (* (salty && spicy) || (salty && sweet) *)

SymPy — simplify_logic from sympy import symbols from sympy.logic.boolalg import ( And, Or, simplify_logic) sweet, salty, spicy = symbols( 'sweet salty spicy') expr = Or( And(sweet, salty), And(salty, spicy, Or(salty, spicy))) simplify_logic(expr) # (salty & spicy) | (salty & sweet)

7 / 15

Conditional Equivalences

All logical operators can be expressed using basic operators ($\lnot$, $\land$, $\lor$).

Operator	Equivalence
Conditional	$p \to q \;\Leftrightarrow\; \lnot p \lor q$
Bicond. to Cond.	$(p \Leftrightarrow q) \;\Leftrightarrow\; (p \to q) \land (\lnot p \to \lnot q)$
Biconditional	$(p \Leftrightarrow q) \;\Leftrightarrow\; (p \land q) \lor (\lnot p \land \lnot q)$

Key result: All propositions can be expressed using only $\lnot$, $\land$, $\lor$.

8 / 15

Disjunctive Normal Form (DNF)

A DNF proposition is the disjunction of one or more conjunctions.

From our example: $(\textit{salty} \land \textit{spicy}) \lor (\textit{salty} \land \textit{sweet})$ is in DNF.

Wolfram — BooleanConvert BooleanConvert[ ((a ~Xor~ b ~Xor~ !c || (a||b) && (b||c||d)) && (!c||b)) ~Xor~ (!c && a), "DNF"] (* (!a && !b) || (!b && c) *)

SymPy — to_dnf from sympy import symbols, Xor from sympy.logic.boolalg import ( And, Or, Not, to_dnf) a, b, c, d = symbols('a b c d') inner = Or(Xor(a,b,Not(c)), And(Or(a,b), Or(b,c,d))) expr = Xor( And(inner, Or(Not(c), b)), And(Not(c), a)) to_dnf(expr, simplify=True) # (~a & ~b) | (~b & c)

9 / 15

DNF — XOR: "For me or against me"

Translate: "You are either for me or against me" $\;\longrightarrow\; f \oplus a$

Wolfram BooleanConvert[f ~Xor~ a, "DNF"] (* (a && !f) || (!a && f) *)

SymPy f, a = symbols('f a') to_dnf(Xor(f, a), simplify=True) # (a & ~f) | (~a & f)

10 / 15

DNF — Counting Function

Problem: Find the logical expression that is true when exactly 2 or 3 of $\{a,b,c,d\}$ are true.

Wolfram — BooleanCountingFunction expr = BooleanCountingFunction[ {2,3}, {a,b,c,d}]; BooleanConvert@expr (* full DNF *) BooleanMinimize@expr (* minimal DNF *)

SymPy from itertools import combinations from sympy import symbols, And, Or, Not from sympy.logic.boolalg import ( to_dnf, simplify_logic) a, b, c, d = symbols('a b c d') vs = [a, b, c, d] def count_fn(ks, vs): n = len(vs) return Or(*[ And(*[vs[i] if i in combo else Not(vs[i]) for i in range(n)]) for k in ks for combo in combinations(range(n), k)]) expr = count_fn([2, 3], vs) print(to_dnf(expr, simplify=True)) print(simplify_logic(expr))

11 / 15

Other Normal Forms

Other normal forms are also possible:

Form	$x \oplus y$ expressed as …
DNF	$(x \land y) \lor (\lnot x \land \lnot y)$
CNF	$(\lnot x \lor y) \land (x \lor \lnot y)$
NAND	$(x \barwedge y) \barwedge (\lnot x \barwedge \lnot y)$
NOR	$(\lnot x \downarrow y) \downarrow (x \downarrow \lnot y)$

Wolfram — CNF BooleanConvert[x ~Xor~ y, "CNF"] (* (!x || y) && (x || !y) *)

SymPy — to_cnf from sympy.logic.boolalg import to_cnf x, y = symbols('x y') to_cnf(Xor(x, y), simplify=True) # (x | y) & (~x | ~y)

Universal gates: NAND ($\barwedge$) and NOR ($\downarrow$) can each express all binary operations.

12 / 15

CNF to DNF Conversion

Convert $(\lnot p \lor q) \land (\lnot p \lor \lnot r) \land (\lnot q \lor r)$ to DNF:

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

$\Leftrightarrow\;\bigl(\lnot p \lor (q \land \lnot r)\bigr) \land (\lnot q \lor r)$Distributivity

$\Leftrightarrow\;\bigl(\lnot p \lor \lnot(\lnot q \lor r)\bigr) \land (\lnot q \lor r)$De Morgan's

$\Leftrightarrow\;\bigl(\lnot p \land (\lnot q \lor r)\bigr) \lor \bigl(\lnot(\lnot q \lor r) \land (\lnot q \lor r)\bigr)$Distributivity

$\Leftrightarrow\;\lnot p \land (\lnot q \lor r) \;\lor\; \bot$Negation

$\Leftrightarrow\;\lnot p \land (\lnot q \lor r)$Identity

Complexity Note

Converting from CNF to DNF is NP-hard — a class of computationally difficult problems.

13 / 15

Satisfiability Research

Satisfiability remains an open problem at the heart of computer science.
Efficiently determining whether any logical expression is satisfiable can be very difficult.
The propositional satisfiability problem (SAT) is the main subject of annual research conferences.

Is there an efficient algorithm for SAT?
P vs. NP — one of the Millennium Prize Problems.

14 / 15

Summary

A proposition is either a tautology, a contradiction, or a contingency.
Many propositional equivalences are used by simplify_logic (SymPy) to simplify Boolean expressions automatically.
Simplifications are standardised through normal forms (DNF, CNF, NAND, NOR).
The previous propositions were declarative statements — more expressive logics (predicates, quantifiers) come next.

SymPy function	Replaces Wolfram
`not satisfiable(Not(expr))`	`TautologyQ`
`bool(satisfiable(expr))`	`SatisfiableQ`
`simplify_logic(expr)`	`BooleanMinimize`
`to_dnf(expr, simplify=True)`	`BooleanConvert[…,"DNF"]`
`to_cnf(expr, simplify=True)`	`BooleanConvert[…,"CNF"]`

15 / 15