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:
Question Part $a)$: Let $P$ and $Q$ be statements. Define the statement $P\circ Q$ by the following truth table:
| $P$ | $Q$ | $P\circ Q$ |
|---|---|---|
| $T$ | $T$ | $F$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
Show that $p\circ Q$ is equivalent to the statement $\neg(P\land Q)$.
This is the definition of $P\circ Q$, that is what this question is saying. So it's just like we defined $\land$ and $\lor$ and $\Rightarrow$ and $\Leftrightarrow$ all of those things. We use a truth table to define them.
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:
| $P$ | $Q$ | $P\circ Q$ | $P\land Q$ | $\neg(P\land Q)$ |
|---|---|---|---|---|
| $T$ | $T$ | $F$ | $T$ | $F$ |
| $T$ | $F$ | $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $T$ |
| $F$ | $F$ | $T$ | $F$ | $T$ |
So since the third and the fifth columns are the same, the two headings so $P\circ Q$ and $\neg(P\land Q)$, are logically equivalent and we're done. That's what we wanted to show, okay? That's part $a)$.
Question Part $b)$: Is $P\land Q$ equivalent to $(P\circ Q)\circ(Q\circ 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\circ Q\equiv \neg(P\land Q)$, and I'm going to rearrange this and hope that this is equivalent to $P\land Q$. So I'm going to use a sequence of logical equivalences to reduce this, and so what are we going to get?
$$\begin{align*} (P\circ Q)\circ(Q\circ P)&\equiv (\neg(P\land Q))\circ(\neg(Q\land P))&&\text{By Part }(a) \end{align*}$$So I just simplified $P\circ Q$ and $Q\circ P$ using part $a)$.
Now I'm going to use DeMorgan's Laws and distribute the negation in there.
$$\begin{align*} (P\circ Q)\circ(Q\circ P)&\equiv (\neg(P\land Q))\circ(\neg(Q\land P))&&\text{By Part }(a)\\ &\equiv(\neg P\lor\neg Q)\circ(\neg Q\lor\neg P)&&\text{By DeMorgan's Laws} \end{align*}$$So now I have the simplified version, now again I have the $\circ$ operators, so what does that say? Well this is now my $P$, $(\neg P\lor\neg Q)$, and this is now my $Q$, $(\neg Q\lor\neg P)$, and I'm going to plug that into part $a)$ again.
$$\begin{align*} (P\circ Q)\circ(Q\circ P)&\equiv (\neg(P\land Q))\circ(\neg(Q\land P))&&\text{By part }(a)\\ &\equiv(\neg P\lor\neg Q)\circ(\neg Q\lor\neg P)&&\text{By DeMorgan's Laws}\\ &\equiv\neg((\neg P\lor\neg Q)\land(\neg Q\lor\neg P))&&\text{By part }(a) \end{align*}$$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.
$$\begin{align*} (P\circ Q)\circ(Q\circ P)&\equiv (\neg(P\land Q))\circ(\neg(Q\land P))&&\text{By part }(a)\\ &\equiv(\neg P\lor\neg Q)\circ(\neg Q\lor\neg P)&&\text{By DeMorgan's Laws}\\ &\equiv\neg((\neg P\lor\neg Q)\land(\neg Q\lor\neg P))&&\text{By part }(a)\\ &\equiv\neg(\neg P\lor\neg Q)\lor\neg(\neg Q\lor \neg P)&&\text{By DeMorgan's Laws}\\ &\equiv(P\land Q)\lor(Q\land P)&&\text{By DeMorgan's Laws}\\ &\equiv(P\land Q)\lor(P\land Q) \end{align*}$$Well if I have $A\lor A$, then that's just $A$, right? So if I make $A=P\land Q$, well it's the same thing, so the $\lor$ doesn't matter.
$$\begin{align*} (P\circ Q)\circ(Q\circ P)&\equiv (\neg(P\land Q))\circ(\neg(Q\land P))&&\text{By part }(a)\\ &\equiv(\neg P\lor\neg Q)\circ(\neg Q\lor\neg P)&&\text{By DeMorgan's Laws}\\ &\equiv\neg((\neg P\lor\neg Q)\land(\neg Q\lor\neg P))&&\text{By part }(a)\\ &\equiv\neg(\neg P\lor\neg Q)\lor\neg(\neg Q\lor \neg P)&&\text{By DeMorgan's Laws}\\ &\equiv(P\land Q)\lor(Q\land P)&&\text{By Demorgan's Laws}\\ &\equiv(P\land Q)\lor(P\land Q)\\ &\equiv P\land Q \end{align*}$$So the question is $P\land Q\equiv (P\circ Q)\circ(Q\circ P)$, 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 enjoy this video and good luck.