Спирина, М.С. Дискретная математика

не являющуюся самодвойственной; не являющуюся линейной; не являющуюся монотонной. Выбор элементарных функций для базиса можно осуществ­ лять с помощью табл. 4.37, где плюсом отмечены свойства, кото­ рыми эти функции обладают. В ней приведено распределение раз­ личных булевых функций двух переменных по пяти рассмотрен­ ным функционально замкнутым классам. О . Какое минимальное число булевых функций должен содержать б а ­ зис? Просим не путать обозначения функций в этой таблице, на­ пример с аналогичной нумерацией в подразд. 4.2. Из табл. 4.37 видно, что каждая из ф у н кц и й ^ = х х1 х 2 (стрелка Пирса) и f(, - х х | х2 (штрих Шеффера) является минимальным базисом, так как соответствует условиям теоремы Поста —Яблон­ ского. Это подтверждает и возможность выражать эти функции через отрицание, конъюнкцию и дизъюнкцию по формулам: х{ I х2 =Xi v х2 или х, I х2 - х, v х2, т.е. x i x = х; X! |х2 = Х,Х2 И Л И X! |х2 = х,х2, т. е. XIX= X. Т а б л и ц а 4.37 Критерии функциональной полноты булевых функций Функ­ ция Д* Ь*2) Значе­ ния Не сохра­ няет 0 Не сохра­ няет 1 Несамо­ двойст­ венная Нелиней­ ная Немоно­ тонная / 0 0000 + + fl X] 4 х 2 1000 + + + + + /з *1*2 0010 + + + /4 *2 1010 + + + /5 X! ®Х2 оно + + + /б х, |х 2 1110 + + + + + /7 *1*2 0001 + + к Х\ <-»JC2 1001 + + + к Х2 —> Х\ 1011 + + + /ю *1 v x 2 0111 + + /и 1 1111 + + 197