1
00:00:00,000 --> 00:00:04,766
Hello everyone. In this video, we're going to
talk about the Fall 2000 exam question 2.

2
00:00:04,766 --> 00:00:07,266
It's a two-part question,
part a is the following:

3
00:00:07,266 --> 00:00:09,866
let P and Q be statements, define the statement

4
00:00:09,866 --> 00:00:13,100
P circle Q by the following truth table.

5
00:00:13,100 --> 00:00:15,300
So what does P circle Q mean?

6
00:00:15,300 --> 00:00:19,866
We're going to define it by using 
this truth table. P, Q, and P circle Q,

7
00:00:19,866 --> 00:00:24,766
and it's going to be defined as…if P and 
Q are both true, then P circle Q is false,

8
00:00:24,766 --> 00:00:28,000
and otherwise P circle Q is true, okay?

9
00:00:28,000 --> 00:00:31,133
This is the definition of P circle Q,
that is what this question is saying.

10
00:00:31,133 --> 00:00:33,500
So it's just like we defined “and” and “or” and

11
00:00:33,500 --> 00:00:36,300
“implies” and “if and only if” all of those things.

12
00:00:36,300 --> 00:00:39,500
We use a truth table to define them.

13
00:00:39,500 --> 00:00:44,733
So question 1 is show that P circle Q is 
equivalent to the statement “not” P “and” Q.

14
00:00:44,733 --> 00:00:48,900
So the way this question is set up, it's clearly 
set up to try to be solved using a truth table,

15
00:00:48,900 --> 00:00:51,233
so I'm going to solve part a with a truth table.

16
00:00:51,233 --> 00:00:54,700
So creating a truth table yields the following:

17
00:00:54,700 --> 00:00:58,333
so P, Q, and P circle Q, that's
just the same as above.

18
00:00:58,333 --> 00:01:02,533
P “and” Q, we're going to take the P and 
Q values, true “and” true becomes true,

19
00:01:02,533 --> 00:01:07,466
and true “and” false is false, false “and” 
true is false, false “and” false is false.

20
00:01:07,466 --> 00:01:11,633
And then the last step is to negate
that. So take the true false false false

21
00:01:11,633 --> 00:01:14,766
column and negate it. You're 
going to get false true true true.

22
00:01:14,766 --> 00:01:18,333
That's the same as the third column. So since 
the third and the fifth columns are the same,

23
00:01:18,333 --> 00:01:23,133
the two headings so P circle Q and 
“not” P “and” Q, are logically equivalent

24
00:01:23,133 --> 00:01:26,400
and we're done. That's what 
we wanted to show, okay?

25
00:01:26,400 --> 00:01:28,200
That's part a.

26
00:01:28,200 --> 00:01:34,433
So part b: is P “and” Q equivalent 
to P circle Q circle Q circle P?

27
00:01:34,433 --> 00:01:38,300
Now the most natural way to solve this
one, again, is to use a truth table, but

28
00:01:38,300 --> 00:01:41,766
I get bored of truth tables very quickly,
so let's try to do this a different way.

29
00:01:41,766 --> 00:01:44,600
So this is part b of a problem, 
so I'm going to use part a that

30
00:01:44,600 --> 00:01:47,733
P circle Q is the same as “not” P “and” Q,

31
00:01:47,733 --> 00:01:50,800
and I'm going to rearrange this and 
hope that this is equivalent to P “and” Q,

32
00:01:50,800 --> 00:01:54,033
or at least if it's equivalent to something 
that's clearly not equivalent to P “and” Q.

33
00:01:54,033 --> 00:01:58,033
Either way is fine. So I'm going 
to use a sequence of logical

34
00:01:58,033 --> 00:02:00,633
equivalences to reduce this,

35
00:02:00,633 --> 00:02:04,200
and so what are we going to get? Well 
we have P circle Q circle Q circle P,

36
00:02:04,200 --> 00:02:09,033
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.

37
00:02:09,033 --> 00:02:13,300
So part a says that P circle Q 
is the same as “not” P “and” Q.

38
00:02:13,300 --> 00:02:17,066
So plug that in. Q circle P is

39
00:02:17,066 --> 00:02:20,966
just flip the roles of P and Q in this, 
so it's going to be “not” Q “and” P,

40
00:02:20,966 --> 00:02:24,400
so “not” Q “and” P and “not” P “and” Q.

41
00:02:24,400 --> 00:02:25,266


42
00:02:25,266 --> 00:02:28,566
That's by part a, now I'm going 
to use the DeMorgan's Laws

43
00:02:28,566 --> 00:02:31,800
and distribute the negation in there,

