Hello everyone. In this video, we're going to talk about the Fall 2000 exam question 2.
It's a two-part question, part a is the following:
let P and Q be statements, define the statement
P circle Q by the following truth table.
So what does P circle Q mean?
We're going to define it by using this truth table. P, Q, and P circle Q,
and it's going to be defined as…if P and Q are both true, then P circle Q is false,
and otherwise P circle Q is true, okay?
This is the definition of P circle Q, that is what this question is saying.
So it's just like we defined “and” and “or” and
“implies” and “if and only if” all of those things.
We use a truth table to define them.
So question 1 is show that P circle Q is equivalent to the statement “not” P “and” Q.
So the way this question is set up, it's clearly set up to try to be solved using a truth table,
so I'm going to solve part a with a truth table.
So creating a truth table yields the following:
so P, Q, and P circle Q, that's just the same as above.
P “and” Q, we're going to take the P and Q values, true “and” true becomes true,
and true “and” false is false, false “and” true is false, false “and” false is false.
And then the last step is to negate that. So take the true false false false
column and negate it. You're going to get false true true true.
That's the same as the third column. So since the third and the fifth columns are the same,
the two headings so P circle Q and “not” P “and” Q, are logically equivalent
and we're done. That's what we wanted to show, okay?
That's part a.
So part b: is P “and” Q equivalent to P circle Q circle Q circle P?
Now the most natural way to solve this one, again, is to use a truth table, but
I get bored of truth tables very quickly, so let's try to do this a different way.
So this is part b of a problem, so I'm going to use part a that
P circle Q is the same as “not” P “and” Q,
and I'm going to rearrange this and hope that this is equivalent to P “and” Q,
or at least if it's equivalent to something that's clearly not equivalent to P “and” Q.
Either way is fine. So I'm going to use a sequence of logical
equivalences to reduce this,
and so what are we going to get? Well we have P circle Q circle Q circle P,
okay, so I'm going to take P circle Q and Q circle P and I'm going to simplify them by using part a.
So part a says that P circle Q is the same as “not” P “and” Q.
So plug that in. Q circle P is
just flip the roles of P and Q in this, so it's going to be “not” Q “and” P,
so “not” Q “and” P and “not” P “and” Q.
That's by part a, now I'm going to use the DeMorgan's Laws
and distribute the negation in there,
and that's right.
So now we have “not” P “or” “not” Q circle “not” Q “or” “not” P.
That's by DeMorgan's Laws, maybe I should write that down.
So let's say,
There we go, by DeMorgan’s Laws, okay?
So now I have the simplified version, now
again I have the circle operators, so what does that say? Well
this is now my P, this big long expression in the front,
and this is now my Q, my long expression in the back, and I'm going to plug that into part a again.
So it's going to be “not” the first expression “and” the second expression.
So that's again just by part a, it looks complicated but it really is just part a.
Just with a couple of more terms.
Now the next part of this it's going to be DeMorgan's Law one more time.
So DeMorgan's law says okay let me…
let me bring in the negation into everything. So
“not” the first term, so those first brackets are right there,
change the “and” to an “or” and then go “not” the second term, okay,
and then one more time I’m going to use DeMorgan's Laws.
So I used a lot of DeMorgan's Laws to get out of this, which is fine.
So DeMorgan's Law again, bring the negation in, “not” “not” P is P,
“not” over “or” is “and” and “not” “not” Q is Q
“or” “not” “not” Q is Q “not” over “or” is “and”, “not” “not” P is P.
So now I have P “and” Q “or” Q “and” P.
So let me rearrange that to P “and” Q “or” P “and” Q.
Well I'm A “or” A, then that's just A, right? So
if I make A equal to P “and” Q, well it's the same thing,
so the "or" doesn't matter so it's logically equivalent to P “and” Q.
So the question is P “and” Q equivalent to this, the answer is yes.
The logical equivalences show this.
Again you can use a
table to do this, that is perfectly fine.
It's tedious, again, but it can be done.
It's probably simpler than this, but I want to give you a little bit of variety
since this is supposed to be a final exam review, so
you should have a little bit of practice with logical equivalences, and
you should have a little bit of practice with the table, okay?
So that’s fantastic stuff. Hopefully you enjoyed this video and good luck.