MATH 3265 Class notes 03-10-2025

notepropositional-logic

Summary of Last Week

$\phi$ is a tautology, $\models \phi ⟺$ for all valuations $V$, $V(\phi )=1$. $\phi$ is provable, $⊢\phi ⟺$ there is a contradictory finite tableau with root labeled $F\phi$.

Theorem

$\models \phi ⟺⊢\phi$. The right direction is the Completeness Theorem, and the left direction is the Soundness Theorem.

Extend this Picture

$\Gamma \models \phi ⟺$ for all valuations $V$ such that $V\models \Gamma$, we have $V\models \phi$ (we say $\phi$ is a consequence of $\Gamma$).

Defined Set of Finite Tableau

Defined Tableau Proof

Following the defined algorithm generates the complete systematic tableau from $\Gamma$ with root $F\phi$.

• To do this, you need to fix an order on $\Gamma$
• $\Gamma$ could be infinite…we will always assume $\Gamma$ is countable, which just means it can be listed as $\Gamma =\left\{{\gamma }_1,{\gamma }_2,\dots \right\}$ (indices are positive whole numbers).

Example

Generate the complete systematic tableau from $\left\{p_0\to p_1,p_1\to p_2\right\}$.

\usepackage{tikz-cd}
\begin{document}
\begin{math}
 
\begin{tikzcd}[ampersand replacement=\&, row sep = 1em, column sep = 0.5em] \& {F \neg p_0} \\ \& {T p_0} \\ \& {T ( p_0 \rightarrow p_1)} \\ {Fp_0} \&\& {Tp_1} \\ \bot \&\& {T(p_1 \rightarrow p_2)} \\ \& {Fp_1} \&\& {Tp_2} \\ \& \bot \&\& \top \arrow[no head, from=1-2, to=2-2] \arrow[no head, from=2-2, to=3-2] \arrow[no head, from=3-2, to=4-3] \arrow[no head, from=4-1, to=3-2] \arrow[no head, from=4-3, to=5-3] \arrow[no head, from=5-3, to=6-4] \arrow[no head, from=6-2, to=5-3] \end{tikzcd}
 
\end{math}
\end{document}
 

We can see that there exists a non-contradictory branch (the one ending with $T{p}_2$) in the complete systematic tableau.

Define valuation $V$ by $V(p_0)=1$, $V(p_1)=1$, and $V(p_2)=1$. Then check that $V$ agrees with all signed formulas on branch.

Example

Generate complete systematic tableau from $\Gamma =\left\{p_0\to p_1,p_1\to p_2,\dots \right\}$ with root labeled $F\neg p_0$ (trying to check if $\Gamma ⊢\neg p_0$).

\usepackage{tikz-cd}
 
\begin{document}
\begin{math}
\begin{tikzcd}[ampersand replacement=\&, row sep = 1em, column sep = 0.5em] \& {F \neg p_0} \\ \& {Tp_0} \\ \& {T(p_0 \rightarrow p_1)} \\ {F p_0} \&\& {Tp_1} \\ \&\& {T(p_1 \rightarrow p_2)} \\ \& {F p_1} \&\& {Tp_2} \\ \&\&\& {T(p_2 \rightarrow p_3)} \\ \&\&\& \vdots \arrow[no head, from=1-2, to=2-2] \arrow[no head, from=2-2, to=3-2] \arrow[no head, from=3-2, to=4-3] \arrow[no head, from=4-1, to=3-2] \arrow[no head, from=5-3, to=4-3] \arrow[no head, from=5-3, to=6-4] \arrow[no head, from=6-2, to=5-3] \arrow[no head, from=6-4, to=7-4] \end{tikzcd}
\end{math}
\end{document}