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

Задача 249

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

Для каждой из следующих формул определить, какие вхождения переменных в них являются свободными, а какие — связанными (и каким квантором). Здесь $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$

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

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

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

Задача 250

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

Для каждой формулы $\Phi$ из предыдущей задачи

?

(а)

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

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

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

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

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

Задача 251

Пусть $R$ — двухместный предикатный символ. Написать замкнутые формулы, означающие:

?

(а)

$R$ рефлексивно;

(б)

$R$ антирефлексивно;

(в)

$R$ симметрично;

(г)

$R$ антисимметрично;

(д)

$R$ транзитивно;

(е)

$R$ — отношение эквивалентности;

(ж)

$R$ — строгий линейный порядок.

Задача 252

Пусть $\leqslant$ — двухместный предикатный символ, который означает отношение нестрогого частичного порядка. Написать формулы, имеющие одну свободную переменную $x$ , означающие:

?

(а)

$x$ — наибольший элемент;

(б)

$x$ — максимальный элемент;

(в)

$x$ — единственный максимальный элемент;

(г)

$x$ сравним со всеми элементами;

(д)

$x$ сравним со всеми максимальными элементами;

(е)

$x$ не сравним в точности с одним элементом.

Задача 253

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

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

Задача 254

Предметная область включает только действительные числа $\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$ является натуральным.

Задача 255

Элементарной арифметикой натуральных чисел называется следующая интерпретация $\mathcal{N}=(\omega , \nu , \sigma )$ : носитель — множество натуральных чисел $\omega$ , трёхместные предикатные символы $A(x, y, z)$ и $M(x, y, z)$ означают, что $x+y=z$ и $x y=z$ соответственно, а названия чисел записывают обычным образом в десятичной системе: 0 — нуль, 1 — один и т. д. Также есть переменные $x, y, z$ и другие, значения которых заранее неизвестны.

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

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

Задача 256

Пусть сигнатура содержит один двухместный предикатный символ $\subseteq$ , который в интерпретации $I=(\mathrm{P}(A), \nu , \sigma )$ означает, как обычно, «быть подмножеством». Записать формулы со свободными переменными из $\left\{ x, y, z\right\}$ , которые истинны в такой интерпретации тогда и только тогда, когда

?

(а)

$x=\varnothing$ ;

(б)

$x=A$ ;

(в)

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

(г)

$x=y \cap z$ ;

(д)

$x=y \cup z$ ;

(е)

$x=y \backslash z$ .

Задача 257

Пусть сигнатура содержит два предикатных символа $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$ , лежащей на ней.

Задача 258

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

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

Задача 259

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

?

Задача 260

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

?

Задача 261

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

?

(а)

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

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

Задача 262

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

?

(а)

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

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

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

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

Задача 263

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

?

(а)

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

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

Задача 264

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

$Рис. 6: Граф \mathfrak {G} из задачи 264.$ Рис. 6: Граф \mathfrak {G} из задачи 264.

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

?

(а)

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

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

Задача 265

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

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

?

(а)

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

Задача 266

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

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

?

(а)

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

Задача 267

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

Доказать следования:

?

(а)

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

(в)

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

(г)

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

Задача 268

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

Привести примеры формул без отрицаний элементарной арифметики, которые показывают, что следования

?

(а)

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

(в)

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

(г)

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

из предыдущей задачи в обратную сторону неверны.

Задача 269

(а)(б)(в)

Привести к предварённому виду следующие формулы, $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)))$ .

Задача 270

(а)(б)(в)

С помощью преобразований доказать следующие эквивалентности, формула $\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$ .

Задача 271

Доказать, что бескванторная формула логики предикатов $\Phi$ , которая не содержит знака равенства $\approx$ , тождественно истинна тогда и только тогда, когда она может быть получена из некоторой тождественно истинной булевой формулы $\Psi$ заменой всех вхождений каждой пропозициональной переменной в $\Psi$ на некоторую атомную подформулу из $\Phi$ .

?

Задача 272

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

С помощью преобразований доказать тождественную истинность следующих формул:

?

(а)

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

(б)

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

(в)

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

(г)

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

Задача 273

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

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

?

Логика предикатов