§ 1. ПОНЯТИЕ АЛГЕБРЫ ЛОГИКИ

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

а + в = в + а;

а • в == в • а;

(а + в)2 = а2 + 2ав + в2.

В алгебре логики применяются три операции — логическое умножение (•), логическое сложение () и логическое отрицание (-). Эти операции являются операциями над суждениями. Суждение имеет одно из двух значений — оно истинно или ложно. Пусть значению “истина” соответствует число 1, а значению “ложь” — число 0. Таким образом в алгебре логики операции осуществляются в конечном счете над числами 1 и 0. В этом имеется некоторое сходство между алгеброй логики и элементарной алгеброй.

Операции алгебры логики “•” и “” соответственно понимаются как конъюнкция и дизъюнкция, операция “-”— как логическое отрицание. Свойства этих операций описываются посредством тождеств 1—13. В качестве знака логического тождества (равенства) употребляется символ “=”.

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

Тождества алгебры логики

1. А • В = В • А;

A  B = B  A.

Тождества 1 устанавливают, что в суждениях с союзами, являющимися конъюнкцией и дизъюнкцией, члены конъюнкции и дизъюнкции можно переставлять.

2. А • (В • С) = (А • В) • С;

A  (B  C) = (A  B)  C.

Эти тождества устанавливают, что последовательность применения к суждениям одной и той же операции “•” или “” может быть любой. Правильность этих тождеств очевидна, поскольку в естественном языке скобки в таких случаях вообще не употребляются.

3.А • (В  C) =A • В  A • С;

А  (В • С) = (А  В) • (А  С).

Знак “•” здесь связывает теснее, чем “”.

В элементарной алгебре есть аналог первого из этих тождеств:

а • (в+с) = (а • в) + (а • с);

аналога второго из них тождеств нет, так как равенство:

а+(в • с) = (а+в) • (в+с) неверно в элементарной алгебре.

Пример суждений, тождественных в силу первого из тождеств 3: “Петров знает английский язык, и он знает французский или немецкий”, “Петров знает английский и французский языки или Петров знает английский и немецкий языки”. Если тождество не кажется очевидным, то его можно проверить при помощи таблицы истинности.

4. А • А = А;

А  А= А.

На основе тождества 4 повторения в сложных суждениях можно сократить.

5. А  (А • В) = А;

А • (А  В) = А.

6. А  0 = А; А • 1 = А;

A l = 1; A • 0 = 0.

_

7. A  A

_

8.А • А = 0.

____ _ _

9. А • В = А  В;

____ _ _

А  В = А • В.

_

10. А • В  A • В = А;

_

(A  B) • (А  В) = А.

_

11. A • B  B = A  B;

_

(А  В) • В = А • В.

=

12. А = А.

_ _

13. 0 = 1; 1 = 0.

Отрицая ложь, получим истину, и наоборот.

В главе V в качестве переменных для суждений использовались символы р, q, r, s и эти же символы с нижними индексами. В том же значении эти символы будут употребляться и в этой главе. Последовательность символов, получаемую в результате замены простых суждений, входящих в сложное суждение, пропозициональными переменными, а союзов “и” и “или” — символами “•” и “”, отрицания — символом “-”, будем называть формулой. Например, суждению "Понятые не приглашены или протокол не составлен" соответствует формула: _ _

p  q.

Формулами являются также пропозициональные переменные и символы 1 и 0.

На основе тождеств 1—13 можно преобразовывать формулы. Например,

____

из формулы p  q • q можно получить тождественную ей формулу 0 следующим образом:

___

1) p q • q — исходная формула;

_ _

2) р •q •q — из 1) на основе Т9 (тождества 9);

_

3) р • 0 — из 2) на основе Т8;

4) 0 — из 3) на основе Т6.

Установлено, что исходная формула тождественна 0, то есть суждение, которому эта формула соответствует, является ложным.

Из того как использовались тождества 1—13 можно уяснить, что в них буквами А, В, С обозначаются формулы.

Построенная алгебра имеет и другие интерпретации.

