ЗАДАЧИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

1 МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра алгебры и геометрии ЗАДАЧИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Методические указания к практическим занятиям для студентов механико-математического факультета Издательство «Самарский университет» Самара 2000

2 Печатается по решению Редакционно-издательского совета Самарского государственного университета Методические указания предназначены для студентов 2 курса специальности «математика». Набор задач соответствует программе курса «Математическая логика» и включает в себя темы: логические формулы, эквивалентные преобразования формул, нормальные формы, логическое следование, прикладные задачи, логические функции, исчисление высказываний, исчисление секвенций, логика предикатов. Составитель Рецензент доцент И.С. Фролов доцент В.Б. Соколовский c Фролов И.С. составление, 2000

3 I. Логические формулы. Таблицы значений 1. Примем следующие обозначения высказываний: A: «сегодня ясно», B: «сегодня идет дождь», C: «сегодня идет снег», D: «сегодня пасмурно». Переведите следующие логические формулы на естественный язык: a) A (B C); b) D A; c) D (C B); d) (D B) A; e) D (B C); f) (D B) C. 2. Расставьте скобки, укажите порядок выполнения операций, отметьте все подформулы и постройте дерево, изображающее структуру следующих формул: a) (A B) C ( B C); b) A B C B A; c) A (B C) (C A B); d) (A B) C A B C. 3. Перепишите, удалив лишние скобки: a) (((A B) C) (A (B C))); b) ((A B) ((C D) (B C))); c) (( A) (((B C) ( A)) (B C))); d) (( ( A)) ((B C) (B (A ( C))))). 4. Постройте таблицы истинности для формул: a) (A B) A B; b) A B A B; c) A B A B; d) A (A B); e) (A B) ((A B) C); f) (A B C) A; g) A B (A B C); h) A (B C); i) (A B) (C C A C); j) A B D C; k) ( A C) (B (D A)); l) A B C D E. 5. Определите значения формул при указанных значениях A и B: a) (A B) (B C) (C A) ( A B) ( B C) ( C A), A = B = 1; b) ((B C) A) D, A = 0, B = 1; c) (( A C) D) (B C E), A = B = Исследуйте следующие формулы на их логические значения: a) A 1 (A 2. (A n 1 A n ). ); b) A 1 A 2. A n B 1 B 2. B n ; c) A 1 A 2. A n B 1 B 2. B n ; d) (A 1 A 2 ) (A 2 A 3 ) (A 3 A 4 ). (A n 1 A n ). 7. Проверьте, что следующие формулы являются тавтологиями: 3

4 a) ( A A) A; b) (A B) A B; c) (A B) ( B A); d) (A B) (A B); e) (A B) (A C B C); f) (A B) (C D) (A C B D); g) (A B) (C D) (A C B D). 8. Докажите выполнимость следующих формул, указав соответствующую модель: a) (A A); b) (A B) (B A); c) ((A B) C) B; d) A B (C B C). 9. Покажите, что следующие формулы опровержимы, указав интерпретации, при которой они ложны: a) A B ( A B) (A B); b) (A B) C (A B) (A C); c) ((A B C) ( B A)) B. 10. Определите, являются ли следующие формулы общезначимыми, выполнимыми, опровержимыми или противоречивыми: a) A A; b) A A; c) A B A B; 11. Докажите эквивалентность формул: a) A B A B; b) A B (A B); c) (A B) (A B) A; d) ((A B) B) B; e) (A B) C; f) (A B) (B C) (A C). d) A B ( A B) (A B); e) (A B) C A (B C). 12. Докажите, что следующие пары формул не эквивалентны друг другу: a) A B и A B; b) A B и B A; c) A (B C) и (A B) C; d) A (B C) и A (B C). 13. Докажите эквивалентность формул методом математической индукции: a) A (B 1. B n ) (A B 1 ). (A B n ); b) (A 1. A n ) A 1. A n ; c) A (B 1. B n ) (A B 1 ). (A B n ); d) (A 1. A n ) A 1. A n. II. Эквивалентные преобразования формул 14. Преобразуйте формулы так, чтобы они содержали только связки и : a) A B A B; b) (A B) B C; c) ( A B) C C B; d) ((A B C) ( B A)) B. 4