44
00:02:31,800 --> 00:02:33,366


45
00:02:33,366 --> 00:02:34,833
and that's right.

46
00:02:34,833 --> 00:02:38,966
So now we have “not” P “or” “not” 
Q circle “not” Q “or” “not” P.

47
00:02:38,966 --> 00:02:42,800
That's by DeMorgan's Laws, 
maybe I should write that down.

48
00:02:42,800 --> 00:02:44,933
So let's say,

49
00:02:44,933 --> 00:02:45,000


50
00:02:45,000 --> 00:02:45,533


51
00:02:45,533 --> 00:02:47,900
There we go, by DeMorgan’s Laws, okay?

52
00:02:47,900 --> 00:02:50,066


53
00:02:50,066 --> 00:02:52,033
So now I have the simplified version, now

54
00:02:52,033 --> 00:02:55,466
again I have the circle operators, 
so what does that say? Well

55
00:02:55,466 --> 00:02:58,300
this is now my P, this big long 
expression in the front,

56
00:02:58,300 --> 00:03:02,900
and this is now my Q, my long expression in the 
back, and I'm going to plug that into part a again.

57
00:03:02,900 --> 00:03:07,900
So it's going to be “not” the first expression 
“and” the second expression.

58
00:03:07,900 --> 00:03:08,800


59
00:03:08,800 --> 00:03:13,433
So that's again just by part a, it looks 
complicated but it really is just part a.

60
00:03:13,433 --> 00:03:14,500


61
00:03:14,500 --> 00:03:17,733
Just with a couple of more terms.

62
00:03:17,733 --> 00:03:21,966
Now the next part of this it's going to 
be DeMorgan's Law one more time.

63
00:03:21,966 --> 00:03:26,800
So DeMorgan's law says okay let me…

64
00:03:26,800 --> 00:03:28,666


65
00:03:28,666 --> 00:03:30,866
let me bring in the negation into everything. So

66
00:03:30,866 --> 00:03:35,033
“not” the first term, so those 
first brackets are right there,

67
00:03:35,033 --> 00:03:39,466
change the “and” to an “or” and 
then go “not” the second term, okay,

68
00:03:39,466 --> 00:03:41,233


69
00:03:41,233 --> 00:03:43,966
and then one more time I’m 
going to use DeMorgan's Laws.

70
00:03:43,966 --> 00:03:48,066
So I used a lot of DeMorgan's Laws 
to get out of this, which is fine.

71
00:03:48,066 --> 00:03:49,233


72
00:03:49,233 --> 00:03:52,433
So DeMorgan's Law again, bring 
the negation in, “not” “not” P is P,

73
00:03:52,433 --> 00:03:56,200
“not” over “or” is “and” 
and “not” “not” Q is Q

74
00:03:56,200 --> 00:04:01,333
“or” “not” “not” Q is Q “not” over
 “or” is “and”, “not” “not” P is P.

75
00:04:01,333 --> 00:04:04,800
So now I have P “and” Q “or” Q “and” P.

76
00:04:04,800 --> 00:04:08,733
So let me rearrange that to 
P “and” Q “or” P “and” Q.

77
00:04:08,733 --> 00:04:13,500
Well I'm A “or” A, then that's just A, right? So

78
00:04:13,500 --> 00:04:16,500
if I make A equal to P “and” Q, 
well it's the same thing,

79
00:04:16,500 --> 00:04:19,300
so the "or" doesn't matter so it's 
logically equivalent to P “and” Q.

80
00:04:19,300 --> 00:04:23,533
So the question is P “and” Q 
equivalent to this, the answer is yes.

81
00:04:23,533 --> 00:04:25,766
The logical equivalences show this.

82
00:04:25,766 --> 00:04:26,700


83
00:04:26,700 --> 00:04:28,933
Again you can use a 

84
00:04:28,933 --> 00:04:32,100
table to do this, that is perfectly fine.

85
00:04:32,100 --> 00:04:34,900
It's tedious, again, but it can be done.

86
00:04:34,900 --> 00:04:38,733
It's probably simpler than this, but I 
want to give you a little bit of variety

87
00:04:38,733 --> 00:04:41,066
since this is supposed to 
be a final exam review, so

88
00:04:41,066 --> 00:04:43,300
you should have a little bit of practice
with logical equivalences, and

89
00:04:43,300 --> 00:04:45,766
you should have a little bit of 
practice with the table, okay?

90
00:04:45,766 --> 00:04:46,633


91
00:04:46,633 --> 00:04:51,266
So that’s fantastic stuff. Hopefully you 
enjoyed this video and good luck.