Булевы функции и способы их задания
1.1. Найти вектор значений функции, заданной формулой над
множеством {f,g,h}, если функциональным символам f,g,h сопоставлены функции, заданные соответственно векторами (10),
(1011) и (1000):
1) g( f( h( x, f(y) ) ), y ) (показать решение)
2) f( g( x, h( g(x,y), f(y) ) ) ) (показать ответ)
1.2. Построить таблицы функций, реализуемых формулами:
1) (x→y)+((y→z)+(z→x)) (показать решение)
2) ¬x →
(¬z ~ (y+x&z) ) (показать ответ)
1.3. Эквивалентны ли формулы (см. [1], стр. 14):
1)
A=((x V y) V z) → ((x V y) (x V z)), B=x~z (показать решение)
2)
A= ¬ ((x→y) V ((x→z)&y)), B=(x & ¬y)( ¬y→(x & ¬z )) (показать ответ)
1.4. Выяснить, можно ли реализовать функцию f формулой глубины k над множеством M (см. [1], стр. 30):
1)
f=xy, k=2, M={|} (штрих
Шеффера) (показать ответ)
2)
f=x+y+z, k=2, M={→,
&} (показать ответ)
3)
f=x&y, k=999, M={→} (показать ответ)
1.5. Доказать, что если f реализуема формулой глубины k над множеством M,
то она реализуема некоторой формулой над M, глубина которой больше k.
1.6. Методом эквивалентных преобразований проверить справедливость
соотношений (см. [1],
стр. 29)
1)
x V (y~z)=(x V y) ~ (x V z) (показать решение)
2)
x→(y&z)=(x→y)&(x→z)
3)
x+(y→z)=(x+y)→(x+z)
1.7. Реализовать f
формулой над M
f=x~y, M={&,→}
1.8. С помощью эквивалентных преобразований (см. [1], стр. 29) привести к ДНФ формулу
(
x V y & ¬z ) & (x V z) (показать решение)
1.9. Построить совершенную ДНФ
(x+y)→yz
1.10. Построить полином Жегалкина методом неопределенных
коэффициентов (см. [1],
стр. 53)
f=(01101000) (показать
ответ)
1.11. Найти все существенные переменные функции
1)
f=(x V y V z¬y
V ¬x¬y¬z) w
2) f=(00110011)
1.12. Найти все коммутативные операции от двух переменных.
1.13. Указать все пары функций от двух переменных, которые
дистрибутивны.
1.14. Указать все пары дистрибутивных функций от двух переменных без
условия коммутативности.
Литература
1. Г.П. Гаврилов, А.А.
Сапоженко. Сборник задач по дискретной математике.
| 
