Последний раз редактировалось mister123 05.11.2012, 19:35, всего редактировалось 1 раз.
Добрый вечер. Есть задача, которую не совсем понятно как делать. Вот условие:
определить количество монотонных булевых функций от 4 переменных, которые принимают значение 0 на всех наборах веса 2.
Пробовал так:
1.Выписал все наборы длины 4 в порядке возрастания
2.Расставил на всех наборах веса 2 нули
3.После выполнения пункта 2, ещё на некотором количестве наборов, в силу того, что функция должны быть монотонной, поставил нули. После чего осталось 5 "свободных" наборов, а именно наборы:
0111, 1011,1101, 1110, 1111
Вот тут стало не совсем понятно, что делать дальше ?
-- 05.11.2012, 20:35 --
Вот что, ещё я заметил, каждый из оставшихся наборов
0111 1011 1101 1110 сравним только с 1 набором 1111, а набор 1111 сравним с любым из ранее перечисленных наборов. Таким образом, если f(1111) = 1, то на остальных наборах значения функция расставляются произвольно - 16 способов. А если f(1111) = 0, то на остальных наборах, т.к. функция монотонная должны быть также нули => 1 способ.
Следовательно, всего функций 16 + 1= 17, что, кстати, совпало с ответом.
Но вот мой вопрос, другой: есть ли какой-то другой способ определить это число, не занимаясь вот таким перебором?
|
