Дискретная математика (стр. 6 из 10)

Пример.

,

если

, то и .

Функция

называется самодвойственной, если .

Пример. Покажем, что формула

задает самодвойственную функцию.

Убедимся, что на всех противоположных наборах значений переменных

и формула принимает противоположные значения. Действительно, составим таблицу истинности:

	x	y	z
0	0	0	0
0	0	0	1
0	0	1	0
1	0	1	1
0	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Получаем

, , , .

4. Класс монотонных функций (обозначается T_Mили M):

, где , , , .

5. Класс линейных функций (обозначается T_Lили L):

.

Эквивалентность является линейной функцией

. Стрелка Пирса – нет, .

, , ,…, ,

т. е.

, ,…, . (7)

Таким образом, проверка линейности сводится к нахождению коэффициентов

по формулам (7) и сопоставлению таблиц истинности данной формулы и полученной формулы .

Пример. Проверим, является ли линейной функция

. Имеем , , . Таким образом, . Сопоставляя таблицы истинности формул и , убеждаемся, что они не совпадают. Вывод: функция нелинейна.

Линейность функции можно также определить с помощью следующей теоремы.

Теорема Жегалкина. Всякая булева функция

представима полиномом Жегалкина, т. е. в виде , где в каждом наборе (i₁,…, i_k) все i_j различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.

Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных.

Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.

Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиомы булева кольца

и равенства, выражающие операции через операции этого булева кольца: и т. д.

Пример. Определим линейность функции

.

Имеем

Полученный полином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна.

Заметим, что если в эквивалентности

формулы являются различными конституентами единицы, то их произведение равно 0, и тогда . Следовательно, для получения полинома Жегалкина из СДНФ можно сразу заменить .

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

Пример. Определим, к каким классам Поста относится булева функция

.

Так как f (0,0)=1, а f (1,1)=0, то

и . Поскольку , то . Так как f (0,0)>f (1,1), то . Полином Жегалкина для функции имеет вид в силу равенства . Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу

Таблица функций

Функция	Классы
	Р0	Р1	S	М	L
х | у	Нет	Нет	Нет	Нет	Нет

Теорема Поста. Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P₀, P₁, S, M, L в системе F найдется функция, не принадлежащая этому классу.

В силу теоремы Поста функция х | у образует полную систему, т. е. с помощью штриха Шеффера можно получить любую булеву функцию. В частности,

.

Система булевых функций называется базисом, если она полна, а удаление любой функции из этой системы делает ее неполной.

Теорема. Каждый базис содержит, не более четырех булевых функций.

Доказательство. Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f– функция из F, не принадлежащая классу Р₀. Тогда, с одной стороны, f (0,0,…, 0)=1, а, с другой – из

следует, что f (1,1,…, 1)=1. Это означает, что f не является самодвойственной функцией, что противоречит предположению.

Пример. Следующие системы булевых функций являются базисами:

.

Таблица 7

Обоснование	Базис
;следовательно,	{И, НЕ} – конъюнктивный базис
;следовательно,	{ИЛИ, НЕ} – дизъюнктивный базис
;	{И, , 1} – базис Жегалкина
;следовательно, ;	{|} – базис Шеффера
;следовательно, ;	{ } – базис Пирса

Пример.