Рассмотрим одну из таких возможных интерпретаций. Пусть буквами А, В, С обозначаются объемы понятий (классы предметов), а символами “•”, “”, “-”соответственно операции пересечения, объединения классов, дополнения к классу в некотором универсуме.

Пересечением классов А и В называется новый класс А • В, элементами которого являются те и только те предметы, которые принадлежат как классу А, так и классу В. Графически этот класс изображается заштрихованной частью кругов А и В:

Объединением классов А и В называется новый класс A  В, элементами которого являются все элементы классов А и В. Графически этот класс представляется заштрихованной поверхностью круговой схемы:

Пусть нулем обозначается нулевой (пустой) класс, а единицей — универсальный, то есть класс, включающий все предметы исследуемой области. Тогда дополнением к классу А в универсальном классе называется класс А, элементами которого являются все элементы универсального класса, за исключением элементов класса А. Обозначим на схеме универсальный класс прямоугольником. Класс А представляется заштрихованной поверхностью.

Для иллюстрации первого из тождеств 3 посредством этой интерпретации начертим три пересекающихся круга А, В, С.

Чтобы получить класс А • (BC), сначала осуществим объединение классов В и С.

Класс BC представлен заштрихованной поверхностью круговой схемы.

Теперь осуществим пересечение классов А и BC:

В результате получим класс А•(BC), представленный поверхностью круговой схемы, заштрихованной дважды.

Затем начертим еще три пересекающихся круга А, В, С. Для графического изображения класса A•BA•C (правой части первого из тождеств 3) представим сначала графически класс АВ:

Затем представим графически класс А•С:

Объединение классов А•В и А•С представляется заштрихованной поверхностью схемы:

При этом оказывается, что классы А•(BC) и A•BA•C совпадают, что подтверждает правильность первого из тождеств 3.

Предлагаем читателю самостоятельно обосновать правильность второго из тождеств 3 описанным способом.

 

§ 2. ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ

А. Сигнализация

Алгебра логики используется при проектировании сигнализации. Пусть руководитель органа внутренних дел формулирует следующие условия работы сигнализации с охраняемого объекта: “желтый световой сигнал у дежурного по объекту включается ночью, если на каком-либо этаже здания, кроме первого этажа появляется человек; если на одном из этих этажей оказываются два человека, то гаснет желтый сигнал и загорается зеленый; если там оказываются три человека, то горят оба сигнала; при появлении на указанных этажах четырех человек горит красный свет; в том случае, когда на этих этажах находится более четырех человек, звучит сирена — сигнал тревоги (можно, например, считать, что в ночное время на эти этажи могут приходить только четыре человека)”.

Исходя из условий задачи, разработчик может считать, что проектируемое устройство имеет один входной сигнал, принимающий шесть значений. Эти значения соответствуют следующим положениям дел:

1-е значение — на втором этаже и выше нет ни одного человека,

2-е значение — на втором этаже и выше один человек,

3-е значение — на втором этаже и выше — 2 человека,

4-е значение — на втором этаже и выше — 3 человека,

5-е значение — на втором этаже и выше — 4 человека,

6-е значение — на втором этаже и выше — более 4 человек.

Представим проектируемое устройство в виде “черного ящика”, имеющею входы и выходы. Его внутреннее устройство нас не интересует. Информацию о числе входов и выходов пусть мы имеем.

Технически реализовать устройство, в котором один вход принимает шесть значений, конечно, возможно, но довольно сложно. Легче создать устройство, в котором, каждый вход принимает по два значения (например, идет электрический ток или нет). В этом случае можно использовать алгебру логики.

Сколько входов, каждый из которых имеет одно из двух значений, должно иметь устройство, реагирующее на шесть положений дел?

Один вход может отразить два положения дел, два входа — четыре положения дел, три — восемь положений дел. Итак, проектируемое устройство имеет три входа = р1, р2, р3, принимающие по два значения. Наборы входных сигналов отобразим в таблице:

р1 р2 р3

1 1 1

1 1 0

