Логические задачи в алгебре Буля

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

Впервые с идеей внедрения логики и математики в процесс познания закономерностей между объектами любой природы выступил немецкий философ и математик Лейбниц (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) необходимо произвести вычисление таблиц функций f ₁, f ₂, f ₃, f ₄, f ₅. Это можно сделать с помощью программы Microsoft Excel. Для этого напишем программу на языке макрокоманд. Так как любая программа требует отладки, будем проводить её посредствам сравнения получающихся в процессе написания программы результатов с образцами, представленными в виде рисунков.

1. Включение компьютера и вход в систему. Результат выполнения представлен на рисунке 1.

Рис. 1.

2. Запуск программы Microsoft Excel.

Параметры: - рабочий стол. Результат выполнения представлен на рисунке 2.

Рис. 2.

3. Выбор активного листа.

Параметры: - лист: «Лист1». Результат выполнения представлен на рисунке 3.

Рис. 3.

4. Занесение заголовка в ячейку.

Параметры: - ячейка: A1, B1; - данные: «X₁», «X₅». Результат выполнения частично представлен на рисунке 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; - данные: «не X₁», «не X₅», «X₁ и не X₅», «не X₁ и X₅», «E1 или F1». Результат выполнения частично представлен на рисунке 7.

Рис. 7.

8. Автозаполнение - формула.

Параметры: - ячейка: C2; - данные: «=НЕ(A2)» - конечная ячейка: C5. Результат выполнения представлен на рисунке 8. Рис. 8.

Аналогичным способом достроим таблицу истинности для функции f ₁, используя функции И, ИЛИ. В результате получим значения для х₁ и х₅, представленные на рис. 9.

Рис. 9.

Построим таблицы истинности для функций f ₂ – f ₅, проводя аналогичные действия с переменными (Рис. 10):

Рис. 10.

Таблица 1. Таблица 2. Таблица 3.

x₁ x₅ f ₁ x₂ x₃ f ₂ x₁ x₄ f ₃

Таблица 4. Таблица 5.

x₃ x₄ x₅ f ₄ X₁ x₂ f ₅

В таблицах 1 – 5 единичные наборы определяются теми наборами переменных, при которых логические функции имеют единичные значения. Для решения поставленной задачи необходимо выбрать пять единичных термов, значения переменных в которых не противоречивы.

В качестве таковых наборов переменных возьмём следующие:

Из этих наборов переменных следует, что решение имеет вид:

(2)

Непротиворечивость решения (2) надо понимать так: значение х₁=0 имеет место в наборах переменных для функций f ₅, f ₁, f ₃ аналогично х₅=1 имеет место для f ₁, f ₄ и т.д.

Для проверки решения (2) подставим его в систему (1) и убедимся в том, что после этого уравнения системы (1) превращаются в тождества.

Для воспроизведения решения (2) в словесной форме необходимо вспомнить высказывания, которые кодировались символами х _i. Из принятой кодировки следует, что х₂=1 означает, что сосуд – финикийский, а х₅=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.

f₁ f₂ f₃ f₄

x₁ x₂ x₃ F¹_J y₁ y₂ y₃ F²_J z₁ z₂ z₃ F³_J s₁ s₂ s₃ F⁴_J

F¹₃ F²₃ F³₃ F⁴₃

F¹₅ F²₅ F³₅ F⁴₅

F¹₆ F²₆ F³₆ F⁴₆

Здесь применительно к функции f_i конъюнктивный терм обозначен через Fⁱ_J так, что верхний индекс i соответствует номеру логической функции.

Если никто из учеников не отказался от своих высказываний, то значение всех логических функций надо положить равными единице, после чего соотношения (4) – (7) примут вид следующей системы алгебраических уравнений для определения двенадцати неизвестных, которые представляются показаниями учеников в обозначениях таблиц 6 – 9:

(10)

Здесь для обозначения конъюнктивных термов, входящих в использован символ . Соотношения (10) представляют математическую модель показаний учеников и их следует называть системой уравнений Булевой алгебры, так как они определены на множестве М = {0;1} с использованием трёх логических операций – дизъюнкции, конъюнкции и отрицания.

В этой системе число неизвестных превышает число уравнений. Однако, так как 1Ú0=1, то решение системы (10) будет определяться такими четырьмя термами: F¹ _j, F² _j, F³ _j, F⁴ _j, (j=3, 5, 6), наборы переменных, которых после подстановки в (10) и проведения логических вычислений превратят уравнение (10) в тождества. При этом термы Fⁱ_J вычисляются по формуле (9) с учётом обозначения переменных согласно таблице 11.

Среди комбинаций из указанных четырёх термов могут оказаться такие, значения наборов переменных которых могут привести к противоречивым показаниям учеников. Например, рассмотрим термы F¹₃, F²₃, F³₃, F⁴₃.

