Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
Кто похитил автомобиль? 6.13. ЛОГИЧЕСКИЕ ЗАДАЧИ 221 Решение. Обозначим высказывания “Андре украл”, “Боб украл”, “Стив украл”, “Том украл” через А, Б, С и Т соответственно. Тогда показания ганг- стеров имеют вид Б, Т, Т, С. Поскольку только один из гангстеров сказал правду, имеет место истинная формула ϕ БT T С ∨ БTT С ∨ Б T T С∨ ∨Б T T С. В этой формуле первый и четвертый конъюнкты тождественно ложны (так как содержат T T). Поэтому ϕ ∼ БTTС∨Б T TС ∼ БTС∨Б TС ∼ ∼ Б ∧ С. Поскольку имеет место Б и С, автомобиль украл Стив. ¤ Минимизация КНФ зачастую позволяет свести серию сложных условий к достаточно простым. Пример 6.13.2. В институте решили организовать гимнастическую сек- цию и понадобилось разработать правила приема в эту секцию. Студенты внесли несколько предложений: • если студент не здоров и не отличник, то он не может быть принят; • если студент является отличником, то не может быть, чтобы он был здоров и его не приняли; • если студент не здоров, то он не отличник и не будет принят; • если студент не принят, то он не отличник. Оказалось, что внесенные предложения сводятся двум простым и есте- ственным правилам (которые и были взяты за основу). Действительно, рас- смотрим элементарные высказывания: З — студент здоров, О — студент яв- ляется отличником, П — студент принят в секцию. Тогда внесенные предло- жения записываются и преобразуются следующим образом: З О → П ∼ З О ∨ П ∼ З ∨ О ∨ П ∼ З ∨ О ∨ П; О → ЗП ∼ О ∨ З ∨ П ∼ О ∨ З ∨ П; З → О П ∼ З ∨ О П ∼ З ∨ О П; П → О ∼ П ∨ О. Конъюнкция ϕ полученных формул составляет описание внесенных предло- жений. Минимальная ДНФ для формулы ϕ имеет вид ЗП ∨ П О, что соот- ветствует предложению “Студент здоров и принят, или не принят и не явля- ется отличником”. Вместе с тем, МКНФ формулы ϕ представляется в виде (О ∨ П)(П ∨ З), что эквивалентно формуле (О → П)(П → З). Последняя формула и соответствует двум искомым правилам: • если студент является отличником, то он будет принят в секцию; • если студент принят, то необходимо, чтобы он был здоров. ¤ 222 Глава 6. АЛГЕБРА ЛОГИКИ Задачи и упражнения 1. Составить таблицы истинности формул: а) (y → x ∨ z) ∨ (x ∨ y → z); б) x | y ↓ z | y ↓ x; в) (x → y) ⊕ (y → z) ⊕ (z → x); г) x ⊕ y → z ∨ x | y ∧ x; д) (x ∨ y → zu) → x ∨ y; е) x ∨ yz → zu ∨ y; ж) (xz → y ∨ u) ∨ ((x → u ∨ z) → y); з) (x ∨ y → z) ∨ (u → yz ∨ x); и) (z → x ∨ y) → (z ∨ u → xy); к) (x ∨ yz → u) → (y → xz ∨ u); л) (z ∨ yu → x) ∨ (y ∨ z → u); м) (x ∨ y ↔ xz) → x ∨ z; н) x | (y → z) ↓ (z ⊕ x → y); о) x | y | z → x ↓ y ↓ z; п) x → z ⊕ (y ⊕ z)(x ⊕ y); р) x ⊕ y ⊕ z ↔ x ↓ z; с) (x ⊕ y | z) → (x ⊕ y) | (x ⊕ z); т) (x ⊕ y → z) → (x → y ⊕ z); у) xy ↓ z → x ↓ y; ф) x(y ↓ z) → xy) ↓ z; х) x ∨ y | z → (x ∨ y) | z; ц) x ∨ y ↓ z → xy | z. 2. Установить, какие из следующих формул являются тождественно истинны- ми и какие — тождественно ложными: а) (x → y) → ((x → z) → (x → y ∧ z)); б) (x → y) → ((x ∧ z) → (y ∨ z)); в) (x ⊕ y ↔ z)(x → yz); г) xyz((x ∨ y)z → (x ↔ z ⊕ y)); д) (x ∨ y) ↓ (x ⊕ y) ⊕ (x → y → (x ∨ y)). ЗАДАЧИ И УПРАЖНЕНИЯ 223 3. Проверить эквивалентности: а) xy ∨ zu ∼ (x ∨ z)(x ∨ u)(y ∨ z)(y ∨ u); б) x ∧ (x ∨ z) ∧ (y ∨ z) ∼ (x ∧ y) ∨ (x ∧ z); в) xy ∨ xz ∨ yz ∨ z ∼ x ∨ y; г) (x ∨ xy ∨ xy)(x ∨ xz ∨ xy ∨ xyz) ∼ x ∨ y; д) (x ∨ y ∨ zx ∨ y ∨ yx ∨ u)(x ∨ xz ∨ xyz) ∼ x ∨ z; е) (xy ∨ xyz ∨ xz)(x ∨ xz ∨ yx ∨ z) ∼ x ∨ z; ж) (x ∨ xy ∨ yzu ∨ xu)(y ∨ yu ∨ yz(x ∨ u)) ∼ y ∨ u; з) xyz(x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ yz)(xy ∨ yz) ∼ xyz; и) xyz(x ∨ xyz ∨ z)(xz ∨ zu ∨ u)(xz ∨ yu) ∼ xyz; к) (x ∨ xy ∨ y(z ∨ u))(yu ∨ x y u ∨ xu ∨ xy)yz ∼ yz; л) xy ∨ xyz ∨ xzu ∨ xyu ∨ xu z ∼ x ∨ z; м) xz ∨ x zu ∨ yzu ∨ xyz ∨ zu ∼ x ∨ z ∨ u; о) yz ∨ xyz ∨ xzu ∨ xzu ∨ xzu ∼ x ∨ z; п) xu ∨ xyu ∨ xzu ∨ xyu ∨ yu ∼ y ∨ u; р) x yz ∨ xyz ∨ xy z ∨ xyz ∨ x z ∼ y ∨ z; с) xy z ∨ xyz ∨ yzu ∨ yz ∨ yzu ∼ x ∨ z; т) x yz ∨ xyz ∨ xyz ∨ xyz ∼ z; у) (xz ∨ xy z ∨ xyz ∨ xz)(zu ∨ zu ∨ xyz) ∼ z; ф) (xyz ∨ xyz ∨ yz ∨ xyz)(x ∨ xy ∨ x yz) ∼ x ∨ y; х) (xy ∨ xz ∨ xy ∨ x y z)(x y ∨ yxz ∨ xzu ∨ xzu) ∼ x ∨ y; ц) (yz ∨ xyz ∨ xyz)(xy ∨ x y ∨ xyz) ∼ 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. 224 Глава 6. АЛГЕБРА ЛОГИКИ 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). ЗАДАЧИ И УПРАЖНЕНИЯ 225 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). 226 Глава 6. АЛГЕБРА ЛОГИКИ 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. Андрей, Борис, Вова и Саша играли в футбол и разбили окно. Когда их спросили, кто это сделал, были получены следующие ответы. Андрей сказал, что окно разбил не он и не Вова, а играть в футбол предложил Саша. Борис ЗАДАЧИ И УПРАЖНЕНИЯ 227 ответил, что окно разбивал не он, а Вова, и добавил, что в футбол он играет лучше, чем Саша. Вова утверждал, что ни он, ни Андрей не разбивали окна, а в футбол на улице он больше не будет играть. Саша заявил, что окно разбил не он, а Вова, и когда он пришел, игра была в полном разгаре. Выяснилось, что каждый из ребят дал два правдивых показания и одно ложное. Кто разбил окно? 14. Три молодые супружеские пары собрались на дружеский ужин. Завязалась беседа. Были высказаны следующие утверждения: • Андрош: Все трое мужчин на пять лет старше своих жен; • Ева: Не стану отрицать, я самая старшая из всех жен; • Имре: Нам с Юлишкой вместе 52 года; • Ласло: Всем шестерым вместе 151 год; • Юлишка: Нам с Ласло вместе 48 лет. Марта была хозяйкой и не смогла принять участие в беседе. Кому сколько лет и кто на ком женат? 15. Пять отпускников встретились в клубе и завели разговор о том, кто где живет: • Амели: Я живу в Акапулько, как и Бенуа, а Пьер живет в Париже; • Бенуа: Я живу в Бресте, Шарль — тоже; Пьер живет в Париже; • Пьер: Я, как и Амели не живу во Франции; Мелани же живет в Мадриде; • Мелани: Мой отец живет в Акапулько, мать в Париже, а сама я живу в Клермон-Ферране; • Шарль: Амели приехала из Акапулько, Бенуа — тоже, а я сам живу в Клермон-Ферране. Известно, что каждый сказал два раза правду и один раз пошутил. Кто где живет? 16. Три брата, Пьер, Поль и Жак, во время отпуска собрали всех своих детей на даче. Вот что каждый из детей сказал: • Изабелла: Мне на три года больше, чем Жану; • Тереза: Моего отца зовут Жаком; • Ив: Мне на 2 года больше, чем Изабелле; 228 Глава 6. АЛГЕБРА ЛОГИКИ • Мари: Я больше люблю играть с одним из своих кузенов, чем со своим братом; • Катрин: Моего отца зовут Пьером; • Анна: Лучше всего мы ладим с сыновьями дяди Жака; • Жан: Мой отец и каждый из его братьев имеют меньше, чем по четыре ребенка; • Франсуа: А у моего отца их меньше всего. Кто чей отец? 17. Перед выборами три брата вели долгую дискуссию, которую закончили сле- дующими довольно запутанными высказываниями: • Пьер: Если Жан проголосует за Дюбуа, я буду голосовать за Дюпона; но если он проголосует за Дюпона, я буду голосовать за Дюбуа; если Жак проголосует за Дюпона, я тоже буду голосовать за Дюпона; • Жан: Если Пьер проголосует за Дюпона, я не буду голосовать за Дюпона; но если Жак проголосует за Дюбуа, то я проголосую за Дюпона; • Жак: Если Пьер проголосует за Дюпона, то я не буду голосовать за Дю- пона. Подошел день выборов. Все братья проголосовали за разных кандидатов. За кого именно? 18. Произошла кража, и было задержано трое подозреваемых. Один из них (вор) всегда лжет; другой (соучастник) иногда лжет, а иногда говорит правду; по- следний (подозреваемый напрасно) вообще никогда не лжет. Дознание нача- лось с вопросов о профессии. Их ответы были таковы: • Бертран: Я маляр, Альфред — настройщик роялей, а Шарль — декоратор; • Альфред: Я врач, Шарль — страховой агент; что касается Бертрана, то ес- ли вы его спросите, он ответит, что он маляр; • Шарль: Альфред настраивает рояли, Бертран — декоратор, а я страховой агент. Какова профессия соучастника? 19. Три журналиста во время завтрака наблюдали за одним человеком. При этом они сделали следующие записи: • Жюль: Сначала он выпил виски, затем съел утку с апельсинами и десерт; наконец, он выпил кофе; ЗАДАЧИ И УПРАЖНЕНИЯ 229 • Жак: Он не пил аперитив; он съел пирог и грушу; • Джим: Сначала он выпил виски, затем съел пирог и клубничный щербет, а закончил завтрак чашкой кофе. Все, что написал один из журналистов — неправда, другой сделал лишь одну ложную запись, а третий — вообще никогда не лжет. Что выбрал человек на десерт? 20. Жан и Пьер время от времени лгут. Жан говорит Пьеру: “Когда я не лгу, ты тоже не лжешь”. Пьер ему отвечает: “А когда я лгу, ты лжешь”. Возмож- но ли, чтобы во время разговора один из них солгал, а другой — нет? 21. При подготовке к походу ребята высказали следующие суждения: • если будет холодно или пойдет дождь, то поход не состоится; • если будет холодно, то пойдет дождь; • если не будет холодно и поход состоится, то дождя не будет. Оказалось, что высказанные суждения сводятся к двум простейшим. Какие это суждения? 22. На вопрос, какая погода будет завтра, синоптик ответил: • если будет мороз, то снег выпадет только при пасмурной погоде; • если не будет мороза, но пойдет снег, то погода будет пасмурной; • не будет ни снега, ни дождя, если небо будет ясным; • Неверно, что если не будет мороза, то для выпадения снега или дождя достаточно наличия пасмурного неба. Какую погоду предсказал синоптик? (Указание. Воспользуйтесь минимальным количеством переменных: если высказывание “Погода будет пасмурной” обозначено буквой П, то противо- положное высказывание “Погода будет ясной” следует обозначить через П.) 23. Саша хочет погулять, но на улице собирается дождь. У него возникают сле- дующие соображения: • если я надену плащ, то, для того чтобы я надел еще и сапоги, необходимо, чтобы пошел дождь; • если я надену сапоги или возьму зонт, но не будет дождя, то плащ надевать не надо; 230 Глава 6. АЛГЕБРА ЛОГИКИ • неверно, что если я не надену плащ, то я обойдусь без сапог и без зонта только тогда, когда не будет дождя; • для того чтобы я не надел ни сапог, ни плаща и не взял зонт, достаточно, чтобы не было дождя. К какому выводу привели Сашу эти соображения? 24. Относительно погоды на следующий день были высказаны следующие сооб- ражения: • дождь или пасмурная погода бывают только при повышенной влажности; • для того, чтобы пошел дождь, необходима пасмурная погода; • ясную погоду без дождя можно ожидать, если воздух будет сухой; • если не будет дождя, то достаточным условием повышенной влажности будет пасмурная погода; • повышенная влажность бывает только при ясной погоде; значит, дождя не будет. Свести эти высказывания к двум простейшим. 25. Андрей, Ваня и Коля собрались в поход. Были высказаны следующие пред- положения: • Андрей пойдет в поход только тогда, когда пойдут Ваня и Коля; • Андрей и Коля друзья, а это значит, что они пойдут в поход вместе или же оба останутся дома; • чтобы Коля пошел в поход, необходимо, чтобы пошел Ваня. Когда ребята пошли в поход, оказалось, из трех его утверждений истинны только два. Кто из названных ребят пошел в поход? 26. Миша пригласил свою сестру приехать к нему в гости. После этого он полу- чил от нее три сообщения: • Я приеду в гости, если только со мной поедет папа; • чтобы я приехала, необходимо, чтобы меня сопровождала мама; • либо приедем мы с мамой, либо приедет только папа. |