0

How can I prove that it is impossible to express a disjunction $A \lor B$ just using the connectives for negation ($\neg$) and equivalence ($\leftrightarrow$)?

Mark Kamsma
  • 12,935
BlueMan
  • 1
  • 2
    Do you mean that it is impossible to express a disjunction $A \lor B$ just using the connectives for negation ($\neg$) and equivalence ($\leftrightarrow$)? Also, you should indicate what you have tried and where you are stuck. This is not a site to just do your homework for you, and if you indicate what you have tried you may receive more tailored answers for your problem. – Mark Kamsma Jun 13 '19 at 12:55
  • Yes, I mean that. I have trying to proof that for hours. I think that I have to use induction because formulas with negation (¬) and equivalence (↔) will be more and more complex. – BlueMan Jun 13 '19 at 13:00
  • 1
    https://math.stackexchange.com/questions/2340622/prove-a-set-is-not-a-complete-set-of-connectives/2341090#2341090 – Bram28 Jun 13 '19 at 18:16

2 Answers2

1

Hint: suppose $\phi(-,-)$ made out from $\leftrightarrow$ alone. Show that $\#(\phi^{-1}(\top))$ is even by induction on the number of $\leftrightarrow$ in $\phi$. Combine this with $\lnot A\equiv (A\leftrightarrow\bot)$ in Boolean logic.

user10354138
  • 33,239
0

Start with a list of functions $L = \{f_1(A, B) = A,~ f_2(A, B) = B\}$.

Then for every pair of functions in the list $f_k, f_j$ (not necessarily distinct) add $f_n(A, B) = f_k(A, B) \leftrightarrow f_j(A, B)$ if it is not already in the list.

Then for every single function $f_k$ add $f_n(A, B) = \lnot f_k(A, B)$ to the list if not already present.

Repeat the 2 above steps until you can't add any more functions to the list. As there are only 16 binary gates, the list will be no larger than 16 (in fact it will be much much smaller than that).

Verify that nothing in the list is a disjunction gate.

DanielV
  • 23,556