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:

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

Tree

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

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

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:

Theorem: $P$ is logically equivalent to $Q$ iff $P \iff Q$ is a tautology.

Important Equivalence Laws

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

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.