1 0 1

1 0 0

0 1 1

0 1 0

0 0 1

0 0 0

Пусть, далее, положения дел сопоставлены значениям входных сигналов так: набор значений 000 — “на этажах 0 человек”, 111— “один человек”, 110 — “два человека”, 101 — “три человека”, 100 — “четыре человека”, 011 — “более четырех человек”.

Устройство выдает четыре двоичных сигнала — q1, q2, q3, q4:

q1 = 1 — включен желтый сигнал,

q1 = 0 — выключен желтый сигнал,

q2 = 1 — включен зеленый сигнал,

q2 = 0 — выключен зеленый сигнал,

q3 = 1 — включен красный сигнал,

q3.= 0 — выключен красный сигнал,

q4 = 1 — включена сирена, сигнал тревоги,

q4 = 0 — выключена сирена.

Затем покажем, как зависят значения выходных сигналов от значений входных сигналов. Рассмотрим набор значений входных сигналов 000. При этом наборе, когда на указанных этажах люди отсутствуют, все выходные сигналы имеют значение 0. При наборе значений 111 входных сигналов (один человек на этажах) q1 имеет значение 1, а остальные выходные сигналы — 0. При наборе значений 110 (два человека) q1 имеет значение 0, q2 — 1, q3 — 0, q4 — 0. При наборе значений входных сигналов 101 (три человека) q1 — 1, q2 — 1, q3 — 0, q4 — 0. При наборе 100 q3 имеет значение 1, q4 — 0. Однако о том, какие значения имеют выходные сигналы q1 и q2 в условии ничего не сказано. Поэтому разработчик должен уточнить условие с заказчиком. Пусть руководитель решит, что в этом случае желтый и зеленый сигналы должны гореть, то есть q1 и q2 имеют значение 1. При наборе 011 (более трех человек) q4 имеет значение 1, а с остальными выходными сигналами дело обстоит так же, как и в предшествующем случае. Пусть заказчик решил, что и в этом случае вес выходные сигналы имеют значение 1. Сказанное можно представить в виде таблицы зависимости значений выходных сигналов от значений входных сигналов:

ВХОДЫ ВЫХОДЫ

p1 p2 p3 q1 q2 q3 q4

1 чел. 1 1 1 1 0 0 0

2 чел. 1 1 0 0 1 0 0

3 чел. 1 0 1 1 1 0 0

4 чел. 1 0 0 1 1 1 1

более 4-х чел. 0 1 1 1 1 1 1

0 1 0

0 0 1

0 чел. 0 0 0 0 0 0 0

Запись условия работы сигнализации в виде такой таблицы позволяет устранить неполноту условий.

Условия работы сигнализации можно упростить и проанализировать с помощью алгебры логики.

Выберем строки таблицы, в которых q1 = 1 (1-я, 3-я, 4-я и 5-я строки).

_ _ _ _

q1 = p1 • p2 • p3  p1 • p2 • p3  p1 • p2 • p3  p1 • p2 • p3

Это равенство получено следующим образом. Если q1 имеет значение 1 в четырех строках, то правый член равенства должен иметь четыре члена, соединенных знаком . Как получены эти члены? Если в первой сверху строке, где q1= 1, p1, p2, p3 имеют значение 1, то пишем p1 • p2 • p3; если в некоторой строке, где q1= 1, какой-то из входов имеет значение 0, соответствующий символ pn пишется со знаком отрицания. Например, в третьей строке p1 =1, _

p2=0, p3 =1, поэтому пишем p1, p2, p3 .

Упростим правую часть равенства:

_ _ _ _

1) p1 • p2 • p3  p1 • p2 • p3  p1 • p2 • p3  p1 • p2 • p3 — правая часть равенства, _ _ _ _

2) p1 • p3 • p2  p1 • p3 • p2  p1 • p2 • p3  p1 • p2 • p3 — из 1) в результате перестановки в первом и втором членах по Т1,

_ _ _

