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

Задача II.5.1

Доказать, что формула $A$ сигнатуры $\sigma$ выполнима в алгебраической системе $\mathfrak {M} = \langle M; \sigma \rangle$ тогда и только тогда, когда $A$ выполнима в любом обогащении $\mathfrak {M}' = \langle M; \sigma ' \rangle$ .

?

Задача II.5.2

Доказать, что для любого предложения $A$ сигнатуры $\sigma$ , относящегося к алгебраической системе $\mathfrak {M} = \langle M; \sigma \rangle$ , имеем $\mathfrak {M} \vDash A$ или $\mathfrak {M} \vDash \neg A$ .

?

Задача II.5.3

(а)(б)

Доказать, что:

?

(а)

$A$ выполнима тогда и только тогда, когда $\neg A$ не тождественно истинна;

(б)

$A$ тождественно истинна тогда и только тогда, когда $\neg A$ невыполнима.

Задача II.5.4

Доказать, что бескванторная формула истинна тогда и только тогда, когда она может быть получена подстановкой из некоторой тождественно истинной формулы исчисления высказываний.

?

Задача II.5.5

(а)(б)(в)

?

(а)

Доказать, что если замкнутая $\forall$ -формула истинна в алгебраической системе, то она истинна в любой ее подсистеме.

(б)

Доказать, что если замкнутая $\forall$ -формула истинна в алгебраической системе, то она истинна в любом ее расширении.

(в)

Привести пример формулы $A$ и алгебраической системы $\mathfrak {M}$ таких, что $\mathfrak {M} \vDash A$ и $A$ ложна в некотором расширении и некоторой подсистеме системы $\mathfrak {M}$ .

Задача II.5.6

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ есть подсистема системы $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$ . Доказать, что для любого предложения $A$ сигнатуры $\sigma$ , относящегося к алгебраической системе $\mathfrak {M} = \langle M; \sigma \rangle$ , $\mathfrak {M} \vDash A$ тогда и только тогда, когда $\mathfrak {M}_{2} \vDash \rho_{P}(A)$ , где $\mathfrak {M}_{2} = \langle M_{1}; \sigma , P \rangle$ есть обогащение $\mathfrak {M}_{1}$ , а $\rho_{P}(A)$ --- релятивизация формулы $A$ , причем для любого $a \in M_{1}$

\mathfrak {M}_{2} \vDash P(a) \Leftrightarrow a \in M.

?

Задача II.5.7

Выполнимы ли формулы:

?

(а)

$\exists x \, P(x)$ ;

(б)

$\forall x \, P(x)$ ;

(в)

$\exists x \forall y (Q(x, x) \& \neg Q(x, y))$ ;

(г)

$\exists x \exists y (P(x) \& \neg P(y))$ ;

(д)

$\exists x \forall y (Q(x, y) \supset \forall z \, R(x, y, z))$ ;

(е)

$(P(x) \supset \forall y (P(y)))$ ?

Задача II.5.8

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

Являются ли тождественно истинными формулы:

?

(а)

$(\exists x \, P(x) \supset \forall x \, P(x))$ ;

(б)

$\neg (\exists x \, P(x) \supset \forall x \, P(x))$ ;

(в)

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

(г)

$(\forall x \exists y \, Q(x, y) \supset \exists y \forall x \, Q(x, y))$ ?

Задача II.5.9

(а)(б)

Пусть $A(t)$ получается из $A(x)$ заменой всех свободных вхождений переменной $x$ на терм $t$ . Доказать тождественную истинность следующих формул, если терм $t$ свободен для $x$ в $A(x)$ :

?

(а)

$\forall x \, A(x) \supset A(t)$ ;

(б)

$A(t) \supset \exists x \, A(x)$ .

Задача II.5.10

(а)(б)

Привести примеры формул $A(x)$ и термов $t$ таких, чтобы формулы (а) и (б) предыдущей задачи не были тождественно истинны.

