§7. Двойственность.
Определение
7.1. Функция
f(
)
называется двойственной к функции g(
),
если f(
)
=
(
).
Возьмём отрицания над обеими частями равенства и подставим
вместо
,
получим
(
)
=
(
)
= g(
),
т.е. функция g двойственна к f. Таким образом, отношение двойственности между функциями симметрично. Из определения двойственности следует, что для любой функции двойственная определяется однозначно. Может оказаться, что функция двойственна самой себе.
Определение 7.2. Функция f( ) называется самодвойственной, если f( ) = ( ).
Примеры
двойственных функций.
Дизъюнкция и конъюнкция двойственны в
силу законов де Моргана. Константа 1 и
константа 0 двойственны в силу свойств
констант:
,
.
Пример 7.1. Функция самодвойственная. Действительно ( ) = ( ) ( ) ( ) =
( )( ) = ( )( ) =
( ) = .
Для выяснения самодвойственности можно сравнить таблицы истинности функций f( ) и ( ).
Пример 7.2. Является ли функция f=(1011) самодвойственной? Зададим f табличным способом:
|
|
f |
f ( ) |
( ) |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Т.к. f ( ) ( ), то функция не является самодвойственной.
Из
определения двойственности вытекает
следующее утверждение, называемое
принципом двойственности: Если в формуле
F,
представляющей функцию f
, все знаки
функций заменить соответственно на
знаки двойственных функций, то полученная
формула
будет представлять функцию
,
двойственную f.
В булевой алгебре принцип двойственности
имеет более конкретный вид:
Принцип двойственности в булевой алгебре. Если в формуле F, представляющую функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу , представляющую функцию , двойственную f.
§8. Полнота.
Определение 8.1. Система логических функций называется функционально полной, если любая логическая функция может быль представлена формулой над , т.е. является суперпозицией функций над .
Из
представления любой логической функции
булевой формулой следует, что система
{,
,
}функционально
полна, причем является функционально
избыточной. Функционально полной будет
и любая система, через функции которой
можно выразить дизъюнкцию, конъюнкцию
и отрицание.
1.
Система {,
}
функционально полная. Действительно,
из закона де Моргана
=
следует, что
и,
следовательно данная система функционально
полна.
2.
Система {,
}
функционально полная. Это вытекает из
следующих формул:
=
,
.
Пример
8.1. Выразить
функцию
(
)
в системе {,
}.
(
)
.
Пример 8.2. Запишем формулу из примера 9.1 в системе {, }.
(
)
.
3. Система {|} штрих Шеффера функционально полная. Ранее было установлено, что | = , тогда | = . При = =x последняя формула примет вид x | x = , получаем:
=
=
(
|
)|(
|
).
Следовательно, система {, } может быть представлена формулами над {|}. Откуда и следует полнота {|}.
4. Система {} стрелка Пирса функционально полная. Известно, что
=
.
Отсюда легко получить:
=
xx,
=
=( )( ). Система {} функционально полная.
5.
Система
{,
,
1} функционально
полная, т.к.
,
и следовательно любая функция полной
системы {,
}
может быть представлена формулами над
.