Exercise 5

\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cM}{\mathcal{M}} \newcommand{\Var}{\mathrm{Var}} \newcommand{\FV}{\mathrm{FV}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]

1 Tautologically implies is decidable for finite sets

Complete this notebook

Solution

Solutions

2 Tautologically Implies

• Prove or disprove. \(\{P \lor Q, \neg P \lor R, \neg Q \lor R \} \models R\)
• Prove or disprove. \(P\to Q\to R \equiv P \land Q \to R\).

Solution

1. True. Let \(v\) satisfy all three premises. Since \(v(P\lor Q)=1\), either \(v(P)=1\) or \(v(Q)=1\). In the first case, \(\neg P\lor R\) forces \(v(R)=1\); in the second, \(\neg Q\lor R\) forces \(v(R)=1\). Thus every model of the premises satisfies \(R\).

2. True, using the convention that \(\to\) associates to the right:

   \[ P\to(Q\to R) \equiv \neg P\lor(\neg Q\lor R) \equiv \neg(P\land Q)\lor R \equiv (P\land Q)\to R. \]

3 Boolean functions

A boolean function on \(n\) variables is a function \(f:\OI^n \to \OI\).

3.1

How many boolean functions are there on \(n\) variables?

Solution

There are \(2^n\) inputs in \(\OI^n\). A function independently assigns either \(0\) or \(1\) to each input, so there are

\[ 2^{2^n} \]

boolean functions on \(n\) variables.

4

---

Notice that \(\vec{x} \in \OI^n\) can be viewed as a truth assignment. Define \(v_{\vec x}\) to be the truth assignment that assigns the \(i\)th atom \(x_i\). I.e., \(v_{\vec x}(P_i) = x_i\).

A propositional formula \(A\) with \(n\) variables realizes a boolean function \(f: \OI^n \to \OI\) if for all \(\vec{x} \in \OI^n\).

\[v_{\vec{x}}(A) = f(\vec{x})\]

4.1

Show that every boolean function with on \(n \geq 1\) variables is realizable by some boolean formula using only the connectives \(\neg, \land, \lor\).

Solution

Assume \(n\geq 1\). For each \(\vec a=(a_1,\ldots,a_n)\in\OI^n\), define

\[ L_i^{\vec a}=\begin{cases}P_i&\text{if }a_i=1,\\ \neg P_i&\text{if }a_i=0,\end{cases} \qquad M_{\vec a}=L_1^{\vec a}\land\cdots\land L_n^{\vec a}. \]

Then \(v_{\vec x}(M_{\vec a})=1\) exactly when \(\vec x=\vec a\). Consequently, if \(f\) is not constantly zero, the disjunctive normal form

\[ A_f=\bigvee_{\vec a:\,f(\vec a)=1}M_{\vec a} \]

realizes \(f\). For the constantly zero function, use \(P_1\land\neg P_1\). All finite conjunctions and disjunctions can be parenthesized using binary connectives.

4.2

In general, a set of connectives that satisfies the property that every boolean function is realized by some boolean formula, only using the connectives in the set is called functionally complete.

Show the following sets are functionally complete.

• \(\{\neg, \land\}\)
• \(\{\neg, \lor\}\)
• \(\{ \uparrow \}\), where \(P \uparrow Q\) is shorthand for \(\neg(P \land Q)\).

Solution

By the preceding result, it suffices to express \(\neg,\land,\lor\) using each proposed set.

• With \(\{\neg,\land\}\), use \(A\lor B\equiv\neg(\neg A\land\neg B)\).

• With \(\{\neg,\lor\}\), use \(A\land B\equiv\neg(\neg A\lor\neg B)\).

• With \(\uparrow\) alone, use

  \[ \neg A\equiv A\uparrow A, \qquad A\land B\equiv(A\uparrow B)\uparrow(A\uparrow B). \]

  \(\uparrow\) therefore expresses both members of the first complete set.

Recursively replacing connectives by these expressions preserves truth values, so each set is functionally complete.

4.3

• Show \(\{\to \}\) is not functionally complete.

Solution

Every formula built from atoms and \(\to\) is true under the assignment making every atom true. This follows by structural induction: atoms are true, and an implication with both subformulas true is true. Such formulas cannot realize the function \(f(x)=1-x\), which is false at \(x=1\).

5 Truth (Enderton 1.2.2)

5.1

Prove or refute the following

Let \(S\) be a set, and \(\alpha, \beta\) be formulas.

1. If either \(S \models \alpha\) or \(S\models \beta\), then \(S\models (\alpha \lor \beta)\).
2. If \(S \models (\alpha \lor \beta)\), then \(S \models \alpha\) or \(S \models \beta\).

Solution

1. True. If \(S\models\alpha\), every model of \(S\) makes \(\alpha\), and hence \(\alpha\lor\beta\), true. The case \(S\models\beta\) is identical. This also holds when \(S\) has no models.

2. False. Take \(S=\{P\lor Q\}\), \(\alpha=P\), and \(\beta=Q\). Certainly \(S\models P\lor Q\). But the assignment \(P=0,Q=1\) shows \(S\not\models P\), and \(P=1,Q=0\) shows \(S\not\models Q\). Different models can satisfy different disjuncts.

6 Duality (Enderton 1.2.9)

Let \(A\) be a formula using only the connectives \(\neg, \lor, \land\). Define the dual, \(A^\delta\) to be the formula obtained by exchanging \(\land\) with \(\lor\) and replacing each atom \(P\) with \(\neg P\). Prove (by structural induction) that

\[ A^\delta \equiv \neg A \]

Solution

By Structural Induction.

• Base case: If \(A=P\), then \(A^\delta=\neg P=\neg A\).

Suppose the claim is true for formulas \(A\) and \(B\), we’ll show it’s true for \(\neg A, (A \lor B)\), and \((A \land B)\).

• \((\neg A)^\delta = \neg (A^\delta) \equiv \neg \neg A\)
• \((A \lor B)^\delta = (A^\delta \land B^\delta) \equiv \neg A \land \neg B \equiv \neg(A \lor B)\)
• \((A \land B)^\delta = (A^\delta \lor B^\delta) \equiv \neg A \lor \neg B \equiv \neg(A \land B)\)

The last two cases use De Morgan’s laws, and the steps that remove the \(\delta\) use the IH.

7 PK

Give PK Proofs of the following

• \(\seq \neg (A \land \neg A)\)
• \(A \land (B \lor C) \seq ((A \land B) \lor (A \land C))\)
• \(A \lor (B \land C) \seq ((A \lor B) \land (A \lor C))\)
• \((\neg (A \land B) \lor C) \seq (\neg A \lor (\neg B \lor C))\)