5 15. Преобразуйте формулы так, чтобы они содержали только связки и : a) ( A B) (A B); d) ((A B) C) A; b) A B ( A C); e) A (B C) A. c) (A B C A) C; 16. Найдите отрицания следующих формул: a) (A (B C)) ( A B); b) ((A ( B ( C D))) E) F ; c) (( A B C) D) E F G; d) ((( A ( B C)) D) E) ( F (G H)). 17. Упростите формулы: a) A A; b) A A; c) (A A) A; d) A (A B); e) ((A B) A) B; f) (A B) (A B). 18. Преобразуйте формулы к возможно более простой форме: a) (A B) (B A) A B; b) ((A B) (B A)); c) ( A B) ((A B) A); d) (A B) ( A B) (A B) ( A B); e) A (A B) ( A C); f) (A B) (A B) (B C) ( A B C); g) (A B) (B A) (C A); h) (A B) (B A C); i) (A B) (B C) (C A) A B C. 19. С помощью эквивалентных преобразований докажите, что следующие формулы тождественно ложны: a) (A B) (A B) A; b) (A B) (A B C) C; c) (A B) ((A B) ( A B)); d) (A B) (A C) (A B) (A C). 20. Докажите равносильность формул, проводя эквивалентные преобразования одной или обеих частей: a) (A B) B A B; b) (A B) ( B A) (A B) A B; c) ( A B) A (A B) A; d) ( A B) (A B) B (A B) ( B A); e) (A B) ( A C) ( A B) (A C); f) (A B) C ( A B C) ( A B C) (B C). 21. Упростите следующие системы высказываний (предполагаемых истинными): 5

6 a) A B, C B, (B C) A; b) A B, A B C, B C; c) A B C, B A C, A B C; d) C A B, B C A, A B C; e) A B C, D E F, C B A, D F E; f) A B C, B (A C), C A B, A B C, A C B, A B C. 22. Упростите следующие системы высказываний, если известно, что хотя бы одно из высказываний истинно: a) A B C, (A B) C, A (B C); b) (A B), B A, B C, (C A); c) A B C, A B C, A B C, (A B C). III. Нормальные формы 23. Эквивалентными преобразованиями приведите следующие формулы к ДНФ и КНФ: a) (A B) (B A); e) (A B) (A C); b) (A B) (B (B B)); f) (A (B C)) (A C); c) (A B) (A C); g) (A B) (C (D A)); d) (A B) (B C); h) (A B) (C D); i) ((A B) (A C)) ( B C). 24. Эквивалентными преобразованиями приведите следующие формулы к CДНФ: a) (A B) (B C); b) A (B C); c) (A B) (C D); d) ( A C) (B C); e) ((A B) C) ( A C); f) A B C; g) ((A B) (A C)) B; h) (A B) (A C) (B C). 25. Эквивалентными преобразованиями приведите следующие формулы к CКНФ: a) (A B) C; b) ( A B) (A C); c) ( A B) (B C); d) (A B) C; e) A B C; f) A B ( C D); g) ( A B) (C D); h) (A B C) D. 26. Используя СДНФ, постройте формулы, принимающие значение 1 только на следующих наборах значений переменных: a) F (0, 0) = F (1, 1) = 1 ; b) F (1, 0) = 1 ; c) F (0, 1, 1) = F (1, 1, 0) = 1 ; d) F (1, 0, 0) = F (0, 1, 0) = F (0, 0, 1) = 1 ; e) F (0, 0, 0) = F (0, 1, 0) = F (1, 1, 1) = 1 ; f) F (0, 1, 1) = F (1, 0, 1) = F (1, 1, 0) = F (0, 0, 0) = 1. 6

