1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logic: exclusive-OR statements to form AND/OR statements

  1. Mar 8, 2017 #1
    1. The problem statement, all variables and given/known data

    Using only NOT and XOR, construct a compound statement having the same truth table as:

    (a) p OR q

    (b) p AND q

    2. Relevant equations

    XOR is "exclusive OR." p XOR q = (p OR q) AND NOT (p AND q).

    I have been working under the assumption that I can use parentheses.

    3. The attempt at a solution

    I know the truth tables for (p OR q) and (p AND q) are TTTF and TFFF, respectively. So, either three Trues and one false or one True and three Falses.

    However, when I use only NOT and XOR I always get two Trues and two Falses. So far this has been the case no matter which combination I try or how many XORs I string together. It's always some combination of two Trues and two Falses.

    Can anyone give me a hint?

  2. jcsd
  3. Mar 8, 2017 #2
    You can use parenthesis.

    There is no solution:
    XOR can be used to generate NOT: XOR(XOR(1,0),X) = NOT(X)
    So the addition of the NOT gate is not needed.

    XOR has affine connectives. That is: XOR(X,Y) = NOT(XOR(NOT(X),Y), so the XOR will always change when X changes. Of course, the same can be said for Y.
    That's one of the attributes an operation must not have in order to be "functionally complete".
    See https://en.wikipedia.org/wiki/Sheffer_stroke#Properties

    The two operations that can be used to generate NOT, AND, and OR are NAND (the Sheffer Stroke) and NOR.

    Actually, it's all explained here: https://en.wikipedia.org/wiki/Functional_completeness.
    Last edited: Mar 8, 2017
  4. Mar 8, 2017 #3


    User Avatar
    Gold Member

    Using only NOT and XOR is exactly equivalent to "Using only XOR". This is because NOT is just an XOR with one input held high, so we can limit the analysis to just the XOR gate.

    SO ... using a gate that ALWAYS has an output with two 1's and two 0's in the truth table would there be any way to make it have a single 1 or 3 ones?

    This is the same as asking "if I always require an output of two apples, can I ever get outputs of 1 apple or 3 apples" ?

    EDIT: Ah, I see Scott beat me to it.
  5. Mar 8, 2017 #4
    Thanks for your replies. I now understand why there can't be any solution.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Logic: exclusive-OR statements to form AND/OR statements