Files
2024-06-23 14:21:36 +03:00

4.1 KiB
Raw Permalink Blame History

Двойственная функция. Принцип двойственности. Самодвойственные функции. Замкнутость класса 𝑆. Лемма о несамодвойственной функции

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

Двойственная функция f^* - f^*(x_1, x_2, \dots, x_n) = \overline{f(\overline{x_1}, \overline{x_2}, \dots, \overline{x_n})} (f^*)^* = f

Примеры:

  • 0^* = 1
  • x^* = x
  • \bar x^* = \bar x
  • (xy)^* = x \vee y
  • (x \oplus y)^* = x \equiv y
  • (x|y)^* = x \downarrow y
  • (x \rightarrow y)^* = y > x

Принцип двойственности

Теорема

Пусть f(x_1, x_2, \dots, x_n) и g(y_1, y_2, \dots, y_m) - логические функции и h = f(x_1, x_2, \dots, x_{k-1}, g(x_1, y_2, \dots, y_m), x_{k+1}, \dots, x_n) Тогда h^* = f^*(x_1, x_2, \dots, x_{k-1}, g^*(y_1, y_2, \dots, y_m), x_{k+1}, \dots, x_n)

Доказательство

НУО k = n: h(x_1, x_2, \dots, x_{n-1}, y_1, y_2, \dots, y_m) = f(x_1, x_2, \dots, x_{n-1}, g(y_1, y_2, \dots, y_m))

По определению двойственности, h^*(x_1, x_2, \dots, x_{n-1}, y_1, y_2, \dots, y_m) = \overline{h(\overline{x_1}, \overline{x_2}, \dots, \overline{x_{n-1}}, \overline{y_1}, \overline{y_2}, \dots, \overline{y_m})} = \overline{f(\overline{x_1}, \overline{x_2}, \dots, \overline{x_{n-1}}, g(\overline{y_1}, \overline{y_2}, \dots, \overline{y_m}))} g(\overline{y_1}, \overline{y_2}, \dots, \overline{y_m}) = \overline{g^*(y_1, y_2, \dots, y_m)}, поэтому h^* = \overline{f\left(\overline{x_1}, \overline{x_2}, \dots, \overline{x_{n-1}}, \overline{g^*(y_1, y_2, \dots, y_m)}\right)} = f^*(x_1, x_2, \dots, x_{n-1}, g^*(y_1, y_2, \dots, y_m))

Следствие

Пусть функция 𝑓 представлена некоторой формулой/схемой. Чтобы получить формулу/схему, представляющую функцию 𝑓^, нужно заменить в формуле все операции и константы / функциональные элементы на двойственные им.

Самодвойственные функции

Самодвойственная функция (класс S) - f(x_1, x_2, \dots, x_n) = f^*(x_1, x_2, \dots, x_n) Не существует самодвойственных функций, существенно зависящих от 2х переменных

Замкнутость класса 𝑆

Теорема

Класс S замкнут

Доказательство

Пусть f(x_1, x_2, \dots, x_n) \in S и g(y_1, y_2, \dots, y_m) \in S Рассмотрим h(x_1, x_2, \dots, x_{n-1}, y_1, y_2, \dots, y_m) = f(x_1, x_2, \dots, x_{n-1}, g(y_1, y_2, \dots, y_m)) Из принципа двойственности, h^* = f^*(x_1, x_2, \dots, x_{n-1}, g^*(y_1, y_2, \dots, y_m)) = f(x_1, x_2, \dots, x_{n-1}, g(y_1, y_2, \dots, y_m)) = h, следовательно, h \in S

Лемма о несамодвойственной функции

Лемма

Если функция f несамодвойственна, то константы являются суперпозицией функций f и \bar x. Т.е. если f \notin S, то {0,1} \subseteq [\{f, \bar x\}]

Доказательство

Пусть f(x_1, x_2, \dots, x_n) \notin S. Тогда существует такой набор (\alpha_1, \alpha_2, \dots, \alpha_n), что f(\alpha_1, \alpha_2, \dots, \alpha_n) = f(\bar\alpha_1, \bar\alpha_2, \dots, \bar\alpha_n) = c \in \{0,1\} (1 курс/2 семестр/Дискретка/Билеты/3#Разложение функции по переменной)

h(x) = f(x^{\alpha_1}, x^{\alpha_2}, \dots, x^{\alpha_n}) h(0) = f(0^{\alpha_1}, 0^{\alpha_2}, \dots, 0^{\alpha_n}) = f(\bar\alpha_1, \bar\alpha_2, \dots, \bar\alpha_n) = c h(1) = f(1^{\alpha_1}, 1^{\alpha_2}, \dots, 1^{\alpha_n}) = f(\alpha_1, \alpha_2, \dots, \alpha_n) = c

Следовательно, h(x) = c, \overline{h(x)} = \bar c