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.

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.