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

  • Thread starter Back2College
  • Start date
  • Tags
    Form Logic
In summary, the attempt to create a compound statement using only NOT and XOR that has the same truth tables as (a) p OR q and (b) p AND q is not possible because XOR is functionally complete and can be used to generate NOT, AND, and OR. Therefore, using only XOR is equivalent to using only NOT and XOR. Additionally, the properties of XOR prevent it from having an output of a single 1 or 3 1's, making it impossible to create a compound statement with the desired truth tables using only NOT and XOR.
  • #1
Back2College
5
0

Homework Statement



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

(a) p OR q

(b) p AND q

Homework 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.

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?

Thanks.
 
Physics news on Phys.org
  • #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:
  • #3
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.
 
  • #4
Thanks for your replies. I now understand why there can't be any solution.
 

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

1. What is an exclusive-OR statement?

An exclusive-OR statement, also known as XOR, is a logical operation that compares two statements and returns a true value only when one of the statements is true and the other is false. It is represented by the symbol ⊕ or !=.

2. How is an exclusive-OR statement different from an exclusive-NOR statement?

An exclusive-NOR statement, also known as XNOR, is a logical operation that compares two statements and returns a true value only when both statements are either true or false. It is represented by the symbol ≡ or =.

3. How do you use exclusive-OR statements to form AND statements?

To form an AND statement using exclusive-OR, you first create an exclusive-OR statement with the two statements you want to compare. Then, you take the negation of the exclusive-OR statement to get the equivalent AND statement. For example, if A and B are two statements, the equivalent AND statement would be ¬(A ⊕ B).

4. How do you use exclusive-OR statements to form OR statements?

To form an OR statement using exclusive-OR, you first create an exclusive-OR statement with the two statements you want to compare. Then, you take the negation of both statements and the exclusive-OR statement to get the equivalent OR statement. For example, if A and B are two statements, the equivalent OR statement would be ¬A ⊕ ¬B ⊕ ¬(A ⊕ B).

5. What is the truth table for exclusive-OR statements?

The truth table for exclusive-OR statements is as follows:
A | B | A ⊕ B
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
This means that an exclusive-OR statement will only return a true value when one of the statements is true and the other is false.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
3K
  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
  • Precalculus Mathematics Homework Help
Replies
19
Views
2K
Back
Top