Making a XOR gate using only AND and OR

Thread Starter

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.

Thank you for your time
 

Papabravo

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

Thread Starter

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,976
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?
 

Thread Starter

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.

Thank you for your time
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,976
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,228
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
21,158
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.

The answer is surprising.
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,976
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,976
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.

The answer is surprising.
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.
 

WBahn

Joined Mar 31, 2012
29,976
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.
 

Thread Starter

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,976
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
21,158
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
 

Thread Starter

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
21,158
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.
 
Top