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

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. Логические основы информатики

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

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

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

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

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

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

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

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

<£-!)•

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

А2 v Б5= 1. В2\/Д3=\. Л v Б3 = 1.

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

L s2 v Б5) а (В2 v Д3) л (Г, v Б3) л (Л3 v Е6) л (В3 v EA).

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

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

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

L = Б5 а В2 а Гх а А3 л Е4.

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

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

Равносильности, выражающие основные законы алгебры логики - student2.ru 4.2.7. Булева алгебра

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

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

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

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

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

х + х = х;

х-х = х.

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

х = х.

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

Равносильности, выражающие основные законы алгебры логики - student2.ru Равносильности, выражающие основные законы алгебры логики - student2.ru х-ушх + у.

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

х+(у-х)=х;

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

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

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

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





Наши рекомендации