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

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

хÙу º уÙх — коммутативность конъюнкции.

хÚу º у Úх— коммутативность дизъюнкции.

х Ù (y Ù z) º (х Ú у) Ú z — ассоциативность конъюнкции.

х Ú (у Ú z) º (х Ú у) Ú z — ассоциативность дизъюнкции.

х Ù (у Ú z) º (х Ù у) Ú (х Ù z) — дистрибутивность конъюнкции относительно дизъюнкции.

х Ú (y Ù z) º (х Ú у) Ù (х Ú z) — дистрибутивность дизъюнкции относительно конъюнкции.

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

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

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

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

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

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

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

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

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

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

Л2у Б5= 1.

В-2 v Дз = 1.

Г{ vft-l.

А3 v Е6= 1.

B3vEAml.

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

L ■ (Л2 v Б5) а (В2 v Дз) д (Г, v Б3) л (Л3 v Е6) л (В3 v ЕА).

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

1з(А, vБ5)л(В2 v Д5)лГ! л(А, v£6)л(В3 vE4).

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

L = Б5 а (В2 v Д3) л Г{ л (А3 v Е^) л (2?3 v ЕА).

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

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

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

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

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

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

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

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

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

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

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

Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.

Каково количество функций п переменных? Очевидно, каждую функцию ал­гебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2п строк. Следовательно, каждая функция п переменных принимает 2п значений, состоящих из нулей и единиц. Таким обра­зом, функция п переменных полностью определяется набором значений из нулей и единиц длины 2п. Общее же количество наборов, состоящих из нулей и единиц длины 2п равно 22”. Значит, количество различных функций алгебры логики п переменных равно 22”.

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

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид

X	fix)	/г(*)	/з(*)	Мх)

Из этой таблицы следует, что две функции одной переменной будут постоян­ными: f\(x) = 1 и f4(x) = 0, a f2(x) я х и/3(г) = х.

Таблица истинности для всевозможных функций двух переменных имеет вид

X

У

/

/«

/з

Л

л

/б

fj

л

/9

/и

/12

/13

и

/l5

/16

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

Построение коммутационных схем на основе

Дата добавления: 2014-01-03