WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

Составитель доцент И.С. Фролов Рецензент доцент В.Б. Соколовский © Фролов И.С.

составление, 2000 I. Логические формулы. Таблицы значений 1. Примем следующие обозначения высказываний: A: сегодня ясно, B: сегодня идет дождь, C: сегодня идет снег, D: сегодня пасмурно. Переведите следующие логические формулы на естественный язык:

a) A ¬(B C); d) (D B) A;

b) D ¬A; e) D (B ¬C);

c) D (C B); 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; g) A B (A B C);

b) ¬A B A B; h) A ¬(B C);

c) A B ¬A B; i) (A B) (C ¬C A C);

d) A (A B); j) ¬A B D ¬C;

e) (A B) ((A B) C); k) (¬A C) (B (D A));

f) (A B ¬C) 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| = 0.

6. Исследуйте следующие формулы на их логические значения:

a) A1 (A2... (An-1 An)...);

b) A1 A2... An B1 B2... Bn;

c) A1 A2... An B1 B2... Bn;

d) (A1 A2) (A2 A3) (A3 A4)... (An-1 An).

7. Проверьте, что следующие формулы являются тавтологиями:

a) (¬A A) A; c) (A B) (¬B ¬A);

b) (A B) A B; 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); c) ¬((A ¬B) C) B;

b) (A B) (B A); 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; d) ((A B) B) B;

b) A ¬A; e) (A B) C;

c) A B A B; f) (A B) (B C) ¬(A C).

11. Докажите эквивалентность формул:

a) A B ¬A B; d) A B (¬A B) (A ¬B);

b) A B ¬(A ¬B); e) (A B) C A (B C).

c) (A B) (A ¬B) A;

12. Докажите, что следующие пары формул не эквивалентны друг другу:

a) A B и ¬A ¬B; c) A (B C) и (A B) C;

b) A B и B A; d) A (B C) и A (B C).

13. Докажите эквивалентность формул методом математической индукции:

a) A (B1... Bn) (A B1)... (A Bn);

b) ¬(A1... An) ¬A1... ¬An;

c) A (B1... Bn) (A B1)... (A Bn);

d) ¬(A1... An) ¬A1... ¬An.

II. Эквивалентные преобразования формул 14. Преобразуйте формулы так, чтобы они содержали только связки ¬ и :

a) ¬A ¬B A B; c) (¬A ¬B) C C ¬B;

b) (A B) B C; d) ((A B C) (¬B ¬A)) ¬B.

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; d) ¬A (A B);

b) A ¬A; e) ((A B) A) B;

c) (A A) A; 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. Упростите следующие системы высказываний (предполагаемых истинными):

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); e) ((A ¬B) C) (¬A C);

b) A (B C); f) A B C;

c) (A B) (C D); g) ((A B) (A C)) ¬B;

d) (¬A C) (B C); h) (A B) (A C) (B C).

25. Эквивалентными преобразованиями приведите следующие формулы к CКНФ:

a) (A B) C; e) A B C;

b) (¬A B) (A C); f) A B (¬C D);

c) (¬A B) (B C); g) (¬A B) (C D);

d) (A B) C; 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.

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) = 0.

28. Найдите СДНФ и СКНФ следующих формул с помощью таблицы значений:

a) A B ; d) (A C) A ¬B ;

b) (A | B) (A B) ; e) A (B (C (A B))) ;

c) (A B) C ; f) ((A ¬B) C) D.

29. Найдите наипростейшие формулы от трех переменных, последние столбцы таблиц значений которых имеют следующий вид:

a) 0 0 0 0 1 1 1 1; d) 1 0 1 1 1 1 0 1;

b) 0 1 0 1 0 1 0 1; e) 1 1 0 0 0 0 1 0;

c) 0 0 1 0 0 1 0 0; f) 1 0 1 0 1 1 1 0.

30. Найдите формулы 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; d) A B |= ¬B ¬A;

b) ¬B, A B |= ¬A; e) A C, B C, A B |= C;

c) A B, B C |= A 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;

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; e) A B, B C;

b) A B, ¬B; f) A B C, C B;

