Неверно что ветер дует тогда и только тогда когда нет дождя

f (x,у) = x Ú у

3) Конъюнкция (логическое умножение).

Соответствующие выражения языка:

· Х в то время, как Y

f (x,у) = x & у

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

4) Импликация (логическое следование).

Соответствующие выражения языка:

· Х достаточно для Y

· Y необходимо для Х

f (x) = x ® у

Построим таблицу истинности, для импликации используя выражение – не может из «истины» следовать «ложь».

Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.

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

Будем упрощать аналитически, используя закон логического склеивания.

5) Эквивалентность (логическая равнозначность ).

Соответствующие выражения языка:

· Х необходимо и достаточно для Y

· Х тогда и только тогда, когда Y

· Х такое же, как и Y

f (x) = x

Построим таблицу истинности, подставляя в значения эквивалентности «Да», если А и В принимают одинаковые значения и «Нет» в случае различных А и В.

Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.

Минимизацию двоичной функции произведем на основании закона де Моргана.

6) Построение одноразрядного двоичного сумматора.

Минимизировать z не представляется возможным, для представления z используют совершенную конъюнктивную нормальную форму (СКНФ).

Для всех наборов переменных, для которых функция равна нулю, записать дизъюнкции, инвертируя те переменные, которым соответствуют единичные значения, затем соединить дизъюнкции знаком конъюнкции.

Для дальнейшего упрощения воспользуемся законом де Моргана:

Решение логических (содержательных) задач

Одним из разделов логики является алгебра высказываний.

Высказывание – это предложение, о котором однозначно можно сказать истинно оно или ложно. Бывают простые и сложные (составные).

Основная задача – на основании истинности или ложности простых высказываний определить истинность и ложность составных высказываний.

Пример 1: Я поеду в Москву и если встречу там друзей, то интересно проведем время.

Решение: М – я поеду в Москву

В – я встречу там друзей М × ( В ® И )

И – мы интересно проведем там время

Пример2: Если я поеду в Москву и встречу там друзей, то интересно проведем время.
Решение: М × В ® И

Пример 3: Не верно, что если дует ветер, то солнце светит только тогда, когда нет дождя.

Решение: В – дует ветер

Д – идет дождь

П – солнечная погода

Пример 5: Не верно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра.

Решение: Д – идет дождь

П – пасмурная погода

Решение логических задач

I способ – с помощью таблиц истинности

Пример 6: Компьютер вышел из строя (нет изображения на экране монитора), однако неизвестно какое устройство не работает (монитор, видеокарта или оперативная память). Можно предположить следующее:

1) если монитор исправен или видео карта несправна, то оперативная память неисправна;

2) если монитор исправен, то оперативная память исправна.

Исправен ли монитор?

1. рассмотрим простые высказывания:

М = Монитор неисправен

В = Видеокарта неисправна

О = Оперативная память неисправна

2. Запишем на языке алгебры логики наши предположения:

3. Пусть F (М,В,О) =

4. Решить данную задачу – значит :

— составить таблицу истинности

— указать, при каких значениях М полученное сложное высказывание истинно.

Необходимо проанализировать все строки таблицы истинности, где F =1.

5. Составим для данного высказывания таблицу истинности: (самостоятельно)

Анализ таблицы показывает, что сложное высказывание истинно во всех случаях, когда М – истинно, т.е. вероятнее всего неисправен именно монитор.

II способ – с помощью преобразования логических выражений

Пример 7: Виктор, Роман, Леонид и Сергей заняли на математической олимпиаде четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:

1) Сергей – первый или Роман – второй

2) Сергей – второй или Виктор – третий

3) Леонид – второй или Виктор – четвертый.

Известно, что в каждом ответе только одно утверждение истинно.

Как распределились места?

Рассмотрим простые высказывания

S 1 = Сергей занял первое место

R 2 = Роман занял второе место

S 2 = Сергей занял второе место

V3 = Виктор занял третье место

L2 = Леонид занял второе место

V4 = Виктор занял четвертое место

На языке алгебры логики ответы ребят можно записать следующим образом:

Конъюнкция истинных высказываний истинна. Следовательно, имеет место равенство:

Раскрыв скобки и упростив это равенство (выполнить самостоятельно), получим:

Другими словами, места на олимпиаде распределились так:

Источник

Решение логических задач методами алгебры логики

Пример 1. Рассмотрим следующее «рассуждение»: «Если число 5 – простое, то оно нечетное. Число 5 – нечетное, следовательно, оно простое». Число 5 действительно простое, но сами рассуждения неверны. Введем обозначения для высказываний: х – «5 – число простое», y – «5 – число нечетное». Тогда посылками будут заключением будет х. Рассуждения шли по схеме Строим формулу для определения правильности рассуждения: Проверим,

