Булевы функции. Полнота и замкнутость. Теорема Поста о полноте

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

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

Пример: Рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных .

Булева функция n переменных F однозначно определяется - разрядным булевым вектором ее значений (т.е. - таблица истинности функции F). Например, в этом примере имеем =(00100111).

Рассматриваемая булева функция F принимает значения 0 на наборах 000, 001, 011 и 100, а значение 1 – на наборах 010, 101, 110 и 111.

Определение: Множество наборов, на которых функция F принимает значение 1, называется характеристическим и обозначается через .

Утверждение: Число булевых функций от n переменных .

Булевы функции (функции алгебры логики):

1. функция () – равна 0 (1) не зависимо от значения аргумента;
2. тождественная функция х – значение функции равно значению аргумента;
3. функция отрицания ()-значение функции равно противоположному значению аргумента;
4. конъюнкция () – равна 1, когда оба аргумента равны 1 – Логическое умножение (И);
5. дизъюнкция () – равна 0, когда оба аргумента равны 0 – Логическое сложение (ИЛИ);
6. сумма по модулю два () – найти обычную сумму и вычислить остаток от деления на 2. Если четное, то «0», если нечетное, то «1»;
7. функция эквивалентности () – отрицание суммы по модулю два () равна 1, когда значения аргументов совпадают;
8. функция импликации () – равна 0, когда , в остальных случаях 1 – Логическое следование;

1. стрелка Пирса () - отрицание - Логическое ИЛИ-НЕ
2. штрих Шеффера () – отрицание - Логическое И-НЕ

Обозначим через любую из функций , , . Существенно только, чтобы символ в тождестве всюду имел один и тот же смысл.

1) обладает свойствами ассоциативности:

2) обладает свойствами коммутативности:

3) для конъюнкции и дизъюнкции выполняются дистрибутивные законы:

4) Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:

5) Выполняются следующие свойства конъюнкции и дизъюнкции:

Пусть имеется некоторая система булевых функций . Замыканием этой системы называется мн-во функций которые могут быть получены их данных, путём применения всевозможных подстановок. (ex: )

Система функций называется полной если её замыкание совпадает с мн-вом всех булевых функций (ex: полные системы).

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

(ex: - не замкнутая; -замкнутая; -замкнутая, т.к. )

Классы булевых функций:

1)

2)

3) S – класс самодвойственных функций (если набора булевых функций, определяется ).

4) М – класс монотонных функций. Функция называется монотонной, если для любой пары сравниваемых наборов выполняется условие:

5) L – класс линейных функций. Функция вида называется линейной (ex: )

Утверждение: Все 5 классов являются замкнутыми.

Докажем замкнутость первых 4х классов:

1. Рассмотрим произвольную пару функций класса : , . Образуем суперпозицию подстановкой в вместо . Найдем значение получившейся функции на нулевом наборе: , .
2. Возьмем произвольные функции из класса : , . Образуем суперпозицию подстановкой в вместо . Найдем значение получившейся функции на нулевом наборе: , .
3. 
4. Рассмотрим произвольную пару сравнимых наборов:

,

Лемма1: Если , то из неё путём подстановки функций можно получить константу.

Лемма2: Если то из неё путём подстановки констант 0 и 1 и функции x можно получить функцию

Лемма3: Если , то из неё путём подстановки констант 0 и 1 и функций , а также, быть может, путём навешивания отрицания над , можно получить функцию

Теорема Поста о полноте: Пусть некоторая система, эта система будет полной тогда и только тогда, когда она не содержится ни в одном из 5 замкнутых классов. Пусть тогда

Пример: система полна.

Док-во: (необходимость) Если система функций V – полна, то она ни одному из классов

Предположим противное. Пусть - полная система: Пример:

получили противоречие, т.е.

(достаточность) полна. Пусть полна.

Док-во достаточности будем проводить в три этапа.

I. Рассмотрим функцию Возможны два случая:

1. Тогда есть константа 1, ибо

Вторая константа получается из:

2. . Тогда есть , ибо

Возьмём , т.к. мы имеем , то в силу леммы1 из мы можем получить константу. Итак, в обоих случаях мы получаем константы 0 и 1.

II. Построение при помощи констант 0, 1 и функции , функции . Это осуществляется на основе леммы 2.

III. Построение при помощи констант 0, 1 и функций и . Это осуществляется на основе леммы 3.

Таким образом, мы реализовали функции . Этим достаточность доказана.