Задачи по курсу «Математическая логика» на ФКН ВШЭ

Срок сдачи — 27 сентября:

1. Всякий раз перед дождём Петя чихает. Как-то раз Петя чихнул. «Значит будет
дождь» — подумал он. Правильно ли рассуждал Петя?

Срок сдачи — 3 октября:

2. Написать формулу от переменных p,q,r,
которая истинна тогда и только тогда, когда ровно две переменных истинны.

3. Вывести в исчислении секвенций формулу
((p -> r) AND (q -> r)) -> ((p V q) -> r)

4. Доказать в исчислении резолюций
несовместность набора дизъюнктов (a V b), (b V c), (c V d), (d V e),
(e V a), (not a V not b), (not b V not c), (not c V not d), (not d V not e),
(not e V not a) в исчислении резолюций.

Срок сдачи 10 октября

5. Вывести в исчислении высказываний формулу

p OR (p AND q) -> p

6. Вывести в исчислении высказываний формулу

(p -> q) AND NOT q -> NOT p

Срок сдачи 17 октября

7. Пусть Г состоит из формул s OR q, p AND r, r -> NOT q.
Является ли это множество противоречивым? полным?

8. Какие из формул p,q,r,s выводятся из этого множества Г?
(Для выводимых множеств указать вывод, а для невыводимых доказать
невыводимость.)

Срок сдачи 24 октября

9. Написать в сигнатуре теории полей утверждение «любой кубический многочлен имеет корень».

10. Выразить в модели (N, 0,1,=,+,*) свойство «x есть наибольший общий делитель y и z».

Срок сдачи 7 ноября

11. Привести к предварённой нормальной форме формулу
\not(\forall x\exists y P(x,y) —> \exists x R(x))

12. Какие из следующих пар моделей изоморфны и/или элементарно
эквивалентны (Z,+,=), (Q,+,=), (D,+,=), (R,+,=)? Здесь D обозначает
множество двоично рациональных чисел, + интерпретируется
как обычное сложение, а = как совпадение.

Срок сдачи 14 ноября

13. Выразимо ли отношение x-y=1 в модели (Z, =, |x-y|=1)?

14. Сигнатура состоит из символов «равно» и «меньше», и констант 0,1.
В теорию включены аксиомы линейного порядка, утверждение «между любыми двумя различными
элементами есть промежуточный элемент» (аксиома плотности) и формула «0 меньше 1».
Следует ли формула «не существует наибольшего элемента» из формул из этой теории?
Следует ли формула «существует по крайней мере четыре различных элемента»
из формул из этой теории? Здесь речь идёт о семантическом следовании для нормальных моделей.

Срок сдачи 21 ноября

15. Доказать невыразимость отношения x=2y в модели (N, <, =) (натуральные числа с отношениями порядка и равенства).

16.
Написать полную систему аксиом для модели (N, <, =) и доказать её полноту с помощью элиминации кванторов (полнота означает, что любая модель этой системы аксиом элементарна эквивалентна модели (N, <, =)).

Срок сдачи 28 ноября

17. Выведите в исчислении предикатов формулы
\exists x A —> \not \forall x\not A
и \not \forall x \not A —> \exists x A, где A произвольная формула.

18. Выведите в исчислении предикатов формулу
((\forall x (P(x) —> Q(x)) AND P(c) ) —> Q(c),
где P,Q — предикатные символы, а c — константа.

Срок сдачи 5 декабря

19. Известно, что формула сигнатуры теории полей истинна
в полях сколь угодно большой характеристики (для любого k существует поле
характеристики p>k, в котором формула истинна). Докажите, что эта
формула истинна в некотором поле бесконечной характеристики (в другой терминиологии — в поле
характеристики 0).

20. Докажите, что если теория имеет бесконечную нормальную модель,
то она имеет и нормальную
модель сколь угодно большой бесконечной
мощности: для любого бесконечного множества A существует
модель теории, мощность носителя которой не меньше мощности A.

Срок сдачи 12 декабря

21. Постройте формулу, у которой спектр состоит из
всех нечётных чисел (спектр формулы состоит из всех натуральных чисел
n, для которых формула имеет нормальную модель с носителем из n элементов).

22. Пусть сигнатура состоит из двух одноместных предикатных символов.
Каково максимальное количество попарно не элементарно эквивалентных моделей
этой сигнатуры?