Исчисление высказываний и исчисление предикатов

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Захарова Ю.Ф.

Дискретная математика

Сборник задач

Исчисление высказываний и исчисление предикатов - student2.ru

ПЕНЗА 2008

УДК

Рецензенты:

Кафедра «Высшей математики и инженерной графики»

Пензенского Артиллеристского Инженерного Института

Кандидат физико-математических наук,

доцент кафедры «Математический анализ»

Пензенского Педагогического Университета

им. В.Г. Белинского

А.В. Гуляев.

Захарова Ю.Ф.

Дискретная математика: Сборник задач. – Пенза: Изд-во Пенз. гос. ун-та, 2008.

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

Сборник подготовлен на кафедре «Высшая и прикладная математика» и предназначен для студентов специальности «Прикладная математика», изучающих курс «Дискретная математика».

УДК

Теория множеств.

Общие сведения.

1. Пересечение.

Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru

3. Разность.

Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru

2. Объединение.

Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru

4. Дополнение (отрицание).

Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru . Операция дополнения подразумевает некоторый универсум (универсальное множество) Исчисление высказываний и исчисление предикатов - student2.ru : Исчисление высказываний и исчисление предикатов - student2.ru .



5. Симметрическая разность.

Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru

Задачи.

Представить диаграммы Эйлера-Венна максимально компактными аналитическими выражениями, в которых использовалось бы минимальное количество логических операций и букв.

1.

Исчисление высказываний и исчисление предикатов - student2.ru

2.

Исчисление высказываний и исчисление предикатов - student2.ru

3.

Исчисление высказываний и исчисление предикатов - student2.ru

4.

Исчисление высказываний и исчисление предикатов - student2.ru

5.

Исчисление высказываний и исчисление предикатов - student2.ru

6.

Исчисление высказываний и исчисление предикатов - student2.ru

7.

Исчисление высказываний и исчисление предикатов - student2.ru

8.

Исчисление высказываний и исчисление предикатов - student2.ru



Доказать с помощью построения диаграмм Эйлера-Венна справедливость следующих выражений.

9. Исчисление высказываний и исчисление предикатов - student2.ru .

10. Исчисление высказываний и исчисление предикатов - student2.ru .

11. Исчисление высказываний и исчисление предикатов - student2.ru .

12. Исчисление высказываний и исчисление предикатов - student2.ru .

13. Исчисление высказываний и исчисление предикатов - student2.ru .

14. Исчисление высказываний и исчисление предикатов - student2.ru .

15. Исчисление высказываний и исчисление предикатов - student2.ru .

16. Исчисление высказываний и исчисление предикатов - student2.ru

Булева логика.

Общие сведения.

Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru Исчисление высказываний и исчисление предикатов - student2.ru


1. Исчисление высказываний и исчисление предикатов - student2.ru .

2. Исчисление высказываний и исчисление предикатов - student2.ru .

3. Исчисление высказываний и исчисление предикатов - student2.ru .

4. Исчисление высказываний и исчисление предикатов - student2.ru .

5. Исчисление высказываний и исчисление предикатов - student2.ru .

6. Исчисление высказываний и исчисление предикатов - student2.ru .

7. Исчисление высказываний и исчисление предикатов - student2.ru .

8. Исчисление высказываний и исчисление предикатов - student2.ru .

9. Исчисление высказываний и исчисление предикатов - student2.ru .

10. Исчисление высказываний и исчисление предикатов - student2.ru .

11. Исчисление высказываний и исчисление предикатов - student2.ru .

12. Исчисление высказываний и исчисление предикатов - student2.ru .

13. Исчисление высказываний и исчисление предикатов - student2.ru .

14. Исчисление высказываний и исчисление предикатов - student2.ru .

15. Исчисление высказываний и исчисление предикатов - student2.ru .

16. Исчисление высказываний и исчисление предикатов - student2.ru .

17. Исчисление высказываний и исчисление предикатов - student2.ru .

