# Propositional formulas, truth assignments proof

Exhibit a propositional formula $\phi$ using only the logical connectives $\neg$ and $\to$ and using all three propositional symbols $A_1,A_2,A_3$ such that for any $\nu$, $\bar{\nu}(\phi)= T \iff \nu (A_1) = T$ and $\nu(A_2) = T$.

• What is ν¯(ϕ)=T? Why is that overbar there? – Doug Spoonwood Oct 15 '14 at 21:08
• The bar is for $\phi$, while $\nu$ is just for all truth assignments to the propositional symbols. – Kevin Carroll Oct 15 '14 at 22:32

We have to use as $\phi$ the formula :

$(A_1 \land A_2) \land (A_3 \lor \lnot A_3)$

that is equivalent to : $(A_1 \land A_2) \land \top \equiv (A_1 \land A_2)$

Condiser the "easy" part : $(A_3 \lor \lnot A_3)$; this is equivalent to : $A_3 \rightarrow A_3$.

Now for : $(A_1 \land A_2)$ that is equivalent to : $\lnot (A_1 \rightarrow \lnot A_2)$.

Joining the two subformulae we have :

$\lnot (A_1 \rightarrow \lnot A_2) \land (A_3 \rightarrow A_3)$.

Applying again the last "transformation", we can get rid of the last $\land$ to obtain the requested expression for $\phi$ :

$\lnot [(A_3 \rightarrow A_3) \rightarrow (A_1 \rightarrow \lnot A_2)]$.