На наборе х = 0, y = 1 формула принимает значение 0, следовательно, она не является тавтологией. Эта формула будет тавтологией, если х = y, т.е. простое число и нечетное число – эквивалентные понятия. «Здравый смысл подсказывает», что в этом случае, действительно, рассуждения верны.

Пример 2. Если Петр занимается спортом, то Петр никогда не болеет. Петр занимается спортом, следовательно, он не болеет.

Введем обозначения для высказываний: x – «Петр занимается спортом», y – «Петр не болеет».

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

Распространенные схемы правильных рассуждений: и . Правильность первой схемы доказана в примере 2.

Докажем правильность второй схемы:

Рассмотрим высказывание вида где А – конъюнкция посылок, В – заключение. Если формула А – тавтология и рассуждения логически правильны, то заключение В принимает значение «истина», что следует из таблицы истинности для импликации. Такие методы доказательства истинности заключения называются прямыми. Иногда удобнее доказать истинность другого высказывания, эквивалентного данному. Такие формы доказательства называются косвенными. Одним из них является метод доказательства от противного.

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

2. Существуют и другие схемы доказательства от противного. Предполагаем, что из следует и приходим к тому, что истинными оказываются и или и . Эти схемы основаны на эквивалентности или .

Действительно, и

Другой метод косвенного доказательства – доказательство по закону контрапозиции, когда вместо истинности мы доказываем истинность . Действительно,

Рассмотрим на конкретных задачах применение исчисления высказываний.

Пример 3. Записать составное высказывание в виде формулы, употребляя булевы переменные для обозначения простых высказываний.

а) если идет дождь, то дует ветер и становится холодно;

б) если дует ветер, идет дождь;

в) ветер дует тогда и только тогда, когда идет дождь;

г) неверно, что ветер дует тогда и только тогда, когда нет дождя.

Решение. Введем обозначения: х – «идет дождь», у – «дует ветер», z – «становится холодно».

Тогда приведенные высказывания можно записать в виде следующих формул:

а) б) в) г) .

Пример 4. Выяснить, являются ли следующие рассуждения логически верными.

Если Джонс не встречал ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то Смит был убийцей или Джонс не лжет. Следовательно, Смит был убийцей.

Решение. Введем логические переменные: х – «Джонс не встречал ночью Смита», у – «Смит убийца», z – «Джонс лжет», t – «убийство состоялось после полуночи». Прежде чем записать формулу, надо уточнить по условию задачи в каком контексте употребляется союз «или». Когда мы говорим «А или В», мы можем подразумевать две разные ситуации: а) или б) Во втором случае высказывания А и В не могут быть одновременно истинными. Чтобы подчеркнуть этот момент, обычно говорят «либо А, либо В». В нашей задаче нет такой оговорки, поэтому мы можем для записи высказывания: «Смит был убийцей или Джонс не лжет» использовать формулу . Итак, мы имеем посылки: , , заключение: у. Надо составить формулу:

и посмотреть, будет ли она тавтологией:

Следовательно, рассуждения логически правильны.

Пример 5. Проверить совместность утверждений.

Здесь употреблено выражение «либо. либо. », поэтому первое составное высказывание следует записать в виде что эквивалентно Конъюнкция посылок имеет вид:

это не равно тождественному 0, следовательно, высказывания не являются противоречивыми.

Пример 6. Четыре ученицы: Маша (М), Нина (Н), Ольга (О) и Поля (П) участвовали в соревнованиях и заняли первые 4 места. На вопрос, кто какое место занял, было дано 3 ответа:

1) О – второе, П – третье;

2) О – первое, Н – второе;

3) М – второе, П – четвертое.

В каждом из этих ответов одна часть верна, а другая нет. Какое место заняла каждая девушка?

Решение. Введем булевы переменные: х – «О – второе», у – «П – третье», z – «О – первое», t – «Н – второе», u – «М – второе», n – «П – четвертое». Получим систему уравнений: так как если x истинно, тогда y ложно, а – истинно и либо Аналогично, Удобнее записать эту систему следующим образом:

Отсюда или окончательно,

Кроме того, так как одна ученица не может занять 2 места и одно место не может быть занято двумя ученицами. В результате в последнем уравнении останется единственный ненулевой член Отсюда или О – первая, М – вторая, П – третья, Н – четвертая.

Пример 7. Во время перемены в классе были Аня, Борис, Ваня и Майя. Один из них разбил окно. На вопрос: ”Кто разбил окно?”, были даны ответы:

Аня: 1) Я не разбивала. 2) Я сидела и читала. 3) Майя знает, кто разбил.

Борис: 1) Я этого не делал. 2) С Майей я давно не разговариваю. 3) Это сделал Ваня.

Ваня: 1) Я не виновен. 2) Разбила Майя. 3) Борис лжёт, говоря, что разбил я.

