# Making a XOR gate using only AND and OR

#### Dispac

Joined Dec 18, 2015
10
Hello ,

Im trying to make a full adder using only AND and OR gates.
However i wasn't able to come up with a way to make NAND, NOR or XOR gates using only AND and OR gates.

Is it even possible to make a full adder using only AND and OR gates?
Solution efficiency isnt an issue, it can be as complex as needed.

#### Papabravo

Joined Feb 24, 2006
20,598
I don't see how it is possible. Didn't you learn about functional completeness?
To be functionally complete AND and OR need NOT.

#### Dispac

Joined Dec 18, 2015
10
Im not an engineer unfortunately, so i have knowledge gaps in this area.
However i was reading its possible to implement a NOT using multiplexors? I know what a multiplexor is but i dont understand how i would translate that schematic into a circuit

#### WBahn

Joined Mar 31, 2012
29,489
So with a multiplexer you select one of two signals depending on the value of a control signal. If that control signal is HI and the data line it selects is always LO, that is half the functionality of a NOT gate, correct? Can you see how to complete the task from there?

#### Dispac

Joined Dec 18, 2015
10
So with a multiplexer you select one of two signals depending on the value of a control signal. If that control signal is HI and the data line it selects is always LO, that is half the functionality of a NOT gate, correct? Can you see how to complete the task from there?
Right, so when the selector is LO it will connect HI to output? I think i get the theory behind it im just not sure how to implement it without ICs and stuff.

#### ian field

Joined Oct 27, 2012
6,536
Hello ,

Im trying to make a full adder using only AND and OR gates.
However i wasn't able to come up with a way to make NAND, NOR or XOR gates using only AND and OR gates.

Is it even possible to make a full adder using only AND and OR gates?
Solution efficiency isnt an issue, it can be as complex as needed.

There's 2 neat ways to do it with gates - but AFAICR: there needs to be some inverting outputs in there somewhere.

It was a doddle when I worked with logic every day - but my memory isn't getting any younger.

Pretty sure how its done is on the internet somewhere.

#### WBahn

Joined Mar 31, 2012
29,489
Right, so when the selector is LO it will connect HI to output? I think i get the theory behind it im just not sure how to implement it without ICs and stuff.
First, think about how you would do it with an IC that is a 2:1 MUX. You have three inputs. To each input you can connect one of three things: An input signal, a fixed HI, or a fixed LO. Given those bounds, how would you implement a NOT gate using a single 2:1 MUX?

#### Hypatia's Protege

Joined Mar 1, 2015
3,226
However i wasn't able to come up with a way to make NAND, NOR or XOR gates using only AND and OR gates.
Sans 'hardware tricks' inversion may not be achieved via any arrangement of 'non-inverters'. -- Conversely, an even number of cascaded 'inverters' = a 'non-inverter' (albeit, as a practical matter, with 'delay')...

You may find a study of 'Karnaugh mapping' (q.v.) both edifying and useful

Best regards
HP

PS -- Please note that, in the context of this post, the term 'inverter' signifies any logic function featuring logic inversion - and, hence, is not limited to the single input inverter (i.e. 'not gate').

Last edited:

#### Papabravo

Joined Feb 24, 2006
20,598
Boolean Algebra is not technically an engineering discipline. It has roots in pure and applied mathematics. In any case "functional completness" answers the following question:

What is the minimum number of Boolean functions required to implement all of the other Boolean functions.

Here is the wiki for it. It is good stuff to know.
https://en.wikipedia.org/wiki/Functional_completeness

#### WBahn

Joined Mar 31, 2012
29,489
Right, so when the selector is LO it will connect HI to output? I think i get the theory behind it im just not sure how to implement it without ICs and stuff.
Oh, and if you are thinking to implement a 2:1 MUX using only AND and OR gates, forget it. If you could do that, then you would be implementing a NOT gate using only AND and OR gates, which can't be done.

There are three basic Boolean operations, AND, OR, and NOT. It turns out that as long as you can implement NOT and either AND or OR, you can implement the other. But you MUST be able to implement both a NOT and at least one of AND or OR. It turns out that of the sixteen possible two-input logic functions, there are six of them that, possibly using multiple instances, you can satisfy these requirements and, as a result, implement arbitrarily complex logic using only lots of that particular gate. Of those six functions, only two are symmetric (meaning that you can flip the inputs and it has no affect on the outputs). Those two gates are NAND and NOR.

