Math Problems Vault

Problem 121

(a)(b)(c)(d)

For each of the following formulas, determine which occurrences of variables in them are free and which are bound (and by which quantifier). Here $Q$ is a three-place predicate symbol.

?

(a)

$(\forall x)((\exists z) Q(x, z, y) \rightarrow (\forall x)(Q(z, x, y) \rightarrow (\exists y)(Q(z, y, x) \vee x \approx z)))$ ;

(b)

$(\exists y)((\exists x)(\neg x \approx y \wedge Q(x, x, y) \wedge (\forall x)(Q(x, z, y) \rightarrow (\exists z)(Q(x, y, z) \vee Q(z, z, y))))$ ;

(c)

$(\forall x)((\exists z) Q(z, z, x) \wedge (\exists x) Q(y, y, x)) \vee (\exists x)((\exists z) Q(x, x, z) \rightarrow (\forall x) Q(x, y, y))$ ;

(d)

$(\exists y) Q(x, y, z) \vee (\exists x)(Q(z, x, y) \wedge (\forall y) Q(y, x, y)) \wedge (\forall z)(\exists x) Q(z, z, x)$ .

Problem 122

(a)(b)(c)(d)

For each formula $\Phi$ from the previous problem, determine which of the following substitutions are possible: $(\Phi )_{y}^{x},(\Phi )_{z}^{x},(\Phi )_{x}^{y},(\Phi )_{z}^{y},(\Phi )_{x}^{z},(\Phi )_{y}^{z}$ . Explain why. In the cases where it is possible, find the result of the substitution. Consider the formula:

?

(a)

(a) from problem 121;

(b)

(b) from problem 121;

(c)

(c) from problem 121;

(d)

(d) from problem 121.

Problem 123

Using the signature from example 27 on p. 140 — the two-place predicate symbols $P^{(2)}$ ("to be a parent of," so $P(x,y)$ means " $x$ is a parent of $y$ ") and $S^{(2)}$ ("to be married to," $S(x,y)$ means " $x$ is married to $y$ "), and the one-place predicate symbol $M^{(1)}$ ("to be male") — write formulas meaning:

?

(a)

$x$ is a grandson of $y$ ;

(b)

$x$ has at least two children;

(c)

$x$ and $y$ have one common child;

(d)

$x$ has an unmarried sister;

(e)

$x$ and $y$ are cousins;

(f)

$x$ is married, and only one of his sons is married.

Problem 124

The domain includes only the real numbers $\mathbb {R}$ and the one-place infinitely differentiable functions on the set $\mathbb {R}$ . The signature contains the three-place predicate symbol $V, V(f, x, y)$ says "the value of the function $f$ at the argument $x$ equals $y$ "; and the two-place symbol $D$ , where $D(f, g)$ means " $f$ is the derivative of $g$ ". Write formulas denoting the following. You may build auxiliary formulas and use ones constructed earlier:

?

(a)

$x$ is a number;

(b)

$f$ is a function;

(c)

$f$ is a constant function;

(d)

$f$ is a function identically equal to zero;

(e)

$x=0$ ;

(f)

$f$ is the identity function;

(g)

$x=1$ ;

(h)

$f$ is the exponential $e^{x}$ ;

(i)

$x+y=z-$ for numbers $x, y, z$ ;

(j)

$x y=z$ — for numbers $x, y, z$ ;

(k)

$x$ is a non-negative number;

(l)

the number $x$ is less than the number $y$ ;

(m)

the function $f$ takes all real values;

(n)

the function $f$ is one-to-one;

(o)

the function $f$ is sine;

(p)

the number $x$ equals $\pi$ ;

(q)

the number $x$ is a natural number.

Problem 125

Write formulas with free variables from $\left\{ x, y, z\right\}$ that are true in elementary arithmetic of natural numbers if and only if

?

(a)

$x$ is an even number;

(b)

$x$ and $y$ are relatively prime;

(c)

$z$ lies in the interval between $x$ and $y$ ;

(d)

$x$ is the greatest common divisor of $y$ and $z$ ;

(e)

$x$ is the least common multiple of all numbers in the interval $[y ; z)$ .

Problem 126

Let the signature contain two predicate symbols $L^{(3)}$ and $E^{(4)}$ . Tarski's geometry is the interpretation whose domain is the set of points in the Euclidean plane, $L(x, y, z)$ means that the points $x, y$ , and $z$ lie on one line and in exactly that order ( $y$ between $x$ and $z$ ; not necessarily distinct), and $E(x, y, u, v)$ means that the lengths of the segments $x y$ and $u v$ are equal.

Write formulas with free variables from the set $\left\{ x, y, z, u\right\}$ that are true in Tarski's geometry if and only if

?

(a)

$x, y$ , and $z$ form a triangle;

(b)

$x$ is the midpoint of the segment $y z$ ;

(c)

the ray $x y$ is the bisector of the angle $\angle z x u$ ;

(d)

the angle $\angle x y z$ is a right angle;

(e)

the points $x, y, z, u$ lie on one circle;

(f)

the triangle $\triangle x y z$ is acute;

(g)

the segment $x y$ is shorter than $z u$ ;

(h)

the point $x$ lies inside the circle with center $y$ and a point $z$ lying on it.

Problem 127

Represent each of the following sentences by a formula of predicate logic, defining in each case a suitable signature.

?

(a)

Not all students study both analysis and history.

(b)

Only one student did not take the discrete mathematics exam.

(c)

Only one student passed all exams with 100 points.

(d)

The maximum score obtained in discrete mathematics exceeds the maximum score obtained in computer science.

(e)

There is a barber who shaves only those residents of the town who do not shave themselves.

(f)

There are politicians who can fool all the people some of the time; there are politicians who can fool some people all the time; but no one can fool all the people all the time.

Problem 128

Write a formula of predicate logic that is true only in interpretations whose domain contains one element (two, three, ..., $k$ elements).

?

Problem 129

Write a formula of predicate logic that is true only in interpretations in which the $(n+1)$ -place relation $F$ represents a function.

?

Problem 130

Determine which of the following formulas are true in elementary arithmetic, and explain what they mean:

?

(a)

$(\forall x)(\exists y)(\exists z)(A(x, y, z) \wedge M(x, y, z))$ ;

(b)

$(\forall x)(\exists y)(A(y, y, x) \vee (\exists z)(A(y, y, z) \wedge A(z, 1, x)))$ ;

(c)

$(\forall x)(\forall y)(\forall z)((\exists u) M(x, u, y) \wedge (\exists u) M(y, u, z) \rightarrow (\exists u) M(x, u, z))$ ;

(d)

$(\forall x)(\exists y)(M(y, y, x) \vee (\exists z)(M(y, y, z) \wedge M(z, y, x)))$ ;

(e)

$(\forall x)(M(x, x, x) \vee (\exists y)(M(x, x, y) \wedge (\exists u)(\exists v)(\exists w)(A(x, u, v) \wedge A(v, w, y) \wedge \wedge (\exists z)(M(u, w, z) \wedge \neg z \approx 0))))$ .

Problem 131

Determine which of the following formulas are true in Tarski's geometry (problem 126 on the opposite page), and explain what they mean:

?

(a)

$(\forall x)(\forall y)(\exists z)(L(x, y, z) \wedge E(x, y, y, z))$ ;

(b)

$(\forall x)(\forall y)(\forall z)(\exists u)(E(u, x, u, y) \wedge E(u, y, u, z))$ ;

(c)

$(\forall x)(\forall y)(\exists u)(\exists v)(\forall z)(E(z, x, z, y) \rightarrow L(z, u, v) \vee L(z, v, u) \vee L(u, z, v))$ ;

(d)

$(\forall x)(\exists y)(\exists z)(\exists u)(L(y, u, z) \wedge (\forall v)(L(y, v, z) \wedge E(x, u, x, v) \rightarrow u \approx v))$ ;

(e)

$(\forall x)(\forall y)(\forall z)(\neg x \approx y \wedge \neg E(x, y, x, z) \rightarrow (\forall u)(E(x, z, x, u) \wedge L(x, u, y) \rightarrow \rightarrow (\forall v)(E(x, u, x, v) \wedge E(y, u, y, v) \rightarrow u \approx v)))$ .

Problem 132

The signature $\Sigma$ is taken from example 28 on p. 141 — the three-place predicate symbol $V$ , where $V(f,x,y)$ means "the value of the function $f$ at the argument $x$ equals $y$ ," and the two-place predicate symbol $D$ , where $D(f,g)$ means " $f$ is the derivative of $g$ "; the interpretation consists of real numbers and infinitely differentiable functions on them. Determine which of the following formulas are true in this interpretation, and explain what they mean:

?

(a)

$(\forall x)(\forall y)((\exists z)(D(z, x) \wedge D(z, y)) \rightarrow x \approx y) ;$

(b)

$(\forall x)(\forall y)(\exists z)(\forall u)(\forall v)(\forall w)(V(x, u, v) \wedge V(y, v, w) \rightarrow V(z, u, w))$ ;

(c)

$(\forall x)(\exists y)(\forall u)(\forall v)(V(x, u, v) \rightarrow V(y, v, u))$ ;

(d)

$(\forall x)(\forall y)((\exists z)(D(z, x) \wedge D(z, y)) \wedge (\exists u)(\exists v)(V(x, u, v) \wedge V(y, u, v)) \rightarrow x \approx y)$ ;

(e)

$(\exists x)(D(x, x) \wedge (\forall y) \neg V(x, y, y))$ ;

(f)

$(\exists x)(\neg D(x, x) \wedge (\exists y)(D(y, x) \wedge D(x, y)))$ .

Problem 133

The signature $\Sigma$ consists of the two-place predicate symbol $E^{(2)}$ , the individual variables $a, \ldots , g$ , and others. The interpretation $\mathfrak {G}$ is depicted in fig. 16; an arrow from $x$ to $y$ means that $(x, y) \in E$ (such interpretations are called graphs; they will be studied in detail in chapter 9 and beyond). Determine which of the following formulas are true in this interpretation, and explain what they mean:

$Fig. 16. The graph \mathfrak {G} from problem 133.$ Fig. 16. The graph \mathfrak {G} from problem 133.

?

(a)

$(\forall x)(\exists y)(\exists z)(E(x, y) \wedge E(z, x))$ ;

(b)

$(\forall x)(\exists y)(\exists z)(E(x, y) \wedge E(y, z) \wedge E(z, x))$ ;

(c)

$(\forall x)(\exists z)(E(z, z) \wedge (E(x, z) \vee (\exists y)(E(x, y) \wedge E(y, z))))$ ;

(d)

$(\forall x)(\forall y)(E(x, y) \rightarrow \neg E(x, x) \vee \neg E(y, y))$ ;

(e)

$(\exists x)(\forall y)(\forall z)(E(x, y) \wedge E(y, z) \rightarrow \neg x \approx y \wedge \neg x \approx z)$ ;

(f)

$(\exists x)(\exists y)(E(x, y) \wedge (\forall z)(E(x, z) \rightarrow y \approx z))$ ;

(g)

$(\exists x)(\forall y)(\forall z)(\forall u)(E(g, y) \wedge E(y, z) \wedge E(z, u) \rightarrow \neg y \approx x \wedge \neg z \approx x \wedge \neg u \approx x)$ .

Problem 134

Prove theorem 43 on p. 150 (the Principle of Replacement for predicate logic): if $Q$ is an $n$ -place predicate symbol, the formulas $\Phi$ and $\Psi$ have no free variables besides possibly $x_{1}, \ldots , x_{n}$ , and $\Phi \equiv \Psi$ , then $(\Theta )_{\Phi }^{Q} \equiv (\Theta )_{\Psi }^{Q}$ for every formula $\Theta$ .

?

Problem 135

Prove the remaining equivalences from theorem 44 on p. 150: for any variable $x$ and any formulas $\Phi , \Psi$ such that $\Psi$ has no free occurrences of $x$ ,

$\neg (\forall x) \Phi \equiv (\exists x) \neg \Phi$ ;
$\neg (\exists x) \Phi \equiv (\forall x) \neg \Phi$ ;
$\Psi \wedge (\forall x) \Phi \equiv (\forall x)(\Psi \wedge \Phi )$ ;
$\Psi \wedge (\exists x) \Phi \equiv (\exists x)(\Psi \wedge \Phi )$ ;
$\Psi \vee (\forall x) \Phi \equiv (\forall x)(\Psi \vee \Phi )$ ;
$\Psi \vee (\exists x) \Phi \equiv (\exists x)(\Psi \vee \Phi )$ ;
$(\exists x) \Psi \equiv (\forall x) \Psi \equiv \Psi$ . The source text already proves 1), 4), and 7) as worked examples; this problem asks for the remaining ones: 2), 3), 5), 6).

