Является ли функция полной Опции

[Tan]

Для того, чтобы доказать является ли функция полной мы рисуем табличку и смотрим, если среди всех столбиков нету тех, в которых были бы только +, то функция полная. Один из этих столбиков (классов) L отвечает за линейность функции, другой S за монотонность. У меня такой вопрос : как эти 2 параметра определить для любой функции и в частноcти для моей ( в моём случае это x | y ).

Сообщение отредактировано: Tan - 10.04.2007 20:38

[КМА]

Монотонность доказывается так.
Берем первый элемент a=(0, 0) и b=(0, 1) как второй элемент, тогда Tm:={f| a=<b => f(a)=<f(b)}, := значит по определению. Tm означает класс монотонных функций. Значит сравниваем при следующих наборах:

Код

a (0, 0) b (0, 1) f(a)<=f(b) == 1 <= 1 == true
a (0, 1) b (1, 0) f(a)<=f(b) == 1 <= 1 == true
a (1, 0) b (1, 1) f(a)<=f(b) == 1 <= 0 == false
Значит не монотонна

На счет линейности, то должно удовлетворить TL:={f | f= c0 +c1x1+...+cnxn}, где + это сложение по модулю 2, а c1x1 обозначет конъюнкцию с1 на х1

Добавлено через 5 мин.

что такое по Жегалкину

Разговор о полиноме Жегалкина. Представление булевой функции над базисом {0, 1, И, +}, где И конъюнкция и + сложение по модулю два.

Добавлено через 7 мин.
Но реально если надо доказать полноту Штриха Шеффера, то это довольно просто, достаточно через него задать функции {И, ИЛИ, НЕ}, о их полносте можно сказать хотя бы из существования СДНФ и СКНФ, т. е. любая функция может быть приведена хотя бы к одной из совершенных форм.

А доказать очень просто.

1) НЕ х= х|x
2) x1 И х2= НЕ (х1|x2)=(x1|x2)|(x1|x2)
3) x1 ИЛИ x2=(НЕ х1) И (НЕ х2)=(x1|x1) И (x2|x2)= ((x1|x1)|(x2|x2))|((x1|x1)|(x2|x2))