Вторник, 06.12.2016, 18:58
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 57
Гостей: 57
Пользователей: 0
» »
08:41
Двойственные функции - что это

Двойственные функции

  • Определение. Двойственной для функции f(x1, x2, …, xn) называется функция$f^*(x_1, x_2,..., x_n)=\overline{f\left ( \bar{x_1}, \bar{x_2},... \bar{x_n} \right )}$

Пример. Построить функцию, двойственную данной:

$1.\,  f=x\vee y;$
$2. \, f=x\rightarrow y.$

Решение.

$1. f^*=\overline{\bar{x}\vee \bar{y}}=\bar{\bar{x}}\wedge\bar{\bar{y}} ;$
$2. f^*=\overline{\bar{x}\rightarrow \bar{y}}=\overline{\bar{\bar{x}} \vee  \bar{y}}=\bar{\bar{\bar{x}}}\wedge \bar{\bar{y}}=\bar{x}\wedge y.$

  • Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
  • Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция $\bar{f}  тоже самодвойственна.
  • Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
  • Противоположными называются те наборы, которые в сумме дают двоичный код числа (2n-1).


Пример. Выяснить являются ли функции самодвойственными:

$1.\,  f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z};$
$2\, f=01110010.$

Решение.
1. Строим таблицу истинности для данной функции  $f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z}$ (табл. 1)

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.


2. Строим таблицу значений для функции f = 01110001 (табл. 2).

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.

  • Теорема. Класс $S =\left \{ f \mid  f = f* \right \}$  самодвойственных функций замкнут относительно суперпозиций.
Категория: Дискретная математика | Просмотров: 224 | Добавил: Admin | Теги: булева алгебра | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .