2020-07-12
121
1. Выбрать в таблице задания функции все наборы аргументов (
), на которых 
.
2. Выписать конституенты нуля 
, соответствующие этим наборам. При этом, если аргумент 
входит в данный набор как 0, то он вписывается без изменений в дизъюнкт, соответствующий данному набору. Если входит в данный набор как 1, то в соответствующий дизъюнкт вписывается его отрицание (
).
|
28. Доказать теорему: при суперпозиции монотонных функций вновь получаются монотонные функции.
29. Функция называется сохраняющей константу 
, если на наборе аргументов вида 
она принимает значение 
. Доказать, что суперпозиция функций, сохраняющей константу , вновь является функцией, сохраняющей эту константу.
30. Если функции 
и 
самодвойственны, то самодвойственны ли функции 
и 
?
31. Если функции и линейны, то линейны ли функции 
?
32. Булева функция называется симметричной, если она не изменяется при любом переименовании аргументов.
|
|
|
Фундаментальной симметричной булевой функцией индекса 
называется такая симметричная булева функция, у которой все конъюнкции, входящие в совершенную ДНФ этой функции, имеют ровно букв без отрицания.
Доказать следующую теорему: любая симметричная булева функция есть дизъюнкция фундаментальных булевых функций, индексы которых однозначно определяются представляемой симметричной функцией.
33. Определить число самодвойственных функций, зависящих от 
аргументов.
34. Доказать полноту системы булевой функции, состоящей из дизъюнкции, константы 0 и эквивалентности. Образует ли эта система базис?
35. Образует ли базис система булевых функций, состоящая из импликации и константы 0?
.36. Установить, является ли полной система, состоящая из дизъюнкции, импликации и конъюнкции.
37. Образуют ли полную систему функция 
и отрицание?
38. Доказать, что если некоторая булева функция не сохраняет константы и несамодвойственна, то она немотонна и нелинейна.
39. Записать основные законы алгебры Буля при арифметической интерпретации следующих логических операций:
где “·”, ”+”, “-“ – арифметические операции умножения, сложения и вычитания соответственно.
|