18. Исчисление высказываний и исчисление предикатов - student2.ru .

19. Исчисление высказываний и исчисление предикатов - student2.ru .

20. Исчисление высказываний и исчисление предикатов - student2.ru .

21. Исчисление высказываний и исчисление предикатов - student2.ru .

22. Исчисление высказываний и исчисление предикатов - student2.ru .

23. Исчисление высказываний и исчисление предикатов - student2.ru .

24. Исчисление высказываний и исчисление предикатов - student2.ru .

25. Исчисление высказываний и исчисление предикатов - student2.ru .

26. Исчисление высказываний и исчисление предикатов - student2.ru .

27. Исчисление высказываний и исчисление предикатов - student2.ru .

28. Исчисление высказываний и исчисление предикатов - student2.ru .

29. Исчисление высказываний и исчисление предикатов - student2.ru .

30. Исчисление высказываний и исчисление предикатов - student2.ru



Задачи.

Упростить выражение:

17. Исчисление высказываний и исчисление предикатов - student2.ru .

18. Исчисление высказываний и исчисление предикатов - student2.ru .

19. Исчисление высказываний и исчисление предикатов - student2.ru .

20. Исчисление высказываний и исчисление предикатов - student2.ru .

21. Исчисление высказываний и исчисление предикатов - student2.ru .

22. Исчисление высказываний и исчисление предикатов - student2.ru .

23. Исчисление высказываний и исчисление предикатов - student2.ru .

24. Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов - student2.ru .

Разложить функцию Исчисление высказываний и исчисление предикатов - student2.ru в многочлен а) по первой переменной; б) по третьей переменной.

25. Исчисление высказываний и исчисление предикатов - student2.ru .

26. Исчисление высказываний и исчисление предикатов - student2.ru .

27. Исчисление высказываний и исчисление предикатов - student2.ru .

28. Исчисление высказываний и исчисление предикатов - student2.ru .

29. Исчисление высказываний и исчисление предикатов - student2.ru .

Решить аналитически (без перебора) системы уравнений:

30. Исчисление высказываний и исчисление предикатов - student2.ru .

31. Исчисление высказываний и исчисление предикатов - student2.ru .

32. Исчисление высказываний и исчисление предикатов - student2.ru .

33. Исчисление высказываний и исчисление предикатов - student2.ru .

34. Исчисление высказываний и исчисление предикатов - student2.ru .

Проверить эквивалентность функций а) по таблице истинности; б) с помощью аналитических преобразований.

35. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

36. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

37. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

38. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

39. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

40. Исчисление высказываний и исчисление предикатов - student2.ru ,

Исчисление высказываний и исчисление предикатов - student2.ru .

Выяснить, какие из функций являются тождественно истинными или тождественно ложными а) по таблице истинности; б) с помощью аналитических преобразований.

41. Исчисление высказываний и исчисление предикатов - student2.ru .

42. Исчисление высказываний и исчисление предикатов - student2.ru .

43. Исчисление высказываний и исчисление предикатов - student2.ru .

44. Исчисление высказываний и исчисление предикатов - student2.ru .

45. Исчисление высказываний и исчисление предикатов - student2.ru .

Найти существенные и фиктивные переменные:

46. Исчисление высказываний и исчисление предикатов - student2.ru .

47. Исчисление высказываний и исчисление предикатов - student2.ru .

48. Исчисление высказываний и исчисление предикатов - student2.ru .

49. Исчисление высказываний и исчисление предикатов - student2.ru .

50. Исчисление высказываний и исчисление предикатов - student2.ru .

51. Исчисление высказываний и исчисление предикатов - student2.ru .

Построить функцию, двойственную к данной а) по таблице истинности; б) по принципу двойственности.

52. Исчисление высказываний и исчисление предикатов - student2.ru ,

53. Исчисление высказываний и исчисление предикатов - student2.ru .

