Making a XOR gate using only AND and OR

Discussion in 'General Electronics Chat' started by Dispac, Dec 18, 2015.

  1. Dispac

    Thread Starter New Member

    Dec 18, 2015
    10
    1
    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
     
  2. Papabravo

    Expert

    Feb 24, 2006
    10,136
    1,786
    I don't see how it is possible. Didn't you learn about functional completeness?
    To be functionally complete AND and OR need NOT.
     
  3. Dispac

    Thread Starter New Member

    Dec 18, 2015
    10
    1
    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
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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?
     
  5. Dispac

    Thread Starter New Member

    Dec 18, 2015
    10
    1
    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.
     
  6. ian field

    Distinguished Member

    Oct 27, 2012
    4,413
    782
    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.
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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?
     
  8. Hypatia's Protege

    Distinguished Member

    Mar 1, 2015
    2,780
    1,220
    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: Dec 18, 2015
  9. Papabravo

    Expert

    Feb 24, 2006
    10,136
    1,786
    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
     
  10. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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.
     
  11. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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 (Text):
    1.  
    2. A|B|A->B
    3. 0|0|  1
    4. 0|1|  1
    5. 1|0|  0
    6. 1|1|  1
    7.  
    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.
     
  12. Papabravo

    Expert

    Feb 24, 2006
    10,136
    1,786
    Kind of ironic that an article on completeness is itself incomplete. Are you going to edit the article to improve it?
     
  13. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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.
     
  14. Dispac

    Thread Starter New Member

    Dec 18, 2015
    10
    1
    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.
     
  15. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    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.
     
  16. Papabravo

    Expert

    Feb 24, 2006
    10,136
    1,786
    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
     
  17. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    :D :D :D
     
    Papabravo likes this.
  18. Dispac

    Thread Starter New Member

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

    Expert

    Feb 24, 2006
    10,136
    1,786
    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.
     
  20. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    I'll guarantee you that's not the case!

    Which is good, since using PM would be a security violation in its own right, plus I no longer hold an active clearance. :D
     
Loading...