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

  • Thread starter Thread starter Back2College
  • Start date Start date
  • Tags Tags
    Form Logic
AI Thread Summary
The discussion centers on the challenge of constructing compound statements equivalent to "p OR q" and "p AND q" using only NOT and XOR operations. Participants clarify that XOR inherently produces a truth table with two true and two false outputs, making it impossible to achieve the desired outputs for the OR and AND operations. It is noted that while NOT can be derived from XOR, the combination of NOT and XOR does not provide functional completeness for generating the necessary logical operations. The consensus is that no solution exists for this problem due to the limitations of XOR. Ultimately, the discussion concludes with an understanding of the constraints imposed by the XOR operation.
Back2College
Messages
5
Reaction score
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
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:
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.
 
Thanks for your replies. I now understand why there can't be any solution.
 

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Thread 'Making the denominator of a certain fraction real'

Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
View full post »

Similar threads

Cubic equation solutions form
Replies
2
Views
2K
I Modus Ponens deduction rule
Replies
12
Views
2K
Is Person A a Knight or a Knave on the Island?
Replies
7
Views
3K
Is it possible to prove (P→Q)↔[(P ∨ Q)↔Q] without using truth tables?
Replies
1
Views
2K
I Axioms of Fuzzy Logic
Replies
7
Views
1K
Set Theory Logic: Finding True Statements in a Given Domain
Replies
2
Views
2K
Is Only If Logic Misinterpreted in Mathematical Statements?
Replies
9
Views
2K
I On the meaning of logical implication within specific context/models
Replies
22
Views
3K
What Is the Correct Symbolic Form and Truth Table for ~(p|q)?
Replies
6
Views
2K
Is my proof by contradiction valid?
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top