?

Problem 136

Prove the equivalences from theorem 47 on p. 155:

$(\exists x)(\Phi \vee \Psi ) \equiv (\exists x) \Phi \vee (\exists x) \Psi$ ;
$(\forall x)(\Phi \wedge \Psi ) \equiv (\forall x) \Phi \wedge (\forall x) \Psi$ ;
$(\exists x)(\exists y) \Phi \equiv (\exists y)(\exists x) \Phi$ ;
$(\forall x)(\forall y) \Phi \equiv (\forall y)(\forall x) \Phi$ .

?

Problem 137

(a)(b)(c)(d)

Prove the following equivalences:

?

(a)

$(\exists x)(x \approx y \wedge \Phi ) \equiv (\Phi )_{y}^{x}$ ;

(b)

$(\forall x)(x \approx y \rightarrow \Phi ) \equiv (\Phi )_{y}^{x}$ ;

(c)

$\Phi \vee (\exists x) \Phi \equiv (\exists x) \Phi$ ;

(d)

$\Phi \wedge (\forall x) \Phi \equiv (\forall x) \Phi$ .

Problem 138

Prove the entailments from theorem 48 on p. 155:

$(\exists x)(\Phi \wedge \Psi ) \Rightarrow (\exists x) \Phi \wedge (\exists x) \Psi$ ;
$(\forall x) \Phi \vee (\forall x) \Psi \Rightarrow (\forall x)(\Phi \vee \Psi )$ ;
$(\exists x)(\forall y) \Phi \Rightarrow (\forall y)(\exists x) \Phi$ .

