Булевы функции. Равносильность. Тавтологии

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

Если f(x₁,…,x_n) булева функция, зависящая от n аргументов, то она вполне определяется своими значениями для 2ⁿ наборов значений аргументов. Кроме того, она вполне определяется подмножеством тех наборов, для которых она принимает значение 1. Поскольку число различных подмножеств равно , то

Теорема: Число различных булевых функций, зависящих от n аргументов равно .

Так, для n=2 число различных булевых функций равно 16. Очевидно, что всякая формула логики высказываний является булевой функцией. В дальнейшем будет показано, что и всякую булевую функцию можно интерпретировать как формулу логики высказываний.

Определение: Две формулы F и G называются равносильными, если они равны как булевы функции, т.е. принимают одинаковые значения при всех наборах значений простых компонент. Обозначается FºG.

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

Тождественно-истинной (тавтологией) называется формула, таблица истинности которой состоит из одних 1 и тождественно-ложной, если все её значения равны 0. Обозначаются они соответственно Fº1 и Fº0. Если формула может принимать как значения 1, так и 0, то она называется выполнимой.

Пример:

В задаче 1 формулы b), c), d), e) - тождественно-истинные, формулы a) и f) - выполнимые.

Примером тождественно-ложной формулы будет ((aÚb)Ù(`aÙ`b)).

Отношение равносильности является отношением эквивалентности на множестве всех формул логики высказываний. Класс эквивалентности - это все формулы, соответствующие одной и той же булевой функции. Изучение булевых функций имеет большое значение как для алгебры и математической логики, так и для приложений в компьютерной математике и теории автоматов. Особую роль играют тавтологии. Проверить, является ли формула тавтологией или равносильны ли данные формулы, можно, составляя таблицы истинности. Процедура эта для большого числа аргументов утомительна или даже невозможна. Однако, существуют методы, позволяющие значительно упростить эту проверку.

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

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

Теорема: Всякая формула логики высказываний равносильна булевой формуле.

Доказательство этой теоремы опирается на следующие равносильности a®bº`aÚb и a«bºabÚ`a`b

Они проверяются таблицей истинности:

Эти равносильности имеют логический смысл.

Формула a®b означает: если верно а то верно b.

А формула `aÚb: или неверно а или верно b.

Это последнее высказывание и есть обоснование таблицы истинности для операции a®b.

Формула a«b переводится так: а верно тогда и только тогда, когда верно b, а формула abÚ`a`b означает или a и b одновременно верны, или одновременно неверны.

Сформулируем также два правила подстановки:

1. Пусть F_A - формула, в которой фиксировано вхождение в неё формулы А (в этом случае говорят, что формула А является частью формулы F, и что формула F длиннее формулы А) и пусть АºВ, тогда F_А ºF_В, где в формуле F формула А заменена на формулу В.

Например F=(a®b)Ùc и A=a®b. Тогда A=a®bºB=`aÚb и (a®b)Ùcº(`aÚb)Ùc.

2. Пусть F_аºG_a, причём в формулах F и G фиксированы все вхождения простой компоненты а. Тогда F_AºG_A, где А - произвольная формула, и в формулах F и G простая компонента а заменена всюду на формулу А.

Пример. abÚ`a`bºa«b. Пусть А=c®d. Тогда (c®d)bÚ( )`bº(c®d)«b

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