Exercises

Exercises Chapter 1

\label{baitap}

Exercise 1

Construct a truth table for each of these compound propositions

a)

(p \(\wedge\) q) \(\rightarrow\) \(\neg\)q

p q \(\neg\)q p\(\wedge\)q (p\(\wedge\)q) \(\rightarrow\) \(\neg\)q
T T F T F
T F T F T
F T F F T
F F T F T
b)

(p\(\vee\)r) \(\rightarrow\) (r\(\vee\neg\)p)

p r \(\neg\)p p\(\vee\)r r\(\vee\neg\)p (p\(\vee\)r) \(\rightarrow\) (r\(\vee\neg\)p)
T T F T T T
T F F T F F
F T T T T T
F F T F T T
c)

(p\(\rightarrow\)q) \(\vee\) (q\(\rightarrow\)p)

p q p\(\rightarrow\)q q\(\rightarrow\)p (p\(\rightarrow\)q)\(\vee\)(q\(\rightarrow\)p)
T T T T T
T F F T T
F T T F T
F F T T T
d)

(p\(\vee\neg\)q) \(\wedge\) (\(\neg\)p\(\vee\)q)

p q \(\neg\)p \(\neg\)q p\(\vee\neg\)q \(\neg\)p\(\vee\)q (p\(\vee\neg\)q) \(\wedge\) (\(\neg\)p\(\vee\)q)
T T F F T T T
T F F T T F F
F T T F F T F
F F T T T T T
e)

(p\(\rightarrow\neg\)q) \(\vee\) (q\(\rightarrow\neg\)p)

p q \(\neg\)p \(\neg\)q p\(\rightarrow\neg\)q q\(\rightarrow\neg\)p (p\(\rightarrow\neg\)q) \(\vee\) (q\(\rightarrow\neg\)p)
T T F F F F F
T F F T T T T
F T T F T F T
F F T T T T T
f)

\(\neg\)(\(\neg\)p\(\wedge\neg\)q)

p q \(\neg\)p \(\neg\)q \(\neg\)p\(\wedge\neg\)q \(\neg\)(\(\neg\)p\(\wedge\neg\)q)
T T F F F T
T F F T F T
F T T F F T
F F T T T F
g)

(p\(\vee\)q) \(\rightarrow\) (p\(\oplus\)q)

p q p\(\vee\)q p\(\oplus\)q (p\(\vee\)q) \(\rightarrow\) (p\(\oplus\)q)
T T T F F
T F T T T
F T T T T
F F F F T
h)

(p\(\wedge\)q) \(\vee\) (r\(\oplus\)q)

p q r p\(\wedge\)q r\(\oplus\)q (p\(\wedge\)q) \(\vee\) (r\(\oplus\)q)
T T T T F F
T T F T T T
T F T F T T
T F F F F T
F T T F F T
F T F F T T
F F T F T T
F F F F F T

Exercise 5

Let p, q and r be the propositions
p : You have the flu.
q : You miss the final examination.
r : You pass the course.
Express each of these propositions as an English sentence.

a)

p \(\rightarrow\) q
You will miss the final examination if you have the flu.

b)

\(\neg\)q \(\leftrightarrow\) r
If you do not miss the final examination then you will pass the course, and conversely.

c)

q \(\rightarrow\) \(\neg\)r
You will not pass the course if you miss the final examination.

d)

p \(\vee\) q \(\vee\) r
You have the flu or you miss the final examination or you pass the course.

e)

(p \(\rightarrow\) \(\neg\)r) \(\vee\) (q \(\rightarrow\) \(\neg\)r)
You will not pass the course if you have the flu or you miss the final examination.

f)

(p \(\wedge\) q) \(\vee\) (\(\neg\)q \(\wedge\) r)
You have the flu and you miss the final examination or you do not miss the final examination and you pass the course.

Exercise 9

Show that these compound propositionals are logically equivalent.

a)

\(\neg\)(p \(\leftrightarrow\) q) and \(\neg\)p \(\leftrightarrow\) q

p q \(\neg\)p p\(\leftrightarrow\)q \(\neg\)(p\(\leftrightarrow\)q) \(\neg\)p\(\leftrightarrow\)q
T T F T F F
T F F F T T
F T T F T T
F F T T F F
b)

(p \(\rightarrow\) q) \(\wedge\) (p \(\rightarrow\) r) and p \(\rightarrow\) (q \(\wedge\) r)

