Math Problems Vault

Problem 249

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

For each of the following formulas determine which occurrences of the 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$

\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$

\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$

\wedge (\forall z)(\exists x) Q(z, z, x).

Problem 250

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

For each formula $\Phi$ from the previous problem

?

(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$

\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$

\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$

\wedge (\forall z)(\exists x) Q(z, z, x).

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.

Problem 251

Let $R$ be a two-place predicate symbol. Write closed formulas meaning:

?

(a)

$R$ is reflexive;

(b)

$R$ is antireflexive;

(c)

$R$ is symmetric;

(d)

$R$ is antisymmetric;

(e)

$R$ is transitive;

(f)

$R$ is an equivalence relation;

(g)

$R$ is a strict linear order.

Problem 252

Let $\leqslant$ be a two-place predicate symbol meaning a non-strict partial order relation. Write formulas with one free variable $x$ meaning:

?

(a)

$x$ is the greatest element;

(b)

$x$ is a maximal element;

(c)

$x$ is the unique maximal element;

(d)

$x$ is comparable with every element;

(e)

$x$ is comparable with every maximal element;

(f)

$x$ is incomparable with exactly one element.

Problem 253

Let us assume that the domain is the set of people, and the signature contains the symbols $P^{(2)}, S^{(2)}$ and $M^{(1)}$ , meaning the relations "to be a parent of", "to be married to", and "to be a man", respectively. Write formulas meaning:

?

(a)

$x$ is the 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 of his sons only one is married.

Problem 254

The domain consists only of the real numbers $\mathbb {R}$ and one-place infinitely differentiable functions on the set $\mathbb {R}$ . The signature contains a three-place predicate symbol $V$ , where $V(f, x, y)$ says "the value of the function $f$ at the argument $x$ equals $y$ "; and a two-place symbol $D$ , where $D(f, g)$ means " $f$ is the derivative of $g$ ". Write formulas denoting the following. It is allowed to construct auxiliary formulas and use those 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 nonnegative number;

(l)

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

(m)

the function $f$ takes all real values;

(n)

the function $f$ is bijective;

(o)

the function $f$ is sine;

(p)

the number $x$ equals $\pi$ ;

(q)

the number $x$ is a natural number.

Problem 255

Elementary arithmetic of natural numbers is the following interpretation $\mathcal{N}=(\omega , \nu , \sigma )$ : the domain is the set of natural numbers $\omega$ , the three-place predicate symbols $A(x, y, z)$ and $M(x, y, z)$ mean that $x+y=z$ and $x y=z$ respectively, and the names of numbers are written in the usual way in decimal notation: 0 — zero, 1 — one, and so on. There are also variables $x, y, z$ and others whose values are not known in advance.

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 coprime;

(c)

$z$ lies between $x$ and $y$ ;

(d)

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

(e)

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

Problem 256

Let the signature contain a single two-place predicate symbol $\subseteq$ , which in the interpretation $I=(\mathrm{P}(A), \nu , \sigma )$ means, as usual, "to be a subset of". Write formulas with free variables from $\left\{ x, y, z\right\}$ that are true in this interpretation if and only if

?

(a)

$x=\varnothing$ ;

(b)

$x=A$ ;

(c)

$\left|x\right|=1$ ;

(d)

$x=y \cap z$ ;

(e)

$x=y \cup z$ ;

(f)

$x=y \backslash z$ .

Problem 257

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 this order ( $y$ between $x$ and $z$ , not necessarily distinct), and $E(x, y, u, v)$ means that the segments $x y$ and $u v$ are equal in length.

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 centered at $y$ passing through the point $z$ lying on it.

Problem 258

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

?

(a)

Not all students take both calculus and history.

(b)

Only one student did not take the discrete mathematics exam.

(c)

Only one student scored 100 points on all exams.

(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 inhabitants of the town who do not shave themselves.

(f)

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

Problem 259

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

?

Problem 260

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

?

Problem 261

Determine which of the following formulas are true in elementary arithmetic (problem 255 on p. 75), 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$

\begin{align} \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)))). \end{align}

