Тогда мы получаем булеву алгебру Аб = <M, +, ∙, ¯>. Обратите внимание, что булева алгебра является дистрибутивной решеткой с дополнениями.

Если под элементами {x, y, z,…} понимать высказывания, знак равенства понимать как равносильность, а под логическим сложением, логическим умножением, отрицанием – дизъюнкцию, конъюнкцию и отрицание, получаем интерпретацию алгебры Буля.

Среди интерпретации алгебры Буля можно отметить алгебру множеств, т.е. алгебру Кантора.

Теорема 2.3 (Стоуна). Булева алгебра изоморфна алгебре Кантора.

Под изоморфизмом между алгебрами A1 = <M1, S1> и A2 = = <M2, S2> в данном случае понимаем такое взаимно однозначное соответствие между элементами носителя и сигнатуры, что [3]:

fi(mi1, mi2, …, mi1n-1) = min ( fi (m1i ,m2i ,...,mni 1) (mni ),

mj M		, (mj ) M		,	j 1,...,k,	f	S , ( f		) S	2	.
i	1	i	2			i	1	i

2.6. Булевы функции

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

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

Функции, которые определены на этих переменных и принимают значения 0 или 1, также называются логическими, или булевыми.

Очевидно, что тождественно истинные или тождественно ложные формулы алгебры логики представляют собой функцииконстанты 1 или 0 соответственно, две равносильные формулы выражают одну и ту же функцию.

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

58

Конституэнтой называется логическое произведение переменных или их отрицаний в виде

n

x

i

,

если

i

1,

& x

i ,

где

x

i

i

i

если

0.

i 1

x

,

i

i

Двоичные эквиваленты формируются из значений i. Например,

конституэнте x1 x2 x3 соответствует двоичный набор 001, а консти-

туэнте x1 x2 x3 – 101.

Если количество переменных равно n, то количество двоичных эквивалентов равно 2n, а количество различных функций от n пере-

менных равно 22n .

Для функций с двумя переменными известны шестнадцать логических функций:

функция константа нуля;

логическое умножение или конъюнкция &;

логическое сложение + или дизъюнкция ;

отрицание (по первой переменной) a;

отрицание (по второй переменной) b;

импликация или функция следования (левая) ;

импликация или функция следования (правая) ;

сложение по модулю два или сложение Жегалкина ;

функция Шеффера ;

стрелка Пирса или функция Вебба ;

обратная импликация или ко-импликация (левая) ;

обратная импликация или ко-импликация (правая) ;

функция тождества или эквивалентность ;

функция константы единицы;

функция сохранения первой переменной a;

функция сохранения второй переменной b.

Значение каждой логической функции описывается таблицей истинности (табл. 2.6).

59