Теоретические вопросы по булевой алгебре

[rar]

Есть такие теоретические вопросы к экзамену. Не могли бы вы помочь мне коротко ответить хотя бы на некоторые.

I. Реализация булевой функции функциональной схемой над полной системой функциональных элементов. Алгоритм построения минимальной функциональной схемы, реализующий заданную функцию.
II. Понятие сложности булевой функции в классе функциональных схем. Теорема Шеннона.
III. Реализация булевой функции контактной схемой. Алгоритм построения минимальной контактной схемы, реализующий заданную функцию.
IV. Понятие сложности булевой функции в классе контактных схем. Теорема Шеннона.

[Xaositect]

Насчет алгоритмов - алгоритм точного построения минимальной схемы -- переборный (задача $\mathbf{NP}$-полна). Так что, вероятно, имеется в виду перебор всех схем, начиная с наименее сложных, и проверка того, реализуют ли они нашу функцию. В любом случае, по вопросу алгоритмов сверьтесь с теми материалами, которые рекомендует преподаватель
Насчет остального - я Вам разве не давал ссылок на Ложкин С.А. — Основы кибернетики? Там все это есть. Если я правильно понимаю, под "теоремой Шеннона" здесь понимается асимптотика функции Шеннона для СФЭ и КС соответственно ($L(n)\sim \dfrac{2^n}{n}$).

[rar]

Спасибо. Разберусь.
И еще одна просьба: не могли бы вы привести какой-нибудь простенький алгоритм проверки булевой функции на монотонность?

[Xaositect]

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

И еще одна просьба: не могли бы вы привести какой-нибудь простенький алгоритм проверки булевой функции на монотонность?

Проверка всех соседних пар наборов. Функция монотонна тогда и только тогда, когда для любых $\alpha$ $f(\alpha_1,\alpha_2,\dots,0,\dots,\alpha_n) \leq f(\alpha_1,\alpha_2,\dots,1,\dots,\alpha_n)$

Иногда просто сразу видно, что функция монотонная, если она представлена формулой, содержащей только монотонные функции. Например, $x\vee yz$.

[rar]

А простыми словами можно сказать, что такое свойство монотонности булевой функции? Для лучше понятийного аппарата, так сказать.
В непрерывном анализе понятно, что такое монотонность функции. А вот в дискретном анализе ещё не совсем.

[Xaositect]

Вот есть у нас булев куб $E_2^n$.
Мы можем ввести на нем порядок $(\alpha_1,\dots,\alpha_n)\leq(\beta_1,\dots,\beta_n) \Leftrightarrow \forall i\ \alpha_i \leq \beta_i$. Этот порядок частичный. Например, $(0,0)\leq (1,0)$, $(0,1)\leq (1,1)$, а $(1,0)$ и $(0,1)$ несравнимы.
Так вот, функция $f$ монотонна, если $\alpha\leq\beta \Rightarrow f(\alpha)\leq f(\beta)$.
Если нарисовать ее на кубе, то можно провести границу, выше которой - единицы, а ниже - нули. Вот пример для функции $x\vee yz$
$\begin{tikzpicture}\draw [color=blue] (0,0)--(0,1); \draw (0,0)--(1,1) (0,0)--(-1,1); \draw [color=blue] (-1,1)--(-1,2) (-1,1)--(0,2); \draw (0,1)--(-1,2) (0,1)--(1,2); \draw[color=blue] (1,1)--(1,2) (1,1)--(0,2);\draw (-1,2)--(0,3) (0,2)--(0,3) (1,2)--(0,3); \fill (0,3) circle (2pt);\fill (0,2) circle (2pt);\fill (-1,2) circle (2pt);\fill (1,2) circle (2pt);\fill (0,3) circle (2pt);\fill (0,1) circle (2pt); \draw (0,0) circle (2pt); \draw (-1,1) circle (2pt);\draw (1,1) circle (2pt); \end{tikzpicture}$

[rar]

Спасибо.

-- Ср июн 17, 2009 21:52:12 --

Вот, допустим, есть функции:

$$\tilde f=01011010$$

$$\tilde g=10100101$$

$$\tilde h=01110001$$

Я установил, что ни одна из них не является монотонной. Правильно?
Потому как:
Для $f:$ $001\leqslant101$, а $f(001)=1>f(101)=0$
Для $g:$ $000\leqslant110$, а $f(000)=1>f(110)=0$
Для $h:$ $001\leqslant101$, а $f(001)=1>f(101)=0$

А если функция заведомо является монотонной, то для нее нужно делать полный перебор сравнений сравнимых наборов?

-- Ср июн 17, 2009 21:56:16 --

И что может сказать теорема Поста о системе из трех вышеприведенных функций?

-- Ср июн 17, 2009 21:58:19 --

И еще вопросик. А есть ли простенький метод определения линейности/нелинейности функции?

[Xaositect]

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

Я установил, что ни одна из них не является монотонной. Правильно?

Да.

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

А если функция заведомо является монотонной, то для нее нужно делать полный перебор сравнений сравнимых наборов?

Как я писал, можно перебирать только соседние.

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

И что может сказать теорема Поста о системе из трех вышеприведенных функций?

Все немонотонны, $h$ нелинейна, $f$ и $g$ несамодвойственны, $f$ не сохраняет $1$, $g$ не сохраняет $0$. Система полна.

-- Ср июн 17, 2009 21:40:25 --

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

И еще вопросик. А есть ли простенький метод определения линейности/нелинейности функции?

Есть такой алгоритм для функции, заданной вектором. Разделяем вектор $\tilde{f}$ на две половины --- левую и правую. Они будут соответствовать функциям $f_0 = f(0,\dots)$ и $f_1 = f(1,\dots)$. Так вот, $f$ линейна тогда и только тогда, когда $f_0$ и $f_1$ линейны и, кроме того, $f_0 \oplus f_1 = \mathrm{const}$.
Пример:
$\tilde{f} = (01101001)$
$\tilde{f_0} = (0110)$
$\tilde{f_1} = (1001)$
$\tilde{f_0} \oplus \tilde{f_1} = (1111)$ - хорошо
$\tilde{f_{00}} = (01)$ - линейна ($f(x) = x$)
$\tilde{f_{01}} = (10)$ - линейна ($f(x) = x\oplus 1$)
$\tilde{f_{00}} \oplus \tilde{f_{01}} = (11)$ - хорошо
Ну и так далее. Эта функция линейна.
Еще пример:
$\tilde{f} = (00010111)$
$\tilde{f_0} = (0001)$
$\tilde{f_1} = (0111)$
$\tilde{f_0} \oplus \tilde{f_1} = (0110)$ - плохо. Функция нелинейна.

А вообще, часто линейные функции угадыываются по паттерну $0110 1001 1001 0110 1001 0110 0110 1001\dots$ Последовательность_Морса-Туэ

[rar]

Понятно. Спасибо вам большое за советы.