Построение функций-констант

Рассмотрим функцию f0. По определению f0(0,..., 0) = 1.

Если f0(1,..., 1) = 1, то h(x) = f0(x,..., x) = 1, т.е. это функция, получаемая из f0 отождествлением всех переменных, является константой 1. В противном случае f0(1,. . . , 1) = 0.Поэтому f0(x,...,x) = Построение функций-констант - student2.ru . Тогда по лемме о несамодвойственной функции из f0 с помощью функции отрицания и тождественной функции можно получить одну из констант.

Вторая константа получается из первой константы с помощью отрицания (т.е. является отрицанием первой константы).

Значит, из f0 можно получить либо одну из констант, либо обе константы и отрицание.

Рассмотрим функцию f1. По определению этой функции f1(1,...,1) = 0. Если f1(0, . . . , 0) = 0, то f1(x, . . . , x) = 0, т.е. это функция-константа 0.

В противном случае f1(0, . . . ,0) = 1 и f1(x, . . . , x) = Построение функций-констант - student2.ru . Тогда из леммы о несамодвойственной функции следует, что из f1 можно получить одну из констант. Вторая константа получается из первой константы с помощью функции Построение функций-констант - student2.ru .

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

4.14.2. Построение отрицания

Рассмотрим функцию fM. По лемме о немонотонной функции через fM с помощью функций-констант и тождественной функции x можно выразить отрицание Построение функций-констант - student2.ru .

4.14.3.Построениеконъюнкции

Рассмотрим функцию fL. По лемме о нелинейной функции из fL с помощью уже полученных функций 0, 1, Построение функций-констант - student2.ru и обозначений переменных можно выразить конъюнкцию x1&x2.

Следовательно, через функции системы B можно выразить функции полной системы Построение функций-констант - student2.ru . Тогда на основании теоремы редукции можно утверждать, что B - это полная система.

Доказательство окончено.

Упражнение.

Используя доказательство критерия полноты, выразить функции x1&x2 и Построение функций-констант - student2.ru через функции полной системы Построение функций-констант - student2.ru .

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

При этом если система B является конечной, то такая проверка может быть проведена за конечное время.

Для проверки полноты произвольной конечной системы B можно построить таблицу со строками, соответствующими функциям системы B, и пятью столбцами, соответствующими пяти классам: Т0, Т1, S, L и M.

Таблица заполняется символами "+" и "-". Некоторый элемент таблицы это "+", если функция, соответствующая строке, содержится в классе функций, соответствующем столбцу. В противном случае элемент таблицы равен "-".

Если в каждом столбце полученной таблицы имеется хотя бы один минус, то B - это полная система.

Если в таблице имеется столбец, содержащий только символы "+", то B - это неполная система.

Например. Для системы B = {x1 ® x2, x1 + x2} таблица имеет вид:

  Т0 Т1 S L M  
x1 ® x2 - + - - -
x1 + x2 + - - + -

Следовательно, множество функций {x1 ® x2, x1 + x2} - это полная система.

Классы Т0, Т1, S, L и Mобъединяет одно общее свойство, которое состоит в том, что всякий из них является "почти" полным.

Наши рекомендации