Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 548
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
228
Глава 6. АЛГЕБРА ЛОГИКИ
• Мари: Я больше люблю играть с одним из своих кузенов, чем со своим братом;
• Катрин: Моего отца зовут Пьером;
• Анна: Лучше всего мы ладим с сыновьями дяди Жака;
• Жан: Мой отец и каждый из его братьев имеют меньше, чем по четыре ребенка;
• Франсуа: А у моего отца их меньше всего.
Кто чей отец?
17. Перед выборами три брата вели долгую дискуссию, которую закончили сле- дующими довольно запутанными высказываниями:
• Пьер: Если Жан проголосует за Дюбуа, я буду голосовать за Дюпона;
но если он проголосует за Дюпона, я буду голосовать за Дюбуа; если Жак проголосует за Дюпона, я тоже буду голосовать за Дюпона;
• Жан: Если Пьер проголосует за Дюпона, я не буду голосовать за Дюпона;
но если Жак проголосует за Дюбуа, то я проголосую за Дюпона;
• Жак: Если Пьер проголосует за Дюпона, то я не буду голосовать за Дю- пона.
Подошел день выборов. Все братья проголосовали за разных кандидатов.
За кого именно?
18. Произошла кража, и было задержано трое подозреваемых. Один из них (вор)
всегда лжет; другой (соучастник) иногда лжет, а иногда говорит правду; по- следний (подозреваемый напрасно) вообще никогда не лжет. Дознание нача- лось с вопросов о профессии. Их ответы были таковы:
• Бертран: Я маляр, Альфред — настройщик роялей, а Шарль — декоратор;
• Альфред: Я врач, Шарль — страховой агент; что касается Бертрана, то ес- ли вы его спросите, он ответит, что он маляр;
• Шарль: Альфред настраивает рояли, Бертран — декоратор, а я страховой агент.
Какова профессия соучастника?
19. Три журналиста во время завтрака наблюдали за одним человеком. При этом они сделали следующие записи:
• Жюль: Сначала он выпил виски, затем съел утку с апельсинами и десерт;
наконец, он выпил кофе;
ЗАДАЧИ И УПРАЖНЕНИЯ
229
• Жак: Он не пил аперитив; он съел пирог и грушу;
• Джим: Сначала он выпил виски, затем съел пирог и клубничный щербет,
а закончил завтрак чашкой кофе.
Все, что написал один из журналистов — неправда, другой сделал лишь одну ложную запись, а третий — вообще никогда не лжет. Что выбрал человек на десерт?
20. Жан и Пьер время от времени лгут. Жан говорит Пьеру: “Когда я не лгу,
ты тоже не лжешь”. Пьер ему отвечает: “А когда я лгу, ты лжешь”. Возмож- но ли, чтобы во время разговора один из них солгал, а другой — нет?
21. При подготовке к походу ребята высказали следующие суждения:
• если будет холодно или пойдет дождь, то поход не состоится;
• если будет холодно, то пойдет дождь;
• если не будет холодно и поход состоится, то дождя не будет.
Оказалось, что высказанные суждения сводятся к двум простейшим. Какие это суждения?
22. На вопрос, какая погода будет завтра, синоптик ответил:
• если будет мороз, то снег выпадет только при пасмурной погоде;
• если не будет мороза, но пойдет снег, то погода будет пасмурной;
• не будет ни снега, ни дождя, если небо будет ясным;
• Неверно, что если не будет мороза, то для выпадения снега или дождя достаточно наличия пасмурного неба.
Какую погоду предсказал синоптик?
(Указание. Воспользуйтесь минимальным количеством переменных: если высказывание “Погода будет пасмурной” обозначено буквой П, то противо- положное высказывание “Погода будет ясной” следует обозначить через П.)
23. Саша хочет погулять, но на улице собирается дождь. У него возникают сле- дующие соображения:
• если я надену плащ, то, для того чтобы я надел еще и сапоги, необходимо,
чтобы пошел дождь;
• если я надену сапоги или возьму зонт, но не будет дождя, то плащ надевать не надо;
230
Глава 6. АЛГЕБРА ЛОГИКИ
• неверно, что если я не надену плащ, то я обойдусь без сапог и без зонта только тогда, когда не будет дождя;
• для того чтобы я не надел ни сапог, ни плаща и не взял зонт, достаточно,
чтобы не было дождя.
К какому выводу привели Сашу эти соображения?
24. Относительно погоды на следующий день были высказаны следующие сооб- ражения:
• дождь или пасмурная погода бывают только при повышенной влажности;
• для того, чтобы пошел дождь, необходима пасмурная погода;
• ясную погоду без дождя можно ожидать, если воздух будет сухой;
• если не будет дождя, то достаточным условием повышенной влажности будет пасмурная погода;
• повышенная влажность бывает только при ясной погоде; значит, дождя не будет.
Свести эти высказывания к двум простейшим.
25. Андрей, Ваня и Коля собрались в поход. Были высказаны следующие пред- положения:
• Андрей пойдет в поход только тогда, когда пойдут Ваня и Коля;
• Андрей и Коля друзья, а это значит, что они пойдут в поход вместе или же оба останутся дома;
• чтобы Коля пошел в поход, необходимо, чтобы пошел Ваня.
Когда ребята пошли в поход, оказалось, из трех его утверждений истинны только два. Кто из названных ребят пошел в поход?
26. Миша пригласил свою сестру приехать к нему в гости. После этого он полу- чил от нее три сообщения:
• Я приеду в гости, если только со мной поедет папа;
• чтобы я приехала, необходимо, чтобы меня сопровождала мама;
• либо приедем мы с мамой, либо приедет только папа.
1 ... 21 22 23 24 25 26 27 28 29
Когда приехали гости, оказалось, что из этих трех сообщений истинным было только одно. Кто приехал навестить Мишу?
ЗАДАЧИ И УПРАЖНЕНИЯ
231 27. В коробке лежат шары: большие и маленькие, красные и зеленые, светлые и темные. Из коробки нужно достать шар, удовлетворяющий следующим условиям:
• если шар светлый, то он может быть маленьким тогда и только тогда,
когда он красный;
• шар может быть большим и светлым, если он зеленый;
• если шар большой, то, для того чтобы он был зеленым, достаточно, чтобы он был темным.
Свести эти высказывания к двум простейшим.
28. Студенты узнали, что к ним в группу должен прийти новичок, приехавший из другого города. Обсуждая эту новость, они высказали ряд предположе- ний:
• для того, чтобы новичок был добрым, достаточно, чтобы он был умным и сильным;
• если новичок сильный, то он либо глупый, либо злой;
• если новичок умный, то для того чтобы он был добрым, необходимо, чтобы он был сильным.
Когда эти высказывания были сведены к двум простейшим, оказалось, что из этих условий выполнено только одно. После этого было высказано еще одно суждение: “Необходимое условие доброты — это ум. Значит, новичок умный, но слабый”. Каким был новичок?
29. Сотрудники фирмы обсуждали вопрос о предстоящей командировке. Были высказаны следующие суждения:
• если поедут Иванов и Петров, то надо послать и Сидорова;
• Сидоров поедет только при условии, что поедет Иванов; значит, Петрова послать нельзя;
• надо послать Иванова или Петрова.
Директор сказал, что можно выполнить лишь одно из этих предложений.
Кого хотели послать в командировку сотрудники и кого решил послать ди- ректор?
Библиографический список
[1] Акритас А. Основы компьютерной алгебры с приложениями / А. Акритас. —
М. : Мир, 1994. — 544 с. (Гл. 3)
1
[2] Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати. — М. : Наука,
1974. — 368 с. (Гл. 4).
[3] Белов В. В. Теория графов / В. В. Белов, Е. М. Воробьев, В. Е. Шаталов. —
М. : Высш. школа, 1976. — 392 с. (Гл. 4).
[4] Гаврилов Г. П. Задачи и упражнения по дискретной математике / Г. П. Гав- рилов, А. А. Сапоженко. — М. : ФИЗМАТЛИТ, 2005. — 416 с. (Гл. 4–6).
[5] Гиндикин С. Г. Алгебра логики в задачах / С. Г. Гиндикин. — М. : Наука,
1972. — 288 с. (Гл. 6).
[6] Горбатов В. А. Фундаментальные основы дискретной математики / В. А. Гор- батов. — М. : ФИЗМАТЛИТ, 2000. — 544 с. (Гл. 1, 2, 4, 6).
[7] Деньдобренко Б. Н. Автоматизация конструирования РЭА / Б. Н. Деньдоб- ренко, А. С. Малика. — М. : Высш. школа, 1980. — 384 с. (Гл. 4).
[8] Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. — М. :
ФИЗМАТЛИТ, 2011. — 356 с. (Гл. 1, 2, 6).
[9] Кнут Д. Искусство программирования для ЭВМ. Т. 1 / Д. Кнут. — М. :
Вильямс, 2011. — 712 с. (Гл. 4).
[10] Кнут Д. Искусство программирования для ЭВМ. Т. 2 / Д. Кнут. — М. :
Вильямс, 2007. — 828 с. (Гл. 4).
[11] Кнут Д. Искусство программирования для ЭВМ. Т. 3 / Д. Кнут. — М. :
Вильямс, 2007. — 822 с. (Гл. 4).
[12] Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофи- дес. — М. : Мир, 1978. — 432 с. (Гл. 4).
1
В скобках указаны номера глав настоящего учебника, при работе над которыми эта литература может оказаться полезной.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
233
[13] Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов. —
СПб. : Лань, 2009. – 400 с. (Гл. 1, 2, 4, 6).
[14] Кук Д. Компьютерная математика / Д. Кук, Г. Бейз. — М. : Наука, 1990. —
384 с. (Гл. 1–4).
[15] Курейчик В. М. Математическое обеспечение конструкторского и техноло- гического проектирования с применением САПР / В. М. Курейчик. — М. :
Радио и связь, 1990. — 352 с. (Гл. 4).
[16] Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л. Л. Максимова. — М. : ФИЗМАТЛИТ, 2006. —
256 с. (Гл. 1, 2, 6).
[17] Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов,
Р. И. Тышкевич. — М. : Наука, 1990. — 384 с. (Гл. 4).
[18] Липский В. Комбинаторика для программистов / В. Липский. — М. : Мир,
1988. — 213 с. (Гл. 4, 5).
[19] Логический подход к искусственному интеллекту: От классической логики к логическому программированию / А. Тейз и др. — М. : Мир, 1990. — 429 с.
(Гл. 4).
[20] Мадер В.В. Школьнику об алгебре логики / В. В. Мадер. — М. : Просвещение,
1993. — 128 с. (Гл. 6)
[21] Мендельсон Э. Введение в математическую логику / Э. Мендельсон. — М. :
Наука, 1984. — 320 с. (Гл. 1, 2).
[22] Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипо- ва. — М. : Изд-во МАИ, 1992. — 264 с. (Гл. 1, 2, 4–6).
[23] Новиков Ф. А. Дискретная математика для программистов / Ф. А. Нови- ков. — СПб : Питер, 2013. — 432 с. (Гл. 1, 2, 4–6).
[24] Общая алгебра / О. В. Мельников и др.; Под ред. Л. А. Скорнякова. — М. :
Наука, 1990. — Т. 1. — 592 с. (Гл. 1, 2).
[25] Общая алгебра / В. А. Артамонов и др.; Под ред. Л. А. Скорнякова. — М. :
Наука, 1990. — Т. 2 — 479 с. (Гл. 1, 2).
[26] Оре О. Теория графов / О. Оре. — М. : УРСС, 2009. — 354 с. (Гл. 4).
234
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
[27] Рейнгольд Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд,
Ю. Нивергельт, Н. Део. — М. : Мир, 1980. — 476 с. (Гл. 4, 5).
[28] Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. — М. :
Мир, 1984. — 454 с. (Гл. 4).
[29] Столл Р. Множества. Логика. Аксиоматические теории / Р. Столл. — М. :
Просвещение, 1968. — 232 с. (Гл. 1, 2, 6).
[30] Фридман А. Теория и проектирование переключательных схем / А. Фридман,
П. Менон. — М. : Мир, 1978. — 580 с. (Гл. 6).
[31] Фудзисава Т. Математика для радиоинженеров: Теория дискретных струк- тур / Т. Фудзисава, Т. Касами. — М. : Радио и связь, 2012. — 242 с. (Гл. 1, 2,
4–6).
[32] Харари Ф. Теория графов / Ф. Харари. — М. : УРСС, 2015. — 304 с. (Гл. 4).
[33] Холл М. Комбинаторика / М. Холл. — М. : Мир, 1970. — 424 с. (Гл. 5).
[34] Чень Ч. Математическая логика и автоматическое доказательство теорем /
Ч. Чень, Р. Ли. — М. : Наука, 1983. — 360 с. (Гл. 6).
[35] Шенфилд Дж. Математическая логика / Дж. Шенфилд. — М. : Наука,
1975. — 528 с. (Гл. 1, 2, 6).
[36] Яблонский С. В. Введение в дискретную математику / С. В. Яблонский. —
М. : Высшая школа, 2010. — 384 с. (Гл. 4, 6).
П р и л о ж е н и е
Варианты типового расчета
Условия задач
1. Докажите тождества, используя только определения операций над мно- жествами.
2. Докажите методом математической индукции.
3. Докажите утверждение.
4. Пусть A = {a, b, c}, B = {1, 2, 3, 4}, P
1
⊆ A × B, P
2
⊆ B
2
. Изобра- зите отношения P
1
и P
2
графически. Найдите [(P
1
◦ P
2
)
−1
]. Проверьте с помощью матрицы [P
2
], является ли отношение P
2
рефлексивным,
симметричным, антисимметричным, транзитивным?
5. Найдите область определения, область значений отношения P . Явля- ется ли отношение P рефлексивным, симметричным, антисимметрич- ным, транзитивным?
6. Является ли алгеброй следующий набор B = hB; Σi?
7. Постройте подсистему B(X), если...
8. Используя многомодульную арифметику с вектором оснований β,
вычислить a + b, a − b, 3 · a, 17
−1
(mod β), 2/13 − 5/19. Каков знак числа x в симметричной системе относительно β?
9. Даны графы G
1
и G
2
. Найдите G
1
∪ G
2
, G
1
∩ G
2
, G
1
⊕ G
2
, G
1
× G
2
. Для графа G
1
∪ G
2
найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.
10. Найдите матрицы фундаментальных циклов, фундаментальных разре- зов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?
11. Составьте таблицы истинности формул.
236
ВАРИАНТЫ ТИПОВОГО РАСЧЕТА
12. Проверьте двумя способами, будут ли эквивалентны следующие фор- мулы...
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
13. С помощью эквивалентных преобразований приведите формулу к ДНФ,
КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
14. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f (x, y, z) двумя способами:
а) методом Квайна;
б) с помощью карт Карно.
Каким классам Поста принадлежит эта функция?
15. С помощью карт Карно найдите сокращенную, все тупиковые и мини- мальные ДНФ, КНФ булевой функции f (x
1
, x
2
, x
3
, x
4
), заданной век- тором своих значений.
16. Является ли полной система функций J? Образует ли она базис?
17. С помощью алгебры логики проверьте истинность соотношения для любых множеств A, B, C. Если соотношение неверно, постройте контр- пример.
18. С помощью алгебры логики докажите первое тождество из задания 1.