darthbarada / mou_ex Goto Github PK

Ссылочка на исочник

Замечание:
Это моя подготовка и мои рассуждения, если что-то не правильно, то напишите в комменты под README.md, или fork-ните и исправьте.
За правильность ответов я не даю гарантии.

Благодарность за помощь в уточнении вопросов:

• Тихомиров Никита
• Князев Антон

Xn={x1,x2,...xn} - множество булевых пременных
B - подмножество P2

Выражение F, составленное из переменных из Xn и из функций из B называется булевой формулой в базисе B над множеством переменных Xn , если F удовлетворяет следующему индуктивному определению:

• Переменная xi,принадлежащая Xn является формулой;
• Если f(x1,x2,...xn) принадлежит B и F1,F2...Fn формулы, то выражение так же является формулой.
• Других формул нет

Множество булевых функций M лежащих в P2 называется замкнутым множеством, если оно совпадает со своим замыканием, т.е. [M] = M

Замечание:
Рассмотрим важнейшие замкнутые множества в P2. Часто рассматриваемыениже замкнутые множества (T0,T1,S,M,L) 
называются так же основными замкнутыми классами.

Для того, чтобы система функций В была функционально полной необходимо и достаточно, чтобы она целиком не лежала ни в одном из 5 основных замкнутых классов: T0,T1,S,M,L

Система (множество) булевых функций B, лежащих в P2,называется функционально полной, если любая булева функция может быть выражена в виде формулы над B

Рассмотрим АНФ импликации и дизъюнкции: 1.АНФ(x->y)= 1 + x + xy 2.АНФ(x v y)= y + x + xy Заметим, что они нелинейные как и конъюнкция.Так что ответ да, однако для простоты доказательства мы ищем конъюнкцию.

1. Если X1X2+X3X4+...+Xn-1Xn - АНФ, то заметим, что X1X2,X3Х4 идут парами нечёт-чёт => n-чётное. Чтобы АНФ равнялась 1 нам нужно выбрать нечёт количество пар (всего пар у нас n/2), тогда вариантов, когда в АНФ встречается нечётн количество пар = n/2 C 1 + n/2 C 3 + n/2 C 5 ..., то есть 2^(n/2-1).
2. Если X1X2+X3X4+...+Xn-1Xn - функция, то ищем когда она равняется 0. Xi-1Xi равняется 0 в 3 случаях: 00,01,10 => Всего значений f у нас 2^n, значений, когда Xi-1Xi равняется 0: 3^(n/2). В итоге получим 2^n - 3^(n/2)

Моё рассуждение: если функция всегда сохраняет 0, то:
1) f принадлежит T0
2) f не принадлежит T1(так как f(1,1...1) должен быть равен 0)
3) f не принадлежит S (так как f(1,1...1)=0)
4) f принадлежит L    (она вообще не должна зависеть от xi, т.е. все xi, i=1,n,- фиктивные)
5) f принадлежит M    (так как при всех подстановках f(x1,x2,...xn)=0)

Следовательно существует только одна функция f=0.

см. лекции в тетради

Функция f*(x1,x2...xn)= ¬f(¬x1,¬x2...¬xn) называется двойственной к функции f(x1,x2...xn).

Вытекает из теоремы

Определение: Cимметричной булевой функцией называется такая булева функция, значение которой не зависит от перестановки её входных бит, а зависит только от количества единиц на входе. Обозначаются как Sim(n) Пример:

0 0| b0         0 0 0| a0
0 1| b1   или   0 0 1| a1
1 0| b1         0 1 0| a1
1 1| b2         0 1 1| a2        (1)
                1 0 0| a1
                1 0 1| a2
                1 1 0| a2
                1 1 1| a3

АНФ такой функции выглядит следующим образом: a0 + a1(x1+x2+...xn) + a2 (x1x2+...+xn-1xn)+a3...+an(x1x2x3...xn) Обычных симметрических:2^(n+1) Симметрических и монотонных:2(n+1 С 1) <- мы выбераем 1 a из всех ai, всё что до неё - 0, после 1, сама a может быть или 0, или 1, поэтому коэффициент 2. Среди них будут самодвойственные, если ai - чётное количество. Рассмотрим пример(1):

0 0 0| 0
0 0 1| 0
0 1 0| 0
0 1 1| 1
1 0 0| 0 - 100 и 011 - несравнимы, так что всё ок.
1 0 1| 1
1 1 0| 1
1 1 1| 1

