Банк задач по математике

Задача 121

(а)(б)(в)(г)

Для каждой из следующих формул определить, какие вхождения переменных в них являются свободными, а какие — связанными (и каким квантором). Здесь $Q$ — трёхместный предикатный символ.

?

(а)

$(\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)))$ ;

(б)

$(\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))))$ ;

(в)

$(\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))$ ;

(г)

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

Задача 122

(а)(б)(в)(г)

Для формулы $\Phi$ из предыдущей задачи определить, какие из следующих замен возможны: $(\Phi )_{y}^{x},(\Phi )_{z}^{x},(\Phi )_{x}^{y},(\Phi )_{z}^{y},(\Phi )_{x}^{z},(\Phi )_{y}^{z}$ . Объяснить, почему. В тех случаях, когда это возможно, найти результат замены. Рассмотреть формулу:

?

(а)

(а) из задачи 121;

(б)

(б) из задачи 121;

(в)

(в) из задачи 121;

(г)

(г) из задачи 121.

Задача 123

Используя сигнатуру из примера 27 на стр. 140 — двухместные предикатные символы $P^{(2)}$ («быть родителем», то есть $P(x,y)$ означает « $x$ — родитель $y$ ») и $S^{(2)}$ («состоять в браке с», $S(x,y)$ означает « $x$ состоит в браке с $y$ »), а также одноместный предикатный символ $M^{(1)}$ («быть мужчиной») — написать формулы, означающие:

?

(а)

$x$ является внуком $y$ ;

(б)

у $x$ есть не менее двух детей;

(в)

$x$ и $y$ имеют одного общего ребёнка;

(г)

у $x$ есть незамужняя сестра;

(д)

$x$ и $y$ — двоюродные братья;

(е)

$x$ женат, а из его сыновей женат только один.

Задача 124

Предметная область включает только действительные числа $\mathbb {R}$ и одноместные бесконечно дифференцируемые функции на множестве $\mathbb {R}$ . Сигнатура содержит трёхместный предикатный символ $V, V(f, x, y)$ говорит «значение функции $f$ на аргументе $x$ равно $y$ »; и двухместный символ $D$ , где $D(f, g)$ означает « $f$ — производная $g$ ». Записать формулы, обозначающие следующее. Допускается строить вспомогательные формулы и использовать построенные ранее:

?

(а)

$x$ — число;

(б)

$f$ — функция;

(в)

$f$ — функция-константа;

(г)

$f$ — функция тождественно равная нулю;

(д)

$x=0$ ;

(е)

$f$ — тождественная функция;

(ж)

$x=1$ ;

(з)

$f$ — экспонента $e^{x}$ ;

(и)

$x+y=z-$ для чисел $x, y, z$ ;

(к)

$x y=z$ — для чисел $x, y, z$ ;

(л)

$x$ — неотрицательное число;

(м)

число $x$ меньше числа $y$ ;

(н)

функция $f$ принимает все действительные значения;

(о)

функция $f$ является взаимно однозначной;

(п)

функция $f$ — это синус;

(р)

число $x$ равно $\pi$ ;

(с)

число $x$ является натуральным.

Задача 125

Записать формулы со свободными переменными из $\left\{ x, y, z\right\}$ , которые истинны в элементарной арифметике натуральных чисел тогда и только тогда, когда

?

(а)

$x$ является чётным числом;

(б)

$x$ и $y$ взаимно просты;

(в)

$z$ лежит в интервале между $x$ и $y$ ;

(г)

$x$ является наибольшим общим делителем $y$ и $z$ ;

(д)

$x$ является наименьшим общим кратным всех чисел из промежутка $[y ; z)$ .

Задача 126

Пусть сигнатура содержит два предикатных символа $L^{(3)}$ и $E^{(4)}$ . Геометрией Тарского называется интерпретация, носителем которой является множество точек на евклидовой плоскости, $L(x, y, z)$ означает, что точки $x, y$ и $z$ лежат на одной прямой и именно в такой последовательности ( $y$ между $x$ и $z$ , не обязательно они различны), а $E(x, y, u, v)$ означает, что длины отрезков $x y$ и $u v$ равны.

Записать формулы со свободными переменными из множества $\left\{ x, y, z, u\right\}$ , которые являются истинными в геометрии Тарского тогда и только тогда, когда

?

(а)

$x, y$ и $z$ образуют треугольник;

(б)

$x$ является серединой отрезка $y z$ ;

(в)

луч $x y$ является биссектрисой угла $\angle z x u$ ;

(г)

угол $\angle x y z$ является прямым;

(д)

точки $x, y, z, u$ лежат на одной окружности;

(е)

треугольник $\triangle x y z$ является остроугольным;

(ж)

отрезок $x y$ короче, чем $z u$ ;

(з)

точка $x$ лежит внутри окружности с центром $y$ и точкой $z$ , лежащей на ней.

Задача 127

Представить каждое из следующих предложений формулой логики предикатов, определив в каждом случае подходящую сигнатуру.

?

(а)

