Алгебра логики. Под алгеброй понимают множество с заданными на нем операциями

Под алгеброй понимают множество с заданными на нем операциями. Например, в качестве множества можно взять множество веществен­ных чисел, а в качестве операций – арифметические операции.

Пусть В = {0;1} – двухэлементное множество, и L – множество всех возможных операций на этом множестве, алгебра A = <В, L > называется алгеброй логики. Эти операции называют булевскими операциями или функциями алгебры ло­гики.

Элементы двухэлементного множества можно обозначать по-разному: 0, 1 или ложь, истина или true, false. Операции, которые были рассмотрены в предыду­щем пункте, принадлежат множеству L.

Любая функция алгебры логики может быть выражена с помощью отрицания, конъюнкции и дизъюнкции. Проверим истинность этого утверждения. Рассмотрим в качестве примера функцию (операцию) «исключающее или». Обозначим ее знаком Å. Таблица истинности для этой функции представлена в табл. 5.

Таблица 5. Таблица истинности для «исключающего или»

А	В	A Å B
Л	Л	Л
Л	И	И
И	Л	И
И	И	Л

Формула выражающая «разделяющее или» через дизъюнкцию конъюнкций, причем каждая конъюнкция состоит из переменных и отрицаний логических переменных А и В выглядит так:

А Å В = (ù А & B) Ú (A & ù B)

Причем формула ((ù A Úù В) & (A Ú В))º ((ù А &В)Ú (А & ù B)) будет истинна при любых значениях А и В, т. е. будет тавтологией. Справедливость равенства может быть проверена с помощью построения таблиц ис­тинности.

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

А → B º ù A Ú B (1)

(А & B) Ú C º (A Ú C) & (B Ú C) (2)

(А Ú B) & C º (A & C) Ú (B & C) (3)

ù (А & B) º ù A Úù B (4)

ù (А Ú B) º ù A &ù B (5)

А & ù A º false (6)

А Ú ù A º true (7)