Determining the truth value of a formula in a given interpretation

[4/100%]
Show
LaTeX
Problem 130 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Лекции по дискретной математике" [ДДК+21]More problems in Chapter 7 "The Language of Predicate Logic"

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

?
(a)

(∀x)(∃y)(∃z)(A(x,y,z)∧M(x,y,z))(\forall x)(\exists y)(\exists z)(A(x, y, z) \wedge M(x, y, z));

(b)

(∀x)(∃y)(A(y,y,x)∨(∃z)(A(y,y,z)∧A(z,1,x)))(\forall x)(\exists y)(A(y, y, x) \vee (\exists z)(A(y, y, z) \wedge A(z, 1, x)));

(c)

(∀x)(∀y)(∀z)((∃u)M(x,u,y)∧(∃u)M(y,u,z)→(∃u)M(x,u,z))(\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)

(∀x)(∃y)(M(y,y,x)∨(∃z)(M(y,y,z)∧M(z,y,x)))(\forall x)(\exists y)(M(y, y, x) \vee (\exists z)(M(y, y, z) \wedge M(z, y, x)));

(e)

(∀x)(M(x,x,x)∨(∃y)(M(x,x,y)∧(∃u)(∃v)(∃w)(A(x,u,v)∧A(v,w,y)∧∧(∃z)(M(u,w,z)∧¬z≈0))))(\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 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Лекции по дискретной математике" [ДДК+21]More problems in Chapter 7 "The Language of Predicate Logic"

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

?
(a)

(∀x)(∀y)(∃z)(L(x,y,z)∧E(x,y,y,z))(\forall x)(\forall y)(\exists z)(L(x, y, z) \wedge E(x, y, y, z));

(b)

(∀x)(∀y)(∀z)(∃u)(E(u,x,u,y)∧E(u,y,u,z))(\forall x)(\forall y)(\forall z)(\exists u)(E(u, x, u, y) \wedge E(u, y, u, z));

(c)

(∀x)(∀y)(∃u)(∃v)(∀z)(E(z,x,z,y)→L(z,u,v)∨L(z,v,u)∨L(u,z,v))(\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)

(∀x)(∃y)(∃z)(∃u)(L(y,u,z)∧(∀v)(L(y,v,z)∧E(x,u,x,v)→u≈v))(\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)

(∀x)(∀y)(∀z)(¬x≈y∧¬E(x,y,x,z)→(∀u)(E(x,z,x,u)∧L(x,u,y)→→(∀v)(E(x,u,x,v)∧E(y,u,y,v)→u≈v)))(\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 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Лекции по дискретной математике" [ДДК+21]More problems in Chapter 7 "The Language of Predicate Logic"

The signature Σ\Sigma is taken from example 28 on p. 141 — the three-place predicate symbol VV, where V(f,x,y)V(f,x,y) means "the value of the function ff at the argument xx equals yy," and the two-place predicate symbol DD, where D(f,g)D(f,g) means "ff is the derivative of gg"; 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)

(∀x)(∀y)((∃z)(D(z,x)∧D(z,y))→x≈y);(\forall x)(\forall y)((\exists z)(D(z, x) \wedge D(z, y)) \rightarrow x \approx y) ;

(b)

(∀x)(∀y)(∃z)(∀u)(∀v)(∀w)(V(x,u,v)∧V(y,v,w)→V(z,u,w))(\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)

(∀x)(∃y)(∀u)(∀v)(V(x,u,v)→V(y,v,u))(\forall x)(\exists y)(\forall u)(\forall v)(V(x, u, v) \rightarrow V(y, v, u));

(d)

(∀x)(∀y)((∃z)(D(z,x)∧D(z,y))∧(∃u)(∃v)(V(x,u,v)∧V(y,u,v))→x≈y)(\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)

(∃x)(D(x,x)∧(∀y)¬V(x,y,y))(\exists x)(D(x, x) \wedge (\forall y) \neg V(x, y, y));

(f)

(∃x)(¬D(x,x)∧(∃y)(D(y,x)∧D(x,y)))(\exists x)(\neg D(x, x) \wedge (\exists y)(D(y, x) \wedge D(x, y))).

Problem 133 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Лекции по дискретной математике" [ДДК+21]More problems in Chapter 7 "The Language of Predicate Logic"

The signature Σ\Sigma consists of the two-place predicate symbol E(2)E^{(2)}, the individual variables a,…,ga, \ldots , g, and others. The interpretation G\mathfrak {G} is depicted in fig. 16; an arrow from xx to yy means that (x,y)∈E(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)

(∀x)(∃y)(∃z)(E(x,y)∧E(z,x))(\forall x)(\exists y)(\exists z)(E(x, y) \wedge E(z, x));

(b)

(∀x)(∃y)(∃z)(E(x,y)∧E(y,z)∧E(z,x))(\forall x)(\exists y)(\exists z)(E(x, y) \wedge E(y, z) \wedge E(z, x));

(c)

(∀x)(∃z)(E(z,z)∧(E(x,z)∨(∃y)(E(x,y)∧E(y,z))))(\forall x)(\exists z)(E(z, z) \wedge (E(x, z) \vee (\exists y)(E(x, y) \wedge E(y, z))));

(d)

(∀x)(∀y)(E(x,y)→¬E(x,x)∨¬E(y,y))(\forall x)(\forall y)(E(x, y) \rightarrow \neg E(x, x) \vee \neg E(y, y));

(e)

(∃x)(∀y)(∀z)(E(x,y)∧E(y,z)→¬x≈y∧¬x≈z)(\exists x)(\forall y)(\forall z)(E(x, y) \wedge E(y, z) \rightarrow \neg x \approx y \wedge \neg x \approx z);

(f)

(∃x)(∃y)(E(x,y)∧(∀z)(E(x,z)→y≈z))(\exists x)(\exists y)(E(x, y) \wedge (\forall z)(E(x, z) \rightarrow y \approx z));

(g)

(∃x)(∀y)(∀z)(∀u)(E(g,y)∧E(y,z)∧E(z,u)→¬y≈x∧¬z≈x∧¬u≈x)(\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).

References

[ДДК+21] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Лекции по дискретной математике. 3-е изд., Тверской государственный университет, 2021.