Logic MT24, Propositional logic

Something which can be true or false.

A string from the alphabet $\{\lnot, \to, \wedge, \vee, \leftrightarrow, (, ), p _ 0, p _ 1, \ldots\}$ in one of the following forms:

• $p _ i$ where $i \in \mathbb N$
• $\lnot \phi$, where $\phi$ is a formula
• The combination of two formulas $\phi$ and $\psi$:
  • $(\phi \to \psi)$, “implication”
  • $(\phi \land \psi)$, “conjunction”
  • $(\phi \lor \psi)$, “disjunction”
  • $(\phi \leftrightarrow \psi)$, “equivalence”

Because it would need to be enclosed in parentheses, but it is not.

Suppose $\phi$ is a formula of $\mathcal L _ \text{prop}$. Then exactly one of the following holds:

• $\phi$ is $p _ i$ for some $i \in \mathbb N$
• $\phi$ is $\lnot \psi$ for a unique formula $\psi$
• $\phi$ is $(\psi \star \chi)$ for a unique pair of formulas $\psi$ and $\chi$.

No proper initial segment is a formula.

Claim: The number of left parentheses occurring in a formula $\varphi$ is equal to the number of right parentheses occurring $\varphi$.

Let $L(\varphi)$ and $R(\varphi)$ denote the number of left and right parentheses in $\varphi$. We prove $L(\varphi) = R(\varphi)$ for all formulas $\varphi$ by induction on $\text{len}(\varphi)$. So suppose $L(\psi) = R(\psi)$ for all formulas $\psi$ with $\text{len}(\psi) < \text{len}(\varphi)$.

If $\varphi$ is a propositional variable, then $L(\varphi) = 0 = R(\varphi)$. Otherwise, $\varphi$ is either of the form $\lnot \psi$ or of the form $(\psi \star \chi)$, with $\psi$ and $\chi$ formulas of length $< \text{len}(\varphi)$ and $\star \in { \to, \land, \lor, \leftrightarrow }$.

If $\phi = \lnot \psi$, then no new parentheses occur and $L(\varphi) = L(\psi) = R(\psi) = R(\phi)$ by the inductive hypothesis. If $\varphi = (\psi \star \chi)$, then one new left and one new right parentheses occur, and by the inductive hypothesis, we have $L(\varphi) = 1 + L(\psi) + L(\chi) = 1 + R(\psi) + R(\chi) = R(\phi)$.

---

Claim: No proper initial segment of a formula $\varphi$ is a formula.

Induct on the length of $\varphi$.

Base case $\text{len}(\varphi) = 1$: Then $\varphi = p _ i$ for some $p _ i$. Any proper initial segment is empty, which is not a formula.

Inductive step $\text{len}(\varphi) > 1$: Pick some $k < \text{len}(\varphi)$. If $k = 0$, then the resulting string is empty and hence not a formula. So we may assume $k > 0$. There are two cases.

