MATH 3265 Class Notes 01-24-2025

notelogic

Propositional Logic

Notation Convention for this Course

Because it is a pain to write the subscripts on variables, we will tend to use $p,q,r,\dots$ to denote variables rather than $v_1,v_2,v_3,\dots$ .

Formation Trees

(Draw trees the same way that we did in PHIL 1102).

Example: Recursive Definition

Define a function $F$ on set of all propositional formulas by recursion.

Base case: Specify $F(v_i)$ for each propositional variable $v_i$.

Inductive cases:

• Specify $F(\neg \phi )$ using $F(\phi )$.
• Specify $F((\phi \wedge \psi ))$ using $F(\phi )$ and $F(\psi )$.
• Specify $F((\phi \vee \psi )$ using $F(\phi )$ and $F(\psi )$.
• Specify $F((\phi \to \psi ))$ using $F(\phi )$ and $F(\psi )$.
• Specify $F((\phi \leftrightarrow \psi ))$ using $F(\phi )$ and $F(\psi )$.

Example: Inductive Proof

Prove that every formula has the same number of left and right parentheses.

Base case: Show every propositional variable $v_i$ has the property $P$. Induction cases:

• Assume $\phi$ has property $P$. Show that $\neg \phi$ also has $P$.
• Assume $\phi$ and $\psi$ both have property $P$. Show that $(\phi \ast \psi )$ has property $P$ for each of $\ast =\wedge ,\vee ,\leftarrow ,\leftrightarrow$.