Suppose $n$ is a positive integer and $X_n = \{(x_1,\ldots ,x_n) \colon x_i ∈ \{T,F\}\}$ is the set of $n$- tuples from $\{T,F\}$. Suppose $f\colon X_n \to \{T,F\}$ is a function and $f(x) = T$ for some $x \in X_n$ . By considering $\{x \in X_n \colon f(x) = T\}$, show that there exist propositional formulas $\psi_1,\ldots ,\psi_r$ in variables $p_1, \ldots , p_n$ such that:
(i) each $\psi_i$ is of the form ${{q_i}_1} \land \ldots \land{{q_i}_n}$,where ${{q_i}_j}$ is $p_j$ or $(¬p_j)$;
(ii) the truth function of the formula $\phi$ given by $\psi_1\lor \ldots \lor\psi_r$ is $f$.
This is question on a lot of past papers for the Logic module I am taking. I think it might be asking for a proof from the notes but I am unsure how to use the proof to answer the 2 individual bits of this question and if it is really what the question is asking for as I am not sure the Theorem is about the same thing as the Q. I felt that the question is asking about, like, the proof of disjunctive normal form?
Theorem 1.5.1
For any function $f\colon X_n \rightarrow \{T,F\}$ there is a formula $\phi$ whose truth function is given by $f$. The formula $\phi$ can be taken to use connectives in $\{\lor,\land,\neg\}$.
And I have the following proof:
If $f$ always has value $F$ then let $\phi$ be the formula $(p_1)∧(¬p_1))$. Otherwise, let $v_1, v_2, \ldots ,v_n \in X_n$ be the places, i.e rows in the truth table, where $f$ takes the value $T$. So each $v_i=({{v_i}_1}, {{v_i}_2}, \ldots,{{v_i}_n})$ where ${{v_i}_j}\in \{T,F\}$.
Let $p_1,p_2, \ldots ,p_n$ be propositional variables and let ${{q_i}_j}=\begin{cases} p_j, &\text{if }{{v_i}_j}=T\\ ¬p_j, &\text{if }{{v_i}_j}=F\end{cases}$.
Let $\psi_i={{q_i}_1}\land {{q_i}_2}\land \ldots \land{{q_i}_n}$ then $\psi_i$ has value $T$ if and only if $p_1$ has value ${{v_i}_1},\, p_2$ has value ${{v_i}_2}\ldots $ and $p_n$ has value ${{v_i}_n}$. Let $\phi$ be $\psi_1\lor \psi_2\lor \ldots \lor \psi_r$ Then for any assignment $\omega$ of truth values we have that $\omega(\phi)=T$ if and only if $\omega(\psi_i)=T$ for some $\psi_i$, if and only if $\omega$ gives $p_1,p_2,\ldots ,p_n$ values as in $v_i$ for some $i$ greater than or equal to $r$. So the truth function of $\phi$ is exactly $f$.
I almost follow the proof but i am unsure how to split it up to answer the 2 questions on past papers correctly. Would the first part (i) just finish at "Let $p_1,p_2,…,p_n$ be propositional variables and let ${{q_i}_j}$= {$p_j$ if ${{v_i}_j}$=T or $¬p_j$ if ${{v_i}_j}$=F}." and the part (ii) start after this? I am not sure how that has "proved it" rather than just said it is true.
Thanks
I wonder why you'd remind students how the standard bookwork proof is done rather than just ask them to demonstrate expressive completeness?
But, as the question is set, you could write "Let $\psi_i={{q_i}_1}\land {{q_i}_2}\land \ldots \land{{q_i}_n}$; that gives us a wff of the kind specified in (i), so it remains to prove (ii)." and then on you go ... That way you hook up your answer to the parts of the question.
But do note that the question assumes that $f$ takes the value $T$ on at least one set of arguments. So you of course shouldn't mention the case where $f$ always takes the value $F$, or that would reveal that you are just dumping the bookwork without your brain in gear!