54. Исчисление высказываний и исчисление предикатов - student2.ru ,

55. Исчисление высказываний и исчисление предикатов - student2.ru .

56. Исчисление высказываний и исчисление предикатов - student2.ru

57. Исчисление высказываний и исчисление предикатов - student2.ru

Построить а) СДНФ; б) СКНФ; в) СПНФ. Сделать вывод о линейности функции.

58. Исчисление высказываний и исчисление предикатов - student2.ru

59. Исчисление высказываний и исчисление предикатов - student2.ru .

60. Исчисление высказываний и исчисление предикатов - student2.ru .

61. Исчисление высказываний и исчисление предикатов - student2.ru .

62. Исчисление высказываний и исчисление предикатов - student2.ru .

63. Исчисление высказываний и исчисление предикатов - student2.ru .

Проверить полноту данных систем:

64. Исчисление высказываний и исчисление предикатов - student2.ru

65. Исчисление высказываний и исчисление предикатов - student2.ru

66. Исчисление высказываний и исчисление предикатов - student2.ru

67. Исчисление высказываний и исчисление предикатов - student2.ru

68. Исчисление высказываний и исчисление предикатов - student2.ru

69. Исчисление высказываний и исчисление предикатов - student2.ru

Исчисление высказываний и исчисление предикатов.

Ниже приведены легенды. Запишите с использованием 4—6 различных букв клаузу, отвечающую тексту или контексту вашей легенды, для чего сформули­руйте необходимые посылки и два следствия: одно истинное, другое ложное. С помощью таблицы истинности найдите МНФ.[1]

70. В одной старой легенде рассказывается, что греческий драматург Софокл погиб при очень странных обстоятельствах. На его лысый череп орел сбросил камень, приняв его за яйцо. Если бы Софокл не сочинял трагедий, то он не уеди­нялся бы в горах и остался бы жить до своей естественной кончины. Он мог бы сочинять свои трагедии в горах при наличии волос на голове или при отсутствии там этих странных птиц.

71. Мотоцикл я сначала не заметил, так как его заслонил бензовоз, а «Волга» ывернула из-за угла, когда «Жигули» были уже вблизи светофора. «Иномарка» роскочила на красный свет и явилась, как мне кажется, причиной всей этой зарии. Из-за нее «Волга» резко затормозила и мотоциклист оказался на асфаль-?. «Жигули», чтобы не задавить мотоциклиста, свернули на тротуар, а бензовоз это время врезался в «Волгу». Если бы не было мотоцикла, то опасной ситуа-ии тоже могло и не быть. Хотя виноват и водитель «Волги», поскольку он явно ревысил скорость.

72. Если облака — это горы в небе и горы — это облака на земле, то гроза — это вулкан на небе и вулкан — это гроза на земле. Вулкан извергает пепел, а гроза — воду. Вулканический пепел и дождевая вода одинаково хорошо сказываются на урожайности полей. Урожай — это благо. Все благо — от Бога. Значит, пепел и вода, вулкан и гроза, горы и облака — от Бога.

73. Увеличение денег в обращении влечет за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, да избежим безработицы и курс денежной единицы останется неизменным.

74. «Что собираешься делать, честолюбивый полководец?» — «Хочу завоевать Африку, мудрый философ». — «Предположим, Африку ты завоевал. Что дальше будешь делать?» — «Пойду походом на Индию». — «Допустим, и Индию ты покорил. Что потом?» — «Потом я уединюсь в своем саду и стану наслаждаться чтением книг. Хочу быть таким же мудрым как ты, философ». — «Почему бы тебе сразу же не отправиться в сад и не приняться за книги?» — «Так ведь ни Африки, Индии я еще не завоевал». — «Да, ты прав, полководец. Я рассуждаю немудро, поскольку не учитываю твоего сегодняшнего честолюбия».

