CMPS 211 Homework Assignment 03 Solution, Fall 2014
American University of Beirut · Discrete Structures · 5 pages · with solution
More CMPS 211 files
- Homework 3 with Solution · Spring 2016Homework · with solutionView
- Homework 6 with Solution · Spring 2016Homework · with solutionView
- Homework 1 with Solution · Spring 2016Homework · with solutionView
- Homework 4 with Solution · Spring 2016Homework · with solutionView
- Homework 5 with Solution · Spring 2016Homework · with solutionView
- Homework 1 · Fall 2015HomeworkView
- Homework 3 · Fall 2015HomeworkView
- Homework 1 Solution · Fall 2015Homework · with solutionView
Show the text of this homework
CMPS
211
–
Fall
2014
Assignment
3
Solution
Exercise
1:
a) All
of
the
professors
are
philosophy
professors
and
understand
logic
b) There
exist
a
professor
that
is
a
philosophy
professor
and
understand
logic
c) All
philosophy
professors
understand
logic
d) There
exist
a
philosophy
professor
that
understand
logic
Exercise
2:
a) ∃x(I(x)
∧
S(x)
∧
N(x))
b) ¬∃x(I(x)
∧
S(x)
∧
N(x))
≡
∀x(¬I(x)
∨
¬S(x)
∨
¬N(x))
c) ∀x(I(x)
∨
S(x)
∨
N(x))
d) ∃x(I(x)
∧
¬S(x)
∧
N(x))
e) ¬∃x(I(x)
∨
S(x)
∨
N(x))
≡
∀x(¬I(x)
∧
¬S(x)
∧
¬N(x))
Exercise
3:
a) P(2):
3>3
=>
False
b) P(3):
7>5
=>
True
c) P(0):
-‐5>-‐1
=>
False
d) ∃x
P(x):
True
(for
x=3
P(3)
is
true)
e) ∃x
¬P(x):
True
(for
x=0
p(0)
is
false)
f) ∀x
P(x):
False
(for
x=2
p(2)
is
false)
g) ∀x
¬P(x):
False
(for
x=3
P(3)
is
true)
Exercise
4:
a) P(-‐4)
∨
P(-‐2)
∨
P(-‐1)
∨
P(1)
∨
P(2)
∨
P(4)
b) P(-‐4)
∧
P(-‐2)
∧
P(-‐1)
∧
P(1)
∧
P(2)
∧
P(4)
c) ((-‐4≠3)
-‐-‐>
P(-‐4))
∧
((-‐2≠3)
-‐-‐>
P(-‐2))
∧
((-‐1≠3)
-‐-‐>
P(-‐1))
∧
((4≠3)
-‐-‐>
P(4))
∧
((2≠3)
-‐-‐>
P(2))
∧
((1≠3)
-‐-‐>
P(1))
d) (-‐4≥1∧P(-‐4))∨(-‐2≥1∧P(-‐2))∨(-‐1≥1∧P(-‐1))∨(4≥1∧P(4))∨(2≥1∧P(2))
∨(1≥1∧P(1))
CMPS
211
–
Fall
2014
e) (¬P(-‐4)∨¬P(-‐2)∨¬P(-‐1)∨¬P(1)∨¬P(2)∨¬P(4))∧[(-‐4<0
-‐-‐>P(-‐4)∧(-‐2<0
-‐-‐>
P(-‐2)∧(-‐1<0
-‐-‐>
P(-‐1)∧
(4<0
-‐-‐>P(4)∧(2<0
-‐-‐>
P(2)∧(1<0
-‐-‐>
P(1)]
Exercise
5:
Let
C(x)
be
x
is
in
my
classroom
The
domain
of
x
is
all
students
in
my
class
The
domain
of
y
is
all
people
a) Let
D(x)
be
x
can
drive
1. ∃x(¬D(x))
2. ∃y(C(y)
∧
¬D(y))
b) Let
N(x)
be
x
has
a
notebook
1. ∀x(N(x))
2. ∀y(C(y)
→
N(y))
c) Let
R(x)
be
x
is
repeating
this
course
1. ∃x(R(x))
2. ∃y(C(y)
∧
R(y))
d) Let
F(x)
be
x
can
solve
Fermat’s
last
theorem
1. ∀x(F(x))
2. ∀y(C(y)
→
F(y))
e) Let
W(x)
be
x
wants
to
be
rich
1. ∃x(¬W(x))
2. ∃y(C(y)
∧
¬W(y))
Exercise
6:
a) There
exist
a
CMPS
professor
that
taught
a
CMPS
course
b) There
exists
a
CMPS
professor
that
taught
all
CMPS
courses
c) All
CMPS
professors
taught
a
CMPS
course
CMPS
211
–
Fall
2014
d) There
exists
a
CMPS
course
that
has
been
taught
by
all
CMPS
professors
e) All
CMPS
courses
has
been
taught
by
CMPS
professors
f) All
CMPS
professors
taught
all
CMPS
courses
Exercise
7:
a) Tarek
Haddad
is
enrolled
in
CMPS
211
b) There
exists
a
student
in
my
school
that
is
enrolled
in
Bio
210
c) There
exists
a
class
in
my
school
that
David
Cook
is
enrolled
in
d) There
exists
a
student
that
is
enrolled
in
Math
201
and
in
CMPS
211
e) There
exists
two
different
students
such
that
if
the
first
one
is
enrolled
in
any
course,
then
the
second
one
is
enrolled
in
the
same
course
f) There
exists
two
different
students
that
are
both
enrolled
in
the
same
class
or
none
of
them
is
enrolled
in
it
Exercise
8:
a) ∀x
∀y
¬Q(x,
y)
b) ∃x
∃y
Q(x,
y)
c) ∃x
(Q(x,
AMC)
∧
Q(x,
IEEE))
d) ∀y
∃x
Q(x,
y)
e) ∃x1
∃x2
(Q(x1,
IEEE)
∧
Q(x2,
IEEE))
Exercise
9:
The
domain
of
x
is
“the
students
in
this
class”
for
[a-‐g]
a) Let
S(x,
y)
be
x
can
speak
y
The
domain
of
y
is
“languages”
∃x
S(x,
Aramaic)
b) Let
E(x,
y)
be
x
has
eaten
y
The
domain
of
y
is
“fruits”
∃x
(E(x,
pears)
∧
¬E(x,
peaches))
CMPS
211
–
Fall
2014
c) Let
I(x,
y)
be
x
plays
y
The
domain
of
y
is
“instruments”
∀x
∃y
I(x,
y)
d) Let
L(x,
y)
be
x
learned
y
The
domain
of
y
is
“programing
languages”
∀x
∃y
L(x,
y)
e) Let
G(x,
y)
be
x
can
speak
y
The
domain
of
y
is
“towns”
∃x1
∃x2
∃y
(G(x1,
y)
∧
G(x2,
y))
f) Let
B(x,
y,
z)
be
x
has
eaten
y
in
z
The
domain
of
y
is
“dishes
offered”
The
domain
of
z
is
“restaurants
on
Bliss
Street”
∃x
∀y
∃z
B(x,
y,
z)
g) Let
P(x,
y,
z)
be
x
has
played
with
y
in
game
z
The
domain
of
x
and
y
is
“Lebanese
soccer
players”
The
domain
of
z
is
the
“games
that
has
been
played”
∀x
∀y
∃z
P(x,
y,
z)
Exercise
10:
The
domain
of
x
is
“the
students
in
this
class”
a) Let
S(x,
y)
be
x
failed
y
The
domain
of
y
is
“courses”
∃x
∀y
¬S(x,
y)
Negation:
∀x
∃y
S(x,
y)
All
of
the
students
in
this
class
have
failed
a
course
b) Let
L(x,
y)
be
x
likes
y
The
domain
of
y
is
“majors”
CMPS
211
–
Fall
2014
∀x
L(x,
CMPS)
Negation:
∃x
¬L(x,
CMPS)
There
exist
some
students
in
this
class
who
hate
CMPS
c) Let
M(x,
y)
be
x
has
taken
y
The
domain
of
y
is
“mathematics
courses
offered
in
this
school”
∃x
∀y
M(x,
y)
Negation:
∀x
∃y
¬M(x,
y)
All
of
the
students
in
this
class
have
not
taken
mathematics
courses
offered
by
this
school
d) Let
B(x,
y,
z)
be
x
has
been
in
y
of
z
The
domain
of
y
is
“rooms
of
buildings”
The
domain
of
z
is
“buildings
in
Beirut”
∃x
∃y
∀z
B(x,
y,
z)
Negation:
∀x
∀y
∃z
¬B(x,
y,
z)
All
the
students
in
this
class
have
not
been
in
every
room
in
at
least
one
building
in
Beirut