alekseev дискретная математика 2012

5.6. Найти число всех функций от n переменных, которые на противоположных наборах принимают одинаковые значения. При n = 2, 3 найти все такие функции, существенно зависящие от всех переменных.

5.7. Найти число всех функций от n переменных, которые на противоположных наборах принимают противоположные значения. При n = 2, 3 найти все такие функции, существенно зависящие от всех переменных.

5.8. Найти число всех функций от n переменных, которые на любой паре соседних наборов принимают противоположные значения. Найти вид этих функций.

5.9. Доказать, что если у функции n 1 имеются фиктивные переменные, то она принимает значение 1 на чѐтном числе наборов. Верно ли обратное утверждение?

5.12. Используя принцип двойственности, построить и упростить формулу, реализующую функцию, двойственную к функции f.

1)f x y z y z x y z ;

4)f x y y z 1 z ;

5)f x y z 0 z 1 x y y z ;

6)f x z x y x y z .

5.13.Представить в совершенной д.н.ф. и совершенной к.н.ф. функции:

5.14. Построить из заданной д.н.ф. функции ее совершенную д.н.ф.:

5.15. Построить из заданной к.н.ф. функции ее совершенную к.н.ф.:

42

1)каждая элементарная конъюнкция содержит хотя бы две буквы с отрицаниями;

2)отсутствуют элементарные конъюнкции, содержащие нечетное число букв с отрицаниями;

3)в каждой элементарной конъюнкции число букв с отрицаниями не больше числа букв без отрицаний.

5.17.Выразить через полином Жегалкина все элементарные функции алгебры логики от двух переменных.

5.18.Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

6)f 1 x2 x3 x1 x2 x3 ;

7)f (x, y, z) x y x y z y z ;

8)f (x, y, z) x y z y z x y z ;

9)f (x, y, z) x y z x y x y z

10)f (x, y, z) x y z x y x y z .~3x = x

43

превосходит длину ее совершенной д.н.ф. n 1 .

5.21. Пользуясь свойством единственности совершенных форм и полинома Жегалкина, выяснить, равносильны ли выражения A и B , представив их в совершенной д.н.ф. или к.н.ф., либо построив для них полиномы Жегалкина:

1)A x1 x2 x3 , B x1 x2 x1 x3 ;

2)A x1 x2 x3 x1 x3 , B x1 x2 x3 ;

3)A x1 x2 x3 , B x1 x3 x2 x3 ;

4)A x1 x2 x3 x1 , B x1 x3 ;

5)A x1 x3 x2 x3 , B x1 x2 x3 ;

6)A x1 x2 , B x1x3 x2 x3 x1 x3 x2 x3 .

44

6. Замкнутые классы и полнота систем функций алгебры логики

Терминология и обозначения

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

Замыканием множества F называется множество всех функций из P2 , являющихся суперпозициями функций из F . Замыкание множества F обозначается через F .

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

Функция алгебры логики f (x1, x2, , xn ) сохраняет константу 0, если f 0,0,...,0 0 . Множество всех булевых функций, сохраняющих константу 0, обозначается через T0 .

Функция алгебры логики f (x1, x2, , xn ) сохраняет константу 1, если f 1,1,...,1 1. Множество всех булевых функций, сохраняющих константу 1, обозначается через T1.

Функция f ( x1,...,xn ) называется самодвойственной, если она совпадает со своей двойственной, т.е. f ( x1,...,xn ) f ( x1,...,xn ) . Функция является самодвойственной тогда и только тогда, когда на любой паре противоположных наборов она принимает противоположные значения. Множество всех самодвойственных функций обозначается через S .

Лемма о несамодвойственной функции. Из всякой несамодвойственной функции f ( x1,...,xn ) с помощью подстановки вместо ее переменных функций

f ( x1,..., xn ) с помощью подстановки вместо ее переменных функций 0, 1 и x

можно получить x .

Функция f (x1, x2 , , xn ) называется линейной, если она представима полиномом Жегалкина не выше первой степени, т. е. если существуют такие константы i 0, 1 (i 0,1, , n) , что

f (x1, x2 , , xn ) = 0 1x1 2x2 nxn .

Множество всех линейных функций обозначается через L .

Лемма о нелинейной функции. Из всякой нелинейной функции ~n с f (x )

помощью подстановки вместо ее переменных констант 0, 1 и функций x1, x1, x2 , x2 и, быть может, путѐм навешивания отрицания над всей функцией, можно получить конъюнкцию x1x2 .

Критерий Поста о полноте. Система функций F полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов:

T0 , T1, S, M , L .

Полная система F называется базисом в P2 , если никакая ее подсистема не

переменных), если она полна, т. е. образует базис в P2 .

6.1. Построить множество всех функций, зависящих от переменных x1, x2 и принадлежащих замыканию множества F :

6.2. Показать, что f F , выразив f формулой над множеством F :

1)f x, F 0, x y ;

3)f x, F x y ;

5)f 0, F xy z ;

6)f x, F x y ;

7)f x y, F x y .

6.3.Воспользовавшись теоремой сведения, доказать полноту системы F :

6.4.Перечислить все булевы функции от одной переменной, которые:

6.5.Перечислить все булевы функции от двух переменных, которые:

1) сохраняют 0; 2) сохраняют 1; 3) сохраняют обе константы.

6.6. Выяснить, при каких n функция ~n сохраняет константы: f (x )

i 1

47

i1

6.7.Доказать, что если булева функция сохраняет 0, то двойственная для нее функция сохраняет 1.

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

переменной, также не сохраняющую 0, т. е. функцию x или константу 1.

6.9. Доказать, что из всякой булевой функции, не сохраняющей 1, отождествлением всех ее переменных, можно получить функцию от одной переменной, также не сохраняющую 1, т. е. функцию x или константу 0.

6.10. Найти все самодвойственные функции, существенно зависящие от двух переменных.

3)f 11 00 01 10 .

6.12.Выяснить, является ли самодвойственной функция f, заданная векторно. Для несамодвойственной функции определить, какие переменные следует

заменить на x , а какие на x , чтобы получить константу:

несамодвойственной функции определить, какие переменные следует заменить на x , а какие на x , чтобы получить константу.

6.14.Какие из элементарных функций алгебры логики являются монотонными?

6.15.Выяснить, является ли монотонной функция f , заданная векторно. Для немонотонной функции подобрать соответствующую замену переменных,

чтобы получить x .

7)f x z y z .

6.17.Доказать, что функция f является монотонной:

1)f x y x y ;

2)f x y x ;

3) f x y z x y z x y z x y z x y z ;

4)f x y x y ;

5)f x y y z z x .

6.21.Доказать, что функция, двойственная монотонной функции, монотонна.

6.22.Доказать, что монотонная функция, не сохраняющая нуль (единицу), равна тождественно единице (нулю).

6.23. Доказать, что если f тождественно не равна константе, а ( f f ) – константа, то f M S .

~n

6.24.Найти все самодвойственные монотонные функции f (x ) , существенно зависящие от всех переменных (n = 1, 2, 3, 4).

6.25.Какие из элементарных булевых функций являются линейными?

6.26.Выяснить, является ли линейной функция f, заданная векторно:

6.27. Выяснить, можно ли путем соответствующей замены переменных получить из функции f конъюнкцию x y :

50