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

Задача II.4.1

(а)(б)(в)

Пусть $f^{1}$ --- одноместный, $g^{2}$ --- двуместный, $h^{3}$ --- трехместный функциональные символы. Являются ли термами слова:

?

(а)

$f^{1}(g^{2}(\nu_{0}, \nu_{1}))$ ;

(б)

$g^{2}(f^{1}(\nu_{2}), h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ;

(в)

$f^{1}(g^{2}(\nu_{0}), h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ?

Задача II.4.2

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

Пусть $f^{1}, g^{2}, h^{3}$ те же, что в предыдущей задаче, $P^{1}$ --- одноместный, $Q^{3}$ --- трехместный предикатные символы. Являются ли формулами слова:

?

(а)

$Q^{3}(\nu_{0}, f^{1}(\nu_{1}), h^{3}(\nu_{1}, \nu_{2}, \nu_{2}))$ ;

(б)

$(P^{1}(\nu_{0}) \supset \forall \nu_{1}(Q^{3}(\nu_{0}, \nu_{1}, \nu_{2}) \& P^{1}(g^{2}(\nu_{0}, \nu_{1}))))$ ;

(в)

$Q^{3}(P^{1}(\nu_{0}), f^{1}(\nu_{1}), f^{1}(\nu_{2}))$ ;

(г)

$f^{1}(h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ?

Задача II.4.3

Показать, что выражение

\exists \nu _{0} \forall \nu _{1} \ldots \forall \nu _{\nu _{0}} (P(\nu _{1}) \& \ldots \& P(\nu _{\nu _{0}})),

где $P$ --- одноместный предикатный символ, не является формулой.

?

Задача II.4.4

(а)(б)

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

?

(а)

$Q^{2}(f^{1}(\nu_{0}), g^{2}(\nu_{0}, \nu_{1}))$ ;

(б)

$(\exists \nu_{0} Q^{2}(\nu_{0}, \nu_{1}) \supset \neg (P^{1}(g^{2}(\nu_{0}, \nu_{1})) \& \forall \nu_{2} P^{1}(\nu_{2})))$ .

Задача II.4.5

(а)(б)

Описать множество термов от одной переменной $\nu_{0}$ :

?

(а)

и функционального символа $f^{1}$ ;

(б)

и функционального символа $g^{2}$ .

Задача II.4.6

(а)(б)(в)

Какие вхождения переменных являются свободными, а какие связанными в формулах:

?

(а)

$\forall \nu_{0}(P(\nu_{0}, \nu_{1}) \supset \forall \nu_{1} Q(\nu_{1}))$ ;

(б)

$(\forall \nu_{0} P(\nu_{0}, \nu_{1}) \supset \forall \nu_{1} R(\nu_{0}, \nu_{1}))$ ;

(в)

$(\neg \exists \nu_{2} Q(\nu_{2}, \nu_{2}) \& R(f(\nu_{1}, \nu_{2})))$ ?

Задача II.4.7

(а)(б)

Являются ли свободными для $x$ в $A$ терм $t$ :

?

(а)

$t = f(\nu_{0}, \nu_{3})$ , $x = \nu_{1}$ , $A = \forall \nu_{0} P(\nu_{0}, \nu_{1})$ ;

(б)

$t = f(\nu_{1}, \nu_{2})$ , $x = \nu_{1}$ , $A = (P(\nu_{1}, \nu_{2}) \supset \exists \nu_{2} Q(\nu_{2}))$ ?

Задача II.4.8

(а)(б)(в)

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

?

(а)

терм, не содержащий переменных, свободен для любой переменной в любой формуле;

(б)

переменная $x$ свободна для $x$ в любой формуле;

(в)

если $A$ не содержит свободных вхождений $x$ , то любой терм свободен для $x$ в $A$ .

Задача II.4.9

Пусть $\mathfrak {M} = \langle \mathbb {N}; S^{3}, P^{3} \rangle$ , где

S^{3}(x, y, z) = \text{и} \Leftrightarrow x + y = z, \qquad P^{3}(x, y, z) = \text{и} \Leftrightarrow x \cdot y = z.

Записать формулу с одной свободной переменной $x$ , истинную в $\mathfrak {M}$ тогда и только тогда, когда:

?

(а)

$x = 0$ ;

(б)

$x = 1$ ;

(в)

$x = 2$ ;

(г)

$x$ четно;

(д)

$x$ нечетно;

(е)

$x$ --- простое число.

Задача II.4.10

Записать формулу с двумя свободными переменными $x$ и $y$ , истинную в $\mathfrak {M}$ из задачи II.4.9 тогда и только тогда, когда:

?

(а)

$x = y$ ;

(б)

$x \leq y$ ;

(в)

$x < y$ ;

(г)

$x$ делит $y$ ;

(д)

$x$ и $y$ являются простыми числами-близнецами.

Задача II.4.11

(а)(б)

Записать формулу с тремя свободными переменными $x, y$ и $z$ , истинную в $\mathfrak {M}$ из задачи II.4.9 тогда и только тогда, когда:

?

(а)

$z$ --- наименьшее общее кратное $x$ и $y$ .

(б)

$z$ --- наибольший общий делитель $x$ и $y$ .

Задача II.4.12

Записать предложение, выражающее в модели $\mathfrak {M}$ из задачи II.4.9:

?

(а)

коммутативность сложения;

(б)

ассоциативность сложения;

(в)

коммутативность умножения;

(г)

ассоциативность умножения;

(д)

дистрибутивность сложения относительно умножения;

(е)

бесконечность множества простых чисел;

(ж)

всякое число есть сумма четырех квадратов;

(з)

существование н.о.к. и н.о.д. для чисел, отличных от нуля.

Задача II.4.13

Записать предложение, выражающее в модели $\mathfrak {M}$ из задачи II.4.9:

?

(а)

несуществование единицы;

(б)

простых чисел --- конечное число;

(в)

всякое число можно представить в виде суммы двух квадратов;

(г)

для всякого числа существует строго меньшее число;

(д)

существование наибольшего натурального числа.

Истинны ли эти предложения в модели $\mathfrak {M}$ ?

Задача II.4.14

(а)(б)

Записать предложение, выражающее в модели $\mathfrak {M}$ из задачи II.4.9:

?

(а)

простых чисел-близнецов бесконечно много;

(б)

всякое четное число, большее 2, есть сумма двух простых.

Задача II.4.15

Записать предложение, выражающее в модели $\mathfrak {M}$ из задачи II.4.9 то, что уравнение $3x^{2} + 2x + 1 = 0$ имеет в точности два различных корня.

?

Задача II.4.16

Записать предложение, выражающее в модели $\mathfrak {M}$ из задачи II.4.9, что система уравнений

\begin{cases} 3x - y = 0, \\ x + y = 1 \end{cases}

не имеет решения.

?

Задача II.4.17

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

Пусть $M$ --- множество точек, прямых и плоскостей 3-мерного евклидова пространства со следующими предикатами:

T(x) = \text{и} \Leftrightarrow x \text{ --- точка};

\text{Пр}(x) = \text{и} \Leftrightarrow x \text{ --- прямая};

\text{Пл}(x) = \text{и} \Leftrightarrow x \text{ --- плоскость};

\text{Л}(x, y) = \text{и} \Leftrightarrow x \text{ --- лежит на } y.

Записать следующие формулы:

?

(а)

через каждые две точки можно провести прямую; если эти точки различны, то такая прямая единственна;

(б)

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

(в)

определение параллельных прямых;

(г)

определение параллельных плоскостей.

Задача II.4.18

(а)(б)

В модели из задачи II.4.17 записать:

?

(а)

аксиому Евклида о параллельных прямых;

(б)

аксиому Лобачевского о параллельных прямых.

Задача II.4.19

(а)(б)(в)

Подобрать предикаты и записать:

?

(а)

аксиомы Гильберта для евклидовой геометрии;

(б)

аксиомы для геометрии Лобачевского;

(в)

аксиомы для геометрии Римана.

Задача II.4.20

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

Рассмотрим модели с одним 2-местным предикатом $R(x, y)$ . Записать, что данный предикат $R(x, y)$ :

?

(а)

рефлексивен;

(б)

симметричен;

(в)

транзитивен;

(г)

является отношением эквивалентности.

Задача II.4.21

(а)(б)

Записать в сигнатуре $\tau = \langle \leq , {=} \rangle$ , где $\leq$ и $=$ есть 2-местные предикаты, аксиомы:

?

(а)

частично упорядоченного множества;

(б)

линейно упорядоченного множества.

Задача II.4.22

Пусть $M$ --- частично упорядоченное множество и

Q^{2}(x, y) = \text{и} \Leftrightarrow x \leq y.

Записать, что:

?

(а)

$x$ есть наименьший элемент;

(б)

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

(в)

$x$ лежит между $y$ и $z$ ;

(г)

множество плотно упорядоченно;

(д)

каждый максимальный элемент является минимальным.

Задача II.4.23

Пусть $M = \mathcal{P}(A)$ , где $A$ --- некоторое множество, и

Q^{2}(x, y) = \text{и} \Leftrightarrow x \subseteq y.

Записать, что:

?

(а)

$x$ есть пересечение $y$ и $z$ ;

(б)

$x$ есть объединение $y$ и $z$ ;

(в)

$x = \emptyset$ ;

(г)

$x = A$ ;

(д)

$x$ есть дополнение $y$ .

Задача II.4.24

(а)(б)

Рассмотрим $\mathfrak {M} = \langle \mathcal{P}(A); {=}, f^{2}, g^{2} \rangle$ , где $f^{2}(x, y) = x \cap y$ , $g^{2}(x, y) = x \cup y$ , $=$ --- предикат равенства множеств. Записать, что:

?

(а)

$x \subseteq y$ ;

(б)

$x$ есть одноэлементное множество.

Задача II.4.25

Записать в сигнатуре $\tau = \langle \leq , {=} \rangle$ аксиомы:

?

(а)

упорядоченного множества с наибольшим и наименьшим элементом;

(б)

дискретно упорядоченного множества;

(в)

решетки;

(г)

дистрибутивной решетки;

(д)

дедекиндовой решетки;

(е)

дистрибутивной решетки с относительными дополнениями;

(ж)

булевой алгебры;

(з)

атомной булевой алгебры.

Задача II.4.26

Записать в подходящей сигнатуре аксиомы:

?

(а)

квазигруппы;

(б)

лупы;

(в)

полугруппы;

(г)

коммутативной полугруппы;

(д)

коммутативной полугруппы с сокращением.

Задача II.4.27

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

Записать в подходящей сигнатуре аксиомы:

?

(а)

группы;

(б)

абелевой группы;

(в)

упорядоченной абелевой группы;

(г)

полной группы.

Задача II.4.28

Записать в подходящей сигнатуре аксиомы:

?

(а)

кольца;

(б)

ассоциативного, коммутативного кольца;

(в)

кольца Ли;

(г)

области целостности;

(д)

тела;

(е)

поля;

(ж)

алгебраически замкнутого поля;

(з)

вещественно замкнутого поля.

Задача II.4.29

Пусть $\mathfrak {M} = \langle \mathbb {N}; P^{1}, g^{1}, 0 \rangle$ , где $g^{1}(x) = x + 1$ , а $P^{1}$ --- произвольный одноместный предикат, $0$ --- нуль. Записать аксиому индукции для $P^{1}$ .

?

Задача II.4.30

Пусть $\mathfrak {M} = \langle M; Q^{2}, P^{1} \rangle$ , где $M$ --- вполне упорядоченное множество, $Q^{2}(x, y) \Leftrightarrow x \leq y$ , $P^{1}$ --- произвольный одноместный предикат. Записать аксиому трансфинитной индукции для $P^{1}$ .

?

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