Логические задачи в алгебре Буля
В настоящее время методы математической логики внедряются в гуманитарные знания как аппарат, позволяющий быстро и эффективно перерабатывать огромные объемы информации. Эти методы, как правило, при объяснении понятий и существующих между ними отношений исключают ошибки, проистекающие за счет неточного толкования смысла понятий, благодаря использованию логических операций.
Впервые с идеей внедрения логики и математики в процесс познания закономерностей между объектами любой природы выступил немецкий философ и математик Лейбниц (1646-1716). Он предвидел возникновение новой области науки, названной им философским исчислением.
Философское исчисление, по идее Лейбница, должно представлять такую логическую систему, в которой все производные понятия выражались бы символами, составленными из известных простых символов, обозначающих элементарные понятия на основании строгих правил. Операции над символами должны производиться по аналогии с алгебраическими операциями так, чтобы формальным путем можно было получать все новые и новые понятия и умозаключения.
Грандиозный замысел Лейбница долгое время оставался без развития. Первый крупный шаг в осуществлении идей Лейбница был сделан Джорджем Булем (1815-1864). В период с 1847 по 1857 г. он опубликовал три работы. Первые две носили характер предварительных исследований. В третьей работе (это объемистая книга в 424 стр.) изложена, в сущности, вся система Буля. Здесь он демонстрирует, как при помощи символических алгебраических методов можно строить логические конструкции. Кроме того, он показывает, как его система может быть распространена на теорию вероятностей.
В этих работах Буль преследует еще одну цель: найти элементарные операции человеческого мышления, выйдя за рамки дедуктивной и индуктивной логики. Выражаясь современным языком, его исследования принадлежали к области кибернетики.
Буль впервые показал, что законы человеческого мышления могут быть формализованы так, что над понятиями могут производиться те же операции, что и над целыми числами. Но в отличие от арифметики, как он показал, формальные операции над понятиями подчиняются следующим двум законам: два одних и тех же понятия сложенные или перемноженные приводят к тому же понятию (в современной Булевой алгебре их называют – отсутствие коэффициентов и степеней).
На формирование Булевой алгебры как самостоятельной научной дисциплины оказали влияние исследования немецкого математика Эрнста Шредера (1841-1902), который дал математическую трактовку закона исключенного третьего аристотелевской логики.
Шредер допускал наличие классов больше двух и для оперирования с ними он сформулировал следующее правило: если среди членов некоторой суммы классов находится хотя бы один, который оказывается отрицанием другого, то вся сумма равна единице. Легко показать, что с помощью этого правила можно построить таблицу операции отрицания Булевой алгебры.
Символическое исчисление Буля Шредер называл логическим исчислением и признавал только три основных операции: сложение, умножение и отрицание; вычитание он считал не безусловно выполнимой операцией. Тем самым Шредер поставил вопрос об оптимальном количестве операций в логике классов.
Однако гениальная догадка Буля состояла в том, что только на множестве числа М={0;1} символическое исчисление не противоречит опыту человеческого мышления. Вопрос же об оптимальности количества операций и в логике классов, и в исчислении Буля решается неоднозначно.
Согласно современным представлениям, алгеброй Буля 
называют элементы множества М={0;1} с заданными в нем операциями S={“Ú”,“Ù”,“-“} дизъюнкции, конъюнкции и отрицания. Обозначается алгебра Буля так: =(М;S), здесь М – множество, S – сигнатура алгебры, т.е. набор операций. Переменные 
будем называть булевыми переменными. Эти переменные обозначают понятия или высказывания как неделимые понятия, если 
=0, то высказывание ложно, если же =1, высказывание истинно.
Рассмотрим следующие логические задачи, которые решаются на базе символического исчисления Буля.
Задача 1.
Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предложения:
Алеша. Это сосуд греческий и изготовлен в 5 веке.
Боря. Это сосуд финикийский и изготовлен в 3 веке.
Гриша. Это сосуд не греческий и изготовлен в 4 веке.
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предложений.
Где и в каком веке изготовлен сосуд?
С помощью Булевой переменной введем обозначения:
- Это сосуд греческий – 
;
- Изготовлен в 5 веке – 
;
- Это сосуд финикийский – 
;
- Изготовлен в 3 веке – 
;
- Это сосуд не греческий – 
;
- Изготовлен в 4 веке – 
.
В этих обозначениях высказывания ребят кодируются логическими функциями следующим образом:
Алеша: 
Боря: 
Гриша: 
Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия позволяют ввести дополнительные логические функции:
,
Полученные таким образом логические функции 
представлены в совершенной дизъюнктивной нормальной форме. Если придать всевозможные значения наборам переменных, от которых зависят указанные функции, то можно получить таблицы для .
Будем считать все 
=1, тогда получим следующую систему уравнений Булевой алгебры:
(1)
Система (1) представляет математическую модель искомой задачи. Один из способов решения (1) состоит в подборе тех единичных термов логических функций 
, наборы переменных которых удовлетворяют системе (1), а значения переменных 
из этих наборов не противоречат друг другу.
Для нахождения всех единичных термов системы (1) необходимо произвести вычисление таблиц функций f1, f2, f3, f4, f5. Это можно сделать с помощью программы Microsoft Excel. Для этого напишем программу на языке макрокоманд. Так как любая программа требует отладки, будем проводить её посредствам сравнения получающихся в процессе написания программы результатов с образцами, представленными в виде рисунков.
1. Включение компьютера и вход в систему. Результат выполнения представлен на рисунке 1.
Рис. 1.
2. Запуск программы Microsoft Excel.
Параметры: - рабочий стол. Результат выполнения представлен на рисунке 2.
Рис. 2.
3. Выбор активного листа.
Параметры: - лист: «Лист1». Результат выполнения представлен на рисунке 3.
Рис. 3.
4. Занесение заголовка в ячейку.
Параметры: - ячейка: A1, B1; - данные: «X1», «X5». Результат выполнения частично представлен на рисунке 4. Рис. 4.
5. Занесение целых чисел в ячейку.
Параметры: - ячейка: A2÷A5; - данные: «1», «1», «0», «0». Результат выполнения частично представлен на рисунке 5. Рис. 5.
6. Занесение целых чисел в ячейку.
Параметры: - ячейка: A2÷A5; - данные: «1», «0», «1», «0». Результат выполнения частично представлен на рисунке 6. Рис. 6.
7. Занесение заголовка в ячейку.
Параметры: - ячейка: C1, D1, E1, F1, G1; - данные: «не X1», «не X5», «X1 и не X5», «не X1 и X5», «E1 или F1». Результат выполнения частично представлен на рисунке 7.
Рис. 7.
8. Автозаполнение - формула.
Параметры: - ячейка: C2; - данные: «=НЕ(A2)» - конечная ячейка: C5. Результат выполнения представлен на рисунке 8. Рис. 8.
Аналогичным способом достроим таблицу истинности для функции f1, используя функции И, ИЛИ. В результате получим значения для х1 и х5, представленные на рис. 9.
Рис. 9.
Построим таблицы истинности для функций f2 – f5, проводя аналогичные действия с переменными (Рис. 10):
Рис. 10.
Таблица 1. Таблица 2. Таблица 3.
| x1 | x5 | f1 | x2 | x3 | f2 | x1 | x4 | f3 | |||
Таблица 4. Таблица 5.
| x3 | x4 | x5 | f4 | X1 | x2 | f5 | |
В таблицах 1 – 5 единичные наборы определяются теми наборами переменных, при которых логические функции имеют единичные значения. Для решения поставленной задачи необходимо выбрать пять единичных термов, значения переменных в которых не противоречивы.
В качестве таковых наборов переменных возьмём следующие:
Из этих наборов переменных следует, что решение имеет вид:
(2)
Непротиворечивость решения (2) надо понимать так: значение х1=0 имеет место в наборах переменных для функций f5, f1, f3 аналогично х5=1 имеет место для f1, f4 и т.д.
Для проверки решения (2) подставим его в систему (1) и убедимся в том, что после этого уравнения системы (1) превращаются в тождества.
Для воспроизведения решения (2) в словесной форме необходимо вспомнить высказывания, которые кодировались символами хi. Из принятой кодировки следует, что х2=1 означает, что сосуд – финикийский, а х5=1 – сосуд изготовлен в 5-ом веке.
Задача 2.
В школе произошло чрезвычайное происшествие: в классе кто-то из учеников разбил окно. Учителем были опрошены четыре ученика— Лёня, Дима, Толя и Миша. Каждый из учеников сделал по три заявления (см. таблицы 6 – 9). Учитель усомнился в одном из трёх заявлений каждого из опрошенных учеников. Последнее означает, что у каждого одно из трёх заявлений неверно. Из анализа всех заявлений необходимо узнать — кто разбил окно.
Таблица 6.
| № | Показания Лёни | События | Вероятности | Переменные |
| Я не виноват. | 
| 
| 
| |
| Я не подходил к окну. | 
| 
| 
| |
| Миша знает, кто разбил окно. | 
| 
|
|
Таблица 7.
| № | Показания Димы | События | Вероятности | Переменные |
| Стекло разбил не я. | 
| 
| 
| |
| С Мишей я не был знаком до поступления в школу. | 
| 
| 
| |
| Это сделал Толя. | 
| 
| 
|
Таблица 8.
| № | Показания Толи | События | Вероятности | Переменные |
| Я не виноват. | 
| 
| 
| |
| Это сделал Миша. | 
| 
| 
| |
| Дима говорит неправду, что я разбил окно. | 
| 
| 
|
Таблица 9.
| № | Показания Миши | События | Вероятности | Переменные |
| Я не виноват. | 
| 
| 
| |
| Стекло разбил Лёня. | 
| 
| 
| |
| Дима может поручиться за меня. | 
| 
| 
|
Для получения вычислимого логического алгоритма решения данной задачи необходимо формализовать её условие, т.е. показаниям всех учеников придать форму математических соотношений, состоящих из символов, обозначающих понятия, и знаков логических операций, выполняемых над указанными символами.
С этой целью предположим, что каждое из показаний Лёни есть события , 
, 
, которые могут произойти или не произойти. Вероятности того, что каждое из названных событий имело место, обозначим соответственно 
, , 
. Вероятности же того, что события не имели место, обозначим через 
, 
, 
. При этом предполагается, что событие 
противоположно событию и т.д. применительно к оставшимся событиям.
Событие 
, состоящее в том, что из трёх показаний Лёни одно не верно, называется сложным событием. Оно составляется как комбинация простых событий следующим образом:
(3)
Здесь операция суммы событий заменена операцией дизъюнкции, а операция произведения— конъюнкцией. Такие законы обоснованы выше. Вероятность сложного события обозначим через 
. В теории вероятностей значения вероятности могут принимать весь спектр числовых значений от нуля до единицы. Применительно к данной задаче будем считать, что вероятности Р принимают только предельные значения: нуль или единица. Это позволяет отождествлять вероятность 
с Булевой переменной 
, т.е. ввести обозначения:
В этом случае 
означает истинность данного события, а 
— ложность. Аналогично 
говорит об истинности сложного события , а 
— об его ложности.
Теперь, согласно теоремам о вероятности суммы и произведения нескольких событий, вероятность 
сложного события определяется следующим образом:
(4)
Проводя аналогичные рассуждения для показаний остальных учеников, и используя обозначения таблиц 2 – 4, заявления Димы, Толи и Миши представим в форме следующих математических соотношений:
(5)
(6)
(7)
Все эти логические формулы однотипны и представляют совершенную дизъюнктивную нормальную форму (СДНФ) одной и той же логической функции 
.
(8)
Придавая набору, 
различные комбинации из нулей и единиц, подставляя их в (8) и производя вычисления с помощью таблиц операций конъюнкции и дизъюнкции, получаем таблицу 10 логической функции 
.
Таблица 10.
|   
|
|
| 0 0 0 0 0 1 0 1 0 0 1 1 | ||
| 1 0 0 1 0 1 1 1 0 1 1 1 |
В таблице 10 через обозначен десятичный код набора переменных, представляющего множество трёхразрядных двоичных чисел.
Единичные значения логической функции называются единичными термами. Для них введём новое обозначение 
.
Единичные термы можно вычислять с помощью операций конъюнкции и отрицания по следующим формулам:
(9)
Поскольку в формулах (9) главной операцией считается операция конъюнкции, то единичные термы называют конъюнктивными термами. Если три конъюнктивных терма объединить знаком дизъюнкции, то согласно теории логических функций, получим аналитическое представление функции в форме СДНФ (8).
Для получения явного вида конъюнктивных термов логических функций 
необходимо вычислить таблицы этих функций с помощью программы Microsoft Excel. Для этого продолжим написание программы на языке макрокоманд и её отладку, путём проведения сравнения получающихся в процессе написания программы результатов с образцами, представленными в виде рисунков.
9. Выбор активного листа.
Параметры: - лист: «Лист2». Результат выполнения представлен на рисунке 10.
Рис. 10.
Все вычисления производятся по технологии, аналогичной той, которая была описана ранее, в пунктах 4 – 8. В результате вычислений получим таблицу, представленную на рис. 11.
Рис. 11.
Из таблицы, представленной на рис. 11, формируем таблицу 11, состоящую из конъюнктивных термов функций и соответствующих им наборов переменных.
Таблица 11.
| f1 | f2 | f3 | f4 | ||||||||||||
| x1 | x2 | x3 | F1J | y1 | y2 | y3 | F2J | z1 | z2 | z3 | F3J | s1 | s2 | s3 | F4J |
| F13 | F23 | F33 | F43 | ||||||||||||
| F15 | F25 | F35 | F45 | ||||||||||||
| F16 | F26 | F36 | F46 |
Здесь применительно к функции fi конъюнктивный терм обозначен через FiJ так, что верхний индекс i соответствует номеру логической функции.
Если никто из учеников не отказался от своих высказываний, то значение всех логических функций надо положить равными единице, после чего соотношения (4) – (7) примут вид следующей системы алгебраических уравнений для определения двенадцати неизвестных, которые представляются показаниями учеников в обозначениях таблиц 6 – 9:
(10)
Здесь для обозначения конъюнктивных термов, входящих в использован символ 
. Соотношения (10) представляют математическую модель показаний учеников и их следует называть системой уравнений Булевой алгебры, так как они определены на множестве М = {0;1} с использованием трёх логических операций – дизъюнкции, конъюнкции и отрицания.
В этой системе число неизвестных превышает число уравнений. Однако, так как 1Ú0=1, то решение системы (10) будет определяться такими четырьмя термами: F1j, F2j, F3j, F4j , (j=3, 5, 6), наборы переменных, которых после подстановки в (10) и проведения логических вычислений превратят уравнение (10) в тождества. При этом термы FiJ вычисляются по формуле (9) с учётом обозначения переменных согласно таблице 11.
Среди комбинаций из указанных четырёх термов могут оказаться такие, значения наборов переменных которых могут привести к противоречивым показаниям учеников. Например, рассмотрим термы F13, F23, F33, F43.
Наборы переменных, соответствующие указанным термам, определяются по таблице 11. В таблице 12 приведены значения переменных, найденные из полученных наборов переменных, а также показания учеников, соответствующие данным значениям переменных.
Чтобы показать, что значения переменных из таблицы 12 суть решение системы (10) необходимо для этих значений вычислить по (9) строки и подставить их в тождества.
Здесь же в таблице 12 даются высказывания мальчиков, соответствующие рассмотренному решению. Из них следует, что все ученики виноваты. Последнее противоречит условию задачи.
Такое решение задачи в дальнейшем будем называть противоречивым
Таблица 12.
| F13=1 | Показания Лёни. |
| x1=0 x2=1 x3=1 | Я виноват. Я не подходил к окну. Миша знает, кто разбил окно. |
| F23=1 | Показания Димы. |
| y1=0 y2=1 y3=1 | Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это сделал Толя. |
| F33=1 | Показания Толи. |
| z1=0 z2=1 z3=1 | Я виноват. Это сделал Миша. Дима говорит неправду, что я разбил окно. |
| F43=1 | Показания Миши. |
| s1=0 s2=1 s3=1 | Я виноват. Стекло разбил Лёня. Дима может поручиться за меня. |
Рассмотрим другое решение: F13=1, F26=1, F35=1, F46=1. Значения переменных и показания учеников, соответствующие этому решению, приведены в таблице 13.
Таблица 13.
| F13=1 | Показания Лёни. |
| x1=0 x2=1 x3=1 | Я виноват. Я не подходил к окну. Миша знает, кто разбил окно. |
| F26=1 | Показания Димы. |
| y1=1 y2=1 y3=0 | Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это не сделал Толя. |
| F35=1 | Показания Толи. |
| z1=1 z2=0 z3=1 | Я не виноват. Это не сделал Миша. Дима говорит неправду, что я разбил окно. |
| F46=1 | Показания Миши. |
| s1=1 s2=1 s3=0 | Я не виноват. Стекло разбил Лёня. Дима не может поручиться за меня. |
Непротиворечивые показания этой таблицы говорят о том, что Лёня виноват и он разбил окно.
Решение, приводящее к логически непротиворечивому результату, назовём непротиворечивым.
Возникает вопрос: Как из множества решений выбрать одно – непротиворечивое?
Вернёмся к первоначальным заявлениям учеников (таблицы 6 – 9) и обратим внимание на то, что из четырёх заявлений – x1, y1, z1, s1 одно не верно.
По аналогии с рассуждениями, приводящими к формулам (3) и (4), указанную особенность четырёх заявлений можно выразить так:
(11)
Теперь значения переменных из таблицы 13 подставим в правую часть формулы (11) и произведём вычисление f с помощью программы Microsoft Excel. Для этого продолжим написание программы на языке макрокоманд.
10. Выбор активного листа.
Параметры: - лист: «Лист2». Результат выполнения представлен на рисунке 11. Рис. 11.
11. Занесение заголовка в ячейку.
Параметры: - ячейка: A1, B1, C1, D1; - данные: «X1», «Y1», «Z1», «S1». Результат выполнения частично представлен на рисунке 12. Рис. 12.
12. Занесение целых чисел в ячейку.
Параметры: - ячейка: A2÷D2; - данные: «0», «1», «1», «1». Результат выполнения частично представлен на рисунке 13. Рис. 13.
13. Занесение заголовка в ячейку.
Параметры: - ячейка: E1, F1, G1, H1, I1, J1, K1, L1, M1; - данные: «не X1», «не Y1», «не Z1», «не S1», «E1 и B1 и C1 и D1», «A1 и F1 и C1 и D1», «A1 и B1 и G1 и D1», «A1 и B1 и C1 и H1», «I1 или J1 или K1 или L1». Результат выполнения частично представлен на рисунке 14.
Рис. 14.
14. Автозаполнение - формула.
Параметры: - ячейка: E2; - данные: «=НЕ(A2)» - конечная ячейка: H2. Результат выполнения представлен на рисунке 15.
Рис. 15.
15. Занесение формул в ячейку.
Параметры: - ячейка: I2; - данные: «=И(E2;B2;C2;D2)». Результат выполнения частично представлен на рисунке 16. Рис. 16.
Аналогичным образом рассчитаем значения, расположенные в ячейках J2, K2, L2 и M2. В данном случае получим: f=fmax=1. Результат выполнения частично представлен на рисунке 17.
Рис. 17.
Проведём расчёт с целью вычисления f по (11) с использованием значений переменных из таблицы 12; тогда будем иметь: f=fmin=0 (Рис. 18).
Рис. 18.
Таким образом, непротиворечивое решение приводит к максимальным значениям логической функции (11). Последнее может означать, что логическая функция (11) представляется критерием отбора непротиворечивого решения системы (10) из множества решений. По аналогии с экономическими задачами линейного и нелинейного программирования, логическую функцию (11) следует назвать целевой функцией.
Теперь алгоритм решения данной задачи (10) – (11) сводится к следующему: перебираем всевозможные комбинации из четырёх термов F1j, F2j, F3j, F4j, затем применительно к каждой выбранной комбинации по таблице 11 определяем значения переменных, по которым вычисляем целевую функцию (11).
Тот вариант из четырёх единичных термов, который определит максимальное значение целевой функции (11), следует признать в качестве непротиворечивого решения.
Очевидно, что такой алгоритм требует большого объёма логических вычислений. Так, например, в рассматриваемой задаче, число комбинаций из четырех термов будет определяться числом сочетаний из двенадцати термов по четыре, т.е. 
=495