How to write a boolean function using only XOR and NOT gates?

Discussion in 'Homework Help' started by thermistor, Mar 6, 2013.

  1. thermistor

    Thread Starter New Member

    Mar 6, 2013
    4
    0
    Can we represent the boolean function of a truth table using only XOR and NOT? And if so, how can this be done? Is there any technique or algorithm?

    Thanks
     
    Last edited: Mar 6, 2013
  2. eng.mustafasalah

    Member

    Nov 10, 2011
    41
    2
    what is that function ?
     
    thermistor likes this.
  3. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    I'd take a piece of paper and try and at first make clear: What is XOR and how does XOR work.
     
    thermistor likes this.
  4. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    Is the question asking if you can represent ANY boolean function using only XOR and NOT? Or is it asking about a SPECIFIC boolean function?
     
    thermistor likes this.
  5. thermistor

    Thread Starter New Member

    Mar 6, 2013
    4
    0
    It asks for a specific function:
    Code ( (Unknown Language)):
    1. A'B'C'+A'BC+AB'C'+AB'C
    Where X' means negation of X and + means OR
     
  6. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    That's good, because, in general, you can't code an arbitrary boolean function using only XOR (the NOT is extraneous because you CAN make a NOT out of an XOR).

    What you need to do is try to rewrite your boolean function into combinations of the form (A'B+AB') or (AB+A'B'). The former is an XOR and the latter is an XNOR, which is an XOR with any odd number of inputs/outputs inverted.

    If you are familiar with Karnaugh maps, those can help you identify the XOR/XNOR relationships.
     
    thermistor likes this.
  7. thermistor

    Thread Starter New Member

    Mar 6, 2013
    4
    0
    I have tried to find a solution. I have tried to use http://www.eetimes.com/design/programmable-logic/4015081/Logic-101--Part-3--Reed-Muller-Logic/
    in order to find a checkboard pattern in order to solve it but I have not found something. Can you help me find if this problem has solution in order not to try without purpose? I give the full truth table of the function that should be written using only NOT and EXOR gates.

    INPUTS OUTPUT
    A B C | E
    --------------------
    0 0 0 1
    0 0 1 0
    0 1 0 0
    0 1 1 1
    1 0 0 1
    1 0 1 1
    1 1 0 0
    1 1 1 0

    What I have found is that the upper half table is B XNOR C (1) and the other
    half A XOR B (2). But I can't find a way to tell if A=0 use function (1) else function (2).
     
  8. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    I could be wrong, but I don't think that function can be done using XOR gates. I don't think there is the necessary antisymmetry across the mid line.

    If it turns out that it can be done, please post the solution once you know it.
     
    thermistor likes this.
  9. thermistor

    Thread Starter New Member

    Mar 6, 2013
    4
    0
    This subject was given in the entry examination for the National School of Public Administration. So I do not have the answer. I asked some other contenstants and they told me that they could not find a solution. So I suspect it is wrong too. I was just trying to solve it in order to confirm this fact. After spending a day to solve it and considering your answer, I give up. Thanks for your help.
     
  10. MrChips

    Moderator

    Oct 2, 2009
    12,452
    3,371
    Maybe the expression was incorrectly stated and should have been:

    A'B'C' + A'BC + ABC' + AB'C
     
  11. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    I was wondering if it shouldn't have been:

    A'B'C'+A'BC+AB'C'+AB'C'

    MrChips caught a typo above. I meant:

    A'B'C'+A'BC+AB'C'+ABC

    Which would be

    A'(B'C'+BC)+A(B'C'+BC)

    A XOR (B XNOR C)
     
    Last edited: Mar 10, 2013
  12. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    National School of Public Administration?

    What kind of school is this? What is meant by "Public Administration"? Here, that term generally refers to government bureaucrats of one ilk or another. A foundation in logic, of any sort, is generally not high on their list of core competencies. But I'm guessing that it has a broader meaning where you are.
     
  13. MrChips

    Moderator

    Oct 2, 2009
    12,452
    3,371
    You made a typo. Your last two terms are the same.

    Here's my guess:

    A'B'C'+A'BC+ABC'+AB'C
     
  14. WBahn

    Moderator

    Mar 31, 2012
    17,788
    4,808
    Yep, sure did. Fixed it in the post above. Thanks!
     
Loading...