I need to draw a circuit for XOR using only AND and OR gates (no NOT gate). Can someone help me understand the logic or a circuit diagram?
XOR is exclusively true, so either A or B must be true, both cannot be true
| A | B | XOR |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
I cannot think of a way to do this without using not. If allowed to use not then (A && !B) || (!A && B)
they are probably allowed to use NAND and NOR as well, but just dont realize it.
You can't. You can build everything with nand or nor, but there's no way to make a 'not' with just 'and' and 'or' which makes something's impossible. There's no combination of 'and' and 'or' gates that take in TT and give you F or FF and give you T because both 'and' and 'or' give T for TT and F for FF
Write out the truth table for XOR(a,b). There are a number of ways to construct an XOR out of other gates, but the easiest way is to simply take your inputs, use inverters where needed to get complementary signals, use AND gates with the appropriate signals to generate a logic 1 for each of the appropriate combinations of inputs that give you a 1 in the XOR truth table, and then OR all of those AND gate outputs together.
If you only have AND and OR though you can't generate the inverted versions of a and b with just ANDs and ORs. Are you allowed to assume you have access to !a and !b? Alternately, are you sure it's not NAND and OR?
I briefly studied computer science and calculus up to linear algebra in college and none of this made sense to me lol. This is eli5 right?
Kind of tough to ELI5 when someone is asking for you to do their college level homework for them.
Truth tables are pretty fundamental in computer science. You take a logic operation like 'and' and you write all the results of all it's inputs for and or or, they takes in two values of true or false and returns true or false.
There's a few common logical operations: AND, OR, NOT, XOR.
OR is equivalent to 'and/or' in English (A, B or Both) where as XOR (exclusive-or) is logically how English speakers usually use 'or' (either A or B but not both).
NAND and NOR are funny. They are just the inverse of AND and OR.
The thing is, if you had a box of only AND you would not be able to make all the other logical operations from it. If you also had NOTs you could toss in, you could make all logic operations from just those two. OR and NOT also let you build all logic gates but neither can do it alone. NAND and NOR however, it turns out ARE logically complete and so if you can make everything only using one of those and that's what we do. Circuits are made of many many many of the same gate (usually NAND but the choice might be arbitrary).
Pretty sure you meant to reply to someone else.
Thought you would want an explanation of the problem. No worries : )
OP went to a text-based explanation subreddit and asked for a circuit diagram. Also the question appears to be impossible to solve. I don't think it's this guy's fault if his answer is a little wonky.
It is impossible. AND and OR aren't logically complete
Yes, but we may not have a complete/accurate view of the question, hence my hedging.
We almost certainly don't. But I blame the OP
If you studied computer science you should be familiar with logical operators like AND, OR, NOT, and XOR. Logic gates and logic gate diagrams are just a way of representing these operations in terms of hardware. An AND gate applies the AND operation to its inputs, and so on.
This isn't how I would explain it to a literal five year old or to someone who has no knowledge of logic gates at all, but that's not actually the point of ELI5. The OPs question implies a basic level of familiarity with these concepts, and anyone with that level of familiarity should be able to understand an explanation like mine.
(Not necessarily my explanation! I won't claim to have explained it super well, but I also don't think anyone with basic familiarity with the concept of logic gates would have much trouble with my explanation.)
This cannot be done with only AND and OR. You need a NOT or a NAND.
Or a NOR.
Is that (NOT OR) NAND or NOT (OR NAND)?
If you have a NAND or NOR you can make a Not gate. If you have a Not and an Or gate, you can make a Nor. Same applies with And and Not for a NAND.
With only NAND you can make any logic function and flip-flops. Same applies with NOR.
So, NAND OR NOR NOT NOT AND OR AND AND AND NOT NAND, right?
First of all, those circuits are abstractions, so forget about ground and voltage things, only input and output signals.
The AND gate can be seen as a demanding character. It wants ALL of it's input to be on in order to output something. If a single one of them is off, then say goodbye to having some sort of signal at the output.
The OR gate in contrast is a more forgiving character. It is happy to have at least one of it's inputs enabled in order to have an output. Even if all inputs are on, it will gladly put a signal. But if no signal is present, no signal will be out.
Now, a XOR gate is someone who likes diversity. It outputs something only when all of it's inputs are different. If both are the same, no matter what that same is, then you have no output.
The problem is that there is no way of making a XOR gate without some sort of NOT gate, as while the OR gate can work when the two inputs are different, it also works when both inputs are the same, and the only way of making that into a no signal is with NOT gates.
The question seems inherently impossible unless "AND" is a typo and it was really "NAND".