Участник:Fad Oleg — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Представление функции формулой)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Тождественные функции. Выражение функций друг через друга.)
Строка 9: Строка 9:
 
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций
 
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций
  
==Тождественные функции. Выражение функций друг через друга.==
+
==Тождественные функции. Выражение функций друг через друга==
  
 
{{Определение
 
{{Определение
Строка 17: Строка 17:
 
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
 
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
  
'''Примеры выражения функций через функции <tex>\{\land, \lor, \lnot \} </tex>.'''
+
{{Пример
 +
|example=Выразим следующие функции через функции <tex>\{\land, \lor, \lnot \} </tex>.
  
 
<tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex>
 
<tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex>
Строка 24: Строка 25:
  
 
<tex>\langle x, y, z \rangle =  \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )</tex>
 
<tex>\langle x, y, z \rangle =  \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )</tex>
 +
}}
  
 
== Подстановка одной функции в другую ==
 
== Подстановка одной функции в другую ==

Версия 15:41, 27 июня 2021

Представление булевых функций

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \{f_1,\ldots,f_n\}[/math]. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math], который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

  • Как построить по данной функции представляющую её формулу?
  • Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
    • В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
  • Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?

Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций

Тождественные функции. Выражение функций друг через друга

Определение:
Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения.


Приведение тождественной функции есть выражение булевой функции через другие.


Пример:
Выразим следующие функции через функции [math]\{\land, \lor, \lnot \} [/math].

[math] x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )[/math]

[math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]

[math]\langle x, y, z \rangle = \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )[/math]


Подстановка одной функции в другую

Определение:
Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math]-того аргумента функции [math]f[/math] значением функции [math]g[/math]:
[math]h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})[/math]


Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

При подстановке функции [math]g[/math] вместо [math]i[/math]-того аргумента функции [math]f[/math], результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:

1. [math] x_{1}, \ldots, x_{i-1}[/math] — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
2. [math] x_{i}, \ldots, x_{i+m-1} [/math] — используются как аргументы для вычисления значения функции [math]g(y_{1}, \ldots, y_{m})[/math]
3. [math] x_{i+m}, \ldots, x_{n+m-1} [/math] — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math]

Пример:

Исходные функции:

  1. [math] f(a,b) = a \vee b [/math]
  2. [math] g(a) = \neg a [/math]

[math] h(a,b) = f(a,g(b)) = a \vee \neg b [/math] — подстановка функции [math]g[/math] вместо второго аргумента функции [math]f[/math]. В данном примере при помощи подстановки мы получили функцию [math]h(a,b)=a \leftarrow b[/math].

Отождествление переменных

Определение:
Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math]-того аргумента функции [math]f[/math] вместо [math]j[/math]-того аргумента:
[math]h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})[/math]


Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math].

Пример:

[math] f(a,b) = a \vee b [/math] — исходная функция

[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию [math]P_{1}[/math] — проектор единственного аргумента.

Стандартный базис

Определение:
Стандартный базис — система булевых функций: [math]\{\land, \lor, \lnot \} [/math]


Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math], то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:

[math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]

[math] x \rightarrow y = \lnot x \lor y [/math]

[math] 0 = x \land \lnot x [/math]

Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.

[math] x \mid y = \lnot \left ( x \land y \right )[/math]

[math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]

Тождественность функций можно доказать с помощью таблицы истинности.

Пример:

Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math].

[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]

Полнота стандартного базиса

Утверждение:
Стандартный базис является полной системой булевых функций
[math]\triangleright[/math]
Данное утверждение - следствие теоремы об СДНФ. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.
[math]\triangleleft[/math]

Замечание:

По закону де Моргана:

[math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]

[math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]

Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:

[math] \{ \land , \lnot \} [/math] (конъюнктивный базис Буля)

[math] \{ \lor , \lnot \} [/math] (дизъюнктивный базис Буля)

Теоремы о числе функций в базисе

Теорема:
Максимально возможное число булевых функций в безызбыточном базисе — четыре.
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольный безызбыточный базис [math] X[/math]. Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):

[math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math], где [math] T_0, T_1, S, M, L[/math] — классы Поста.

Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\{f_0, f_1, f_s, f_m, f_l \}[/math] — полная, то [math]\left | X \right | \le 5[/math]

Рассмотрим [math]f_0[/math]. Возможны два случая:

1. [math] f_0(1, 1, \ldots, 1) = 0 [/math], тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.

[math] f_0 = f_1 = f_m [/math]. Значит, [math]\left | X \right | \le 3[/math].

2. [math] f_0(1, 1, \ldots, 1) = 1 [/math], тогда [math]f_0[/math] несамодвойственная, т.е.

[math] f_0 = f_s [/math]. Значит, [math]\left | X \right | \le 4[/math].
[math]\triangleleft[/math]
Теорема:
Для любого числа [math]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math], что [math]\left | X \right | = k[/math].
Доказательство:
[math]\triangleright[/math]

Приведём примеры базисов для каждого [math]k[/math]:

[math]k = 1 \Rightarrow X = \{ \downarrow \}[/math];

[math]k = 2 \Rightarrow X = \{ \lnot, \land \}[/math];

[math]k = 3 \Rightarrow X = \{ \land, \oplus, 1\}[/math];

[math]k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}[/math];

Докажем, что последняя система является базисом:

[math] 0 \notin T_1[/math];

[math] 1 \notin T_0[/math];

[math] x\land y \notin L\ и\ S[/math];

[math] x\oplus y\oplus z \notin M[/math]

(доказывается с помощью таблицы истинности).
[math]\triangleleft[/math]

Источники

Полные системы булевых функций — Википедия

Категория: Дискретная математика и алгоритмы

Категория: Булевы функции