Processing math: 100%

Fall 2000 Exam Question 2

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.

Solution

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.