?

(а)

(б)

Задача II.5.11

Доказать, что формула

(\forall x \exists y \, P(x, y) \, \& \, \forall x \forall y (P(x, y) \supset \neg P(y, x)) \, \& \, \forall x \forall y \forall z (P(x, y) \supset (P(y, z) \supset P(x, z))))

выполнима в некоторой бесконечной модели и ложна во всех конечных.

?

Задача II.5.12

Доказать, что формула

\exists x \forall y (F(x, y) \supset (\neg F(y, x) \supset (F(x, x) \equiv F(y, y))))

истинна в любой модели, содержащей не более трех элементов.

?

Задача II.5.13

(а)(б)

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

?

(а)

$\exists x \forall y \exists z ((F(y, z) \supset F(x, z)) \supset (F(x, x) \supset F(y, x)))$ ;

(б)

$(\forall x_{1} \forall x_{2} \forall x_{3} (F(x_{1}, x_{1}) \& (F(x_{1}, x_{3}) \supset (F(x_{1}, x_{2}) \vee F(x_{2}, x_{3})))) \supset \exists y \forall z \, F(y, z))$ .

Задача II.5.14

Записать формулу с одноместными предикатами, выполнимую лишь в моделях, содержащих не менее пяти элементов.

?

Задача II.5.15

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

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

?

(а)

$(\neg \exists x \, A(x) \supset \neg \forall x \, A(x))$ ;

(б)

$(\exists x (A(x) \& (B \supset C(x))) \supset (\forall x (A(x) \supset \neg C(x)) \supset \neg B))$ , где $x$ не свободна в $B$ ;

(в)

$(\forall x (A(x) \supset \neg B(x)) \supset \neg (\exists x \, A(x) \& \forall x \, B(x)))$ ;

(г)

$(\forall x (A(x) \supset \neg B(x)) \supset \neg (\forall x \, A(x) \& \exists x \, B(x)))$ .

Задача II.5.16

Доказать, что если $B$ не содержит свободных вхождений $x$ , то:

?

(а)

$\neg \forall x \, A(x) \sim \exists x \, \neg A(x)$ ;

(б)

$\neg \exists x \, A(x) \sim \forall x \, \neg A(x)$ ;

(в)

$(\forall x \, A(x) \& B) \sim \forall x (A(x) \& B)$ ;

(г)

$(B \& \forall x \, A(x)) \sim \forall x (B \& A(x))$ ;

(д)

$(\exists x \, A(x) \& B) \sim \exists x (A(x) \& B)$ ;

(е)

$(B \& \exists x \, A(x)) \sim \exists x (B \& A(x))$ ;

(ж)

$(B \vee \forall x \, A(x)) \sim \forall x (B \vee A(x))$ ;

(з)

$(\forall x \, A(x) \vee B) \sim \forall x (A(x) \vee B)$ ;

(и)

$(\exists x \, A(x) \vee B) \sim \exists x (A(x) \vee B)$ ;

(к)

$(B \vee \exists x \, A(x)) \sim \exists x (B \vee A(x))$ ;

(л)

$(\forall x \, A(x) \supset B) \sim \exists x (A(x) \supset B)$ ;

(м)

$(B \supset \forall x \, A(x)) \sim \forall x (B \supset A(x))$ ;

(н)

$(\exists x \, A(x) \supset B) \sim \forall x (A(x) \supset B)$ ;

(о)

$(B \supset \exists x \, A(x)) \sim \exists x (B \supset A(x))$ ;

(п)

$(\forall x \, A(x) \& \forall x \, C(x)) \sim \forall x (A(x) \& C(x))$ ;

(р)

$(\exists x \, A(x) \vee \exists x \, C(x)) \sim \exists x (A(x) \vee C(x))$ ;

(с)

