Как можно доказать, что не существует монотонной самодвойственной булевой функции, у которой имеется ровно две нижние единицы, при этом нижней единицей для функции f называется такая вершина a, что f(a)=1, а для всех вершин b, для которых b‹a, f(b)=0?

Математика Университет Булевые функции и их свойства монотонная самодвойственная булева функция доказательство булевой функции нижние единицы булевой функции свойства булевых функций математическая логика комбинаторная математика Новый

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

1. Определение нижних единиц:

   По определению, нижняя единица для булевой функции f - это такая вершина a, что f(a) = 1, и для всех вершин b, которые меньше a (b < a), выполняется f(b) = 0. Если у функции f есть ровно две нижние единицы, обозначим их как a1 и a2.

2. Монотонность функции:

   Монотонная функция означает, что если b < c, то f(b) ≤ f(c). В нашем случае, если a1 < a2, то f(a1) = 1 и f(a2) = 1, а для всех b < a1, f(b) = 0. Это означает, что все значения функции ниже a1 равны 0.

3. Самодвойственность функции:

   Функция называется самодвойственной, если для любого набора входных значений x, f(x) = ¬f(¬x), где ¬ - операция отрицания. Это свойство требует, чтобы функция была "симметрична" относительно своих значений.

4. Анализ значений функции:

   Поскольку у нас есть две нижние единицы a1 и a2, и они обе равны 1, давайте рассмотрим их "отрицания". Для значений меньше a1, функция равна 0. Это значит, что для всех b < a1, f(b) = 0. Теперь, согласно самодвойственности, для этих же b, мы должны иметь f(¬b) = 1. Но так как ¬b будет больше a1 и a2, это противоречит монотонности, так как для значений больше a1 и a2 функция должна оставаться равной 1 или 0, но не может быть равной 1 для b < a1 и 0 для ¬b.

5. Вывод:

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