Понятие замкнутого класса. Класс монотонных логических функций.Понятие замкнутого класса. Класс линейный логических функций..

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

Классы логических функций

Функция, "сохраняющая 0".

Это - такая логическая функция, значение которой равно 0, если все аргументы равны 0: f(0,0,...,0) = 0.

Примером функции, сохраняющей 0, является функция .

Функция, "сохраняющая 1".

Это - такая логическая функция, значение которой равно 1, если все аргументы равны 1: f(1,1,...,1) = 1.

Примером функции, сохраняющей 1, является функция &.

"Монотонная" функция.

Это - такая логическая функция, которую можно выразить через & и .

Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары строк в таблице, которые отличаются всего в одном столбце (не считая крайнего правого). Например: 0,0,0,0 и 0,0,0,1; 1,0,0,1 и 1,1,0,1. Пусть в одной строке в некотором столбце стоит "0", а в другой строке в этом же столбце стоит "1". Нельзя, чтобы в крайнем правом столбце, где записано значение функции было наоборот: "1", а потом "0". Если такая ситуация нигде не встречается, то функция монотонная, и ее можно выразить через и &. Пример монотонной функции: .

"Линейная" функция.

Это - такая логическая функция, которую можно выразить через , 0 и 1.

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

Двойственные функции.

Логические функции f и g называются двойственными, если

f(~x1, ~x2,...,~xN) = ~g(x1, x2,..., xN).

Кратко это будем обозначать так: "f" * "g". Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Ниже приведен список двойственных функций для всех унарных и бинарных операций.
"0" * "1"
"x" * "x"
"~" * "~"
"&" * " "
" " * " "
"|" * " "
"<" * " "
">" * " "

"Самодвойственная" функция.

Это - логическая функция, которая двойственна самой себе:

f(~x1, ~x2,...,~xN) = ~f(x1, x2,..., xN).

 

 

37. Теорема о функциональной полноте в слабом смысле.

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

Определение. Система функций S называется полной в слабом смысле, если система является полной (в сильном смысле, т. е. в смысле определения в пункте 1).

Теорема 1. (Поста). Для того, чтобы система функций S была полной в слабом смысле необходимо и достаточно, чтобы она содержала хотя бы одну нелинейную функцию и хотя бы одну немонотонную функцию.

Теорема 2. (Пост). Для того, чтобы система функций была полной (в сильном смысле) необходимо и достаточно, чтобы она не содержалась целиком ни в одном из замкнутых классов K0, K1, KS, KM и KL.

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

Достаточность доказывается в 3 этапа:

1. построение констант 0 и 1 с помощью функций , и ;

2. построение функции–отрицания с помощью констант 0, 1 и функции;

3. построение конъюнкции с помощью констант 0, 1, функции и .

После этого учитывая, что дизъюнкция представляется через конъюнкцию и отрицание и что система полная, достаточность доказана.

Замечание. Из теоремы, в частности, следует, что всякий замкнутый класс, отличный от множества всех булевых функций, содержится в одном из классов K0, K1, KS, KM, KL. По этой причине перечисленные классы называют основными замкнутыми классами пространства булевых функций.

Пример. Рассмотрим совокупность булевых функций . Составим и заполним следующую таблицу, отмечая знаком «+» функции, принадлежащие соответствующим классам. Заполнение первых трех строчек очевидно. Кроме того, непосредственно видно, что функция сохраняет константы 0 и 1. Уже по форме записи она является линейной. Самодвойственоость функции вытекает из таблицы значений (см. на следующей странице), а монотонность очевидна из диаграммы Хассе.

Из таблицы видно, что множество функций S не содержится полностью ни в одном из пяти основных замкнутых классов (нет ни одного столбца целиком заполненного символами «+»). Следовательно, система функций S является полной (в сильном смысле), а совокупность – полная в слабом смысле.