Travel2 mins ago
Help with logic
Is anyone any good with logic and boolean algebra? I have (PandQ)or(Rand S) and I'm trying to get step-by-step to the point where this this implies (PorR)and(QorS) using Boolean algebra, but I keep getting stuck in a loop!
Answers
1 to 18 of 18
Best Answer
No best answer has yet been selected by dk_psy. Once a best answer has been selected, it will be shown here.
For more on marking an answer as the "Best Answer", please visit our FAQ.
Assume P=false,Q=true,R=true,S=false, then:
P AND Q=false, R AND S=false, so (P AND Q) OR (R AND S)=false OR false=false
Also P OR R=true, Q OR S=true, so (P OR R) AND (Q OR S)=true AND true=true
So this is a counter example, which means that generally
(P AND Q) OR (R AND S) does not equal (P OR R) AND (Q OR S)
So are you sure about your problem being posed correctly?
P AND Q=false, R AND S=false, so (P AND Q) OR (R AND S)=false OR false=false
Also P OR R=true, Q OR S=true, so (P OR R) AND (Q OR S)=true AND true=true
So this is a counter example, which means that generally
(P AND Q) OR (R AND S) does not equal (P OR R) AND (Q OR S)
So are you sure about your problem being posed correctly?
What you are saying doesn't make sense to me.
I'll assume that in your last post Q AND S at the end should be Q OR S and also that the =S at the end was a typo.
Just to take a simpler example and to make sure we understand each other:
P=false, Q=true implies that P AND Q =false and that P OR Q = true
Leaving Boolean algebra for a minute :
In algebra if we write 2x then that doesn't imply anything, but if we right 2x=4 then that implies that x=2.
Similarly 2(x-2) does not imply anything, but 2(x-2)=4 implies that x=4.
Again your Boolean expression (P AND Q) OR (R AND S) does not imply anything on its own, it's just an expression like those above in ordinary algebra.
There are identities in Boolean algebra, such as:
P OR (R AND S)=(P OR R) AND (P OR S)
So, to sum up, I'm still confused about your intentions. It certainly doesn't make sense to me to say:
Does (P AND Q) OR (R AND S) imply (P OR R) AND (Q OR S)?
I'll assume that in your last post Q AND S at the end should be Q OR S and also that the =S at the end was a typo.
Just to take a simpler example and to make sure we understand each other:
P=false, Q=true implies that P AND Q =false and that P OR Q = true
Leaving Boolean algebra for a minute :
In algebra if we write 2x then that doesn't imply anything, but if we right 2x=4 then that implies that x=2.
Similarly 2(x-2) does not imply anything, but 2(x-2)=4 implies that x=4.
Again your Boolean expression (P AND Q) OR (R AND S) does not imply anything on its own, it's just an expression like those above in ordinary algebra.
There are identities in Boolean algebra, such as:
P OR (R AND S)=(P OR R) AND (P OR S)
So, to sum up, I'm still confused about your intentions. It certainly doesn't make sense to me to say:
Does (P AND Q) OR (R AND S) imply (P OR R) AND (Q OR S)?
Unfortunately, since they are not equivalent you will not be able to do this without specifying some other initial conditions. This can easily be demonstrated by working the problem backward. If you use "+" to indicate OR and "." to indicate AND, you can use pretty normal algebra to manipulate the equation. You get...
(P+R).(Q+S) = P.Q + P.S + R.Q + R.S
Although this includes your initial values P.Q and R.S it also satisfies a couple of other conditions (P.S and R.Q) that were not initially specified. If either of those can be TRUE then then your initial equation doesn't imply the result you are looking for.
However, if you know at the start that P.S and Q.R are FALSE then since doing an OR with a known FALSE value doesn't change the result you can just add them to your initial equation and factorise it (the reverse of what I did above).
So the proof runs something like:
Result = P.Q + R.S
but P.S =FALSE and Q.R = FALSE so, since A+FALSE = A
Result = P.Q + R.S + P.S + Q.R
Result = P.(Q + S) + R.(Q + S)
Result = (P + R).(Q + S)
I hope that makes sense
(P+R).(Q+S) = P.Q + P.S + R.Q + R.S
Although this includes your initial values P.Q and R.S it also satisfies a couple of other conditions (P.S and R.Q) that were not initially specified. If either of those can be TRUE then then your initial equation doesn't imply the result you are looking for.
However, if you know at the start that P.S and Q.R are FALSE then since doing an OR with a known FALSE value doesn't change the result you can just add them to your initial equation and factorise it (the reverse of what I did above).
So the proof runs something like:
Result = P.Q + R.S
but P.S =FALSE and Q.R = FALSE so, since A+FALSE = A
Result = P.Q + R.S + P.S + Q.R
Result = P.(Q + S) + R.(Q + S)
Result = (P + R).(Q + S)
I hope that makes sense
Actually, this looks rather like the classic double-switched light problem. If that is the case then it is quite likely that P/S and Q/R are not actually independent variables.
If P/S represents a double-throw switch then if P is TRUE then S must be FALSE. Similarly with the Q/R pair. This means that P.S = FALSE and Q.R = FALSE.
Then my previous explanation works perfectly.
If P/S represents a double-throw switch then if P is TRUE then S must be FALSE. Similarly with the Q/R pair. This means that P.S = FALSE and Q.R = FALSE.
Then my previous explanation works perfectly.
I've not read all the answers but it doesn't make sense to me either.
You are correct the 2 equations are not equal, so it must be my ignorance not to know what is meant by one implying the other. (Neither = S either.) Are you sure the question is stated correctly ?
About 4 decades ago I thought I was rather good at this too. Amazing what one forgets when one doesn't use it any more.
You are correct the 2 equations are not equal, so it must be my ignorance not to know what is meant by one implying the other. (Neither = S either.) Are you sure the question is stated correctly ?
About 4 decades ago I thought I was rather good at this too. Amazing what one forgets when one doesn't use it any more.
Thanks for this - please ignore the '=S' - this is just an emoticon to say I'm confused, lol; i didn't click that it might confuse matters!
The question is about set theory; I'm trying to prove that (AxB)union(CxD) is a subset of (AunionC)x(BunionD) using Boolean algebra, I.e. prove that (x-is-in-A and y-is-in-B) or (x-is-in-C and y-is-in-D) is a subset of (x-is-in-A union C) and (y-is-in B union D).
The question is about set theory; I'm trying to prove that (AxB)union(CxD) is a subset of (AunionC)x(BunionD) using Boolean algebra, I.e. prove that (x-is-in-A and y-is-in-B) or (x-is-in-C and y-is-in-D) is a subset of (x-is-in-A union C) and (y-is-in B union D).
I remember now doing all this in maths at primary school in the late 60s but it never arose again until university and I have certainly never had to teach it since. I'm wondering why we covered it at age 9-10- I have a feeling it was called Modern Maths and was being trialled.
Could you try to depict it using Venn diagrams ?
Could you try to depict it using Venn diagrams ?
I never took to electronics- it was the one part of Physics A level I couldn't handle, but I don't recall any of this Boolean algebra in that. Anyway, I steered clear of science after that and worked in finance, general management and teaching. I can follow your well set out solution though, although for me a visual representation using Venn diagrams would be a good starting point to help clarify my thoughts.
1 to 18 of 18
