expressing inclusive OR using exclusive OR. [closed]

Question

On page 5 of Hamilton`s mathematical logic book, it's been stated that we can express A or B or both using XOR, as also possible to express negation and conjunction using XOR.

I couldn't find any suitable form. What is the form to express $A \vee B$ using XOR?

Answer 1

Here's one way to do it: $$ A \, \mathsf{OR} \, B = (A \; \mathsf{XOR} \; B)\,\mathsf{XOR}\, (A \;\mathsf{AND}\; B) $$ Or, using just negation and conjunction, we of course have $$ A \, \mathsf{OR} \, B = \mathsf{NOT}(\mathsf{NOT}(A) \; \mathsf{AND}\; \mathsf{NOT}(B)) $$ Interestingly, we can express XOR using "not" and "and" in a fairly obvious way, but we can also express "not" using "xor" with $$ \mathsf{NOT}(A) = A \;\mathsf{XOR} \; [\mathsf{true}] $$

Answer 2

One way of looking at this is that with AND and XOR you are essentially doing arithmetic modulo 2. Indeed, if $\varphi:Var\to\{0,1\}$ is a valuation of the variables in $Var$ (identifying $1$ with True and $0$ with False), for any expressions $A,B$

• $\varphi(A\ AND\ B) = \varphi(A)\cdot\varphi(B)$,
• $\varphi(A\ XOR\ B) = \varphi(A) + \varphi(B) \mod 2$, and
• $\varphi(NOT\ A) = 1 - \varphi(A) \mod 2$ ( $= 1 + \varphi(A) \mod 2$).

Then using these, you can obtain arbitrarily polynomials over $\mathbb{Z}/2$, and these can express all Boolean functions. In particular for $OR$, we want $\varphi(A\ OR\ B) = 0$ if $\varphi(A)=\varphi(B)=0$, and $1$ otherwise; this can be achieved as

• $\varphi(A\ OR\ B) = \varphi(A) + \varphi(B) + \varphi(A)\varphi(B) \mod 2 = \varphi((A\ XOR\ B)\ XOR\ (A\ AND\ B))$ (Omnomnomnom's first solution), or
• $\varphi(A\ OR\ B) = 1 - (1 - \varphi(A))(1 - \varphi(B)) \mod 2 = \varphi(NOT\ ((NOT\ A)\ AND\ (NOT\ B)))$ (Omnomnomnom's second solution).