Формулы и функции алгебры логики

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

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

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

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

		. . . . .
		. . . . .
		. . . . .
...	...	. . . . .	...	. . . . .
		. . . . .

Числовсех функций алгебры логики от n переменных равно , функций алгебры логики от двух переменных – 16.

Рассмотрим эти функции:

= 0 – «константа 0»;

= x ∙ y–«конъюнкция» (x и y);

=– «левая импликация»;

= x– «переменная x»;

=– «правая импликация»;

= y – «переменная y»;

= = – «сложение по модулю 2»;

= – «дизъюнкция» (x или y);

= = – «стрелка Пирса» (x стрелка y);

= = – «эквивалентноcть» (x эквивалентно y);

=– «отрицание» (не y);

= = – «x правая импликация y, или y импликация x»;

= –«отрицание»(не x);

= x → y= –«импликация» (если x, то y);

= x|y= – «штрих Шеффера» (x штрих y);

=1 – «константа 1».

Для удобства записей выражений в алгебре логике в дальнейшем мы будем придерживаться следующих правил:

· если над некоторым выражением стоит отрицание, то это выражение мы не будем заключать в скобки;

· знак «&» мы будем иногда опускать (как знак операции пересечения в алгебре множеств);

· будем считать, что знак «&» сильнее, чем знаки дизъюнкции, сложения по модулю 2, эквивалентности, импликации, стрелки Пирса и штриха Шеффера, тем самым мы будем, где это возможно, опускать скобки;

· на основании закона ассоциативности мы будем опускать скобки при записи нескольких идущих подряд дизъюнкций и конъюнкций.

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

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

Если формула содержит три переменные, то наборов значений переменных восемь: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати.

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

Если при всех наборах значений переменных x и y формула принимает значение 1, то является тождественно истинной, если при всех наборах значений переменных x и y формула принимает значение 0, то является тождественно ложной, если формула в некоторых случаях принимает значение 1, а в некоторых – 0, то есть является выполнимой.

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

Пример 1.Проверить эквивалентность булевых формул .