Notes taken for CSCB36 course at UofT, this post is for Chapter 5, Propositional Logic.
Propositional Formulas
Let $PV$ be a set of propositional variables. The set of propositional formulas, denoted $F_{PV}$ is the smallest set such that:
Basis: Any propositional variable in $PV$ belongs to $F_{PV}$.
Induction Step: If $P_1$ and $P_2$ belong to $F_{PV}$ then so do the following:
 $\neg P_1$
 $P_1 \wedge P_2$
 $P_1 \vee P_2$
 $P_1 \to P_2$
 $P_1 \iff P_2$
Note: $\neg$ is called unary connective, since it is applied to one subformula, others are called binary connectives.
Tree Representation of $F_{PV}$
Propositional formulas can be nicely drawn using trees.
For example, the formula $(a \vee b) \wedge \neg c$ can be drawn as
Truth Assignment
Let $PV$ be a set of propositional variables. A truth assignment is a function $r: PV \to \{0, 1\}$.
A truth assignment tells us, for each propositional variable, whether it represents a proposition that is true or false.
Extended Truth Assignment
Extended truth assignment can be used to assign a truth value to any propositional formula, given that you have $r$.
Let $r: PV \to \{0,1\}$. Define a function $r^*:F_{PV} \to \{0,1\}$ so it is the smallest set such that:
Basis: $P \in PV$. In this case, $r^*(P) = r(P)$.
Induction step: $P \notin PV$. Then there are $Q_1, Q_2 \in F_{PV}$ such that $P$ is one of the following formula: $\neg Q_1$, $(Q_1 \wedge Q_2)$, $(Q_1 \vee Q_2)$, $(Q_1 \to Q_2)$, and $(Q_1 \iff Q_2)$.
By induction, we can assume $r^*(Q_1)$ and $r^*(Q_2)$ are already known.
The function for all 5 cases are ignored since they should be trivial to figure out.
If $r^*(P) = 0$ then we say $r$ falsifies $P$, otherwise it satisfies $P$.
Some Notes on Logical Connectives
Inclusive / Exclusive OR
When OR is inclusive, that means if $A$ and $B$ are both true, then the whole statement is still true.
When it is exclusive, it means if $A$ and $B$ are both true, then the statement is false.
In formal math, we always use inclusive or, we have a special connective for exclusive or, namely xor.
Unique Readability Theorem
For any propositional formulas $P_1, P_2, Q_1, Q_2$ and binary connectives $+$ and $$. If $(P_1 + P_2) = (Q_1  Q_2)$ then $P_1 = Q_1$, $+ = $ and $P_2 = Q_2$.
This theroem basically states, there is only one way to construct a formula. However, if we omit the parentheses this is not going to be true anymore.
Even use of parentheses is nice, but usually they are not necessary, so we use some conventions.
Conventions to Omit Parentheses

There is no need to write outmost parentheses, say $(a \wedge b)$ is the same as $a \wedge b$.

$\wedge$ and $\vee$ have precedence over $\to$ and $\iff$.

$\wedge$ has precedence over $\vee$.

Grouping is assumed to be to the right, $a \to b \to c$ is the same as $a \to (b \to c)$
Truth Tables
A truth table of $P$ tells us the truth value of $P$ under all possible truth assignments.
For example, $x \vee y \to \neg x \wedge z$, the truth table is going to be:
Tautologies and Satisfiability
 $P$ is a tautology iff every truth assignment satisfies $P$.
 $P$ is satisfiable iff there is a truth assignment that satisfied $P$.
 $P$ is unsatisfiable iff it is not satisfiable. In another word, $\neg P$ is a tautology.
Logical Implication
Definition: A propositional formula $P$ logically implies propositional formula $Q$ if and only if every truth assignment that satisfies $P$ also satisfies $Q$.
Theorem: $P$ logically implies $Q$ iff $P \to Q$ is a tautology.
Logical Equivalence
Definition: $P$ is logically equivalent to $Q$ iff $P$ logically implis $Q$ and $Q$ logically implies $P$.
Properties of logical equivalence:
 Reflexivity: $P$ is logically equivalent to $P$.
 Symmetry: If $P$ is logically equivalent to $Q$ and $Q$ is logically equivalent to $P$.
 Transitivity: If $P$ is logically equivalent to $Q$, and $Q$ is logically equivalent to $R$, then $P$ is logically equivalent to $R$.
Theorem: $P$ is logically equivalent to $Q$ iff $P \iff Q$ is a tautology.
Important Equivalence Laws
 $\neg \neg P \equiv P$
 $\neg (P \wedge Q) \equiv \neg P \vee \neg Q$
 $\neg (P \vee Q) \equiv \neg P \wedge \neg Q$
 $P \wedge Q \equiv Q \wedge P$
 $P \vee Q \equiv Q \vee P$
 $P \wedge (Q \wedge R) \equiv (P \wedge Q) \wedge R$
 $P \vee (Q \vee R) \equiv (P \vee Q) \vee R$
 $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$
 $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$
 $P \wedge (Q \vee \neg Q) \equiv P$
 $P \vee (Q \wedge \neg Q) \equiv P$
 $P \wedge P \equiv P$
 $P \vee P \equiv P$
 $P \to Q \equiv \neg P \vee Q$
 $P \to Q \equiv \neg Q \to \neg P$
 $P \iff Q \equiv P \wedge Q \vee \neg P \wedge \neg Q$
Theorem: Let $R$ be any propositional formula, $S$ be any subformula of $R$, $S’$ be any formula that is logically equivalent to $S$, and $R’$ be the formula that results from $R$ by replacing $S$ with $S’$. Then $R’$ is logically equivalent to $R$.
Normal Forms of Propositional Formulas
 Literal  Only have one propositional variable or the negation of that variable.
 Minterm  Is a literal, or a conjuction of two or more literals.
 Maxterm  Is a literal, or a disjunction of two or more literals.
 Disjunctive Normal Form  Is minterm, or a disjunction of two or more minterms.
 Conjunctive Normal Form  Is maxterm, or a conjunction of two or more maxterms.
They talked about circuit design, already took B58 which covers way more details, not going to take notes here.
Complete Sets of Connectives
Definition: A set of connectives is complete iff every boolean function can be represented by a propositional formula that uses only connectives from that set.
Theorem: $\{\neg, \wedge, \vee\}$ is a complete set of connectives.
Theorem: $\{\neg, \wedge\}$ is a complete set of connectives.
Theorem: $\{\neg, \vee\}$ is a complete set of connectives.
Theorem: $\{\}$ is a complete set of connectives (NAND).
Theorem: $\{\downarrow\}$ is a complete set of connectives (NOR).
$\oplus$ is exclusive or.