Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
∼ xyz ∨ yz; ч) (xyu ∨ xy ∨ yxu)(xu ∨ xyu ∨ x yu) ∼ xu ∨ yu ∨ xy; ш) (x z ∨ z ∨ zu ∨ xy)(z ∨ zu ∨ xu ∨ y z u) ∼ z ∨ u ∨ xy ∨ x y; щ) (yu ∨ xu ∨ xyu ∨ x yu)(x ∨ x u ∨ yu) ∼ x ∨ yu; ы) y ∨ z ∨ x ∨ z ∨ xy ∼ xz ∨ yz; э) x ∨ y(x ∨ z) ∨ yx ∨ z ∼ xy; ю) x ∨ y ∨ z ∨ x ∨ z ∨ xy ∼ xz ∨ yz; я) xz ∨ y ∨ y ∨ yx ∨ z ∼ xy ∨ yz. ЗАДАЧИ И УПРАЖНЕНИЯ 227 4. Привести к ДНФ, КНФ, СДНФ и СКНФ следующие формулы: а) (x ∨ z)(x ∨ yz); б) x ∨ ((x → yz)((z ⊕ u) → xu)); в) ((x | z ↓ x) ⊕ xy) ↔ (z → x); г) x ∨ y ∨ x ∨ y ∨ z ∨ xyz; д) y ∨ z ∨ x ∨ y ∨ z ∨ xyz; е) xy ∨ yz ∨ x ∨ yz ∨ xyz; ж) x ∨ (x ∨ z)y ∨ xy ∨ zxy ∨ x y; з) yz ∨ xyz ∨ (x ∨ y)z ∨ yz ∨ x z; и) x ∨ xyz ∨ y ∨ z(x ∨ y); к) (xyz ∨ x(y ∨ z))z ∨ (x ∨ z)y ∨ xyz; л) xy ∨ zx ∨ y; м) xy ∨ yz ∨ x ∨ y ∨ z; н) y ∨ z ∨ y z ∨ y ∨ xy ∨ xz; о) (x ∨ y)(x ∨ z)(y ∨ z); п) x ∨ y ∨ z ∨ z ∨ x(yz ∨ y z); р) x ∨ z → y ∨ (y ↔ z); с) (x ↔ (y → z)) ∨ x → y ∨ z; т) xyz → x y → x ↔ z; у) x ∨ y → z ↔ z → xy; ф) x ∨ (y ∨ z → x) ↔ x → yz; х) x → y → x → (z → x → y); ц) x → y → z → x(y → z); ч) xyz → yz → (z → xy); ш) x ↔ (z → y) ∨ y → x ∨ y; щ) (z → xy) ↔ (x → yz); ы) z → y → x ↔ xz; э) (z → y → x) → y(z ↔ x); ю) (xy → z → (x ∨ z → xy)) → xy; я) (x → (y ↔ x ∨ z)) → ((y → x ∨ z) → xz). 228 Глава 6. АЛГЕБРА ЛОГИКИ 5. Используя метод Квайна и карты Карно, найти МДНФ и МКНФ следующих формул: а) x y z ∨ xyz ∨ xyz ∨ xyz ∨ xyz; б) y ∨ x z ∨ x ∨ z; в) xz ∨ y z ∨ xy ∨ x ∨ y; г) x ∨ yz ∨ y ∨ z; д) (x → y(x → z)) → y(x ∨ y ↔ z); е) (y → z → x) → (y ∨ z → x → yz); ж) (x → (x ∨ y ↔ z)) → (x ∨ y ↔ yz); з) ((yz ↔ x) → z) → y(x ∨ z ↔ z); и) ((x ↔ yz) → z) → (x ∨ z ↔ y); к) ((x ↔ y ∨ z) → x ∨ z) → (xz ∨ y → x y); л) (z → (x ↔ y ∨ z)) → (xz ∨ y ↔ xyz); м) (xy → z → y) → (xz ↔ x ∨ y); н) (xz → (y ↔ z)) → (x ∨ y → xz); о) ((y ∨ z ↔ xz) → y) → (z → x → xy); п) (yz → x → z) → x(y ↔ z); р) ((y ↔ z) → (x ∨ y → x z)) → yz → x; с) (x → (y ∨ z ↔ x)) → y(z ↔ xy); т) (x ∨ y z → x ∨ z) → y → x ∨ z; у) ((y ∨ z ↔ xz) → xy) → y → x; ф) x ∨ y → z → (x → yz → y(x ↔ z)); х) (xz → (y ↔ z)) → (x ∨ y → x → y ∨ z); ц) (y ∨ z → x) → (z → y → xz); ч) (xy → (x ∨ yz → y)) → (x ∨ z ↔ y ∨ z); ш) (x → (x ∨ z ↔ y)) → (x ∨ z → yz); щ) (y → (x ∨ z → z)) → x(y ↔ xz); ы) ((y ∨ z ↔ x) → y) → (y → x ∨ z → yz → x); э) (xy → (x ∨ z → y)) → (x ∨ z ↔ y ∨ z); ю) (xz → (y ∨ z → x)) → (y ∨ z ↔ xy); я) (xy → z → y) → (z → x ∨ y). ЗАДАЧИ И УПРАЖНЕНИЯ 229 1 1 1 1 1 1 1 1 1 1 1 x y z u x y z u 0 0 0 0 0 0 0 0 0 0 0 0 Рис. 6.31 Рис. 6.32 6. Найти СДНФ и МДНФ по карте Карно, изображенной на рис. 6.31. 7. Найти СКНФ и МКНФ по карте Карно, изображенной на рис. 6.32. 8. Найти полиномы Жегалкина для следующих формул: а) x ↓ y | z; б) (x → y)(y ↓ z); в) x | ((x → y) ∨ z). 9. Найти полином Жегалкина для булевой функции f , заданной следующим вектором значений. Определить, каким классам Поста принадлежит функ- ция f : а) (10110100); б) (10010110); в) (11110101). 10. Проверить с помощью теоремы Поста полноту следующих систем булевых функций: а) {→, ¬}; б) {↔, ⊕}; в) {↓}; г) {∧, →, ⊕}. Какие из указанных систем образуют базис? 11. Среди всех булевых функций от двух переменных (см. § 6.3) найти всевоз- можные базисы, состоящие из одной, двух, трех функций. 12. Состоялся розыгрыш футбольного кубка между командами “Пламя”, “Ре- корд”, “Стрела” и “Трактор”. Было высказано три прогноза: победит “Пла- мя” или “Рекорд”; не победит “Пламя”; не победит ни “Рекорд”, ни “Трактор”. Известно, что подтвердился только один прогноз. Какая команда выиграла кубок? 13. Андрей, Борис, Вова и Саша играли в футбол и разбили окно. Когда их спросили, кто это сделал, были получены следующие ответы. Андрей сказал, что окно разбил не он и не Вова, а играть в футбол предложил Саша. Борис 230 Глава 6. АЛГЕБРА ЛОГИКИ ответил, что окно разбивал не он, а Вова, и добавил, что в футбол он играет лучше, чем Саша. Вова утверждал, что ни он, ни Андрей не разбивали окна, а в футбол на улице он больше не будет играть. Саша заявил, что окно разбил не он, а Вова, и когда он пришел, игра была в полном разгаре. Выяснилось, что каждый из ребят дал два правдивых показания и одно ложное. Кто разбил окно? 14. Три молодые супружеские пары собрались на дружеский ужин. Завязалась беседа. Были высказаны следующие утверждения: • Андрош: Все трое мужчин на пять лет старше своих жен; • Ева: Не стану отрицать, я самая старшая из всех жен; • Имре: Нам с Юлишкой вместе 52 года; • Ласло: Всем шестерым вместе 151 год; • Юлишка: Нам с Ласло вместе 48 лет. Марта была хозяйкой и не смогла принять участие в беседе. Кому сколько лет и кто на ком женат? 15. Пять отпускников встретились в клубе и завели разговор о том, кто где живет: • Амели: Я живу в Акапулько, как и Бенуа, а Пьер живет в Париже; • Бенуа: Я живу в Бресте, Шарль — тоже; Пьер живет в Париже; • Пьер: Я, как и Амели не живу во Франции; Мелани же живет в Мадриде; • Мелани: Мой отец живет в Акапулько, мать в Париже, а сама я живу в Клермон-Ферране; • Шарль: Амели приехала из Акапулько, Бенуа — тоже, а я сам живу в Клермон-Ферране. Известно, что каждый сказал два раза правду и один раз пошутил. Кто где живет? 16. Три брата, Пьер, Поль и Жак, во время отпуска собрали всех своих детей на даче. Вот что каждый из детей сказал: • Изабелла: Мне на три года больше, чем Жану; • Тереза: Моего отца зовут Жаком; • Ив: Мне на 2 года больше, чем Изабелле; ЗАДАЧИ И УПРАЖНЕНИЯ 231 • Мари: Я больше люблю играть с одним из своих кузенов, чем со своим братом; • Катрин: Моего отца зовут Пьером; • Анна: Лучше всего мы ладим с сыновьями дяди Жака; • Жан: Мой отец и каждый из его братьев имеют меньше, чем по четыре ребенка; • Франсуа: А у моего отца их меньше всего. Кто чей отец? 17. Перед выборами три брата вели долгую дискуссию, которую закончили сле- дующими довольно запутанными высказываниями: • Пьер: Если Жан проголосует за Дюбуа, я буду голосовать за Дюпона; но если он проголосует за Дюпона, я буду голосовать за Дюбуа; если Жак проголосует за Дюпона, я тоже буду голосовать за Дюпона; • Жан: Если Пьер проголосует за Дюпона, я не буду голосовать за Дюпона; но если Жак проголосует за Дюбуа, то я проголосую за Дюпона; • Жак: Если Пьер проголосует за Дюпона, то я не буду голосовать за Дю- пона. Подошел день выборов. Все братья проголосовали за разных кандидатов. За кого именно? 18. Произошла кража, и было задержано трое подозреваемых. Один из них (вор) всегда лжет; другой (соучастник) иногда лжет, а иногда говорит правду; по- следний (подозреваемый напрасно) вообще никогда не лжет. Дознание нача- лось с вопросов о профессии. Их ответы были таковы: • Бертран: Я маляр, Альфред — настройщик роялей, а Шарль — декоратор; • Альфред: Я врач, Шарль — страховой агент; что касается Бертрана, то ес- ли вы его спросите, он ответит, что он маляр; • Шарль: Альфред настраивает рояли, Бертран — декоратор, а я страховой агент. Какова профессия соучастника? 19. Три журналиста во время завтрака наблюдали за одним человеком. При этом они сделали следующие записи: • Жюль: Сначала он выпил виски, затем съел утку с апельсинами и десерт; наконец, он выпил кофе; 232 Глава 6. АЛГЕБРА ЛОГИКИ • Жак: Он не пил аперитив; он съел пирог и грушу; • Джим: Сначала он выпил виски, затем съел пирог и клубничный щербет, а закончил завтрак чашкой кофе. Все, что написал один из журналистов — неправда, другой сделал лишь одну ложную запись, а третий — вообще никогда не лжет. Что выбрал человек на десерт? 20. Жан и Пьер время от времени лгут. Жан говорит Пьеру: “Когда я не лгу, ты тоже не лжешь”. Пьер ему отвечает: “А когда я лгу, ты лжешь”. Возмож- но ли, чтобы во время разговора один из них солгал, а другой — нет? 21. При подготовке к походу ребята высказали следующие суждения: • если будет холодно или пойдет дождь, то поход не состоится; • если будет холодно, то пойдет дождь; • если не будет холодно и поход состоится, то дождя не будет. Оказалось, что высказанные суждения сводятся к двум простейшим. Какие это суждения? 22. На вопрос, какая погода будет завтра, синоптик ответил: • если будет мороз, то снег выпадет только при пасмурной погоде; • если не будет мороза, но пойдет снег, то погода будет пасмурной; • не будет ни снега, ни дождя, если небо будет ясным; • Неверно, что если не будет мороза, то для выпадения снега или дождя достаточно наличия пасмурного неба. Какую погоду предсказал синоптик? (Указание. Воспользуйтесь минимальным количеством переменных: если высказывание “Погода будет пасмурной” обозначено буквой П, то противо- положное высказывание “Погода будет ясной” следует обозначить через П.) 23. Саша хочет погулять, но на улице собирается дождь. У него возникают сле- дующие соображения: • если я надену плащ, то, для того чтобы я надел еще и сапоги, необходимо, чтобы пошел дождь; • если я надену сапоги или возьму зонт, но не будет дождя, то плащ надевать не надо; ЗАДАЧИ И УПРАЖНЕНИЯ 233 • неверно, что если я не надену плащ, то я обойдусь без сапог и без зонта только тогда, когда не будет дождя; • для того чтобы я не надел ни сапог, ни плаща и не взял зонт, достаточно, чтобы не было дождя. К какому выводу привели Сашу эти соображения? 24. Относительно погоды на следующий день были высказаны следующие сооб- ражения: • дождь или пасмурная погода бывают только при повышенной влажности; • для того, чтобы пошел дождь, необходима пасмурная погода; • ясную погоду без дождя можно ожидать, если воздух будет сухой; • если не будет дождя, то достаточным условием повышенной влажности будет пасмурная погода; • повышенная влажность бывает только при ясной погоде; значит, дождя не будет. Свести эти высказывания к двум простейшим. 25. Андрей, Ваня и Коля собрались в поход. Были высказаны следующие пред- положения: • Андрей пойдет в поход только тогда, когда пойдут Ваня и Коля; • Андрей и Коля друзья, а это значит, что они пойдут в поход вместе или же оба останутся дома; • чтобы Коля пошел в поход, необходимо, чтобы пошел Ваня. Когда ребята пошли в поход, оказалось, из трех его утверждений истинны только два. Кто из названных ребят пошел в поход? 26. Миша пригласил свою сестру приехать к нему в гости. После этого он полу- чил от нее три сообщения: • Я приеду в гости, если только со мной поедет папа; • чтобы я приехала, необходимо, чтобы меня сопровождала мама; • либо приедем мы с мамой, либо приедет только папа. Когда приехали гости, оказалось, что из этих трех сообщений истинным было только одно. Кто приехал навестить Мишу? 234 Глава 6. АЛГЕБРА ЛОГИКИ 27. В коробке лежат шары: большие и маленькие, красные и зеленые, светлые и темные. Из коробки нужно достать шар, удовлетворяющий следующим условиям: • если шар светлый, то он может быть маленьким тогда и только тогда, когда он красный; • шар может быть большим и светлым, если он зеленый; • если шар большой, то, для того чтобы он был зеленым, достаточно, чтобы он был темным. Свести эти высказывания к двум простейшим. 28. Студенты узнали, что к ним в группу должен прийти новичок, приехавший из другого города. Обсуждая эту новость, они высказали ряд предположе- ний: • для того, чтобы новичок был добрым, достаточно, чтобы он был умным и сильным; • если новичок сильный, то он либо глупый, либо злой; • если новичок умный, то для того чтобы он был добрым, необходимо, чтобы он был сильным. Когда эти высказывания были сведены к двум простейшим, оказалось, что из этих условий выполнено только одно. После этого было высказано еще одно суждение: “Необходимое условие доброты — это ум. Значит, новичок умный, но слабый”. Каким был новичок? 29. Сотрудники фирмы обсуждали вопрос о предстоящей командировке. Были высказаны следующие суждения: • если поедут Иванов и Петров, то надо послать и Сидорова; • Сидоров поедет только при условии, что поедет Иванов; значит, Петрова послать нельзя; • надо послать Иванова или Петрова. Директор сказал, что можно выполнить лишь одно из этих предложений. Кого хотели послать в командировку сотрудники и кого решил послать ди- ректор? Библиографический список [1] Акритас А. Основы компьютерной алгебры с приложениями / А. Акритас. — М. : Мир, 1994. — 544 с. (Гл. 3) 1 [2] Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати. — М. : Наука, 1974. — 368 с. (Гл. 4). [3] Белов В. В. Теория графов / В. В. Белов, Е. М. Воробьев, В. Е. Шаталов. — М. : Высш. школа, 1976. — 392 с. (Гл. 4). [4] Гаврилов Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А. А. Сапоженко. — М. : Наука, 1977. — 368 с. (Гл. 4–6). [5] Гаврилов Г. П. Задачи и упражнения по курсу дискретной математики / Г. П. Гаврилов, А. А. Сапоженко. — М. : Наука, 1992. — 408 с. (Гл. 4–6). [6] Гиндикин С. Г. Алгебра логики в задачах / С. Г. Гиндикин. — М. : Наука, 1972. — 288 с. (Гл. 6). [7] Горбатов В. А. Фундаментальные основы дискретной математики / В. А. Гор- батов. — М. : Физматлит, 2000. — 544 с. (Гл. 1, 2, 4, 6). [8] Деньдобренко Б. Н. Автоматизация конструирования РЭА / Б. Н. Деньдоб- ренко, А. С. Малика. — М. : Высш. школа, 1980. — 384 с. (Гл. 4). [9] Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. — М. : ФИЗМАТЛИТ, 2011. — 356 с. (Гл. 1, 2, 6). [10] Кнут Д. Искусство программирования для ЭВМ. Т. 1 / Д. Кнут. — М. : Мир, 1976. — 735 с. (Гл. 4). [11] Кнут Д. Искусство программирования для ЭВМ. Т. 2 / Д. Кнут. — М. : Мир, 1977. — 724 с. (Гл. 4). [12] Кнут Д. Искусство программирования для ЭВМ. Т. 3 / Д. Кнут. — М. : Мир, 1978. — 844 с. (Гл. 4). 1 В скобках указаны номера глав настоящего учебника, при работе над которыми эта литература может оказаться полезной. 236 БИБЛИОГРАФИЧЕСКИЙ СПИСОК [13] Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофи- дес. — М. : Мир, 1978. — 432 с. (Гл. 4). [14] Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов, Г. М. Адельсон-Вельский. — М. : Энергия, 1980. – 342 с. (Гл. 1, 2, 4, 6). [15] Кук Д. Компьютерная математика / Д. Кук, Г. Бейз. — М. : Наука, 1990. — 384 с. (Гл. 1–4). [16] Курейчик В. М. Математическое обеспечение конструкторского и техноло- гического проектирования с применением САПР / В. М. Курейчик. — М. : Радио и связь, 1990. — 352 с. (Гл. 4). [17] Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л. Л. Максимова. — М. : ФИЗМАТЛИТ, 2001. — 256 с. (Гл. 1, 2, 6). [18] Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М. : Наука, 1990. — 384 с. (Гл. 4). [19] Липский В. Комбинаторика для программистов / В. Липский. — М. : Мир, 1988. — 213 с. (Гл. 4, 5). [20] Логический подход к искусственному интеллекту: От классической логики к логическому программированию / А. Тейз и др. — М. : Мир, 1990. — 429 с. (Гл. 4). [21] Мадер В.В. Школьнику об алгебре логики / В. В. Мадер. — М. : Просвещение, 1993. — 128 с. (Гл. 6) [22] Мендельсон Э. Введение в математическую логику / Э. Мендельсон. — М. : Наука, 1984. — 320 с. (Гл. 1, 2). [23] Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипо- ва. — М. : Изд-во МАИ, 1992. — 264 с. (Гл. 1, 2, 4–6). [24] Новиков Ф. А. Дискретная математика для программистов / Ф. А. Нови- ков. — СПб : Питер, 2001. — 304 с. (Гл. 1, 2, 4–6). [25] Общая алгебра / О. В. Мельников и др.; Под ред. Л. А. Скорнякова. — М. : Наука, 1990. — Т. 1. — 592 с. (Гл. 1, 2). БИБЛИОГРАФИЧЕСКИЙ СПИСОК 237 [26] Общая алгебра / В. А. Артамонов и др.; Под ред. Л. А. Скорнякова. — М. : Наука, 1990. — Т. 2 — 479 с. (Гл. 1, 2). [27] Оре О. Теория графов / О. Оре. — М. : Наука, 1968. — 336 с. (Гл. 4). [28] Рейнгольд Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. — М. : Мир, 1980. — 476 с. (Гл. 4, 5). [29] |