Не все студенты изучают и анализ, и историю.

(б)

Только один студент не сдавал экзамен по дискретной математике.

(в)

Только один студент сдал все экзамены на 100 баллов.

(г)

Максимальные баллы, полученные по дискретной математике, превышают максимальные баллы, полученные по информатике.

(д)

Имеется брадобрей, бреющий только тех жителей города, которые не бреются сами.

(е)

Есть политики, которые могут обманывать всех людей некоторое время, есть политики, которые могут обманывать некоторых людей всё время, но никто не может обманывать всех людей всё время.

Задача 128

Написать формулу логики предикатов, истинную только в интерпретациях, носитель которых содержит один элемент (два, три,.., $k$ элементов).

?

Задача 129

Написать формулу логики предикатов, истинную только в интерпретациях, в которых $(n+1)$ -местное отношение $F$ означает функцию.

?

Задача 130

Определить, какие из следующих формул истинны в элементарной арифметике, пояснить, что они означают:

?

(а)

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

(б)

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

(в)

$(\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))$ ;

(г)

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

(д)

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

Задача 131

Определить, какие из следующих формул истинны в геометрии Тарского (задача 126 на противоположной странице), пояснить, что они означают:

?

(а)

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

(б)

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

(в)

$(\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))$ ;

(г)

$(\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))$ ;

(д)

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

Задача 132

Сигнатура $\Sigma$ взята из примера 28 на стр. 141 — трёхместный предикатный символ $V$ , где $V(f,x,y)$ означает «значение функции $f$ на аргументе $x$ равно $y$ », и двухместный предикатный символ $D$ , где $D(f,g)$ означает « $f$ — производная $g$ »; интерпретация состоит из действительных чисел и бесконечно дифференцируемых функций на них. Определить, какие из следующих формул истинны в этой интерпретации, пояснить, что они означают:

?

(а)

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

(б)

$(\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))$ ;

(в)

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

(г)

$(\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)$ ;

(д)

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

(е)

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

Задача 133

Сигнатура $\Sigma$ состоит из двухместного предикатного символа $E^{(2)}$ , предметных переменных $a, \ldots , g$ и других. Интерпретация $\mathfrak {G}$ изображена на рис.16, стрелка из $x$ в $y$ означает, что $(x, y) \in E$ (такие интерпретации называются графами, они будут подробно изучаться в главе 9 и далее). Определить, какие из следующих формул истинны в этой интерпретации, пояснить, что они означают:

$Рис. 16. Граф \mathfrak {G} из задачи 133.$ Рис. 16. Граф \mathfrak {G} из задачи 133.

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

(ж)

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

Задача 134

Доказать теорему 43 на стр. 150 (принцип замены для логики предикатов): если $Q$ — $n$ -местный предикатный символ, формулы $\Phi$ и $\Psi$ не имеют свободных переменных, кроме, может быть, $x_{1}, \ldots , x_{n}$ , и $\Phi \equiv \Psi$ , то $(\Theta )_{\Phi }^{Q} \equiv (\Theta )_{\Psi }^{Q}$ для любой формулы $\Theta$ .

?

Задача 135

Доказать оставшиеся эквивалентности из теоремы 44 на стр. 150: для любой переменной $x$ и любых формул $\Phi , \Psi$ таких, что $\Psi$ не содержит свободных вхождений $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$ . В тексте книги уже доказаны 1), 4) и 7) в качестве разобранных примеров; в этой задаче требуется доказать оставшиеся: 2), 3), 5), 6).

?

Задача 136

Доказать эквивалентности из теоремы 47 на стр. 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$ .

?

Задача 137

(а)(б)(в)(г)

Доказать следующие эквивалентности:

?

(а)

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

(б)

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

(в)

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

(г)

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

Задача 138

Доказать следования из теоремы 48 на стр. 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$ .

?

Задача 139

Привести оставшиеся примеры, показывающие, что следования из теоремы 48 на стр. 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$ — в обратную сторону неверны. (Пример 34 уже приводит контрпример для первого: на интерпретации с носителем $\omega$ и одноместными предикатными символами $O$ , $E$ , означающими «нечётное» и «чётное» соответственно, формула $(\exists x) O(x) \wedge (\exists x) E(x)$ истинна, а $(\exists x)(O(x) \wedge E(x))$ ложна. Здесь требуются оставшиеся примеры — для 2) и 3).)

?

Задача 140

Доказать следование $(\forall x)(\Phi \rightarrow \Psi ) \Rightarrow (\forall x) \Phi \rightarrow (\forall x) \Psi$ . Показать, что в обратную сторону следование не выполнено.

?

Задача 141

(а)(б)(в)

Привести к предварённому виду следующие формулы, $Q$ — двухместный предикатный символ:

?

(а)

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

(б)

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

(в)

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

Задача 142

(а)(б)(в)

С помощью преобразований доказать следующие эквивалентности, формула $\Theta$ не содержит переменной $x$ свободно:

?

(а)

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

(б)

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

(в)

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

Язык логики предикатов