?

Problem 139

Give the remaining examples showing that the entailments from theorem 48 on p. 155 — 1) $(\exists x)(\Phi \wedge \Psi ) \Rightarrow (\exists x) \Phi \wedge (\exists x) \Psi$ , 2) $(\forall x) \Phi \vee (\forall x) \Psi \Rightarrow (\forall x)(\Phi \vee \Psi )$ , 3) $(\exists x)(\forall y) \Phi \Rightarrow (\forall y)(\exists x) \Phi$ — do not hold in the reverse direction. (Example 34 already gives a counterexample for the first: on the interpretation with domain $\omega$ and one-place predicate symbols $O$ , $E$ meaning "odd" and "even" respectively, the formula $(\exists x) O(x) \wedge (\exists x) E(x)$ is true while $(\exists x)(O(x) \wedge E(x))$ is false. The remaining examples asked for here are for 2) and 3).)

?

Problem 140

Prove the entailment $(\forall x)(\Phi \rightarrow \Psi ) \Rightarrow (\forall x) \Phi \rightarrow (\forall x) \Psi$ . Show that the entailment does not hold in the reverse direction.

?

Problem 141

(a)(b)(c)

Bring the following formulas to prenex form, $Q$ is a two-place predicate symbol:

?

(a)

$\neg (\forall z) \neg (\forall x)(\exists y)(\forall u)(Q(x, y) \wedge Q(z, u))$ ;

(b)

$(\exists x)(\forall y) Q(x, y) \rightarrow (\exists x)(\forall y) Q(y, x)$ ;

(c)

$\neg ((\forall x)((\forall y) Q(x, y) \rightarrow Q(x, z)) \vee ((\forall z) Q(z, x) \wedge \neg (\exists y) Q(y, x)))$ .

Problem 142

(a)(b)(c)

Using transformations, prove the following equivalences, where the formula $\Theta$ does not contain the variable $x$ free:

?

(a)

$(\exists x)(\Phi \rightarrow \Psi ) \equiv (\forall x) \Phi \rightarrow (\exists x) \Psi$ ;

(b)

$(\forall x)(\Theta \rightarrow \Phi ) \equiv \Theta \rightarrow (\forall x) \Phi$ ;

(c)

$(\forall x)(\Phi \rightarrow \Theta ) \equiv (\exists x) \Phi \rightarrow \Theta$ .