I need to prove the functional completeness of $\{\text{or},\text{ xor},\text{ xnor}\}$ with the help of $\{\text{not},\text{ or},\text{ and}\}$ (which have been already proven to be functional complete). My attempt is that I only have to show that $\{\text{or},\text{ xor}\}$ is functional complete as $\text{xnor}$ is the negation of $\text{xor}$ while $\text{xor}$ is defined as $(x \wedge ¬y) \vee (¬x \wedge y)$. My attempt is to show that I can use $\{\text{or},\text{ xor}\}$ for $\{\text{not},\text{ or},\text{ and}\}$ but I already fail showing that $¬x$ can be replaced by $\{\text{or},\text{ xor}\}$... $¬x = ¬x+¬x = ¬¬(¬x+¬x)$ at this point I have no clue how to continue any constructive ideas?
Functional completeness of $\{\text{or},\text{ xor}, \text{ xnor}\}$
2
$\begingroup$
logic
propositional-calculus
-
1how $ab$out showing you c$a$n $b$uild `not` with `{or,xor,xnor}` and `and` with `{or, xor, xnor}`? – 2012-10-24
2 Answers
3
Having "or" and "xor" alone is not enough -- since false or false = false xor false = false, there's no way for any combination of those two operations to produce "true" if all you have is "false". So you have no hope of expressing negation.
However: Note that $x\text{ xnor }x$ is always true, and therefore $x\text{ xor }(x\text{ xnor }x)$ is ...?
Now use De Morgan to build "and".
-
0Ok, I understand the argumentation. – 2012-10-24
2
A few hints:
- $a \text{ XOR } a = \text{false}$
- $a \text{ XNOR } a = \text{true}$
- $a \text{ XOR } \text{true} = \text{NOT } a$
- $a \text{ AND } b = \text{NOT }((\text{NOT } a) \text{ OR } (\text{NOT }b))$