Лекции Математическая логика (стр. 4 )

Определение 4.

Рассмотрим два набора значений аргументов . Функция называется монотонной, если для любых наборов , т. е. , .

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

Определение 5.

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

Пример.

Полную систему назовём базисом. Удаление любой функции из базиса приведёт к разрушению системы.

Минимальные базисы:

1. 

2. 

3. 

4. 

Определение 6.

Множество M – замкнутый класс, если любая суперпозиция функций снова принадлежит M.

Множество линейных функций – замкнутый класс.

Теорема 1.

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

4 Пусть имеем БФ без отрицаний. Приведём её к ДНФ.

Возьмём набор аргументов .

Пусть , тогда

Теперь рассмотрим набор .

Условие монотонности выполняется.

f – монотонная БФ, отличная от 0 и 1. Она имеет ДНФ. Все содержащиеся в ДНФ конъюнкции будем называть импликантами. Пусть в этой функции существует импликант вида , где K – все остальные элементы конъюнкции. Тогда на любом наборе, в котором , .

получается из .

Таким образом, также будет импликантой.

не может быть простой импликантой, т. е. все конъюнкции без отрицания.3

Теорема 2.

Множество любых монотонных функций есть замкнутый класс.

4Следует из предыдущей теоремы, т. к. подстановка формулы без отрицаний в формулу без отрицаний даст формулу без отрицаний.3

Следствие 1.

Класс монотонных функций – замыкание системы . Любая БФ – суперпозиция .

Теоремы о полноте.

Лемма 1.

О немонотонных функциях.

Если не монотонна, то подстановкой констант можно получить отрицание. Точнее из n-1 констант.

4Пусть f не монотонна: . Если и отличаются k компонентами, то в в k стоят 0, а в в k стоят 1.

Будем заменять в 0 на 1 по одной.

Возьмём .

Пусть и отличаются в i-ой компоненте. Тогда .

Подставим в f и .

3

Лемма 2.

О нелинейных функциях.

Если БФ нелинейна, то с помощью подстановки констант и использования отрицаний можно получить и , т. е. существует представление и в виде суперпозиции констант, отрицаний и самой функции f.

4Пусть f нелинейна, тогда её полином Жегалкина содержит конъюнкцию переменных .

Пусть , а все .

Тогда, подставив константы в полином Жегалкина, останутся . Т. о. функция имеет вид , где – константы 0 или 1. Т. о. получаем таблицу:

				Вид полинома	Эквивалентная БФ	Искомая суперпозиция
	0	0	0
	0	0	1
	0	1	0
	0	1	1
	1	0	0
	1	0	1
	1	1	0
	1	1	1

В последнем столбце искомое представление в виде конъюнкции или дизъюнкции.3