p q r p\(\rightarrow\)q p\(\rightarrow\)r (p\(\rightarrow\)q)\(\wedge\)(p\(\rightarrow\)r) q\(\wedge\)r p\(\rightarrow\)(q\(\wedge\)r)
T T T T T T T T
T T F T F F F F
T F T F T F F F
T F F F F F F F
F F T T T T F T
F T F T T T F T
F T T T T T T T
F F F T T T F T
c)

(p \(\rightarrow\) r) \(\wedge\) (q \(\rightarrow\) r) and (p \(\vee\) q) \(\rightarrow\) r

p q r p\(\rightarrow\)r q\(\rightarrow\)r (p\(\rightarrow\)r)\(\wedge\)(q\(\rightarrow\)r) p\(\vee\)q (p\(\vee\)q)\(\rightarrow\)r
T T T T T T T T
T T F F F F T F
T F T T T T T T
T F F F T F T F
F F T T T T F T
F T F T F F T F
F T T T T T T T
F F F T T T F T
d)

(p \(\rightarrow\) q) \(\vee\) (p \(\rightarrow\) r) and p \(\rightarrow\) (q \(\vee\) r)

p q r p\(\rightarrow\)q p\(\rightarrow\)r (p\(\rightarrow\)q)\(\vee\)(p\(\rightarrow\)r) q\(\vee\)r p\(\rightarrow\)(q\(\vee\)r)
T T T T T T T T
T T F T F T T T
T F T F T T T T
T F F F F F F F
F F T T T T T T
F T F T T T T T
F T T T T T T T
F F F T T T F T
e)

\(\neg\)p \(\rightarrow\) (q \(\rightarrow\) r) and q \(\rightarrow\) (p \(\vee\) r)

p q r \(\neg\)p q\(\rightarrow\)r \(\neg\)p\(\rightarrow\)(q\(\rightarrow\)r) p\(\vee\)r q\(\rightarrow\)(p\(\vee\)r)
T T T F T T T T
T T F F F T T T
T F T F T T T T
T F F F T T T T
F F T T T T T T
F T F T F F F F
F T T T T T T T
F F F T T T F T
f)

p \(\leftrightarrow\) q and (p \(\rightarrow\) q) \(\wedge\) (q \(\rightarrow\) p)

p q p\(\leftrightarrow\)q p\(\rightarrow\)q q\(\rightarrow\)p (p\(\rightarrow\)q)\(\wedge\)(q\(\rightarrow\)p)
T T T T T T
T F F F T F
F T F T F F
F F T T T T

Exercise 13

You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of g: “You can graduate," m: “You owe money to the university," r: “You have completed the requirements of your major," and b: “You have an overdue library book."

g \(\rightarrow\) (r \(\wedge\) \(\neg\)(m \(\wedge\) b))

Exercises Chapter 2

Exercise 5

Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English.

a)

\(\exists\)xP(x)
Some students spend more than five hours every weekday in class.

b)

\(\forall\)xP(x)
All students spend more than five hours every weekday in class.

c)

\(\exists\)x\(\neg\)P(x)
Some students do not spend more than five hours every weekday in class

d)

\(\forall\)x\(\neg\)P(x)
All students do not spend more than five hours every weekday in class.

Exercise 9

Let L(x, y) be the statement “x loves y," where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statements.

a)

Everybody loves Jerry.
\(\forall\)xL(x,Jerry)

b)

Everybody loves somebody.
\(\forall\)x\(\exists\)yL(x,y)

c)

There is somebody whom everybody loves.
\(\exists\)y\(\forall\)xL(x,y)

d)

There is somebody whom Lydia does not love.
\(\exists\)y\(\neg\)L(Lydia,y)

e)

There is somebody whom no one loves.
\(\exists\)y\(\forall\)xL(x,y)

f)

There is exactly one person whom everybody loves.
\(\exists\)y(\(\forall\)xL(x,y) \(\wedge\) \(\forall\)z(\(\forall\)wL(w,z)) \(\rightarrow\) z \(\equiv\) y)

Exercise 13

What rule of inference is used in each of these arguments?

a)

Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major.

p
\(\therefore\) p \(\vee\) q

b)

Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major.

p \(\wedge\) q
\(\therefore\) p

c)

If it is rainy, then the pool will be closed. It is rainy. Therefor, the pool is closed.

p
p \(\rightarrow\) q
\(\therefore\) q

d)

If it snows today, then university will close. The university is not closed today. Therefore, it did not snow today.

\(\neg\)