7 27. Используя СКНФ, постройте формулы, принимающие значение 0 только на следующих наборах значений переменных: a) F (0, 1) = F (1, 0) = 0 ; b) F (0, 1) = 0 ; c) F (1, 0, 0) = F (1, 0, 1) = 0 ; d) F (0, 1, 1) = F (0, 0, 0) = F (0, 1, 0) = 0 ; e) F (0, 0, 0) = F (0, 1, 0) = F (1, 1, 1) = 0 ; f) F (1, 1, 1) = F (0, 0, 1) = F (1, 1, 0) = F (1, 0, 0) = Найдите СДНФ и СКНФ следующих формул с помощью таблицы значений: a) A B ; b) (A B) (A B) ; c) (A B) C ; d) (A C) A B ; e) A (B (C (A B))) ; f) ((A B) C) D. 29. Найдите наипростейшие формулы от трех переменных, последние столбцы таблиц значений которых имеют следующий вид: a) ; d) ; b) ; e) ; c) ; f) Найдите формулы F = F (A, B), такие, чтобы имели место следующие эквивалентности: a) F (A B) A B; b) F A B (B A) F ; c) (F A) (A B) ((A B) (A F )). 31. Найдите формулы от трех переменных F (A, B, C), такие, чтобы : a) A F A B и A F A C; b) A F A B C и F A (B C) A; c) A F B A C и (C B) A A F. IV. Логическое следование 32. Проверьте справедливость логических следований: a) A, A B = B; b) B, A B = A; c) A B, B C = A C; d) A B = B A; e) A C, B C, A B = C; f) A = A B; g) (A B) C = (A B) (A C); h) A (B C) = (A B) (A C). 33. Методом от противного выяснить, справедливо ли следующее: a) A B, D C, C B = A D; b) A B, (A D) C E, D C = (A D) B E; c) A C, B D, E F, A B, F D = E C; 7

8 d) A B C, C D E, F D E = A B F ; e) A (B C), C D E, F D E = A (B F ); f) A B C D, D E F = A F. 34. Найдите все неэквивалентные между собой и не тождественно истинные формулы, являющиеся логическими следствиями следующих формул: a) A B, A; b) A B, B; c) A B, A; d) A B, A, B; e) A B, B C; f) A B C, C B; g) A B C, A B; h) A B C, B A. 35. Найдите формулу F (A, C), зависящую только от A и C и являющуюся логическим следствием указанных формул: a) A B, C B; c) A B, B C, A D; b) A B, B C, C A; d) A B, C D, B D; e) A B, B C, C D, B D. 36. Найдите все неэквивалентные между собой и не тождественно ложные формулы, для которых следующая формула является логическими следствием : a) A B; b) A B; c) (A B); d) A B A B. 37. Найдите недостающую посылку, такую, чтобы было верно логическое следование : a) A B C, B D, F (C, D) = A D; b) A C, B D, F (C, D) = A B; c) A C, B A C, F (A, B) = B C; d) A C, B C, C B D, F (A, B) = A D; e) A B, F (A, B, C) = C. V. Прикладные задачи 38. Покажите, что следующие высказывания являются тавтологиями: a) Действительное число a больше 2 или меньше 1 в том и только в том случае, когда из того, что a не больше 2, следует, что a меньше 1. b) Если справедливо утверждение, что каждое алгебраическое уравнение с действительными коэффициентами нечетной степени имеет по меньшей мере один действительный корень, то справедливо и утверждение, что каждое алгебраическое уравнение с действительными коэффициентами, не имеющее действительного корня, имеет четную степень. 8