Problem 262

Determine which of the following formulas are true in Tarski's geometry (problem 257 on p. 75), 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$

\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$

\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$

\begin{align} & \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))). \end{align}

Problem 263

The signature and interpretation are taken from problem 254 on p. 74. Determine which of the following formulas are true in this interpretation, 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$

\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 264

The signature $\Sigma$ consists of a two-place predicate symbol $E^{(2)}$ , the individual variables $a, \ldots , g$ and others. The interpretation $\mathfrak {G}$ is depicted in fig. 6, an arrow from $x$ to $y$ means that $(x, y) \in E$ (such interpretations are called graphs).

$Fig. 6: The graph \mathfrak {G} from problem 264.$ Fig. 6: The graph \mathfrak {G} from problem 264.

Determine which of the following formulas are true in this interpretation, explain what they mean:

?

(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$

\rightarrow \neg y \approx x \wedge \neg z \approx x \wedge \neg u \approx x). \tag {⊛}

Problem 265

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

Prove the following equivalences:

?

(a)

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

(b)

$(\forall x)(\Phi \wedge \Psi ) \equiv (\forall x) \Phi \wedge (\forall x) \Psi$ ;

(c)

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

(d)

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

Problem 266

(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 267

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

Prove the following implications:

?

(a)

$(\exists x)(\Phi \wedge \Psi ) \Rightarrow (\exists x) \Phi \wedge (\exists x) \Psi$ ;

(b)

$(\forall x) \Phi \vee (\forall x) \Psi \Rightarrow (\forall x)(\Phi \vee \Psi )$ ;

(c)

$(\forall x)(\Phi \rightarrow \Psi ) \Rightarrow (\forall x) \Phi \rightarrow (\forall x) \Psi$ ;

(d)

$(\exists x)(\forall y) \Phi \Rightarrow (\forall y)(\exists x) \Phi$ .

Problem 268

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

Give examples of formulas without negations of elementary arithmetic that show that the implications

?

(a)

$(\exists x)(\Phi \wedge \Psi ) \Rightarrow (\exists x) \Phi \wedge (\exists x) \Psi$ ;

(b)

$(\forall x) \Phi \vee (\forall x) \Psi \Rightarrow (\forall x)(\Phi \vee \Psi )$ ;

(c)

$(\forall x)(\Phi \rightarrow \Psi ) \Rightarrow (\forall x) \Phi \rightarrow (\forall x) \Psi$ ;

(d)

$(\exists x)(\forall y) \Phi \Rightarrow (\forall y)(\exists x) \Phi$ .

from the previous problem are false in the reverse direction.

Problem 269

(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 270

(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$ .

Problem 271

Prove that a quantifier-free formula of predicate logic $\Phi$ that does not contain the equality sign $\approx$ is identically true if and only if it can be obtained from some identically true Boolean formula $\Psi$ by replacing every occurrence of each propositional variable in $\Psi$ with some atomic subformula of $\Phi$ .

?

Problem 272

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

Using transformations, prove the identical truth of the following formulas:

?

(a)

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

(b)

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

(c)

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

(d)

$((\forall x) \Phi \rightarrow (\forall x) \neg \Psi ) \rightarrow ((\forall x)(\Phi \rightarrow \Psi ) \rightarrow (\exists x) \neg \Phi )$ .

Problem 273

Prove that the following formula cannot be true on any finite domain, but can be true on infinite ones:

\begin{aligned} (\exists x)(\forall y) \neg R(y, x) \wedge & (\forall x)(\exists y) R(x, y) \wedge \\ & \wedge (\forall x)(\forall y)(\forall z)(R(x, y) \wedge R(z, y) \rightarrow x \approx z) \end{aligned}

?