1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
\newcount\indentlevel
\newcount\itno
\def\reset{\itno=1}\reset
\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
\aftergroup\afterstartlist}
\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
s\or t\or u\or v\or w\or x\or y\or z\fi}
\def\li#1\par{\medskip\item{\ifcase\indentlevel \number\itno.\or
\alph\itno)\else
(\number\itno)\fi
}%
#1\smallskip\advance\itno by 1}
\def\hline{\noalign{\hrule}}
\let\impl\rightarrow
\newskip\tableskip
\tableskip=10pt plus 10pt
\li Evaluate each of the conditional statements to true or false
{\startlist
\li If $1+2=4,$ then $9+0= -9$
With $p$ $1+2=4$ and $q$ $9+0= -9,$ this statement is $p\impl
q.$
$1+2\neq 4,$ so this conditional is vacuously true.
\li $13 > 19$ only if 13 is prime
With $p$ 13 is prime and $q$ $13 > 19,$ this statement is
$p\impl q,$ and since $p$ is true and $q$ is false, this
statement is false.
\li Horses can fly whenever horses cannot fly
With $p$ ``horses cannot fly'' and $q$ ``horses can fly,'' this
is equivalent to $p\impl q.$ Since horses cannot fly, $p$ is
true and $q$ is false, so the statement is false.
\li $3\cdot3 = 9,$ if $9+9 = 18$
With $p$ $9+9 = 18$ and $q$ $3\cdot3=9,$ this statement is
equivalent to $p\impl q,$ and since both are true, this
statement is true.
}
\li Let $p$ and $q$ be propositions, where $p$ is the statement ``It is
snowing outside,'' and $q$ is the statement ``It is June.'' Express each
of the following propositions as an English sentence.
{\startlist
\li $p\impl q.$
``If it is snowing outside, it is June.''
\li $\lnot p \land q.$
``It is not snowing outside, and it is June.''
\li $\lnot p \lor (p\land q).$
``It is not snowing outside, or it is snowing outside in June.''
}
\li Consider the statement: ``If the TAs make the homework too hard,
then the students will be sad.'' Write the converse, contrapositive, and
inverse of the statement. Don't worry about the grammar/tense, we just
want to see the correct idea.
{\startlist
\li Converse
``If the students will be sad, the TAs make the homework too hard.''
\li Contrapositive
``If the students aren't sad, the TAs didn't make the homework too
hard.''
\li Inverse
``If the TAs don't make the homework too hard, the students will be
happy.''
}
\li How many rows appear in a truth table for each of these compound
propositions?
{\startlist
\li $p\land q$
The number of rows is $2^v$ where v is the number of variables in
the expression. Therefore, this expression will have $2^2 = 4$ rows.
\li $\lnot p \impl (p\impl q)$
This still only has two variables, so it will have $2^2 = 4$ rows.
\li $(\lnot p\land q\land s)\lor(p\land\lnot q\land s)\lor(p\land
q\land\lnot s)$
This has three variables, so it will have $2^3 = 8$ rows.
}
\li Using the following propositions, translate the sentence ``You
cannot see the movie if you are not over 18 years old and you do not
have the permission of a parent'' to a compound proposition.
$m := \hbox{``You can see the movie''}$
$e := \hbox{``You are over 18 years old''}$
$p := \hbox{``You have the permission of a parent''}$
This is $(\lnot p\land\lnot e)\impl \lnot m.$
\li Construct truth tables for the following propositions. Include all
intermediate columns to receive full credit for each table.
{\startlist
\li $p\lor q\land\lnot p$
\leavevmode
\halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline
&&$p$&&&&$q$&&&&$\lnot p$&&&&$q\land\lnot p$&&&&
$p\lor q\land\lnot p$&&\cr\hline
&&T&&&&T&&&&F&&&&F&&&&T&&\cr\hline
&&T&&&&F&&&&F&&&&F&&&&T&&\cr\hline
&&F&&&&T&&&&T&&&&T&&&&T&&\cr\hline
&&F&&&&F&&&&T&&&&F&&&&F&&\cr\hline
}
\li $(p\lor\lnot q) \impl q$
\leavevmode
\halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline
&&$p$&&&&$q$&&&&$\lnot q$&&&&$p\lor\lnot q$&&&&
$(p\lor\lnot q)\impl q$&&\cr\hline
&&T&&&&T&&&&F&&&&T&&&&T&&\cr\hline
&&T&&&&F&&&&T&&&&T&&&&F&&\cr\hline
&&F&&&&T&&&&F&&&&F&&&&T&&\cr\hline
&&F&&&&F&&&&T&&&&T&&&&F&&\cr\hline
}
\li $(\lnot q\impl\lnot q) \iff (\lnot p \impl \lnot q)$
\leavevmode
\halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline
&&$p$&&&&$q$&&&&$\lnot p$&&&&$\lnot q$&&&&$\lnot q\impl\lnot q$&&&&
$\lnot p\impl\lnot q$&&&&
$(\lnot q\impl\lnot q)\iff(\lnot p\impl\lnot q)$&&\cr\hline
&&T&&&&T&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline
&&T&&&&F&&&&F&&&&T&&&&T&&&&T&&&&T&&\cr\hline
&&F&&&&T&&&&T&&&&F&&&&T&&&&F&&&&F&&\cr\hline
&&F&&&&F&&&&T&&&&T&&&&T&&&&T&&&&T&&\cr\hline
}
}
\li There is a spaceship where every passenger has exactly one role.
Each passenger can either be a Crewmate or an Imposter. A Crewmate
always tells the truth, and an Imposter always lies. For each question,
determine the role of Person A and the role of Person B, or write
``Cannot be determined'' for that person if there is not enough
information. Explain your reasoning for full credit! (You can use a
truth table or just plain English to explain.)
{\startlist
\li Person A says ``I am a Crewmate, or B is a Crewmate,'' and
Person B says ``A is a Crewmate if I am an Imposter.''
If and only if A is a crewmate, their statement is true. Similarly,
if and only if B is a crewmate, their statement is true. We will use
this principle for all of the problems.
In this problem, if both are crewmates, both statements are true (B
is not an imposter, so their statement is vacuously true, and A is a
crewmate or B is a crewmate).
However, if both are imposters, both statements are false (neither
is a crewmate and A is not a crewmate even though B is an imposter).
This means we can't figure out any information.
\li Person A says ``I am an Imposter, and Person B is a Crewmate,''
and Person B says nothing.
Both must be imposters. If A is a crewmate, their statement ``I am
an imposter'' is a lie, so they are an imposter by contradiction.
Since A is an an imposter, this statement must be a lie, so ``Person
B is a crewmate'' is false, and B is an imposter.
\li Person A says ``Both Person B and I are Imposters,'' and Person
B says ``At least one of us is a Crewmate.''
By a similar logic as b, ``I am an imposter'' would be a lie if A
were a crewmate, so A is an imposter. And since that statement is
true, ``Person B is an imposter'' must be a lie, and Person B is a
crewmate. This makes B's statement true, validating our view.
}
\li Show that $(p\impl q)\lor\lnot p \equiv p\impl q$ using logical
equivalences. Cite the laws of equivalences used to reach each step.
\leavevmode
\goodbreak
\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline
&$(p\impl q)\lor\lnot p$&Given&&\cr
&$(\lnot p\lor q)\lor\lnot p$&Conditional Identity&&\cr
&$(q\lor\lnot p)\lor\lnot p$&Commutative Law&&\cr
&$q\lor(\lnot p\lor\lnot p)$&Associative Law&&\cr
&$q\lor\lnot p$&Idempotent Law&&\cr
&$p\impl q$&Conditional Identity&&\cr
\hline
}
\li Show that $\lnot ((p\land q)\lor p)\impl \lnot p$ is a tautology
using:
{\startlist
\li a truth table (include all intermediate columns)
\halign{&\vrule\strut#&#\tabskip\tableskip&#&#\tabskip0pt\cr\hline
&&$p$&&&&$q$&&&&$p\land q$&&&&$(p\land q)\lor p$&&&&
$\lnot((p\land q)\lor p)$&&&&
$\lnot p$&&&&$\lnot ((p\land q)\lor p)\impl \lnot p$&&\cr\hline
&&T&&&&T&&&&T&&&&T&&&&F&&&&F&&&&T&&\cr\hline
&&T&&&&F&&&&F&&&&T&&&&F&&&&F&&&&T&&\cr\hline
&&F&&&&T&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline
&&F&&&&F&&&&F&&&&F&&&&T&&&&T&&&&T&&\cr\hline
}
\li logical equivalences (cite the laws of equivalence used to reach
each step)
\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline
&$\lnot ((p\land q)\lor p)\impl \lnot p$&Given&&\cr
&$\lnot p\impl \lnot p$&Absorption Law&&\cr
&$p\lor\lnot p$&Conditional Identity&&\cr
&$T$&Complement Law&&\cr
\hline
}
}
\bye
|