9 c) Два утверждения: «Система n линейных однородных уравнений с n неизвестными имеет единственное решение тогда и только тогда, когда определитель системы отличен от нуля» и «Система n линейных однородных уравнений с n неизвестными имеет по меньшей мере два решения тогда и только тогда, когда определитель системы равен нулю» одновременно истинны или одновременно ложны. d) Если справедливо, что дифференцируемая функция непрерывна, то невозможно, чтобы функция была дифференцируема и разрывна. e) Если справедливо, что невырожденная матрица имеет обратную, то справедливо также, что матрица вырождена или имеет обратную. 39. Найдите все следствия из посылок: a) «Если последняя цифра целого числа четна, то это число делится на 2 или на 4»; «Если целое число делится на 4, то оно делится на 2». b) «Если целое число делится на 2 и на 5, то оно делится на 10»; «Целое число a делится на 2 и не делится на 5». c) «Если у четырехугольника две противоположные стороны параллельны и они же равны, то этот четырехугольник параллелограмм»; «У данного четырехугольника две противоположные стороны равны или параллельны». d) «Если целое число больше 2, то оно простое либо составное»; «Если целое число четное и больше 2, то оно не простое». 9

10 Проверка правильности рассуждений 40. Если завтра будет холодно (A), то я надену теплую куртку (B), если рукав будет починен (C). Завтра будет холодно, а рукав не будет починен. Следует ли отсюда, что я не надену теплую куртку? 41. Андрей или переутомился (A), или болен(b). Если он переутомился, то он раздражается (C). Он не раздражается. Следует ли отсюда, что он не болен? 42. Если цех II не будет участвовать в выпуске нового образца продукции, то не будет участвовать и цех I. Если же цех II будет участвовать в выпуске нового образца, то в этой работе непременно должны быть задействованы цеха I и III. Необходимо ли участие цеха III, если в выпуске нового образца будет участвовать цех I? 43. Или Анна и Антон одного возраста (A), или Анна старше Антона (B). Если Анна и Антон одного возраста, то Наташа и Антон не одного возраста (C). Если Анна старше Антона, то Антон старше Николая (D). Следует ли отсюда, что либо Наташа и Антон не одного возраста, либо Антон старше Николая? 44. Если 2 простое число (A), то 2 наименьшее простое число (B). Если 2 наименьшее простое число, то 1 не является простым числом (C). Число 1 не является простым числом. Следует ли отсюда, что 2 наименьшее простое число? Следует ли отсюда, что 2 простое число? 45. Если 6 составное число (A), то 12 составное число (B). Если 12 составное число, то существует простое число, большее чем 12 (C). Если существует простое число, большее 12, то существует составное число, большее 12 (D). Если 6 делится на 2 (E), то 6 составное число. Число 12 составное. Следует ли отсюда, что 6 составное число? Упрощение систем высказываний 46. Администрация морского порта издала следующие распоряжения: (1) Если капитан корабля получает специальное указание, то он должен покинуть порт на своем корабля. (2) Если капитан не получает специального указания, то он не должен покидать порта или он впредь лишается возможности захода в этот порт. (3) Капитан или лишается впредь возможности захода в этот порт, или не получает специального указания. Как можно упростить эту систему распоряжений? 47. Командир осажденной крепости послал следующие три сообщения: (1) Если нам удастся получить продовольствие, то нам не будет угрожать смерть от голода. (2) Если нам не удастся получить 10

