Класс $S$. Теорема о замкнyтости класса $S$
Самодвойственная функция - булева функция, двойственная сама к себе.
Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции $~f(x_1, x_2,\dots,x_n)$ выполняется тождество $f (x_1,x_2,\dots,x_n)=\overline { f(\bar { x } _1,\bar { x } _2,\dots,\bar { x } _n) } $. Обозначают, что $f \in S$.
Функцией, двойственной к функции $f(x_1,\ldots,x_n)$, называется функция $f^*(x_1,\ldots,x_n)=\overline f(\overline x_1,\ldots,\overline x_n)$. Значит, функция $f(x_1,\ldots,x_n)$ является самодвойственной, если $\overline f(\overline x_1,\ldots,\overline x_n)=f(x_1,\ldots,x_n)$. Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.
Теорема: Класс самодвойственных функций замкнут относительно суперпозиции.
Доказательство: Пусть функции $f, g_1, g_2,…,g_m$ самодвойственны. Тогда $f^*=f, g_i^* = g_i~i=1 ... m$. Суперпозиция $h=f(g_1, g_2, ..., g_m)$ самодвойственна, ибо $h^* = (f(g_1, g_2, ..., g_m))^* =$\ { по теореме о суперпозиции двойственной ф-ции\ } $ = hf^*(g_1*, g_2*, ...,g_ { m } ^*) = h$
Построение двойственных функций.
Введём стандартное обозначение. Булеву функцию, двойственную $f$ будем обозначать как $f^*$.
Пусть ф-ция $f$ задана таблицей со стандартным упорядочением строк. Покажем, как по этой таблице для $f$ можно построить так же упорядоченную таблицу для $f^*$.
Алгоритм прост.
- Развернуть столбец значений $f_n$ вокруг центральной его точки на $180^\circ$ { последнее значение в столбце станет 1-м, предпоследнее – 2-м и т.д. } ;
- Выполнить поразрядное отрицание значений развёрнутого столбца { т.е. заменить в нём нули на единицы, а единицы на нули } ;
- Полученный в результате указанных выше действий столбец записать в стандартно упорядоченную таблицу как столбец значений функции $f^*$.
Множество самодвойственных функций обозначается символом $S$. Множество $S$ является замкнутым классом. Действительно, если функции $f(x_1,\ldots,x_n),f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n)$ являются самодвойственными, то функция $g(x_1,\ldots,x_n)=f(f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n))$ также является самодвойственной: $\overline g(\overline x_1,\ldots,\overline x_n) = \overline f(f_1(\overline x_1,\ldots,\overline x_n),\ldots,f_k(\overline x_1,\ldots,\overline x_n)) = \overline f(\overline f_1(x_1,\ldots,x_n),\ldots,\overline f_k(x_1,\ldots,x_n)) = $ $ = f(f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n)) = g(x_1,\ldots,x_n)$.
$S$ является предполным классом.
Примеры самодвойственных функций: $x, \overline x, (x\wedge y)\vee(x\wedge z)\vee(y\wedge z)$. В свою очередь конъюнкция, дизъюнкция и константы самодвойственными не являются.
Далее:
Несобственные интегралы от неограниченной функции
СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице
Булевы функции от $n$ переменных
Класс Te . Теорема о замкнутости Te
Вычисление криволинейного интеграла первого рода. Примеры
Теорема об алгоритме распознавания полноты
Вычисление тройного интеграла. Теорема о переходе от тройного интеграла к повторному
Замена переменных в тройном интеграле
Частные случаи векторных полей
Вычисление криволинейного интеграла первого рода. Плоский случай
Условия независимости криволинейного интеграла от пути интегрирования
Примеры применения цилиндрических и сферических координат
Функции k-значной логики. Элементарные функции. Лемма об аналоге правила де Моргана
Теорема Стокса
Формула Грина
Огравление $\Rightarrow $
Комментарии ()