MODULE
ONE
PROBLEM
SET
1
Directions:
Type
your
solutions
into
this
document
and
be
sure
to
show
all
steps
for
arriving
at
your
solution.
Just
giving
a
final
number
may
not
receive
full
credit.
P
ROBLEM
1
In
the
following
question,
the
domain
of
discourse
is
a
set
of
male
patients
in
a
clinical
study.
Define
the
following
predicates:
•
P (x) : x was given the placebo
•
D(x)
:
x
was
given
the
medication
•
M
(x)
:
x
had
migraines
Translate
each
of
the
following
statements
into
a
logical
expression.
Then
negate
the
expression
by
adding
a
negation
operation
to
the
beginning
of
the
expression.
Apply
De
Morgan’s
law
until
each
negation
operation
applies
directly
to
a
predicate
and
then
translate
the
logical
expression
back
into
English.
Sample
question:
Some
patient
was
given
the
placebo
and
the
medication.
•
∃
x
(P
(x)
∧
D(x))
•
Negation:
¬∃
x
(P
(x)
∧
D(x))
•
Applying
De
Morgan’s
law:
A
x
(
¬
P
(x)
∨
¬
D(x))
•
English:
Every
patient
was
either
not
given
the
placebo
or
not
given
the
medication
(or
both).
(a)
Every
patient
was
given
the
medication
or
the
placebo
or
both.
A
x
(D(x)
∨
P
(x))
Negation:
¬A
x
(D(x)
∨
P
(x))
Applying
De
Morgan’s
law:
∃
x(
¬
D(x)
∧
¬
P
(x))
English:
There
is
a
patient
who
was
not
given
the
medication
and
not
giventhe
placebo.
(b)
Every patient who took the placebo had migraines. (Hint: you will
need to
apply
the
conditional
identity,
p
→
q
≡
¬
p
∨
q.)
A
x
(P
(x)
−→
M
(x))
Negation:
¬A
x
(P
(x)
−→
M
(x))
Applying
Conditional
identity:
(P
(x)
Applying
Double
Negation;
¬¬
P
(x)
≡
Applying
De
Morgan’s
law:
∃
x
(P
(x)
−→
M
(x))
P
(x)
∧ ¬M (x))
≡
(
¬
P
(x)
∨
¬
M
(x))
English:
Some
patient
took
the
placebo
and
did
not
have
migraines.
(c)
There
is
a
patient
who
had
migraines
and
was
given
the
placebo.
∃
x
(M
(x)
∧
P
(x))
Negation:
¬∃
x
(M
(x)
∧
P
(x))
Applying
De
Morgan’s
law:
A
x
(
¬
M
(x)
∨
¬
P
(x))
English:
Every
patient
did
not
have
migraines
or
did
not
take
the
placebo.
P
ROBLEM
2
Use
De
Morgan’s
law
for
quantified
statements
and
the
laws
of
propositionallogic
to
show
the
following
equivalences:
(a)
¬A
x
(P
(x)
∧
¬
Q(x))
≡
∃
x
(
¬
P
(x)
∨
Q(x))
¬A
x
(P
(x)
∧
¬
Q(x))
Applying
De
Morgan’s
Law:
∃
x
(
¬
(P
(x)
∨
¬¬
Q(x))
Applying
Double
Negation:
∃
x
(
¬
P
(x)
∨
Q(x))
Therefore ∃x (¬P (x) ∨ Q(x)) ≡ ∃x (¬P (x) ∨ Q(x))
(b)
¬A
x
(
¬
P
(x)
→
Q(x))
≡
∃
x
(
¬
P
(x)
∧
¬
Q(x))
¬A
x
(
¬
P
(x)
−→
Q(x))
Applying
Conditional
identity:
(
¬¬
P
(x)
∨
Q(x))
Applying
Double
Negation:
e
(P
(x)
∨
e
Q(x))
Applying De Morgan’s Law: ∃x (¬P (x) ∨ ¬Q(x))
Therefore ∃x (¬P (x) ∨ ¬Q(x)) ≡ ∃x (¬P (x) ∨ ¬Q(x))
(c)
¬∃
x
¬
P
(x)
∨
(Q(x)
∧
¬
R(x))
≡
A
x
P
(x)
∧
(
¬
Q(x)
∨
R(x))
¬∃x (¬P (x) ∨ (Q(x) ∧ ¬R(x)))
Applying
De
Morgan’s
Law:
A
x
(P
(x)
∧
¬
(Q(x)
∧
¬
R(x)))
A
x
(P
(x)
∧
(
¬
Q(x)
∨
¬¬
R(x)))
Applying
Double
Negation:
A
x
(P
(x)
∧
(
¬
Q(x)
∨
R(x)))
Therefore
A
x
(P
(x)
∧
(
¬
Q(x)
∨
R(x)))
≡
A
x
(P
(x)
∧
(
¬
Q(x)
∨
R(x)))
P
ROBLEM
3
The
domain
of
discourse
for
this
problem
is
a
group
of
three
people
who
are
working
on
a
project.
To
make
notation
easier,
the
people
are
numbered
1,
2,
3.
The
predicate
M
(x,
y)
indicates
whether
x
has
sent
an
email
to
y,
so
M
(2,
3)
is
read
“Person
2
has
sent
an
email
to
person
3.”
The
table
below
shows
the
value
of
the
predicate
M
(x,
y)
for
each
(x,
e
y)
pair.
The
truth
e
value
in
row
x
e
and
columny
gives
the
truth
value
for
M(x,
y).
M
1
2
3
1
T
T
T
2
T
F
T
3
T
T
F
Determine
if
the
quantified
statement
is
true
or
false.
Justify
your
an-
swer.
(a)
Ax Ay (x
y)
→
M
(x,
y))
False: This is because according to the first row of the truth table,
Person1sent an email to everyone including themselves.
(b)
Ax ∃y ¬M (x, y)
False:
Everyone
received
an
email
from
someone
according
to
the
truthtable.
(c)
∃x Ay M (x, y)
True: Someone sent an email to every one. Person1 sent an email to
every-one including themselves.
P
ROBLEM
4
Translate
each
of
the
following
English
statements
into
logical
expressions.
Thedomain
of
discourse
is
the
set
of
all
real
numbers.
(a)
The
reciprocal
of
every
positive
number
less
than
one
is
greater
than
one.
A
x
((x
>
0)
∧
((x
<
1)
∧
(1/x
>
1)))
(b)
There
is
no
smallest
number.
A
x
(x
>
−
infinity)
(c)
Every
number
other
than
0
has
a
multiplicative
inverse.
A
x
(x!
=
0
∧
1/x)
P
ROBLEM
5
The
sets
A,
B,
and
C
are
defined
as
follows:
A
=
tall,
grande,
venti
B
=
foam,
no
−
foam
C
=
non
−
fat,
whole
Use
the
definitions
for
A,
B,
and
C
to
answer
the
questions.
Express
the
elementsusing
n-tuple
notation,
not
string
notation.
(a)
Write
an
element
from
the
set
A
×
B
×
C.(tall,
no-foam,
whole)
(b)
Write
an
element
from
the
set
B
×
A
×
C.(foam,
venti,
non-fat)
(c)
Write
the
set
B
×
C
using
roster
notation.
B
×
C
=
(foam,
non-fat),
(foam,
whole),
(no-foam,
non-fat),
(no-
foam,whole)