11 продовольствие, то или нам будет угрожать смерть от голода, или мы попытаемся прорвать кольцо окружения. (3) Если нам будет угрожать смерть от голода, то мы попытаемся прорвать кольцо окружения. Как можно сократить эти сообщения, не меняя их смысла? «Логические» задачи 48. Семья состоит из пяти человек: Алексей (А), Вера (В), Глеб (Г), Даша (Д), Евгений (Е), и среди них есть любители телевидения. Известно, что: (1) если телевизор смотрит А, то смотрит и В; (2) смотрят либо Д, либо Е, либо оба вместе; (3) смотрят либо В, либо Г, но не вместе; (4) Д и Г либо смотрят вместе, либо вовсе не смотрят; (5) если смотрит Е, то смотрят А и Д. Кто же смотрит телевизор? 49. Имеются два симптома S 1 и S 2 двух болезней B 1 и B 2. Известно: (1) при B 2 есть S 1 ; (2) при B 1 и отсутствии B 2 есть S 2 ; (3) при B 2 и отсутствии B 1 нет S 2 ; (4) при S 1 или S 2 есть, по крайней мере, B 1 или B 2. Найдите формулы, позволяющие по значениям симптомов S 1 и S 2 определить значения B 1 и B Кубок оспаривали четыре команды: A, B, C и D. Трое болельщиков высказали свои мнения: (1) победу одержит либо A, либо B; (2) A не будет победителем; (3) ни D, ни B не выиграют кубок. Прав оказался лишь один из них. Кому достался кубок? 51. Шестеро подозреваемых в преступлении давали показания. А: «Е виновен». Б: «А лжет, и я не виновен». В: «Виновны А или Е, или оба». Г: «В говорит правду». Д: «В и Е оба лгут». Е: «Я не виновен». Если правду сказал один, и только один из подозреваемых, то кто совершил преступление? 52. Четыре приятеля А, Б, В, Г живут в разных комнатах общежития. На вопрос, где они живут, трое дали по два ответа, из которых один истинный, другой ложный. А: «Я живу в первой комнате, Г живет во второй». Б: «Я живу в третьей комнате, А во второй». В: «Я живу во второй комнате, Б в четвертой». Кто в какой комнате живет? 53. При составлении расписания уроков на один день учителя математики, истории и литературы высказали следующие пожелания: математик просил поставить ему или первый, или второй урок; историк или первый, или третий; учитель литературы или второй, или третий. Как составить расписание уроков, чтобы учесть все пожелания? 54. Для четырех человек A, C, D, E необходимо составить 11

12 график дежурств на четыре дня (каждый дежурит ровно по одному разу и каждый день дежурит только один), учитывая, что: (1) C и D не могут дежурить в первый день; (2) если C дежурит во второй день или D в третий, то E будет дежурить в четвертый; (3) если A не будет дежурить в третий день, то E обязан дежурить во второй; (4) если A или D будут дежурить во второй день, то C будет дежурить в четвертый; (5) если D не будет дежурить в четвертый день, то A придется дежурить в первый, а C в третий день. VI. Логические функции 55. Постройте таблицы значений для следующих логических функций: a) (x y) (y z) (z x); e) (((x y) z) y) z; b) (x y) (y z) (z x); f) (x y x)((x y) z); c) (x y) (xy z); g) x y t z; d) (xy xz) (x y); h) (x (y z)) (u v). 56. Покажите, что: a) x y = x y; b) x y = xy x y; c) (x y) z = x(y z) (x z); d) ((x y) (x y))((x y) (x y)) = x y. 57. Покажите, что: a) xy = (x y); b) x y = x y; c) x y = (x y)(x y); d) x y = (x y) (x y); e) x y = (x y); f) x y = x y. 58. Покажите, что: a) x = x x; c) x y = (x x) (y y); b) xy = (x y) (x y); d) x y = x (y y); e) x y = [(x (y y)) (y (x x))] [(x (y y)) (y (x x))]. 59. Для функции голосования g(x, y, z) докажите: a) g(x, y, z) = xy yz zx; c) g(x, x, y) = x; b) g(xy, yz, zx) = xyz; d) g(x, x, y) = y; e) g самодвойственная функция; f) x y z = g(g(x, y, z), g(x, y, z), g(x, y, z)); g) g(x, y, z) = g( g(x, y, z), y, z). 60. Выразите с помощью суперпозиций: a), и через и ; b), и через и ; c),, и через ; d),, и через ; 12 e) и через и ; f) и через и 0; g) и через и 1; h) через.

