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

 

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

Обычно используется следующая схема решения:

1. Изучается условие задачи.

2. Вводится система обозначений для логических высказываний.

3. Конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи.

4. Определяются значения истинности этой логической формулы.

5. Из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Покажем на ряде конкретных примеров, как исполь­зовать возможности алгебры логики для решения элемен­тарных логических задач.

Пример 1. Жили четыре мальчика: Александр, Иван, Петр, Николай. Фамилии друзей те же, что и имена: Александров, Петров, Иванов, Николаев, только такие, что ни у кого из них имя и фамилия не были одинаковы. Кроме того, Александр не был Ивановым. Требуется определить фамилию каждого из мальчиков, если известно, что имя мальчика, у которого была фамилия Петров, есть фамилия того мальчика, имя которого - фамилия Николая.

Решение. Поставим в соответствие каждому мальчику символ Ху, где X - имя, a Y - фамилия мальчика. Тогда по условию задачи ложны высказывания:

А_А, И_И, П_П, Н_Н, А_И.

Но есть мальчик У_Х такой, что истинна конъюнкция Х_П & У_Х & Н_У.

Очевидно, что Х ≠ П, Х ≠ Н, У≠ Н, У≠ П.

Тогда возможны два случая:

1. X = А и Y = И,

2. Х = И и У = А.

Но первый случай невозможен, т.к. по условию Александр не может быть Ивановым А_И = 0.

Следовательно, имеет место второй случай. Значит, Иван имеет фамилию Александров, Николай – Иванов, Александр – Петров, Петр - Николаев.

Пример 2. По подозрению в совершенном преступлеиии задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом - ложь. Вот, что они утверждали:

Браун: «Я совершил это. Джон не виноват»,

Джон: «Браун не виноват. Преступление совершил Смит»,

Смит: «Я не виноват» виновен Браун».

Определите имя старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Решение. Обозначим буквами Б, Д и С высказывания: виноват Браун, виноват Джон, виноват Смит соответст­венно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций: Б& Д, Б& С, Б& С, из которых, по условию задачи, две ложны, а одна ис­тинна.

Поэтому будет истинной формула

L = (Б & Д) v (Б & С) v (Б & С),

Таблица истинности этой формулы имеет вид:

Б	Д	С	Б& Д	С& Б	Б& С	L
1	1	1	0	0	0	0
1	1	0	0	1	0	1
1	0	1	1	0	0	1
1	0	0	1	1	0	1
0	1	1	0	0	1	1
0	1	0	0	0	0	0
0	0	1	0	0	1	1
0	0	0	0	0	0	0

Отсюда видно, что формула L истинна в пяти из восьми занумерованных случаев. Случай 4 следует ис­ключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит усло­вию задачи. В случаях 2, 3 и 5 оказываются истинными по два высказывания: Б и Д, Б и С, Д и С соответственно, что также противоречит условию задачи. Следователь­но, справедлив случай 7, то есть преступник - Смит. Он - известный мошенник, и оба его высказывания лож­ны: Б & С = 0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон - уважаемый в городе старик, а Браун - малоизвестный чиновник.

Пример 3. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: " Чей именно проект был принят? ", министры дали такие ответы:

Россия — " Проект не наш, проект не США";

США — " Проект не России, проект Китая";

Китай — " Проект не наш, проект России".

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определить, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия — " Проект не наш" (1), " Проект не США" (2);
США — " Проект не России" (3), " Проект Китая" (4);
Китай — " Проект не наш" (5), " Проект России" (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

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

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

 

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

Эти устройства (их в общем случае называют пере­ключательными схемами) содержат сотни реле, элект­ронных ламп, полупроводников и электромагнитных элементов. Описание и конструирование таких схем в силу их громоздкости весьма затруднительно. Еще в 1910 году физик П. С. Эренфест указал на воз­можность применения аппарата алгебры логики при исследовании релейно-контактных схем (РКС). Однако его идеи стали реализовываться значительно позже, когда создание общей теории конструирования РКС стало ост­ро необходимым.

Использование алгебры логики в конструировании РКС оказалось возможным в связи с тем, что каждой схеме можно поставить в соответствие некоторую фор­мулу алгебры логики, и каждая формула алгебры логи­ки реализуется с помощью некоторой схемы. Это обстоятельство позволяет выявить возможности заданной схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению формулы.

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

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

1) переключателей, которыми могут быть механичес­кие действующие устройства (выключатели, переключа­ющие ключи, кнопочные устройства и т. д.), электромаг­нитные реле, электронные лампы, полупроводниковые элементы и т.п.;

2) соединяющих их проводников;

3) входов в схему и выходов из нее (клемм, на которые подается электрическое напряжение). Они называются полюсами схемы.

Сопротивления, конденсаторы и т.д. на схемах не изображаются.

Переключательной схемой принимается в расчет только два состояния каждого переключателя, которые называют «замкнутым» и «разомкнутым». Рассмотрим простейшую схему, содержащую один переключатель Р и имеющую один вход А и один выход В. Переключателю Р поставим в соответствие высказы­вание р, гласящее: «Переключатель Р замкнут». Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения. Будем в этом случае говорить, что схема проводит ток. Если р ложно, то переключатель.разомкнут, и схема тока не проводит или на полюсе В снимается минимальное напря­жение при подаче на полюс А максимального напряже­ния.

Если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответствие переключательная схема (рисунок 15).

А В

Рисунок 15 – Переключательная схема

Формулам включающим основные логические опе­рации, также могут быть поставлены в соответствие пе­реключательные схемы.

Конъюнкция двух высказываний р и q будет представ­лена двухполюсной схемой с последовательным соедине­нием двух переключателей Р и Q (рисунок 16).

А В

Рисунок 16 – Переключательная схема конъюнкции

Эта схема пропускает ток тогда и только тогда, когда истинны и р, и q одновременно, то есть истинна конъюн­кция р & q.

В

А

Дизъюнкция двух высказываний р и q изобразится двухполюсной схемой с параллельным соединением двух переключателей Р и Q (рисунок 17).

Рисунок 17 – Переключательная схема дизъюнкции

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

Если высказывание р есть отрицание высказывания р, то тождественно истинная формула р v р изображает­ся схемой, которая проводит ток всегда (рисунок 14), а тож­дественно ложная формула р & р изобразится схемой, которая всегда разомкнута (рисунок 18).

Рисунок 18 – Переключательная схема дизъюнкции противоречивых высказываний

Рисунок 19 – переключательная схема конъюнкции противоречивых высказываний

		А		В
	А
		В

Из рисунков 17, 18 и 19 путем последовательного и параллельного их соединения могут быть построены новые двухполюсные переключательные схемы, которые называют П-схемами.

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

Например: формуле

L = (х & у & z) v (х & у & z) v (х & у & z) v (х & у & z)

соответствует рисунок 20:

Рисунок 20 – Переключательная схема

Упростив эту формулу, получаем L=((x v y) & z) v (x & y).

Последней формуле соответствует рисунок 21.

Рисунок 21 – Переключательная схема

Б

А

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