Help with logic

[dk_psy]

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!

[vascop]

Just to avoid the possibility of any confusion between the words "and" and "or" in ordinary language and in Boolean logic, lets use "AND" for Boolean and, and "OR" for Boolean or.
So are you saying that you are trying to prove that:
(P AND Q) OR (R AND S)=(P OR R) AND (Q OR S)?

[vascop]

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?

[dk_psy]

I'm not trying to prove that they are equal (as I know this is not true), but I'm trying to show that (P AND Q) OR (R AND S) IMPLIES (P OR R) AND (Q AND S)

=S

[vascop]

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)?

[vascop]

What you can ask about the Boolean expressions
(P AND Q) OR (R AND S) and(English language "and")
(P OR R) AND (Q OR S)
is this:
Are both expressions equivalent?
Or written in another way:
Is (P AND Q) OR (R AND S)=(P OR R) AND (Q OR S)?
Answer: No

[divlong]

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

[divlong]

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.

[Old_Geezer]

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.

[dk_psy]

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

[factor-fiction]

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 ?

[vascop]

A x B is clearly a subset of A which is clearly a subset of (A union C)
C x D is clearly a subset of D which is clearly a subset of (B union D)
So (A x B) union (C x D) is subset of (A union C) x (B union D)
QED

[Old_Geezer]

Had you had a job designing digital electronic circuits, as I once had factor30, then you would have used it on a near daily basis. Wow was that job really that many years ago ? Time flies.

[factor-fiction]

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.

[divlong]

Ah, right. Well, it's already been answered. You need to work the problem backward.

(AuC)x(BuD) = (AxB)u(AxD)u(BxC)u(CxD)

(AxB)u(CxD) is clearly a subset of this.

[divlong]

I didn't notice vascop's proof, but I think it falls down in the last line.

The union of the two subsets is not necessarily a subset of the intersection of the supersets. After all, the intersection could actually be empty!

[vascop]

divlong:But then so would (AxB)u(CxD) be the empty set.

[divlong]

I agree that it's true, but I think there are a few steps missing in the proof.

In the general case:
A is a subset of C
B is a subset of D

(AuB) is not necessarily a subset of (CxD) as C and D may not intersect.

[vascop]

Yes but this isn't the general case, so my proof is OK for the reasons I stated in my last post.