13 61. Докажите полноту систем функций: a) ; e) ; b) ; f) ; c) ; g) ; d) ; h) ; i) ; j) ; k) < >; l) < >. 62. Докажите, что нельзя с помощью суперпозиций выразить: a) через,, и ; c) через и ; b) через и ; d) через и. 63. Постройте многочлен Жегалкина для функций от трех переменных, заданных следующими таблицами значений: a) ; d) ; b) ; e) ; c) ; f) Приведите к многочлену Жегалкина следующие функции: a) xy xz; d) (x y)(y z); b) (x y)(y xz); e) ((x y) z) x; c) (x y) z; f) x(x z) (x y). 65. Решите логические уравнения: a) x y = 0; b) (x y = 1; c) (x y) = x; d) (x y) = y; a) e) (1 x) y = 0; f) xy = x y. g) x y = x y. < 66. Решите системы логических < уравнений: x y = x, x y = xy, b) c) x y = x; y x = x y; < xy = x y, x y = x. 67. Постройте релейно-контактные схемы для следующих логических функций, считая, что x y = x y : a) (x y)(y z); c) (x y) x(y z); b) ((x y)(y z)) (x z); d) (x (y z)) (y x). VII. Исчисление высказываний 68. Являются ли доказательствами в ИВ следующие последовательности формул: a) (A (A B)); b) (A (A B)), ((A (A B)) (B (A (A B)))), (B (A (A B))); c) (A (B A)), ((A (B A)) B), B. 69. Выводами из каких множеств гипотез Γ являются следующие последовательности формул: 13

14 a) (A (B C)), A, (B C), B, C; b) ((A B) ((A B) A)), (A B), ((A B) A), ( B (A B)), B, (A B), A. 70. Постройте вывод в ИВ : a) A, A B B ; b) A A B ; c) A, B B A ; d) A B B A ; e) A B B C ; f) A B B A ; g) A C, B C A B C ; h) A B C A ; l) A B, B A ; i) A, A C B C ; m) A B, B A ; j) B, A (B C) A C ; n) A A ; k) A B, A (B C) C ; o) A B A B. 71. Постройте доказательство в ИВ (используя теорему A A, но не используя теорему дедукции: a) A A A ; b) A A A ; c) A (A B) (A B) ; d) A B A C. 72. Постройте доказательство, используя аксиомы для : a) A A; b) A A A; c) A (A B) A; d) A (A B) A. 73. Выведите с помощью теоремы дедукции: a) A (B C) (A B) C ; b) A (B C) B (A C) ; c) (A B) C A (B C) ; d) A (C B) (C A) ; e) A B, B C A C ; f) A A B ; g) A B B A ; h) A B B A ; i) A B (A C) (B C). 74. Выведите, используя свойства выводимости : a) A A ; b) (A A) ; c) A (A A) ; d) (A B) (B A) ; e) (A B) (A B) ; f) ((A B) B) B ; g) A B C, D (E F ), C (E F ) A (B D) ; h) A B, C B, (D A) C E A (E D). 75. Покажите, что : a) (A B) C A (B C) ; b) (A B) C A (B C) ; c) (A B) ( A B) ; d) (A B) ( A B). VIII. Исчисление секвенций 76. Постройте дерево доказательства секвенций, пользуясь правилами для, -вв., : 14

15 a) A B B; e) A A; b) (A B) C A (B C); f) A B A; c) A (A B) A; g) A (B A); d) A B A C; h) A B, A (B C) C. 77. Постройте дерево доказательства секвенций, пользуясь правилами для, : a) A B, A ; b) A A B; c) A B B A; d) A, B (A B); e) (A A); f) (A A) B. 78. Постройте дерево доказательства секвенций, используя правило разбора случаев ( -уд. ) : a) A B B A; b) A (B A) A; c) A B A B; d) A B A C B C; e) A A; f) A (B C) (A B) (A C). 79. Выведите секвенции: a) A (A B B); b) A (A B B); c) (A B C) (A (B C)); d) A B C, D C A B D. 80. Покажите, что : a) (A B) A B; b) (A B) A B; c) A (B C) (A B) (A C). IX. Логика предикатов Истинность в логике предикатов 81. Определите, какие из следующих предложений истинные, а какие ложные, считая предметной областью множество действительных чисел R : a) x y(x + y = 9); b) x y(x + y = 9); c) x y(x + y = 9); d) x y(x + y = 9); e) x(((x > 1) (x < 2)) (x = x)); f) x((x 2 > x) ((x > 1) (x < 0))); g) a(( x(ax = 1)) (a 0)); h) a b x(x 2 + ax + b > 0); j) b a x(x 2 + ax + b = 0); i) b a x(x 2 + ax + b > 0); k) a b x(x 2 + ax + b = 0). 82. Из следующих предикатов с помощью кванторов постройте всевозможные предложения (как первые четыре предложения предыдущей задачи) и определите их истинностные значения, считая предметной областью множество R : a) x 2 + y 2 = 16; b) x < y; 15 c) (x = 0) (x = 1); d) x 2 = 25.

16 83. Пусть P (x), Q(x) предикаты, определенные на множестве U. Обозначим M P множество истинности предиката. Докажите: a) M P Q = M P M Q ; d) M P Q = U M P M Q ; b) M P Q = M P M Q ; e) M P Q = U M P = M Q. c) M P = U M P ; 84. В условиях предыдущей задачи выразите через M P и M Q множества истинности указанных предикатов: a) P (x) Q(x); b) P (x) Q(x); c) P (x) Q(x); d) P (x) Q(x); e) P (x) Q(y); f) P (x) Q(y). 85. Определите и изобразите на R множества истинности следующих одноместных предикатов: a) x + 4 < 3; b) cos(x) > 1; c) x > 0; d) (x 2 > 9) (x > 3); e) (x > 1) (x < 1); f) (x > 1) (x < 1); g) (x > 1) (x < 1); h) (x > 1) (x < 1). 86. Определите и изобразите на действительной плоскости множества истинности следующих двуместных предикатов: a) (x 0) (y 0); b) (x 0) (y 0); c) (x 0) (y 0); d) (x 0) (y 0); e) ( x = y ) (xy > 0); f) ( x > 2) ( x < 3); g) (x 2 > 0) (x 2 2x 3 > 0); h) (x 2 + y 2 > 1) (xy < 0). Запись предложений естественного языка 87. Запишите определения следующих предикатов в виде формул, принимая в качестве предметной области множество натуральных чисел и используя предикатный символ =, функциональные символы + и : a) d(x, y) «x делится на y»; b) D 0 (x, y, z) «z является общим делителем x и y»; c) D(x, y, z) «z является наибольшим общим делителем x и y»; d) P (x) «x простое число». 88. Запишите следующие утверждения в виде формул (при условиях предыдущей задачи): a) «если числа x и y делятся на z, то их сумма тоже делится на z»; b) «если x делится на y и y делится на z, то x делится на z»; c) «сумма двух чисел, имеющих разную четность, нечетна»; d) «x < y»; e) «остаток от деления x на 5 равен 2»; f) «если произведение двух чисел делится на простое число, то на 16

17 него делится хотя бы один из сомножителей». 89. Переведите следующие формулы на русский язык: a) z(2z = x); c) y(y y = x); b) z(3z = x); d) y z(y y = z) (z y = x); e) x y( u(y u = x) v(x v = y) (x = y)). 90. Пользуясь обозначениями предикатов d(x, y), P (x), введенными в предыдущих задачах, а также E(x) «x четное число», O(x) «x нечетное число», переведите на русский язык: a) x(d(x, 2) E(x)); b) x(e(x) d(6, x)); c) x(e(x) y(d(y, x) E(y))); d) x(p (x) y(e(y) d(y, x))); e) x(o(x) y(p (y) d(y, x))). 91. Запишите определения следующих предикатов в виде формул, принимая в качестве предметной области множество точек и прямых в одной плоскости и используя предикатные символы =, T(x) «x есть точка», Π(x) «x есть прямая», i(x, y) «x точка, лежащая на прямой y» : a) Пер(x, y) «x и y пересекающиеся прямые»; b) Пар(x, y) «x и y параллельные прямые»; c) (x, y, z) «x, y, z вершины некоторого треугольника», т.е. «x, y, z не лежат на одной прямой». 92. Запишите следующие утверждения в виде формул (при условиях предыдущей задачи): a) «x есть точка пересечения прямых y и z»; b) «прямые x, y, z не проходят через одну точку»; c) «через любые две различные точки проходит одна прямая и притом только одна»; d) «две различные прямые не могут иметь больше одной общей точки»; e) «через всякую точку, не лежащую на прямой, можно провести прямую, параллельную данной»; f) «через всякую точку, не лежащую на прямой, можно провести не более одной прямой, параллельной данной». 93. Переведите следующие формулы на русский язык (при условиях задачи 91): a) x y z t(i(x, t) i(y, t) i(z, t)); b) x y z(π(x) Π(y) Π(z) (x = z) u(i(u, x) i(u, y)) v(i(v, y) i(v, z)) w(i(w, x) i(w, z))). 94. Запишите следующие предложения в виде формул: a) «существует ровно один x, такой, что Q(x)»; 17