$\forall x \, A(x) \sim \forall y \, A(y)$ , где $A(x)$ не содержит $y$ , $A(y)$ получается заменой всех свободных вхождений $x$ в $A(x)$ на $y$ ;

(т)

$\exists x \, A(x) \sim \exists y \, A(y)$ , где $A(x)$ не содержит $y$ , $A(y)$ получается заменой всех свободных вхождений $x$ в $A(x)$ на $y$ ;

(у)

$\forall x \, B \sim B$ ;

(ф)

$\exists x \, B \sim B$ .

Задача II.5.17

Пусть $A$ --- формула, $B$ --- подформула формулы $A$ , $A_{1}$ --- результат замены некоторого вхождения $B$ в $A$ на формулу $B_{1}$ . Доказать, что если $B \sim B_{1}$ , то $A \sim A_{1}$ (теорема о замене).

?

Задача II.5.18

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

?

Задача II.5.19

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

Привести к пренексной нормальной форме, считая $A$ и $B$ бескванторными формулами:

?

(а)

$\neg \exists x \forall y \exists z \forall u \, A$ ;

(б)

$(\exists x \forall y \, A(x, y) \& \exists x \forall y \, B(x, y))$ ;

(в)

$(\exists x \forall y \, A(x, y) \vee \exists x \forall y \, B(x, y))$ ;

(г)

$(\exists x \forall y \, A(x, y) \supset \exists x \forall y \, B(x, y))$ .

Задача II.5.20

Пусть $\sigma = \langle \left\{ P_{i}^{n_{i}}\right\}_{i \in I}, \left\{ f_{j}^{n_{j}}\right\}_{j \in J}, \left\{ a_{k}\right\}_{k \in K} \rangle$ , $T$ --- множество всех термов сигнатуры $\sigma$ . Определить на $T$ предикаты и функции так, чтобы $T$ стало алгебраической системой сигнатуры $\sigma$ .

?

Задача II.5.21

(а)(б)

?

(а)

Пусть формула сигнатуры $\sigma$ имеет вид

\forall x_{1} \ldots \forall x_{n} \exists y_{1} \ldots \exists y_{m} \, B(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m})

для некоторой формулы $B$ (возможно, содержащей кванторы); $\varphi_{1}, \ldots , \varphi_{m}$ --- $n$ -местные функциональные символы, не входящие в $\sigma$ . Доказать, что для любой системы $\mathfrak {M} = \langle M; \sigma \rangle$ существует обогащение $\mathfrak {M}_{1}$ сигнатуры $\sigma ' = \sigma \cup \left\{ \varphi_{1}, \ldots , \varphi_{m}\right\}$ такое, что

\mathfrak {M}_{1} \vDash \forall x_{1} \ldots \forall x_{n} (\exists y_{1} \ldots \exists y_{m} \, B(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) \equiv B(x_{1}, \ldots , x_{n}, \varphi _{1}(x_{1}, \ldots , x_{n}), \ldots , \varphi _{m}(x_{1}, \ldots , x_{n}))).

(б)

Доказать, что для любого предложения $A$ сигнатуры $\sigma$ существует некоторая $\forall$ -формула $A_{1}$ сигнатуры $\sigma '$ , полученной добавлением к $\sigma$ новых функциональных символов, обладающая следующим свойством: для любой системы $\mathfrak {M} = \langle M; \sigma \rangle$ существует обогащение $\mathfrak {M}_{1}$ сигнатуры $\sigma '$ такое, что