1. $\varphi = \lnot \psi$ where $\psi$ is a formula. If $k > 1$, then by the inductive hypothesis, no initial segment of $\psi’$ of $\psi$ can be formula, so $\lnot \psi’$ is not a formula.
2. $\varphi = (\psi \star \chi)$ where $\star$ is a binary connective ${\to, \land, \lor, \leftrightarrow}$. Any proper initial segment will not contain ‘$)$’, and so the initial ‘$($’ will go unmatched. But the parentheses in any well-formed expression must be balanced.

---

Claim: Unique readability holds.

Induct on the length of $\varphi$.

Base case $\text{len}(\varphi) = 1$: Then $\varphi = p _ i$ for some unique $i$, as all other possibilities have length $> 1$.

Inductive step $\text{len}(\varphi) > 1$: If the initial character is $\varphi$ is ‘$\lnot$’, then it must be uniquely case (b), and by the inductive hypothesis, we are done.

Otherwise, $\varphi = (\psi \star \chi)$ for some formulas $\psi, \chi$ and a binary connective $\star$. We aim to show that this decomposition is unique.

Suppose $\varphi = (\psi _ 1 \star _ 1 \chi _ 1)$ and $\varphi = (\psi _ 2 \star _ 2 \chi _ 2)$ are $2$ such decompositions, and suppose for a contradiction that $\text{len}(\psi _ 1) \ne \text{len}(\psi _ 2)$. By the inductive hypothesis, $\psi _ 1, \chi _ 1, \psi _ 2, \chi _ 2$ are uniquely readable. Without loss of generality, we may assume $\text{len}(\psi _ 1) < \text{len}(\psi _ 2)$. But then $\psi _ 1$ gives a proper initial segment of a formula that is a formula, which is impossible. Hence $\text{len}(\psi _ 1) = \text{len}(\psi _ 2)$. Then $\psi _ 1 = \psi _ 2$ and $\star _ 1 = \star _ 2$ as both occur in the same positions.

But then by identical reasoning, $\text{len}(\psi _ 1) = \text{len}(\psi _ 2)$ and $\psi _ 1 = \psi _ 2$, and so any decomposition $\varphi = (\psi \star \chi)$ must be unique.

@important~

The set of all formulas of $\mathcal L _ \text{prop}$.

The set of all formulas which contain only variables from the set $\{p _ 0, \ldots, p _ {n-1}\}$.

\[\mathcal L _ \text{prop}[\lnot, \to]\]

(i.e. propositional formulas using only negation and implication, this is adequate).

A function

\[v : \\{p _ 0, \ldots, \\} \to \\{T, F\\}\]

(i.e. an assignment of true or value to the propositional variables).

$v$ can be extended to a function $\tilde v$:

\[\tilde v : \text{Form}(\mathcal L _ \text{prop}) \to \\{T, F\\}\]

by “evaluating the formula” given those truth values (what this means can be made rigorous with the unique readability theorem).

\[\tilde v(\phi) = T\]

It is satisfied by some valuation.

$\phi$ is satisfied by every valuation.

$\phi$ is satisfiable iff $\lnot \phi$ is not logically valid.

$v$ satisfies $\Gamma$ if it satisfies every element of $\Gamma$.

Every valuation that satisfies $\Gamma$ satisfies $\phi$: for all valuations $v$, if $\tilde v (\psi) = T$ for all $\psi \in \Gamma$, then $\tilde v(\phi) = T$.

Suppose:

• $\Gamma$ is a set of formulas
• $\psi$, $\phi$ are formulas (not necessarily in $\Gamma$)

Then:

\[\Gamma \cup \\{\psi\\} \models \phi \text{ iff } \Gamma \models (\psi \to \phi)\]

and, in particular when $\Gamma$ is empty:

\[\psi \models \phi \text { iff } \models \psi \to \phi\]

(i.e. $\psi \models \phi$ iff $\psi \to \phi$ is valid. This is like an entailment version of the deduction theorem).

Suppose that $\Gamma \cup \{\psi\} \models \phi$. Let $v$ be a valuation satisfying $\Gamma$, we aim to show that this valuation also satisfies $(\psi \to \phi)$.

• If $\tilde v(\psi) = T$, then $\tilde v(\phi) = T$, since $\Gamma \cup \{\psi\} \models \phi$. Hence $\tilde v((\psi \to \phi)) = T$ by the truth table of “$\to$”.
• If $\tilde v(\psi) = F$, then $\tilde v((\psi \to \phi)) = T$ by the truth table of “$\to$”.

Hence $\Gamma \models (\psi \to \phi)$.

Now suppose that $\Gamma \models (\psi \to \phi)$. Let $v$ be a valuation satisfying $\Gamma \cup \{\psi\}$. Then $\tilde v((\psi \to \phi)) = T = \tilde v(\psi)$, so $\tilde v(\phi) = T$ by the truth table of “$\to$”.

Hence $\Gamma \cup \{\psi\} \models \phi$.

$\phi \models \psi$ and $\psi \models \phi$, so $\tilde v(\phi) = \tilde v(\psi)$ for every valuation $v$. The notation is $\phi \equiv \psi$.

\[J : V _ n \to \\{T, F\\}\]

where $V _ n$ is the set of all valuations on the first $n$ propositional variables, i.e. functions $v : \{p _ 0, \ldots, p _ {n-1}\} \to \{T, F\}$.

An $n$-ary truth function is a function of the form

\[J : V _ n \to \\{T, F\\}\]

where $V _ n$ is the set of all valuations on $n$ propositional variables. Then $\phi$ represents the $n$-ary truth function given by

\[\begin{aligned} &J _ \phi^n : V _ n \to \\{T, F\\} \\\ &v \mapsto \tilde v(\phi) \end{aligned}\]

They are equal.

Let

\[U := \\{v \in V _ n \mid J(v) = T\\}\]

i.e. the set of valuations where $J$ is true. If $U$ is empty, then take $\phi = (p _ 0 \land \lnot p _ 0)$. Then $\phi$ represents $J$ since both are identically false.

Otherwise, suppose $U = \{v _ 0, \ldots, v _ {k-1}\}$. Consider the formula

\[\phi := \bigvee^{k-1} _ {i = 0} \bigwedge^{n-1} _ {j = 0} \psi _ {i,j}\]

where

\[\psi _ {i,j} = \begin{cases} p _ j &\text{if } v _ i(p _ j) = T \\\\ \lnot p _ j &\text{if } v _ i(p _ j) = F \end{cases}\]

Now consider an arbitrary valuation $w \in V _ n$ and some $0 \le i \le k-1$. Then

\[\tilde w\left( \bigwedge^{n-1} _ {j = 0} \psi _ {i,j} \right) = T \iff w = v _ i\]

since the construction of $\psi$ ensures that the valuations must match exactly. Hence

\[\begin{aligned} J^n _ \phi (w) = T &\iff \tilde w(\phi) = T \\\\ &\iff (w = v _ 0 \text { or ... or } w = v _ {k-1}) \\\\ &\iff w \in U \\\\ &\iff J(w) = T \end{aligned}\]

so then $J^n _ \phi = J$.

The language with those connectives and the corresponding formulas.

Every $n$-ary truth function is represented by some $\phi \in \text{Form} _ n(\mathcal L _ \text{prop}[\ast _ 1, \ldots, \ast _ k])$, i.e. every $n$-ary truth function can be made out of an expression in this language.