Равносильности, выражающие основные законы алгебры логики

1. х лу = у ах — коммутативность конъюнкции.

2. xv y = y v х— коммутативность дизъюнкции.

3. х л (у л z) s (х л у) л z — ассоциативность конъюнкции.

4. х v (у v z) = (x v у) v z — ассоциативность дизъюнкции.

5. х л (у v г) = (х л у) v (х л г) — дистрибутивность конъюнкции относительно
дизъюнкции.

6. х v (у л г) = (х v у) л (х v г) — дистрибутивность дизъюнкции относительно
конъюнкции.

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

ЛОГИКИ

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

Глава 4. Логические основы информатики

Пример. Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

1. Антон был вторым, а Борис — пятым.

2. Виктор был вторым, а Денис — третьим.

3. Григорий был первым, а Борис — третьим.

4. Антон был третьим, а Евгений — шестым.

5. Виктор был третьим, а Евгений — четвертым.

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

Обозначим участника первой буквой его имени, нижний индекс около буквы (цифра) будет обозначать номер места, которое он занял в турнире, то есть в вы­ражении Х_у имеем, что X — это участник турнира, а у — номер места, которое он занял в турнире. Обозначим буквой L истинное распределение мест в турнире

<£-!)•

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

А₂ v Б₅= 1. В₂\/Д₃=\. Л v Б₃ = 1.

Тогда будет истинной формула

L _s (Л₂ v Б₅) а (В₂ v Д₃) л (Г, v Б₃) л (Л₃ v Е₆) л (В₃ v E_A).

Исходя из данных условия, можно начать преобразования. Поскольку одно из входящих в дизъюнкции высказываний обязательно истинно, а второе обязатель­но ложно, то за отправную точку в преобразованиях можно принять пару Г_х v Б₅ = 1. В этой паре высказывание Г_х является истинным, а Б₃ — ложным, поскольку на первое место нет других претендентов. Тогда, используя равносильность х v О ■ х, получаем Г_х v 0 = Г_и и формула приводится к виду

Поскольку вариант Б₃ оказался ложным, а других претендентов на пятое место нет, то истинным будет вариант Б₅. Тогда в первой по счету паре, применив ту же равносильность, что и на предыдущем шаге, мы также оставляем одно высказы­вание, и основная формула принимает вид

Продолжая эти равносильные преобразования, приводим формулу к виду

L = Б₅ а В₂ а Г_х а А₃ л Е₄.

Отсюда следует, что Б₅ ■ 1, В₂ ■ 1, Г\ = 1, Л₃ = 1, Е_А = 1, то есть первым был Григо­рий, вторым — Виктор и т. д. Это и является ответом на вопрос, поставленный в задаче.

Алгебра логики 119

4.2.7. Булева алгебра

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

Рассмотрим непустое множество М элементов любой природы {х, у, 2,...}, в ко­тором определены отношение равенства (=) и три операции: сложение (+), умно­жение (•) и отрицание (""), подчиняющиеся следующим законам: □ Коммутативные законы:

□ Ассоциативные законы:

□ Дистрибутивные законы:

□ Законы идемпотентности:

х + х = х;

х-х = х.

□ Закон двойного отрицания:

х = х.

□ Законы де-Моргана:

х-ушх + у.

□ Законы поглощения:

х+(у-х)=х;

Такое множество М называют булевой алгеброй.

Если под основными элементами х, у, z,... подразумевать высказывания, под операциями сложения, умножения и отрицания булевой алгебры — соответственно, дизъюнкцию, конъюнкцию и отрицание алгебры высказываний, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей алге­бры высказываний, все аксиомы булевой алгебры выполняются.

В тех случаях, когда для некоторой системы аксиом удается подобрать конкрет­ные объекты и конкретные соотношения между ними так, что все аксиомы выпол­няются, говорят, что найдена интерпретация, или модель, данной системы аксиом.

Значит, алгебра логики является интерпретацией булевой алгебры. Булева алгебра имеет и другие интерпретации. Например, если под основными элемен­тами х, у, z,... множества М подразумевать множества, под операциями булевой