Chapter one, Revision Examples.

Question 1

Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate
“x has asked y a question,” where the domain consists of
all people associated with your school.
f ) Some student has asked every faculty member a question.

Answer 1

f) This is a little ambiguous in English. If the statement is that there is a very inquisitive student, one
who has gone around and asked a question of every professor, then this is similar to part ( d), without the
negation: 3x(S(x) /\ :/y(F(y) —> A(x, y))). On the other hand, the statement might be intended as asserting
simply that for every professor, there exists some student who has asked that professor a question. In other
words, the questioner might depend on the questionee. Note how the meaning changes with the change in
order of quantifiers. Under the second interpretation the answer is \fy(F(y)—> 3x(S(x) /\ A(x, y))). The first
interpretation is probably the intended one.

Question 2

Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate
“x has asked y a question,” where the domain consists of
all people associated with your school.
g) There is a faculty member who has asked every other
faculty member a question.

Answer 2

g) This is pretty straightforward, except that we have to rule out the possibility that the askee is the same
as the asker. Our sentence needs to say that there exists a faculty member such that for every other faculty
member, the first has asked the second a question: 3x(F(x) /\ \fy((F(y) /\ y -:f x)—> A(x, y))).

Question 3

Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate
“x has asked y a question,” where the domain consists of
all people associated with your school.
d) Some student has not asked any faculty member a
question.
e) There is a faculty member who has never been asked
a question by a student.

Answer 3

d) There is a student such that for every faculty member, that student has not asked that faculty member a
question. Note how we need to include the Sand F predicates: 3x(S(x) /\ ‘Vy(F(y)-> -,A(x, y))). We could
also write this as 3x(S(x) /\ -i3y(F(y) /\ A(x, y))).
e) This is very similar to part (d), with the role of the players reversed: 3x(F(x) /\ ‘Vy(S(y)-> -iA(y,x))).
26 Chapter 1 The Foundations: Logic and Proofs

Question 4

Let T(x, y) mean that student x likes cuisine y, where the
domain for x consists of all students at your school and
the domain for y consists of all cuisines. Express each of
these statements by a simple English sentence.
d) ∀x∀z∃y((x ≠ z) → ¬(T(x, y) ∧ T(z, y)))
e) ∃x∃z∀y(T(x, y) ↔ T(z, y))
f ) ∀x∀z∃y(T(x, y) ↔ T(z, y))

Answer 4

d) For every pair of distinct students at
your school, there is some cuisine that at least one them does
not like. e) There are two students at your school who like
exactly the same set of cuisines. f) For every pair of students
at your school, there is some cuisine about which they have
the same opinion (either they both like it or they both do not
like it).

Question 5

Determine whether ∀x(P(x) → Q(x)) and ∀xP(x) →

∀xQ(x) are logically equivalent. Justify your answer.

Answer 5

They are not equivalent.
Let P(x) be any propositional function that is sometimes true
and sometimes false, and let Q(x) be any propositional function that is always false. Then ∀x(P(x) → Q(x)) is false but
∀xP(x) → ∀xQ(x) is true

Question 6

Express each of these statements using logical operators,
predicates, and quantifiers.
a) Some propositions are tautologies.
b) The negation of a contradiction is a tautology.
c) The disjunction of two contingencies can be a tautology.
d) The conjunction of two tautologies is a tautology

Answer 6

29. Let T(x) mean that x is
    a tautology and C(x) mean that x is a contradiction. a) ∃x T(x)
    b) ∀x(C(x) → T(¬x)) c) ∃x∃y(¬T(x) ∧ ¬C(x) ∧ ¬T(y) ∧
    ¬C(y)∧T(x ∨ y)) d) ∀x∀y((T(x) ∧T(y)) → T(x∧y))

Question 7

Sudoku
suuji wa dokushin ni kagiru
“the digits must remain single”

Answer 7

To assert that no cell contains more than one number, we take the conjunction over all
values of n, n′
, i, and j, where each variable ranges from 1 to 9 and n ≠ n′ of p(i, j, n) →
¬p(i, j, n′).

Question 8

The n-Queens Problem

Answer 8

Read it, please. u have to do your best to get in IIIT H.
- ¬p(i, j) ∨ ¬p(i, k) asserts that
at least one of ¬p(i, j) and ¬p(i, k) is true, which means that at least one of p(i, j) and p(i, k) is
false. think on this one, why not p v q.

Question 9

Each inhabitant of a remote village always tells the truth
or always lies. A villager will give only a “Yes” or a “No”
response to a question a tourist asks. Suppose you are a
tourist visiting this area and come to a fork in the road.
One branch leads to the ruins you want to visit; the other
branch leads deep into the jungle. A villager is standing
at the fork in the road. What one question can you ask the
villager to determine which branch to take?

Answer 9

“If I were to ask you whether

the right branch leads to the ruins, would you answer yes?”

Question 10

Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”

Answer 10

Let p denote “The diagnostic message is stored in the buffer” and let q
denote “The diagnostic message is retransmitted.” The specifications can then be written as
p ∨ q, ¬p, and p → q
we conclude that these specifications
are consistent, because they are all true when p is false and q is true. We could come to the same
conclusion by the use of a truth table to examine the four possible assignments of truth values to p
and q.

