Представить в виде формул над системой (дискр. мат.)

[rar]

Представить формулами и функциональными схемами над

$$\Sigma$$

функции

$$0$$

,

$$1$$

,

$$\bar x$$

,

$$x\&y$$

и

$$x\vee y$$

.


Система функций

$$\Sigma =\{f, g, h\}$$

.

Таблица истинности функций системы:

$$\begin{array}{ccccccc} x_1&x_2&x_3& &f&g&h\\ 0&0&0&&0&1&0\\ 0&0&1&&1&0&0\\ 0&1&0&&0&0&0\\ 0&1&1&&1&1&1\\ 1&0&0&&1&1&0\\ 1&0&1&&0&0&1\\ 1&1&0&&1&0&1\\ 1&1&1&&0&1&1\\ \end{array}$$

Система полна по Теореме Поста (проверка полноты это первая часть задания была).

Вот таблица полноты системы:



Ну вот теперь объясните мне, как представить формулами и функциональными схемами на системой эти элементарные функции. Опиши, что для этого надо. Какой алгоритм. А-то, я не совсем понимаю как это делается.

[Xaositect]

В общем случае - ничего, кроме перебора.
В данном конкретном функции достаточно хорошие
$f = x_1\oplus x_3$
$g = x_2\oplus x_3\oplus 1$
функция $h$ известна как медиана: $h = x_1x_2\vee x_2x_3\vee x_1x_3 = x_1x_2\oplus x_2x_3\oplus x_1x_3$
Начать можно с отождествления всех или некотрых переменных у наших функций. Например:
$0 = f(x,x,x)$
А когда получите константы, можно их подставлять в исходные функции и получать что-нибудь полезное:
$h(0,x,y) = xy$

[rar]

А таблица полноты у меня правильно составлена? Посмотрите пожалуйста.

[Xaositect]

$f$ немонотонна. Остальное верно.

[rar]

Xaositect в сообщении #215847 писал(а):

$f$ немонотонна. Остальное верно.

Хм. Вот мой алгоритм:

$$N_f=\{001, 011, 100, 110\}$$

$$M_1=\{001, 011\}$$

$$M_2=\{011\}$$

$$M_3=\{100, 110\}$$

$$M_4=\{110\}$$

$$M_i\subset N_f$$

для всех

$$i=1,...,4$$

$$\Rightarrow$$

$$f\in M$$

Разве не верно?

[Xaositect]

$f(011)>f(111)$, хотя $011<111$

Если я правильно понимаю, у вас множества $M$ должны включать все наборы, большие или равные данного.
То есть, например, $M_2 = \{011, 111\}$

[rar]

Вот описание алгоритма:

I. Наборы

$$N_f$$

записываем в порядке возрастания номеров:

$$N_f=(\tilde \delta_1, ... , \tilde \delta_T)$$

,

$$0\leqslant p(\tilde \delta_1)<...<p(\tilde \delta_T)\leqslant 2^n-1$$

(

$$p(\tilde \delta_i)$$

- десятеричный номер двоичного числа).
II. Последовательно для каждого

$$i=1,2,...,T$$

находим множество

$$M_i=\{\tilde \delta\in E^n|\tilde \delta_i\leqslant\tilde \delta\}$$

.

Проверяем условие

$$M_i\subset N_f$$

,

$$i=1,2,...,T$$

. Если оно выполняется для всех индексов

$$i$$

, то функция

$$f(x_1,...,x_n)$$

- монотонна. В противном случае - немонотонна. Причем при первом

$$i$$

, для которого

$$M_i\subset N_f$$

не выполняется, алгоритм прекращает работу.


Делал в точности по этому методу. Получается, что функция монотонна. Разве не так? Если нет объясните.

[Xaositect]

Ну вот
Возьмем ваш второй набор 011
Надо построить множество $M_2 = \{\delta\in E_2^n|011\leq \delta\}$
Оно будет $\{011,111\}$, а не $\{011\}$

[rar]

В

$$N_f$$

набора

$$111$$

нет.

[Xaositect]

rar в сообщении #215867 писал(а):

В

$$N_f$$

набора

$$111$$

нет.

Вот именно. В $N_f$ набора 111 нет, а в $M_2$ он есть.
Если бы будем для $M_i$ брать наборы только из $N_f$, то у нас все $M_i$ точно будут подмножествами $N_f$. Вся суть в том, что на всех наборах $\delta\geq011$ должна быть единица.

[rar]

Xaositect в сообщении #215892 писал(а):

Вот именно. В $N_f$ набора 111 нет, а в $M_2$ он есть.

А как он там оказался?

[Xaositect]

$M_2 = \{\delta|\delta\geq 011\}$
$111\geq 011$

[rar]

Да и по многочлену Жегалкина для

$$h$$

. У меня он получается

$$h(x_1,x_2,x_3)=0$$

. Правильно?

[Xaositect]

$h(x_1,x_2,x_3)$ никак не может быть равно 0
$h$ же не равна тождественно нулю.

[rar]

Xaositect в сообщении #215903 писал(а):

$M_2 = \{\delta|\delta\geq 011\}$
$111\geq 011$

Честно. Не понимаю, как вы к этому приходите.
Я рассуждаю так. Берем первый набор из

$$N_f=\{001, 011, 100, 110\}$$

. Это- $$011$$. Сравниваем его с каждым набором после него стоящим.
То есть,

$$011$$

сравниваем с

$$011$$

. Сравниваем первые цифры 0 <= 1 - да. Вторые 0 <= 1 - да. Третьи 1 <= 1 - да.
Получаем

$$M_1=\{001, 011, ...\}$$

(сам набор всегда входит первым)
Сравниваем со следующим. 0 <= 1 - да. 0 <= 0 - да. 1 <= 0 - нет. Третий набор не входит. И так до последнего. И получаем

$$M_1=\{001, 011\}$$

(только два набора). И так далее.
По этому алгоритму у меня никакого 111 там не получается.

-- Чт май 21, 2009 18:43:21 --

Xaositect в сообщении #215906 писал(а):

$h(x_1,x_2,x_3)$ никак не может быть равно 0
$h$ же не равна тождественно нулю.

Вот как я находил многочлен Жегалкина:

$$\left\{\begin{array}{l} a_0=h(0,0,0)=0 \\ a_1=h(0,0,0)\oplus h(1,0,0)=0\oplus 0=0 \\ a_2=h(0,0,0)\oplus h(0,1,0)=0\oplus 0=0 \\ a_3=h(0,0,0)\oplus h(0,0,1)=0\oplus 0=0 \end{array}$$

$\Phi(x_1,x_2,x_3)=a_0\oplus a_1x_1\oplus a_2x_2 \oplus a_3x_3=0\oplus 0x_1 \oplus 0x_2\oplus 0x_3=0\oplus 0\oplus 0 \oplus 0=0$