18 b) «существует по меньшей мере два различных x, таких, что Q(x)»; c) «существует не более двух x, таких, что Q(x)»; d) «существует ровно два различных x, таких, что Q(x)». Формулы логики предикатов 95. Приведите к предваренной нормальной форме: a) xf (x) xg(x); b) ( xf (x) yg(y)); c) y u(( xf (x, y, z) xg(x, y)) zf (y, u, z)); d) xf (x, z) (G(x, y) zh(z, x)); e) x yf (x, y, z) x yg(y, x) zh(z); f) x yf (x, y) x yg(x, y); g) ( xf (x, y, z) xf (x, x, x)) F (x, y, z); h) ( z x(g(x, y) F (x, z)) yh(y, z)); i) x( F (x) y( F (y) z( F (z) uf (u)))); j) F (x, y) yg(x, y, z) xf (x, x); k) xf (x, y, z) ( yf (x, y, z) ( zf (x, y, z) G(u))). 96. Докажите эквивалентность формул: a) x(f (x) G(x)) xf (x) xg(x); b) x y(f (x) G(y)) y x(f (x) G(y)); c) x y(f (x) G(y)) y x(f (x) G(y)). 97. Докажите общезначимость формул: a) x(f (x) F (x)); b) xf (x) xf (x); c) xf (x) F (y); 98. Выполнимы ли следующие формулы: a) xf (x); b) xf (x); c) xf (x) xf (x); d) y xf (x, y) x yf (x, y); e) F (y) xf (x); f) xg(x, x) y zg(y, z). d) x y(f (x, x) F (x, y)); e) x y(f (x) F (y)); f) F (x) yf (y). 99. Докажите невыполнимость формул: a) x(f (x) F (x)); b) F (x) xf (x); c) y x F (y, x) x yf (x, y); d) x y(h(x) H(y)) xh(x) x H(x) Докажите, что следующие формулы выполнимы, но не общезначимы: a) x yf (x, y); b) F (y) xf (x); c) xf (x) F (y); d) x yf (x, y) y xf (x, y); e) y xh(x, y) x yh(x, y); f) xf (x, y) xf (y, x); 18

19 * * * Список рекомендуемой литературы Гладкий А.В. Математическая логика. М.: Рос.гос.гум.ун-т, Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, Клини С.К. Математическая логика. М.: Мир, Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. М.: МГУ, Мендельсон Э. Введение в математическую логику. М.: Наука, Новиков П.С. Элементы математической логики. М.: Наука, Гиндикин С.Г. Алгебра логики в задачах. М.: Наука, Игошин В.И. Задачник-практикум по математической логики. М.: Просвещение, Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука,

20 . Печатается в авторской редакции Л.Р. N от Подписано в печать Формат 60 84/16. Бумага офсетная. Печать оперативная. Уч.-изд.л. 1,25. Тираж 150 экз. Заказ N Издательство «Самарский университет», , Самара, ул. Акад. Павлова, 1. УОП СамГУ, ПЛД N от