2.4. Двойственность булевых функций
Операция (или функция) f называется двойственной для операции  , если таблица,
задающая функцию f, получается из таблицы,
задающей функцию , путём замены в ней всюду "0" на "1" и "1" на "0",
включая и замену значений функции.
Для примера рассмотрим функции дизъюнкции и коньюкции двух
переменных, которые задаются соответствующими таблицами:
| X1 |
X2 |
v |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 | |
|
| X1 |
X2 |
& |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 | |
Преобразуем вторую таблицу в соответствии с введенным
обозначением, получим:
| X1 |
X2 |
? |
| 1 |
1 |
1 |
| 1 |
0 |
1 |
| 0 |
1 |
1 |
| 0 |
0 |
0 | |
 |
| X1 |
X2 |
v |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 | |
Что соответствует таблице операции дизъюнкции с точностью
до перестановки строк.
Преобразование формул, при котором знаки всех операций в
логическом выражении заменяются на знаки двойственных им
операций, "0" заменяется на "1", а "1" на "0", называется
преобразованием двойственности.
В качестве примера рассмотрим преобразование следующей
функции трех переменных (табл 2.2).
СДНФf =
X1· X2· X3 v
X1·
X2·
X3 v
X1· X2· X3;
СКНФf =
(X1 v
X2 v X3)·
(X1 v X2 v
X3)·
(X1 v
X2 v X3)·
(X1 v X2 v
X3)·
(X1 v X2 v X3).
Таблица 2.2.
| X1 |
X2 |
X3 |
f |
| 0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
0 |
| 0 |
1 |
0 |
0 |
| 0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
0 |
0 |
| 1 |
1 |
1 |
0 |
Выполним из функции преобразование двойственности (Табл. 2.3)
Таблица 2.3.
| X1 |
X2 |
X3 |
f * |
| 1 |
1 |
1 |
0 |
| 1 |
1 |
0 |
1 |
| 1 |
0 |
1 |
1 |
| 1 |
0 |
0 |
0 |
| 0 |
1 |
1 |
0 |
| 0 |
1 |
0 |
1 |
| 0 |
0 |
1 |
1 |
| 0 |
0 |
0 |
1 |
Совершенные нормальные формы для двойственной функции
f * примут вид:
СДНФ f * =
X1· X2· X3 v
X1· X2· X3 v
X1· X2· X3 v
X1· X2· X3 v
X1· X2· X3;
СКНФ f * =
(X1 v X2 v X3)·
(X1 v X2 v X3)·
(X1 v X2 v X3).
Отсюда следует, что:
СДНФ f =
(СДНФ f * )*
СКНФ f =
(СКНФ f * )*
СДНФ f * =
(СКНФ f )*
СКНФ f * =
(СДНФ f )*
|
.gif){kind=spacer}
