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

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

В СФЕРЕ ПРАВОПОРЯДКА

АЛГЕБРА ЛОГИКИ И ЕЕ ПРИМЕНЕНИЕ

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

а + в = в + а;

а • в == в • а;

(а + в)² = а² + 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 описанным способом.

Дата добавления: 2014-12-29