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

Определение 3.1. Пусть - множество исходных функций. Символы переменных , …, будем считать формулами глубины 0. Формула F имеет глубину k+ 1, если F имеет вид , где ÎS, - число аргументов функции , - формулы, максимальная из глубин которых равна k.

Все формулы называются подформулами F; - называется внешней или главной операцией формулы F. Все подформулы формул также называются подформулами F. Например, (, , ) - это формула глубины 1, а - формула глубины 3, содержащая одну подформулу глубины 2 и две подформулы глубины 1.

В дальнейшем формулы будут иметь более привычный вид, при котором знаки функций стоят между аргументами. Например, если в предыдущем примере обозначает дизъюнкцию, - конъюнкцию, - сложение по модулю 2, то приведенная формула имеет вид:

( Ú ) Å( &( Å )).

Всякая формула, выражающая функцию f как суперпозицию других функций, задает способ ее вычисления. Этот способ определяется следующим правилом: формулу можно вычислить, только если вычислены значения всех ее подформул. Вычислим значение предыдущей формулы на наборе =1, =1, = 0. Получим Ú =1, Å = 0, &( Å ) = 1& 0 = 0, ( Ú ) Å( &( Å )) = 1Å 0 =1.

Так же как для алгебраических выражений для записи логических формул используют соглашение о приоритете операций. Перечислим приоритет логических операций в порядке его убывания: Ø, Ù, Ú, ®, ~. Операции |, ¯ имеют тот же приоритет, что и Ù, а Å - тот же приоритет, что и ~. Таким образом в формуле без скобок сначала выполняется Ø, затем Ù и т.д.

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

Пример 3.1. Составим таблицу истинности для формулы Ø (А Ù В Ú С).

В отличие от табличного задания, представление функции формулой не единственно. Например, функцию штрих Шеффера можно представить формулами: | = Ú и | = Ø( & ); а функцию стрелка Пирса - формулами: ¯ = & и ¯ = Ø( Ú ).

Определение 3.2. Формула, истинная при всех возможных значениях переменных, называется общезначимой или тавтологией.

Определение 3.3. Формула, ложная при всех возможных значениях переменных, называется невыполнимой или противоречием.

Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными. Эквивалентность формул обозначается знаком равенства =, т.е. | = Ú = Ø( & ). Для проверки эквивалентности формул существует стандартный способ: для каждой формулы строится таблица истинности, а затем две таблицы сравниваются. Этот метод требует 2× вычислений для формул от п переменных. Существуют и другие методы установления эквивалентности формул и получения новых формул, эквивалентных исходной.

Пример 3.2. Проверить эквивалентность формул и . Составим для этих формул таблицу истинности.

A	B	A Ú B

Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают.

Пример 3.3. Проверить эквивалентность формул А ~ В и . Составим для этих формул таблицы истинности. Формулы эквивалентны, так как 3-й и 8-й столбцы таблицы совпадают.

А	В	А~В			АВ		АВÚ