1 Множества. Логика Буля - лекции

►Пример. Суперпозиции функции штрих Шеффера x1 | x2 имеют

следующий вид: x1 | x1 , x1 | (x1 | x2 ) , x1 | (x2 | x3 ) и так далее. Таким образом, суперпозиция функций одного аргумента порождает функции одного ар-

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

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

Теорема 1. Каждый из классов булевых функций, а также множество всех булевых функций, является замкнутым.

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

Теорема Поста12. Для того чтобы система булевых функций была базисной, необходимо и достаточно, чтобы она включала в себя хотя бы одну функцию, не принадлежащую 0-, 1-, 2-, 3- и 4- классам.

Другими словами, система функций является базисной, если она перекрывает нулями все строки 0-, 1-, 2-, 3- и 4- классов в табл. 2. Например, системы функций f 2 , f7 , f16 ; f 2 , f11 ; f8 , f11 – базисные.

Таким образом, ответом на поставленный выше вопрос является сле-

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

►Пример. Проверить систему функций { , } на функциональную

полноту.

Решение. Проверим, выполняется ли теорема Поста для данной си-

12 Эмиль Леон Пост (1897, Августов, Царство Польское (ныне Польша) — 1954, Нью-Йорк) — американский математик и логик; один из основателей многозначной логики; основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.

45

СДНФ и СПНФ функции x1 x2 имеет вид: fСДНФ fСПНФ x1 x2 . СПНФ содержит конъюнкцию переменных, поэтому функция x1 x2 не линейная и не принадлежит 2-классу.

Найдѐм значения исходной и двойственной ей функций.

Значения исходной функции и двойственной ей не равны, поэтому

46

Значения исходной функции и двойственной ей равны, поэтому x1 – самодвойственная и принадлежит 3-классу.

При x1 0 x1 1 f (x1 ) 0 1 f (x1 ) 1 0 , значит, функция x1 не монотонная и не принадлежит 4-классу.

Результаты исследования занесѐм в таблицу 3.

Мы показали, что система функций { , } не содержится целиком ни

в одном из пяти классов, следовательно, по теореме Поста { , } – полная

система функций. ◄ ►Пример. Проверить систему, состоящую из одной функции {|} , на

Многочлен Жегалкина имеет вид:

47

f (x1 , x2 ) 1 x1 x2 .

Поэтому функция штрих Шеффера не линейная. Из теоремы Поста следует, что штрих Шеффера образует полную систему функций. ◄

48