\mathfrak {M}_{1} \vDash (A \equiv A').

(Добавленные функции в $\mathfrak {M}_{1}$ называются скулемовскими функциями.)

Задача II.5.22

Для формулы $\forall x \exists z \forall y \exists u ((y > z \supset y > x) \& (u < z) \& \neg (u < x))$ построить $\forall$ -формулу, существование которой утверждается в задаче II.5.21(б). Для системы $\mathfrak {M} = \langle \mathbb {N}; {<} \rangle$ найти требуемое обогащение.

?

Задача II.5.23

Для формулы $\forall x \forall y \exists z \exists t (P(x, t) \& \neg P(y, z))$ построить $\forall$ -формулу, существование которой утверждается в задаче II.5.21(б). Для любой системы $\mathfrak {M} = \langle M; P \rangle$ , где $M = \left\{ 0, 1\right\}$ , найти подходящее обогащение.

?

Задача II.5.24

Для формулы

\forall x \forall y \exists z \exists v \forall t (\neg S(x, y, y) \supset (S(z, v, x) \& P(v, t, t)))

и системы $\mathfrak {M} = \langle \mathbb {N}; S^{3}, P^{3} \rangle$ из задачи II.4.9 построить скулемовские функции (см. задачу II.5.21(б)).

?

Задача II.5.25

Доказать, что если формула сигнатуры $\sigma$ выполнима, то она выполнима на некоторой алгебре термов сигнатуры $\sigma ' \supseteq \sigma$ .

?

Задача II.5.26

(а)(б)

?

(а)

Пусть $A(u, x, y)$ не содержит свободных переменных, отличных от $u, x$ , и $y$ . Доказать, что формула $\exists u \forall x \exists y \, A(u, x, y)$ тождественно истинна тогда и только тогда, когда тождественно истинна формула

\exists u (\forall x (\exists y \, A(u, x, y) \supset P(u, x)) \supset \forall x \, P(u, x)),

где $P$ --- двуместный предикатный символ, не входящий в $A(u, x, y)$ .

(б)

Доказать, что для любого предложения $A$ можно построить скулемовскую нормальную форму $A^{*}$ такую, что $A$ тождественно истинна тогда и только тогда, когда $A^{*}$ тождественно истинна.

Задача II.5.27

Пусть $A^{*}$ --- скулемовская нормальная форма предложения $A$ . Показать, что $A \sim A^{*}$ в общем случае неверно. Всегда ли верно, что $A \vDash A^{*}$ ? Аналогичный вопрос для $A^{*} \vDash A$ .

?

Задача II.5.28

(а)(б)(в)

Привести к скулемовской нормальной форме:

?

(а)

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

(б)

$\exists x \forall y \exists z \forall v \, R(x, y, z, v)$ ;

(в)

$\forall x \exists y \forall v \exists z \, R(x, y, z, v)$ .

Задача II.5.29

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- произвольная модель и $M \subseteq M_{1}$ . Доказать, что существует расширение $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$ модели $\mathfrak {M}$ такое, что для любой формулы $A(x_{1}, \ldots , x_{n})$ и любых элементов $a_{1}, \ldots , a_{n} \in M$

\mathfrak {M} \vDash A(a_{1}, \ldots , a_{n}) \Leftrightarrow \mathfrak {M}_{1} \vDash A(a_{1}, \ldots , a_{n}).

?

Задача II.5.30

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ и $M = \left\{ m_{1}, \ldots , m_{n}\right\}$ . Пусть $C(x)$ --- формула со свободной переменной $x$ сигнатуры $\sigma_{M} = \sigma \cup M$ . Доказать, что

\mathfrak {M} \vDash \exists x \, C(x) \Leftrightarrow \mathfrak {M} \vDash (C(m_{1}) \vee \ldots \vee C(m_{n}));

\mathfrak {M} \vDash \forall x \, C(x) \Leftrightarrow \mathfrak {M} \vDash (C(m_{1}) \& \ldots \& C(m_{n})).

?

Задача II.5.31

Доказать, что если алгебраическая система $\mathfrak {M}$ конечна, то для любого предложения $A$ можно построить бескванторное предложение $A^{*}$ , относящееся к $\mathfrak {M}$ , такое, что $\mathfrak {M} \vDash (A \equiv A^{*})$ .

?

Задача II.5.32

Доказать, что если алгебраическая система конечна, то для любой формулы можно в конечное число шагов проверить, выполнима она на этой системе или нет.

?

Задача II.5.33

Доказать, что формула вида $\forall x_{1} \ldots \forall x_{m} \, A(x_{1}, \ldots , x_{m})$ , где $A(x_{1}, \ldots , x_{m})$ --- бескванторная формула без функциональных символов и констант, тождественно истинна тогда и только тогда, когда она истинна в любой модели из $m$ элементов.

?

Задача II.5.34

Доказать, что формула вида $\exists x_{1} \ldots \exists x_{m} \, A(x_{1}, \ldots , x_{m})$ , где $A(x_{1}, \ldots , x_{m})$ --- бескванторная формула без функциональных символов и констант, тождественно истинна тогда и только тогда, когда она истинна в любой одноэлементной модели.

?

Задача II.5.35

Доказать, что формула вида

\forall x_{1} \ldots \forall x_{m} \exists y_{1} \ldots \exists y_{n} \, A(x_{1}, \ldots , x_{m}, y_{1}, \ldots , y_{n}),

где $A(x_{1}, \ldots , x_{m}, y_{1}, \ldots , y_{n})$ --- бескванторная формула без функциональных символов и констант, тождественно истинна тогда и только тогда, когда она истинна в любой модели из $m$ элементов.

?

Задача II.5.36

Пусть $A$ --- формула сигнатуры $\sigma = \langle P_{1}, \ldots , P_{n} \rangle$ , где $P_{1}, \ldots , P_{n}$ --- одноместные предикатные символы. Доказать, что $A$ выполнима тогда и только тогда, когда $A$ выполнима в модели, содержащей не более $2^{n}$ элементов.

?

Задача II.5.37

(а)(б)(в)

Выполнимы ли формулы:

?

(а)

$\forall x \exists y (P(x) \equiv \neg P(y))$ ;

(б)

$\exists x \forall y \exists z (P^{1}(x) \equiv (P^{2}(y) \vee P^{3}(z)))$ ;

(в)

$\exists y \forall x (P(x) \equiv \neg P(y))$ ?

Задача II.5.38

Пусть $\sigma = \langle P^{1}, \ldots , P^{n} \rangle$ , где $P^{1}, \ldots , P^{n}$ --- одноместные предикатные символы. Доказать, что для любого предложения $A$ сигнатуры $\sigma$ существует формула $B$ , эквивалентная $A$ , построенная с помощью , $\vee$ и $\neg$ из $\exists$ -составляющих, т.е. формул вида $\exists x (B_{1} \& \ldots \& B_{s})$ , где $s \geq 1$ и $B_{i}$ ( $1 \leq i \leq s$ ) имеет вид $P(x)$ или $\neg P(x)$ для некоторого $P$ из $\sigma$ .

?

Задача II.5.39

Для $\exists$ -составляющей $C$ (см. задачу II.5.38) обозначим через $C(B_{1}, \ldots , B_{n})$ формулу, полученную из $C$ стиранием квантора $\exists x$ и заменой всех вхождений подформул $P^{1}(x), \ldots , P^{n}(x)$ в $C$ на $B_{1}, \ldots , B_{n}$ соответственно. Доказать, что формула

A = (C_{1} \& \ldots \& C_{k} \& \neg C_{k + 1} \& \ldots \& \neg C_{k + m}),

где $C_{1}, \ldots , C_{k + m}$ --- $\exists$ -составляющие, $k \geq 1$ , $m \geq 0$ , выполнима тогда и только тогда, когда выполнима формула алгебры высказываний

A_{1} = (C_{1}(B_{11}, \ldots , B_{1n}) \& \neg C_{k + 1}(B_{11}, \ldots , B_{1n}) \& \ldots \& \neg C_{k + m}(B_{11}, \ldots , B_{1n}) \& \ldots \& C_{k}(B_{k1}, \ldots , B_{kn}) \& {}

{} \& \neg C_{k + 1}(B_{k1}, \ldots , B_{kn}) \& \ldots \& \neg C_{k + m}(B_{k1}, \ldots , B_{kn})).

?

Задача II.5.40

Указать метод построения по любому предложению $A$ с одноместными предикатами формулы $B$ исчисления высказываний такой, что выполнимость формулы $A$ эквивалентна выполнимости $B$ .

?

Задача II.5.41

(а)(б)(в)

Пользуясь методом задачи II.5.40, установить, выполнимы ли следующие формулы:

?

(а)

$\neg \forall x (P(x) \supset \forall y (P(y) \supset ((Q(x) \supset \neg Q(y)) \vee \forall z \, P(z))))$ ;

(б)

$\forall x \exists y \, \neg (P(y) \supset ((P(x) \supset Q(x)) \supset ((Q(x) \supset R(x)) \supset R(y))))$ ;

(в)

$\forall x \exists z \forall y (((P(y) \& Q(z)) \supset (P(x) \vee R(z))) \supset (Q(x) \equiv \neg Q(y)))$ .

Задача II.5.42

(а)(б)(в)

Написать предложение сигнатуры $\langle {=} \rangle$ :

?

(а)

истинное во всех нормальных моделях, содержащих не более $n$ элементов ( $n \geq 1$ ), и ложное в остальных нормальных моделях;

(б)

истинное во всех нормальных моделях, содержащих не менее $n$ элементов ( $n \geq 1$ ), и ложное в остальных нормальных моделях;

(в)

истинное во всех нормальных моделях, содержащих в точности $n$ элементов ( $n \geq 1$ ), и ложное в остальных нормальных моделях.

Задача II.5.43

Пусть

E_{1} \rightleftharpoons \exists x (x = x),

E_{n} \rightleftharpoons \exists x_{1} \ldots \exists x_{n} \Bigl( \bigwedge _{1 \leq i < j \leq n} \neg (x_{i} = x_{j}) \Bigr) \quad \text{для } n \geq 2.

?

(а)

Доказать, что $E_{n}$ истинна во всякой нормальной модели, содержащей по крайней мере $n$ элементов.

(б)

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

\exists \nu \Bigl( \Bigl( \bigwedge _{1 \leq i < j \leq n} \neg (x_{i} = x_{j}) \Bigr) \& \bigwedge _{1 \leq i \leq n} \neg (\nu = x_{i}) \Bigr),

\Bigl( \Bigl( \bigwedge _{1 \leq i < j \leq n} \neg (x_{i} = x_{j}) \Bigr) \& E_{n + 1} \Bigr).

(в)

Доказать, что каждое предложение сигнатуры $\langle {=} \rangle$ эквивалентно на нормальных моделях формуле, построенной из $E_{1}, \ldots , E_{n}$ с помощью , $\vee$ и $\neg$ .

(г)

Назовем спектром формулы $A$ совокупность мощностей нормальных моделей, на которых выполнима формула $A$ . Показать, что каждая выполнимая формула, построенная из $E_{1}, \ldots , E_{n}$ с помощью , $\vee$ и $\neg$ , имеет спектр, являющийся объединением конечного числа интервалов вида

\left\{ m \mid a \leq m \leq b\right\} \text{ и } \left\{ m \mid m \geq a\right\} \quad (a \in \mathbb {N}, b \in \mathbb {N}).

(д)

Показать, что предложение сигнатуры $\langle {=} \rangle$ тождественно истинно на нормальных моделях тогда и только тогда, когда оно имеет спектр $\left\{ m \mid m \geq 1\right\}$ .

Задача II.5.44

Найти бесконечную систему формул сигнатуры $\langle {=} \rangle$ , выполнимую лишь в бесконечных нормальных моделях.

?

Задача II.5.45

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

?

Выполнимость формул логики предикатов