75. Любой марксист — диалектик, но не всякий диалектик — марксист. Любой марксист — материалист, но не всякий материалист — марксист. Гегель был диа­лектик, но не материалист. Фейербах был материалист, но не диалектик. Итак, если бы Гегель и Фейербах могли объединиться в один кружок, то Маркс уже не понадобился бы.

76. Существуют две теории возникновения человека на земле — теория эволю­ции Дарвина и теория сотворения человека Господом Богом. Если справедлива теория эволюции, то самопроизвольное возникновение человека без соответст­вующих превращений живых организмов невозможно. Как доказали ученые, та­кие превращения действительно имели место. По теории же сотворения человек был слеплен из простой глины, а жизнь в него вдохнул Господь. Глины всегда было много, а насчет дыхания Бога тоже сомневаться не приходится, поскольку есть на то свидетельство Библии. Отсюда вывод — две названные теории друг другу не противоречат.

77. Если в цепи будет большой перепад напряжения, то сгорит предохрани­тель, что повлечет за собой необходимость его замены. При целом предохрани­теле телевизор, конечно, будет работать, но только если он включен в сеть пита­ния. Если телевизор работает нормально, то я увижу сегодняшние «Новости» Итак, я смотрю телевизионные «Новости» при условии отсутствия перепада на­пряжения и подключения телевизора к сети питания.

78. Уменьшение температуры приводит к снижению давления и уменьшению объема. Увеличение объема приводит к росту скорости потока. Повышение дав­ления приводит к падению уровня, если при этом уменьшать температуру. Сни­жение скорости приводит к уменьшению давления или росту температуры Тех­нолог Иванов рассудил так: «Мне надо повысить давление при одновременном снижении скорости потока, поэтому я должен увеличить объем и температуру»

79. Человек, который решил свести счеты со своей жизнью, вряд ли будет за час до этого просматривать статистические данные по зерну за прошлый год. Сломанная герань только подчеркивает кем-то хорошо скрытые следы борьбы и насилия. Очень, конечно, странно, что дверь оказалась заперта изнутри, а вахтер ничего не заметил. Как же преступнику удалось выйти из помещения? И каковы, собственно, мотивы преступления? Такой тихий, скромный человек, ничего кроме семьи и работы его не интересовало. Правда, жена сообщила, что она вчера вечером видела его в обществе двух подозрительных молодых людей. Да и вахтер утверждал, что примерно в течение получаса отлучался для обхода территории. Тем не менее не хватает какого-то звена в этой загадочной цепи событий, чтобы уверенно сказать — «самоубийство» кем-то старательно инсце­нировано.

80. Из утверждения «два плюс два равно пяти» следует, что я и папа рим­ский — одно и то же лицо. В самом деле, если от обеих частей указанного равен­ства отнять по двойке, то будет справедливо равенство «два равно трем». Если от обеих частей нового равенства отнять по единице, то будет справедливо равенство - «один равен двум». Один - это я, а двойка - это я и папа римский. Поско­льку верно, что «один равен двум», то я есть папа римский.

Для приведенных легенд ввести соответствующие предикаты, составить предикатную клаузу и доказать ее истинность.

Рекомендуемая литература

1. Акимов О.Е. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003. – 376 с.

2. Алехина М.А. Методические указания к решению задач по математической логике. Пенза: Изд-во Пенз. гос. техн. ун-та, 1997. – 25 с.

3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 1977.

4. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001. – 304 с.

Содержание

1. Теория множеств................................................................................................................................... 3

1.1. Общие сведения...................................................................................................................................... 3

1.2. Задачи......................................................................................................................................................... 2

2. Булева логика........................................................................................................................................... 2

2.1. Общие сведения...................................................................................................................................... 2

2.2. Задачи......................................................................................................................................................... 2

3. Исчисление высказываний и исчисление предикатов..................................... 5

Рекомендуемая литература............................................................................................................. 9

[1] Тексты данных задач взяты из книги О.Е. Акимова - Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003. – 376 с.

Наши рекомендации