#### WBahn

Joined Mar 31, 2012
29,489
Boolean Algebra is not technically an engineering discipline. It has roots in pure and applied mathematics. In any case "functional completness" answers the following question:

What is the minimum number of Boolean functions required to implement all of the other Boolean functions.

Here is the wiki for it. It is good stuff to know.
https://en.wikipedia.org/wiki/Functional_completeness
That Wikipedia article is incomplete and, because of how it phrases things, is outright incorrect as a result.

If flat states that NAND and NOR are the only two binary Sheffer functions and, a bit later, that these are the only two binary universal gates. This simply isn't true -- there are actually four other such gates. Since they are not symmetric, they are not implemented in discrete logic gates in practice (at least not that I'm aware of), but they are still perfectly valid logic functions.

Taking just one of them, A -> B, this has the truth table:

Code:
A|B|A->B
0|0|  1
0|1|  1
1|0|  0
1|1|  1
To show that this is universal, we only show that we can implement NOT and then either AND or OR. An equivalent alternative is to show how we can implement any other universal gate.

Doing the former is quite trivial. If we tie B LO then we have a NOT gate with A as the input. If we then use this NOT gate to invert the A input of another gate, we have an OR gate.

If, having the NOT now available, we instead use it to invert the B input of another gate, we have a NAND gate.

#### Papabravo

Joined Feb 24, 2006
20,598
Kind of ironic that an article on completeness is itself incomplete. Are you going to edit the article to improve it?

#### WBahn

Joined Mar 31, 2012
29,489
Kind of ironic that an article on completeness is itself incomplete. Are you going to edit the article to improve it?
I tried editing an article (not tech related) on Wikipedia a number of years ago and my edits, which had multiple sources cited, were removed because they did didn't conform to the illusion that the person/people that started the article obviously cherished. The justification was "original research". I've never tried to contribute since.

#### Dispac

Joined Dec 18, 2015
10
Ah I see...so what i aim to do is practically impossible. Thank you for clearing that up for me. Unless there is a way to make an adder using only those two.
Also is there some project you could do with only AND and OR gates?
Any leads on where i should search?
And thank you for all the information and patience Wbahn, Hypatia and Bravo.

#### WBahn

Joined Mar 31, 2012
29,489
Forget the adder -- you need an inversion capability since the sum is zero if both of the inputs are one (talking a half adder here).

Why are you wanting/needing to restrict yourself to just AND and OR?

You might look into monotone Boolean functions.

#### Papabravo

Joined Feb 24, 2006
20,598
I fear that not allowing the NOT operation will severely handicap your efforts. I don't know if they still exist but PAL devices were popular for many years in the 70's through the 90's. Each input went through a buffer/inverter that gave you the value and its complement. Having an input and it's complement allows you to use an AND/OR architecture to implement any combinatorial function. There was an economic reason for doing this. Without it the device would have been nearly useless.

https://en.wikipedia.org/wiki/Programmable_Array_Logic

WARNING: Wikipedia articles may be incomplete or contain errors, so caveat emptor

#### WBahn

Joined Mar 31, 2012
29,489
WARNING: Wikipedia articles may be incomplete or contain errors, so caveat emptor

#### Dispac

Joined Dec 18, 2015
10
Worlds first circuit in an unintended application. Top secret stuff, i'd pm you but this site isnt making it easy.

#### Papabravo

Joined Feb 24, 2006
20,598
Worlds first circuit in an unintended application. Top secret stuff, i'd pm you but this site isnt making it easy.
No problem, I don't usually respond to PMs.
I have a truly marvelous device, that I'm documenting in the margins of one of my old textbooks. Details to follow soon.

#### WBahn

Joined Mar 31, 2012
29,489
Worlds first circuit in an unintended application.
I'll guarantee you that's not the case!

Top secret stuff, i'd pm you but this site isnt making it easy.
Which is good, since using PM would be a security violation in its own right, plus I no longer hold an active clearance.