c) A B, ¬A; g) A B C, A B;

d) A B, 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; c) ¬(A B);

b) 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) Если справедливо утверждение, что каждое алгебраическое уравнение с действительными коэффициентами нечетной степени имеет по меньшей мере один действительный корень, то справедливо и утверждение, что каждое алгебраическое уравнение с действительными коэффициентами, не имеющее действительного корня, имеет четную степень.

c) Два утверждения: Система n линейных однородных уравнений с n неизвестными имеет единственное решение тогда и только тогда, когда определитель системы отличен от нуля и Система n линейных однородных уравнений с n неизвестными имеет по меньшей мере два решения тогда и только тогда, когда определитель системы равен нулю одновременно истинны или одновременно ложны.

d) Если справедливо, что дифференцируемая функция непрерывна, то невозможно, чтобы функция была дифференцируема и разрывна.

e) Если справедливо, что невырожденная матрица имеет обратную, то справедливо также, что матрица вырождена или имеет обратную.

39. Найдите все следствия из посылок:

a) Если последняя цифра целого числа четна, то это число делится на 2 или на 4 ; Если целое число делится на 4, то оно делится на 2.

b) Если целое число делится на 2 и на 5, то оно делится на 10 ;

Целое число a делится на 2 и не делится на 5.

c) Если у четырехугольника две противоположные стороны параллельны и они же равны, то этот четырехугольник параллелограмм ; У данного четырехугольника две противоположные стороны равны или параллельны.





d) Если целое число больше 2, то оно простое либо составное ;

Если целое число четное и больше 2, то оно не простое.

Проверка правильности рассуждений 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) Если нам не удастся получить продовольствие, то или нам будет угрожать смерть от голода, или мы попытаемся прорвать кольцо окружения. (3) Если нам будет угрожать смерть от голода, то мы попытаемся прорвать кольцо окружения.

Как можно сократить эти сообщения, не меняя их смысла Логические задачи 48. Семья состоит из пяти человек: Алексей (А), Вера (В), Глеб (Г), Даша (Д), Евгений (Е), и среди них есть любители телевидения. Известно, что: (1) если телевизор смотрит А, то смотрит и В; (2) смотрят либо Д, либо Е, либо оба вместе; (3) смотрят либо В, либо Г, но не вместе; (4) Д и Г либо смотрят вместе, либо вовсе не смотрят; (5) если смотрит Е, то смотрят А и Д. Кто же смотрит телевизор 49. Имеются два симптома S1 и S2 двух болезней B1 и B2. Известно: (1) при B2 есть S1; (2) при B1 и отсутствии B2 есть S2; (3) при B2 и отсутствии B1 нет S2; (4) при S1 или S2 есть, по крайней мере, Bили B2.

Найдите формулы, позволяющие по значениям симптомов S1 и Sопределить значения B1 и B2.

50. Кубок оспаривали четыре команды: A, B, C и D. Трое болельщиков высказали свои мнения: (1) победу одержит либо A, либо B; (2) A не будет победителем; (3) ни D, ни B не выиграют кубок.

Прав оказался лишь один из них. Кому достался кубок 51. Шестеро подозреваемых в преступлении давали показания.

А: Е виновен. Б: А лжет, и я не виновен. В: Виновны А или Е, или оба. Г: В говорит правду. Д: В и Е оба лгут. Е: Я не виновен. Если правду сказал один, и только один из подозреваемых, то кто совершил преступление 52. Четыре приятеля А, Б, В, Г живут в разных комнатах общежития. На вопрос, где они живут, трое дали по два ответа, из которых один истинный, другой ложный.

А: Я живу в первой комнате, Г живет во второй. Б: Я живу в третьей комнате, А во второй. В: Я живу во второй комнате, Б в четвертой.

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

математик просил поставить ему или первый, или второй урок; историк или первый, или третий; учитель литературы или второй, или третий. Как составить расписание уроков, чтобы учесть все пожелания 54. Для четырех человек A, C, D, E необходимо составить график дежурств на четыре дня (каждый дежурит ровно по одному разу и каждый день дежурит только один), учитывая, что: (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.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.