Определение: Функция Шеффера ложна тогда и только тогда, когда оба значения переменных истинны. Обозначение: x|y x|y = ¬(xy)

Замечание:
Всего шефферовых функций от n переменных: 2^((2^n)-2) - 2^(2^(n-1)-1)

Пример равновесной шефферовой функции: 1|x => ¬x, а ¬x равновесный.

Это число позиций, в которых соответствующие символы двух наборов одинаковой длины различны.

Шаром радиуса R с центром a (а принадлежит Z(2,n)) называют множество наборов, удалённых от набора а на расстояние не больше R. |Vr(a)|=n C 0 + n C 1 + n C 2 +... + n C r

Сферой радиуса R с центром a (а принадлежит Z(2,n)) называют множество наборов, удалённых от набора а на одинаковое расстояние R. |Sr(a)|=n C r

Другими важными замкнутыми классами являются:

Класс конъюнкций K, являющийся замыканием множества {конъюнкция,0,1}. Он представляет собой множество функций вида с0(с1 v x1)(с2 v x2)...(сn v xn). Класс дизъюнкций D, являющийся замыканием множества {v,0,1}. Он представляет собой множество функций вида с0 v(с1x1)v(с2x2)...v(сnxn). Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений). Класс O^(m) функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах. Класс O^(infty) функций, для которых выполнено условие f(x1,x2...xn)>=xi, где xi — одна из переменных функции. Класс I^(m) функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах. Класс I^(infty) функций, для которых выполнено условие f(x1,x2...xn)<=xi, где xi — одна из переменных функции.

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

V(k) – непустое множество называется линейным векторным пространством если для n – мерных векторов множества V выполнены аксиомы ЛВП:

1. Свойство замкнутости ЛВП относительно сложения векторов и умножения вектора на число из К
2. Существование нулевого элемента
3. Существование противоположного элемента
4. Закон сложения и умножения векторов на число:

a. Коммутативности
b. Ассоциативности
c. Дистрибутивности

5. Дополнительные законы:

a. Закон дистрибутивности относительно сложения скаляров: b. Ассоциативности
c. 1*a=a

Антисамодвойственных функций от n переменных столько же, сколько и самодвойственных функций от n переменных, то есть 2^(2^(n-1)).

f(x1,x2,...xn),fi(x1,x2,...xn) принадлежат antiS, i=1,n F(x1,x2,...xn)=f(f1(x1,x2,...xn),f2(x1,x2,...xn),...fn(x1,x2,...xn)) F(¬x1,¬x2,...¬xn)=f(f1(¬x1,¬x2,...¬xn),f2(¬x1,¬x2,...¬xn),...fn(¬x1,¬x2,...¬xn))=f(¬f1(x1,x2,...xn),¬f2(x1,x2,...xn),...¬fn(x1,x2,...xn))=¬F(x1,x2,...xn) => antiS не замкнутый.

2^(2^(n-1))

Наводящий пример:
x2 - фиктивная

0  0 | a1
-----  ||
0  1 | a1
---------
1  0 | a2
-----  ||
1  1 | a2

Если вратце, то делим все наборы на 4 равные части, из которых только у 2 выбираем значения.

Переменную xi называют фиктивной переменной булевой функции f(x1, ... ,xn), если значение функции не зависит от значения этой переменной, т .е. если для любых значений переменных х1, ... , xi-1, хi+1, ... , xn выполняется условие: f(x1,...xi-1,0,xi+1,...,xn)=f(x1,...xi-1,1,xi+1,...,xn).

Определение: Булева функция y=f(x1,x2 ... xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2 ... ak-1, ak+1, ak+2 ... an, что f(a1,a2 ... ak-1, 0, ak+1, ak+2 ... an) ≠ f(a1, a2 ... ak-1, 1, ak+1, ak+2 ... an). 2^(2^(n-2))

Наводящий пример:
x1 и x2 - существенные
0   0   0  |  b1
0   0   1  |  b1
---------
0   1   0  | ¬b1
0   1   1  | ¬b1
----------------
1   0   0  | ¬b1
1   0   1  | ¬b1
---------
1   1   0  | b1
1   1   1  | b1

f(0,x2,x3) ≠ f(1,x2,x3) и f(x1,0,x3) ≠ f(x1,1,x3) 

¬x