Question 11

“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16
years old.”

Answer 11

Let q, r, and s represent “You can ride the roller coaster,” “You are under 4 feet tall,”
and “You are older than 16 years old,” respectively. Then the sentence can be translated to
(r ∧ ¬s) → ¬q.

Question 12

For hiking on the trail to be safe, it is necessary but
not sufficient that berries not be ripe along the trail
and for grizzly bears not to have been seen in the area.

Answer 12

(h →(¬b ∧ ¬g)) ∧ ¬((¬b ∧ ¬g) → h)

Question 13

1. 5
2. Express each of these system specifications using predicates, quantifiers, and logical connectives, if necessary.
   b) There is a process that continues to run during all error conditions only if the kernel is working correctly.

Answer 13

b) 3pVe((H(e)–> S(p,running))–> S(kernel,working correctly)), where H(e) means that error condition e is
in effect and S(x,y) means that the status of xis y. Obviously there are other ways to express this with
different choices of predicates. Note that “only if” is the converse of “if,’’ so the kernel’s working properly is
the conclusion, not the hypothesis.

Question 14

1. 5
2. Express each of these system specifications using predicates, quantifiers, and logical connectives, if necessary.
   c) All users on the campus network can access all websites whose url has a .edu extension.

Answer 14

c) Vu\ls(E(s, .edu)–+ A(u,s)), where E(s,x) means that websites has extension x, and A(u,s) means that
user u can access website s

Question 15

1.5
17. Express each of these system specifications using predicates, quantifiers, and logical connectives, if necessary.
∗d) There are exactly two systems that monitor every remote server.

Answer 15

d) This is tricky, because we have to interpret the English sentence first, and different interpretations would
lead to different answers. We will assume that the specification is that there exist two distinct systems such
that they monitor every remote server, and no other system has the property of monitoring every remote
system. Thus our answer is 3x3y(x -1- y /\ Vz((Vs M(z, s)) f-7 (z = x V z = y))), where M(a, b) means that
system a monitors remote server b. Note that the last part of our expression serves two purposes-it says
that x and y do monitor all servers, and it says that no other system does. There are at least two other
interpretations of this sentence, which would lead to different legitimate answers.

Question 16

1.5
43. Use quantifiers and logical connectives to express the fact
that every linear polynomial (that is, polynomial of degree 1) with real coefficients and where the coefficient of
x is nonzero, has exactly one real root.

Answer 16

43. We want to say that for each pair of coefficients (the m and the b in the expression mx + b ), as long as m
    is not 0, there is a unique x making that expression equal to 0. So we write \im\ib(m =I- 0-+ :3x(mx + b =
    O /\ \iw(mw + b = 0-+ w = x))). Notice that the uniqueness is expressed by the last part of our proposition.

Question 17

1.6
Determine whether this argument, taken from Kalish and
Montague [KaMo64], is valid.
If Superman were able and willing to prevent evil,
he would do so. If Superman were unable to prevent evil, he would be impotent; if he were unwilling
to prevent evil, he would be malevolent. Superman
does not prevent evil. If Superman exists, he is neither impotent nor malevolent. Therefore, Superman
does not exist.

Answer 17

Valid

Question 18

prove root 2 and root 3 are irrational:

Answer 18

√2 replaced with √3. First, we suppose that √3 = c∕d where the fraction
c∕d is in lowest terms. Squaring both sides tells us that 3 = c2∕d2, so that 3d2 = c2. Can we
use this equation to show that 3 must be a factor of both c and d, similar to how we used the
equation 2b2 = a2 in Example 11 in Section 1.7 to show that 2 must be a factor of both a
and b? (Recall that an integer s is a factor of the integer t if t∕s is an integer. An integer n is
even if and only if 2 is a factor of n.) In turns out that we can, but we need some ammunition
from number theory, which we will develop in Chapter 4. We sketch out the remainder of the
proof, but leave the justification of these steps until Chapter 4. Because 3 is a factor of c2, it
must also be a factor of c. Furthermore, because 3 is a factor of c, 9 is a factor of c2, which
means that 9 is a factor of 3d2. This implies that 3 is a factor of d2, which means that 3 is a
factor of that d. This makes 3 a factor of both c and d, which contradicts the assumption that
c∕d is in lowest terms

Question 19

Can we tile the board obtained by deleting the upper left and lower right corner squares of a
standard checkerboard?

Answer 19

We color the squares of this checkerboard using alternating white and black
squares.
Suppose we can use dominoes to tile a standard checkerboard with opposite corners removed. Note that the standard checkerboard with opposite corners removed contains
64 − 2 = 62 squares. The tiling would use 62∕2 = 31 dominoes. Note that each domino in this
tiling covers one white and one black square. Consequently, the tiling covers 31 white squares
and 31 black squares. However, when we remove two opposite corner squares, either 32 of the
remaining squares are white and 30 are black or else 30 are white and 32 are black. This contradicts the assumption that we can use dominoes to cover a standard checkerboard with opposite
corners removed, completing the proof.