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$.

  • $\begingroup$ What is ν¯(ϕ)=T? Why is that overbar there? $\endgroup$ – Doug Spoonwood Oct 15 '14 at 21:08
  • $\begingroup$ The bar is for $\phi$, while $\nu$ is just for all truth assignments to the propositional symbols. $\endgroup$ – 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)]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.