Найти базис функций самодвойственных и монотонных!! Дискра

denis2000

Это задача по дискре (ММ): базис пространства самодвойственных и монотонных функций. Если можете, напишите за воскресенье!
Спасибо!

62408

Базис для монотонных, например, {1, 0, xy, x v y}.
Можно сказать следующее: монотонные функции представляются в виде сокращённой дизъюнктивной нормальной формы, в которой не встречается отрицание => на него забиваем. Если выкинуть из предложенного базиса либо конъюнкцию, либо дизъюнкцию, то вторую нельзя будет получить с помощью оставшейся. Если убрать любую из констант, то получится ситуация, когда оставшаяся система не будет полна, поскольку она будет сохранять либо 0, либо 1, чего на самом деле для монотонных нет.
Можно взять базис с меньшим числом функций - {1,0, x v yz}.
Базис для самодвойственных - {xy' v xz' v y'z'}, где ' - черта.
Это самодвойственная функция, система из одного элемента, так что выкидывать для проверки подсистем на полноту смысла нет. Нужно показать, что с помощью предложенной функции можно выразить любую самодвойственную. Точного доказательства не помню.

denis2000

ОК, спасибо, насчёт этих базисов понятно. А как теперь из них получить базис пространства и монотонных, и самодвойственных. Т.е. пересечения этих пространств!

Sanych

Взять функцию
xy v yz v zx,
она же
x(y v z) v yz
Базис одноэлементный
подставляя x и z равные y, получаем функцию y=x(y) v y
подставляя
z=xp v xq v pq, получаем
x(p v q v y) v pqy
далее подставляя y=xr v xs v rs,
получаем x(p v q v r v s) v pqrs
ну и так далее с любым числом переменных
теперь произвольная (монотонная самодвойственная) функция f(x_1,x_2, ... x_n)
получается, например, следующим образом:
берём какую-нибудь основу, например x_1, а далее по очереди для всех наборов w_i на которых f(w)=0
добавляем соответствующее "слагаемое" по схеме:
F->
F(y_1 v y_2 v y_3 v... v y_s) v y_1y_2y_3 ...y_s
где (y_i) -- те переменные x_i, которые равны 0 для данного набора
В итоге получаем искомую функцию f.
пример: функция f(x,y,z)=y получается как
x->
(набор 0,0,0)
x(x v y v z)v xyz=x->
(набор 1,0,0)
x(yv z)v yz=xy v yz v xz->
(набор 0,0,1)
(xy v yz v xzx v y) v xy=(xy v xz v yz) v xy= xy v yz v zx->
(набор 1,0,1)
(xy v yz v zxy) v y=y
Вот так мне правда и самому это понятно только в виде рисунков на булевом кубе, но единственное, что можно сделать... пусть кто-нибудь соберётся и напишет, почему всё на самом деле очевидно
Оставить комментарий
Имя или ник:
Комментарий: