# expressing inclusive OR using exclusive OR. [closed]

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?

• If you have negation and conjunction, you don't need XOR at all! Negation and conjunction are a complete set of connectives - they can be used to express every connective. Jul 23, 2015 at 11:59
• @CarlMummert I know, but assuming we have defined disjunction as the exclusive OR, how can we express the inclusive OR using the new defined disjunction? Jul 23, 2015 at 12:02
• It is not clear what you are asking. The question states you have conjunction and negation. Just use those and ignore the XOR entirely. Jul 23, 2015 at 12:05
• @CarlMummert you can take a look at page 5 of Hamilton's logic book where XOR is expressed using OR, while expressing OR using XOR has been left as an exercise. Jul 23, 2015 at 12:17
• @CarlMummert Check out the answer below, it clarifies the point I was trying to reach Jul 23, 2015 at 12:24

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}]$$

• Thank you, I checked the truth table and it was correct. Jul 23, 2015 at 12:22

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).
• Your answer is really a complete and detailed one. Thank you Jul 23, 2015 at 12:26