3) p1 • p3  p1 • p2 • p3  p1 • p2 • p3 — из 2) по Т10, взяв в качестве А — p1 • p3, а в качестве В — p2,

_ _ _

4) p1 • ( p3  p2 • p3 )  p1 • p2 • p3 — из 3) по Т3,

_ _ _

5) p1 • ( p2  p3 • p3 )  p1 • p2 • p3 — из 4) по Т1,

_ _

6) p1 • (p2  p3 )  p1 • p2 • p3 — из 5) по Т11,

_ _

7) p1 • p2  p1  p1 • p2 • p3 — из 6) по Т3,

_ _

8) p1 • p2  p3 • (p1  p1 • p2 ) — из 7) по Т1 и Т3,

_ _

9) p1 • p2  p3 • (p2 • p1  p1 ) — из 8) по Т1,

_

10) p1 • p2  p3 • (p2  p1 ) — из 9) поТ11,

_

11) p1 • p2  p3 • p2  p3 • p1 — из 10) по Т3,

_

12) p1 • p2  p2 • p3  p1 • p3 — из 11) по Т1.

q1 = p1 • p2  p2 • p3  p1 • p3 .

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

Упражнение

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

2. Уточните и упростите условия работы автоматизированной системы управления (АСУ) при помощи алгебры логики: в противопожарных целях температура на объекте не должна превышать 40° С; для предупреждения перегрева объекта предлагается установить два вентилятора (малый и большой) и разработать АСУ, удовлетворяющую следующим условиям: при температуре ниже 20° С вентиляторы не работают, при температуре от 20° С до 30° С работает малый вентилятор, при температуре от 31° С до 36° С работает большой вентилятор, при температуре свыше 36° С работают оба вентилятора, а когда температура на объекте достигает 40° С, звучит сигнал тревоги — сирена.

В. Управленческое решение

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

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

Пусть управленческое решение устанавливает, что:

1) к патрульно-постовой службе могут привлекаться сотрудники наружной службы горрайоргана внутренних дел;

2) никто не может быть одновременно сотрудником наружной службы и оперативного подразделения, если он не привлекается к несению патрульно-постовой службы;

3) никто из личного состава оперативных подразделений не привлекается к патрульно-постовой службе.

Упростим это предписание, состоящее из трех суждений. Для этого обозначим класс сотрудников патрульно-постовой службы символом П, класс сотрудников наружной службы — А, класс сотрудников оперативного подразделения — Оn.

Запишем предписание следующим образом:

_

   1) все П суть А, а в виде тождества — П • А= 0, т.е. класс П включается в класс А;

_

2) все, кто есть А и О суть П, А • Оn • П = 0;

3) никто из Оn не есть П, Оn • П = 0.

Затем преобразуем это предписание:

_

1) П • А=0 — первое суждение предписания,

_

2) П • A  0=0 — из 1) по Т6,

_ _

3) П • A  A • Оn • П=0 — из 2), используя второе суждение,

_ _

4) П • А  А • Оn • П  0=0 — из 3) Т6,

_ _

5) П • А  А • Оn П  Оn , • П=0 — из 4), используя третье суждение,

_ _ _

6) П • А  А • Оn • П  (Оn • П) • (A  A)=0 — из 5) на основании

_ _ _ Т6 и Т7,

7) П • A  А • Оn • П  Оn • П • А  Оn • П • А=0 — из 6) на основании

_ _ _ Т3,

8) П • А  Оn • П • А  А • Оn • П  А • Оn • П=0 — из 7) на основании

_ _ _ Т1,

9) П • А  П • А • Оn  А • Оn • П  A • Оn П=0 — из 8) на основании

_ _ Т1,

10) П • А  А • Оn • П  A • Оn • П=0 — из 9) на основании

_ Т5,

11) П • А  А • Оn = 0 — из 10) на основании

Т10.

Если объединение двух классов равно 0, то каждый из этих классов равен

_

0, следовательно, П • А=0 и А • Оn =0.

Получаем предписание, тождественное исходному:

1) патрульно-постовая служба формируется из состава наружной службы;

