7

According to wikipedia, the set {^, ¬} is functionally complete. But is there any 2-set functionally complete set with XOR (e.g. (¬A) ⊕ A is always true).

I'm looking for a 2-set functionally complete with xor e.g. is {&,⊕} or {¬.⊕} functionally complete?

Niklas Rosencrantz
  • 2,265
  • 2
    See wikipedia: "Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives ... " http://en.wikipedia.org/wiki/Functional_completeness – Myself Mar 17 '13 at 19:28

1 Answers1

12

$\{{\neg},{\oplus}\}$ is not complete; see this question.

$\{{\land},{\oplus}\}$ is not complete either, because if all the inputs are false, then the output is always false too.

However $\{{\to}, {\oplus}\}$ is complete, because $\{{\neg},{\to}\}$ is known to be, and $(A\to A)\oplus A$ is equivalent to $\neg A$.

Community
  • 1
hmakholm left over Monica
  • 286,031