The connectives @, $ are defined in the following truth table:

$$\begin{matrix} p &q &p@q &p$q \\ F& F& F&T \\ F& T& F&F \\ T& F& T&T \\ T& T& F&T \end{matrix}$$

The question asks if the set of connectives {@, $}  is functionally complete.

I was able to express negation with the system, but I'm failing to express $\left \{ \vee \ , \wedge \right \}$.

This gave me an indication to try to prove that {@, $} is not functionally complete.

My problem is that I'm not able to properly describe the structural induction hypothesis.

All I'm familiar with is the case that the set of connectives doesn't able to describe negation - for this I only need a single atom.

In the case of the question, it seems that I need two atoms, but again I'm not able to properly describe it. 

  • 2
    $\begingroup$ Try $(p@p)\$p$ for negation - there are other expressions. Then consider $p\$\big((q@q)\$q\big)$ $\endgroup$
    – Henry
    Commented May 26 at 17:04
  • $\begingroup$ @Henry Thank you very much !!! Is there any intuition you can give on how you came up with this p$((q@q)$q) ? $\endgroup$
    – Daniel
    Commented May 26 at 17:14
  • 1
    $\begingroup$ $p\$q$ has three Ts and one F in the truth table, so if you adjust the inputs using negation then you can use it to give $\vee$ $\endgroup$
    – Henry
    Commented May 26 at 17:45
  • 2
    $\begingroup$ $p\$ q$ is equivalent to $q\to p$. So once you have negation you can just invoke the functional completeness of $\{\to,\neg\}$. $\endgroup$ Commented May 26 at 19:54


You must log in to answer this question.

Browse other questions tagged .