2) никто из личного состава оперативных подразделений не может быть сотрудником наружной службы.

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

С. Другие применения алгебры логики

1. Символическая логика, в том числе алгебра логики, широко применяется в кибернетике. Об отце символической логики Лейбнице Норберт Винер, сформулировавший основные идеи кибернетики, пишет: “Если бы мне пришлось выбирать в анналах истории наук святого — покровителя кибернетики, то я выбрал бы Лейбница. Философия Лейбница концентрируется вокруг двух идей, тесно связанных между собой: идеи универсальной символики и идеи логического исчисления.

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

2. Алгебра логики применяется при проектировании переключательных схем, являющихся элементами автоматизированных систем управления и вычислительных машин. При этом символ “•” интерпретируется как последовательное соединение переключателей, а символ “” — как параллельное. Например, формулам p • (q  r) и р • q  р • r соответствуют следующие схемы:

р = 1 — переключатель замкнут, р = 0 — разомкнут. Если в схеме имеются два (или более) переключателя р, то они могут быть замкнуты (или разомкнуты) только одновременно (именно поэтому они обозначаются одной и той же буквой).

По электрической цепи, изображенной на левой схеме, ток идет тогда и только тогда, когда он идет по цепи, изображенной на правой схеме, так как формулы р • (q  r ) и р • q  р • r — тождественные.

Символ “-” интерпретируется как противоположное состояние

_ _

переключателя, т.е. если р = 1, то p = 0, а если переключатель р замкнут, то p

_

разомкнут. Так, формуле р  p соответствует схема:

_

По этой цепи ток идет всегда, так как р  р = 1, т.е. если переключатель р

_

разомкнут, то переключатель р замкнут, и наоборот. Лампочка горит постоянно. Можно упростить схему, убрав оба переключателя.

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

3. “Прекрасно приспособленная для описания комбинаторных явлений, эта теория получает многочисленные применения к исследованию операций, где се нередко связывают с теорией структур.”

Алгебра логики применяется также в сетевом планировании и линейном программировании.

4. Алгебра логики применяется при установлении правильности или неправильности рассуждении. Пример рассуждения: “Если Иванов является участником этого преступления, то он знал потерпевшего. Иванов не знал потерпевшего, но знал его жену. Потерпевший знал Иванова. Следовательно, Иванов не является участником этого преступления.” Переведем рассуждение на язык алгебры логики. Обозначим символами простые суждения, входящие в рассуждение: “Иванов является участником этого преступления” (р), “Иванов знал потерпевшего” (q), “Иванов знал жену потерпевшего” (r), “потерпевший знал Иванова” (s). Затем переведем на язык алгебры логики посылки и

_

заключение рассуждения. При этом вместо “если р, то q” напишем p  q. Союз “но” по смыслу соответствует союзу “и”.

Переводом посылок и заключения являются формулы:

_ _ _

р  q, q • r, s и p соответственно.

Формулы, переводящие посылки, последовательно соединим друг с другом символом “•”: ((p  q) • (q • r)) • s.

Поставив над полученной формулой знак отрицания, присоединим к ней символом “” формулу, соответствующую заключению:

________________

_ _ _

((p  q) • (q • r)) • s  p

Полученная формула является переводом на язык символов исходного рассуждения. Если исходное рассуждение является правильным, то полученная формула равно 1.

______________

_ _ _

   1) ((p  q) • (q • r)) • s  p — исходная формула

___________

_ _ _

   2) (p q) • (q • r)  s  p — из 1) по Т9,

____ ____

_ _ _ _

   3)  p q  q • r  s  p — из 2) по Т9,

= _ = _ _

   4)  p • q  q  r  s  p — из 3) по Т9,

= = _ _ _

   5)  p  q  r  s  p — из 4) по Т11,

_ = _ _

   6) p  p  q  r  s — из 5) по Т12 и Т1,

= _ _

   7) 1  q  r  s — из 6) по Т7,

   8) 1 — из 7) по Т6.

Анализируемое рассуждение является правильным.