Основные свойства элементарных функций

1. Коммутативность: , где .

2. Ассоциативность: , где .

3. Дистрибутивность

,

,

.

4. Законы де Моргана:

а) ; б) .

5. Закон двойного отрицания .

Для упрощения формул часто используются тождества:

6. Законы поглощения: а) ; б) .

7. а) ;

б) ;

в) ;

г) ;

д) .

8. а) ; б) .

9. а) (склеивание);

б) (обобщенное склеивание); и т.д.

Для проверки всех приведенных равенств достаточно воспользоваться таблицей истинности.

Функция называется двойственной к функции .

Табл. 1.8

0	0	0	1	1
0	0	1	0	0
0	1	0	1	0
0	1	1	0	0
1	0	0	1	1
1	0	1	1	0
1	1	0	1	1
1	1	1	0	0

Замечание. Таблица двойственной функции получается из таблицы функции инвертированием столбца значений функции и его переворачиванием (см. табл. 1.8).

Из определения двойственности следует, что

,

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

Функция называется самодвойственной, если . Например, самодвойственными являются функции и .

Обозначим через все различные символы переменных, встречающихся в множествах .

Теорема. Если

, то

.

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

.

Следствие. (Принцип двойственности.) Если формула реализует функцию , то формула реализует функцию . Эту формулу называют формулой, двойственной к , и обозначают . Задачи для самостоятельного решения

1. Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :

а) и ;

б) и ;

в) и ;

г) и .

2. Построив таблицы соответствующих функций, убедиться в справедливости следующих равенств:

а) ;

б) ;

в) ;

г) ;

д) .

3. Используя свойства элементарных функций, доказать эквивалентность формул и :

а) и ;

б) и ;

в) и .

4. Найти пары двойственных функций и все самодвойственные функции в множестве:

а)

, ;

б).

5. Доказать, что является двойственной к :

а) , ;

б) , ;

в) и .

6. Функция называется симметрической, если , где произвольная перестановка чисел . Определить число симметрических функций от переменных. Ответы

1. а), б), в), да; г) нет. 4. а) пары двойственных: , , ; самодвойственных функций нет; б) , , , . 6.