Наборы переменных, соответствующие указанным термам, определяются по таблице 11. В таблице 12 приведены значения переменных, найденные из полученных наборов переменных, а также показания учеников, соответствующие данным значениям переменных.

Чтобы показать, что значения переменных из таблицы 12 суть решение системы (10) необходимо для этих значений вычислить по (9) строки и подставить их в тождества.

Здесь же в таблице 12 даются высказывания мальчиков, соответствующие рассмотренному решению. Из них следует, что все ученики виноваты. Последнее противоречит условию задачи.

Такое решение задачи в дальнейшем будем называть противоречивым

Таблица 12.

F¹₃=1 Показания Лёни.

x₁=0 x₂=1 x₃=1 Я виноват. Я не подходил к окну. Миша знает, кто разбил окно.

F²₃=1 Показания Димы.

y₁=0 y₂=1 y₃=1 Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это сделал Толя.

F³₃=1 Показания Толи.

z₁=0 z₂=1 z₃=1 Я виноват. Это сделал Миша. Дима говорит неправду, что я разбил окно.

F⁴₃=1 Показания Миши.

s₁=0 s₂=1 s₃=1 Я виноват. Стекло разбил Лёня. Дима может поручиться за меня.

Рассмотрим другое решение: F¹₃=1, F²₆=1, F³₅=1, F⁴₆=1. Значения переменных и показания учеников, соответствующие этому решению, приведены в таблице 13.

Таблица 13.

F¹₃=1 Показания Лёни.

x₁=0 x₂=1 x₃=1 Я виноват. Я не подходил к окну. Миша знает, кто разбил окно.

F²₆=1 Показания Димы.

y₁=1 y₂=1 y₃=0 Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это не сделал Толя.

F³₅=1 Показания Толи.

z₁=1 z₂=0 z₃=1 Я не виноват. Это не сделал Миша. Дима говорит неправду, что я разбил окно.

F⁴₆=1 Показания Миши.

s₁=1 s₂=1 s₃=0 Я не виноват. Стекло разбил Лёня. Дима не может поручиться за меня.

Непротиворечивые показания этой таблицы говорят о том, что Лёня виноват и он разбил окно.

Решение, приводящее к логически непротиворечивому результату, назовём непротиворечивым.

Возникает вопрос: Как из множества решений выбрать одно – непротиворечивое?

Вернёмся к первоначальным заявлениям учеников (таблицы 6 – 9) и обратим внимание на то, что из четырёх заявлений – x₁, y₁, z₁, s₁ одно не верно.

По аналогии с рассуждениями, приводящими к формулам (3) и (4), указанную особенность четырёх заявлений можно выразить так:

(11)

Теперь значения переменных из таблицы 13 подставим в правую часть формулы (11) и произведём вычисление f с помощью программы Microsoft Excel. Для этого продолжим написание программы на языке макрокоманд.

10. Выбор активного листа.

Параметры: - лист: «Лист2». Результат выполнения представлен на рисунке 11. Рис. 11.

11. Занесение заголовка в ячейку.

Параметры: - ячейка: A1, B1, C1, D1; - данные: «X₁», «Y₁», «Z₁», «S₁». Результат выполнения частично представлен на рисунке 12. Рис. 12.

12. Занесение целых чисел в ячейку.

Параметры: - ячейка: A2÷D2; - данные: «0», «1», «1», «1». Результат выполнения частично представлен на рисунке 13. Рис. 13.

13. Занесение заголовка в ячейку.

Параметры: - ячейка: E1, F1, G1, H1, I1, J1, K1, L1, M1; - данные: «не X₁», «не Y₁», «не Z₁», «не S₁», «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 = f _max=1. Результат выполнения частично представлен на рисунке 17.

Рис. 17.

Проведём расчёт с целью вычисления f по (11) с использованием значений переменных из таблицы 12; тогда будем иметь: f = f _min=0 (Рис. 18).

Рис. 18.

Таким образом, непротиворечивое решение приводит к максимальным значениям логической функции (11). Последнее может означать, что логическая функция (11) представляется критерием отбора непротиворечивого решения системы (10) из множества решений. По аналогии с экономическими задачами линейного и нелинейного программирования, логическую функцию (11) следует назвать целевой функцией.

Теперь алгоритм решения данной задачи (10) – (11) сводится к следующему: перебираем всевозможные комбинации из четырёх термов F¹ _j, F² _j, F³ _j, F⁴ _j, затем применительно к каждой выбранной комбинации по таблице 11 определяем значения переменных, по которым вычисляем целевую функцию (11).

Тот вариант из четырёх единичных термов, который определит максимальное значение целевой функции (11), следует признать в качестве непротиворечивого решения.

Очевидно, что такой алгоритм требует большого объёма логических вычислений. Так, например, в рассматриваемой задаче, число комбинаций из четырех термов будет определяться числом сочетаний из двенадцати термов по четыре, т.е. =495