Exercise 1.9.1: Which logical expressions with nested quantifiers are propositions?

infoAbout

The table below shows the value of a predicate M(x, y) for every possible combination of values of the variables x and y. The domain for x and y is {1, 2, 3}. The row number indicates the value for x and the column number indicates the value for y. For example M(1, 2) = F because the value in row 1, column 2, is F.

M		y
		1	2	3
x	1	T	F	T
	2	T	F	T
	3	T	T	F

Indicate whether each of the logical expressions is a proposition. If so, indicate whether the proposition is true or false.

(a)

M(1, 1)

(b)

y M(x, y)

(c)

x M(x, 3)

(d)

x y M(x, y)

(e)

x y M(x, y)

(f)

M(x, 2)

(g)

y x M(x, y)

Feedback?

Exercise 1.9.2: Truth values for statements with nested quantifiers - small finite domain.

infoAbout

The tables below show the values of predicates P(x, y), Q(x, y), and S(x, y) for every possible combination of values of the variables x and y. The row number indicates the value for x and the column number indicates the value for y. The domain for x and y is {1, 2, 3}.

P	1	2	3
1	T	F	T
2	T	F	T
3	T	T	F

Q	1	2	3
1	F	F	F
2	T	T	T
3	T	F	F

S	1	2	3
1	F	F	F
2	F	F	F
3	F	F	F

Indicate whether each of the quantified statements is true or false.

(a)

x y P(x, y)

(b)

x y Q(x, y)

(c)

x y P(y, x)

(d)

x y S(x, y)

(e)

x y Q(x, y)

(f)

x y P(x, y)

(g)

x y P(x, y)

(h)

x y Q(x, y)

(i)

x y S(x, y)

Feedback?

Exercise 1.9.3: Truth values for mathematical expressions with nested quantifiers.

infoAbout

Determine the truth value of each expression below. The domain is the set of all real numbers.

(a)

xy (xy > 0)

(b)

xy (xy = 0)

(c)

xyz (z = (x - y)/3)

(d)

xyz (z = (x - y)/3)

(e)

xy (xy = yx)

(f)

xyz (x² + y² = z²)

(g)

xy (y² = x)

(h)

xy (x < 0 y² = x)

(i)

x y (x² = y² x y)

(j)

x y (x² = y² |x| |y|)

(k)

x y (x² y² |x| = |y|)

Feedback?

Exercise 1.9.4: De Morgan's law and nested quantifiers.

infoAbout

Write the negation of each of the following logical expressions so that all negations immediately precede predicates. In some cases, it may be necessary to apply one or more laws of propositional logic.

(a)

x y z P(y, x, z)

(b)

x y (P(x, y) Q(x, y))

(c)

x y (P(x, y) Q(x, y))

(d)

x y (P(x, y) P(y, x))

(e)

x y P(x, y) x y Q(x, y)

Feedback?

Exercise 1.9.5: Applying De Morgan's law to English statements with nested quantifiers.

infoAbout

The domain for variables x and y is a group of people. The predicate F(x, y) is true if and only if x is a friend of y. For the purposes of this problem, assume that for any person x and person y, either x is a friend of y or x is an enemy of y. Therefore, F(x, y) means that x is an enemy of y.

Translate each statement 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 the negation operation applies directly to the predicate and then translate the logical expression back into English.

(a)

Everyone is a friend of everyone.

(b)

Someone is a friend of someone.

(c)

Someone is a friend of everyone.

(d)

Everyone is a friend of someone.