Двойственность

Определение 7.1. Функция f () называется двойственной к функции g (), если f () = ().

Возьмём отрицания над обеими частями равенства и подставим

вместо , получим () = () = g (),

т.е. функция g двойственна к f. Таким образом, отношение двойственности между функциями симметрично. Из определения двойственности следует, что для любой функции двойственная определяется однозначно. Может оказаться, что функция двойственна самой себе.

Определение 7.2. Функция f () называется самодвойственной, если f () = ().

Примеры двойственных функций. Дизъюнкция и конъюнкция двойственны в силу законов де Моргана. Константа 1 и константа 0 двойственны в силу свойств констант: , .

Пример 7.1. Функция Ú Ú - самодвойственная. Действительно Ø( Ú Ú ) = ( Ú ) ( Ú ) ( Ú ) =

( Ú Ú Ú )( Ú ) = ( Ú Ú )( Ú ) =

( Ú Ú Ú Ú Ú ) = Ú Ú .

Для выяснения самодвойственности можно сравнить таблицы истинности функций f () и ().

Пример 7.2. Является ли функция f= (1011) самодвойственной? Зададим f табличным способом:

		f	f ( )	( )

Т.к. f ( )¹ ( ), то функция не является самодвойственной.

Из определения двойственности вытекает следующее утверждение, называемое принципом двойственности: Если в формуле F, представляющей функцию f, все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула будет представлять функцию , двойственную f. В булевой алгебре принцип двойственности имеет более конкретный вид:

Принцип двойственности в булевой алгебре. Если в формуле F, представляющую функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции - на конъюнкции, 1 на 0, 0 на 1, то получим формулу , представляющую функцию , двойственную f.

Date: 2015-06-06; view: 1308; Нарушение авторских прав