Майя: 1) Я не разбивала. 2) Это вина Ани. 3) Борис знает, что я не виновна, т.е. мы с ним беседовали во время перемены.

Затем каждый признался, что из трёх ответов каждого, два – истинны, а один ложный. Кто разбил окно?

Решение. Введем булевы переменные. Высказывания, принадлежащие Ане, обозначим буквами с индексами ; высказывания, принадлежащие Борису – соответственно, принадлежащие Ване – и принадлежащие Майе – .

Запишем все формулы, которые являются тавтологиями, получим уравнения:

;

;

;

.

Выпишем все противоречия:

Чтобы иметь возможность воспользоваться этими противоречиями, возьмём конъюнкцию двух тавтологий:

и

что тоже будет тавтологией.

Получим

В этой формуле слева останется всего три ненулевых члена:

или Последнее уравнение даёт Так как и то и следовательно, а

Следовательно, окно разбила Аня.

Рассмотрим еще одну задачу, для решения которой не требуется аппарат логики высказываний, но тем не менее эта задача относится к логическим задачам.

Пример 8. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные, а один рыжие волосы, но ни у кого цвет волос не совпадает с фамилией», – заметил черноволосый. «Ты прав», – сказал Белов. Какой цвет волос у художника?

Решение. Составим таблицу.

Невозможное сочетание фамилии и цвета волос будем обозначать 0, возможное 1. Очевидно, что в каждой строке и в каждом столбце должна быть только одна 1. Получим два варианта.

Из условия задачи ясно, что черноволосый не Белов, поэтому первый вариант не подходит. Следовательно, Белов – рыжий, Чернов – белый, Рыжов – черный.

Пример 9. На склад, имеющий два помещения для хранения больших количеств двух видов топлива – угля и кокса, каждого отдельно, поступают грузовики, каждый всякий раз с одним из этих видов топлива. К механизму, открывающему шахты, предъявляется требование, чтобы он открыл шахту в помещении для угля, если прибывает грузовик с этим топливом, и шахту в помещении для кокса, если прибывает грузовик с коксом. Для обеспечения хорошей сортировки топлива было предъявлено дополнительное требование: всякий раз в помещение склада впускается только один грузовик и открывается лишь одна шахта.

Спрашивается, имеет ли этот механизм также следующее свойство: если не въехал в помещение склада грузовик с углем, то шахта для угля не откроется, а если не въехал грузовик с коксом, то не откроется шахта для кокса.

Решение. Введем булевы переменные: высказывание « прибыл грузовик с углем» обозначим через x, « прибыл грузовик с коксом» – y, «открыта шахта для угля» – z, «открыта шахта для кокса» – t. Тогда посылками будут: заключение Задача сводится к тому, чтобы выяснить, правильны ли рассуждения , т. е. вытекает ли это заключение из конъюнкции посылок. Кроме того, имеются два дополнительных условия, что может въехать только одна машина и открывается лишь одна дверь. Эти условия можно задать равенствами: и . аналогично, (представление в виде СДНФ или СКНФ). Построим формулу:

Так как , то аналогично, , следовательно, Мы получили тавтологию, следовательно, рассуждения верны.

Пример 10. На предприятии есть три цеха: A, B, C, договорившиеся о порядке утверждения проектов, а именно:

1. Если цех B не участвует в утверждении проекта, то в этом утверждении не участвует и цех A.

2. Если цех B принимает участие в утверждении проекта, то в нем принимают участие цеха A и C.

Спрашивается, обязан ли при этих условиях цех C принимать участие в утверждении проекта, когда в нем принимает участие цех A?

Решение. Логические переменные: « А участвует в утверждении проекта» обозначим через А, «В участвует в утверждении проекта» – В, «С участвует в утверждении проекта» – С. Посылки: . Утверждение Надо выяснить, верны ли рассуждения, т.е. выяснить будет ли тавтологией формула:

следовательно, рассуждения верны.

Пример 11. Перед судом стоят три человека, из которых каждый может быть либо туземцем, либо колониалистом. Судья знает, что туземцы всегда отвечают на вопросы правдиво, между тем как колониалисты всегда лгут. Однако судья не знает, кто из них туземец, а кто колониалист. Он спрашивает первого, но не понимает его ответа. Поэтому он спрашивает сначала второго, а потом третьего о том, что ответил первый. Второй говорит, что первый назвал себя туземцем. Третий говорит, что первый назвал себя колониалистом. Кем были второй и третий подсудимые?

Решение. Во-первых, если первый человек туземец, то он назовет себя туземцем, если он колониалист, то тоже назовет себя туземцем. Высказывание «первый сказал, что он туземец» обозначим через x, «второй туземец» – y, «третий туземец» – z, и заметим, что x º 1.

Имеем следовательно, второй – туземец. следовательно, третий – колониалист.

Источник