Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения:
- [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, \ldots, x) = 1[/math] .
- [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math] .
- [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, \ldots, x) = 0[/math] .
- [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math] .
Таким образом, возможны четыре варианта:
- Мы получили функцию [math] \neg [/math] .
Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(\lnot x_0)[/math] . Где [math]x_0 = (x_, x_, \ldots, x_)[/math] .
Рассмотрим [math]f_s(x^>, x^>, \ldots, x^>)[/math] , где либо [math]x^> = x[/math] , при [math]x_ = 1[/math] . Либо [math]x^> = \lnot x[/math] , при [math]x_ = 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname [/math] . Таким образом мы получили одну из констант.
- Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]\lnot 0 = 1[/math] .
- Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]\lnot 1 = 0[/math] .
- Мы получили [math]1[/math] и [math]0[/math] .
Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, \ldots, x_n[/math] , что [math]f_m(x_1, x_2, \ldots, x_, 0 , x_, \ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, \ldots, x_, 1 , x_, \ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, \ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, \ldots, x_, x, x_, \ldots, x_n)= \lnot x[/math] .
В итоге имеем три функции: [math] \neg [/math] , [math]0[/math] , [math]1[/math] .
Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).
Рассмотрим несколько вариантов:
- Присутствует член [math]\oplus ~1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет.
- Присутствуют три члена, без [math]\oplus ~1[/math] : [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math] .
- Присутствуют два члена, без [math]\oplus ~1[/math] . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] . Например, если функция [math]g_l(x_1, x_2, \ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, \ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] \wedge [/math] можно выразить как [math]g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)[/math] , где [math]\lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, \ldots, i_m[/math] .
- Присутствует один член. Выразим [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] аналогично пункту 3.
В итоге получим функцию [math] \neg [/math] , а также либо функцию [math] \wedge [/math] , либо функцию [math] \vee [/math] . Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math] , а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math] , то мы получили базис [math] \wedge [/math] , [math] \vee [/math] , [math] \neg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math] .
Примеры
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.
Широко известны такие полные системы булевых функций:
- [math]\left\<\land,\lor,\neg\right\>[/math] (конъюнкция, дизъюнкция, отрицание);
- [math]\left\<\land,\oplus,1\right\>[/math] (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.
Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.
См. также
- Булевы функции
- Суперпозиции
- Полином Жегалкина
Источники информации
- Википедия — Критерий Поста
- Википедия — Замкнутые классы булевых функций
- Образовательный сайт MiniSoft
- Post’s lattice
- Лекции по дискретной математике
Булевы функции. Интересная задачка.
Пожалуйста, используйте IE6/7/8 с плагином MathPlayer, Firefox с установленными математическими шрифтами или Opera 9.5 и выше.
| Объявления |
Последний пост |
| |
Правила и принципы форума «Высшая математика» |
28.10.2009 15:17 |
| |
Книги по математике и экономике в добрые руки! |
07.10.2023 13:49 |
| |
Гранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2023/2024 |
28.11.2022 13:56 |
05.01.2005 01:37
Булевы функции. Интересная задачка.
Число всех немонотонных функций от n переменных равно числу всех антицепей на множестве булева куба размерности n. Доказать. Как? 🙂
05.01.2005 05:48
половину уже сделал
Число всех монотонных функций я получил.
Оно такое: n!*(n+2)*2^((2^n)-(n+1)). Я рассмотрел количество всех цепей и длину каждой цепи в булевом кубе и возможные комбинации образов, которые зависят от длины цепи.
Как искать количество антицепей — не дойдёт. Там понятно только одно, что количество максимальных антицепей — n (макс. антицепь — это k-слой булева куба).
05.01.2005 05:55
Дата регистрации:
19 лет назад
Пожалуйста, дайте определение антицепи.
Напомните определение «антицепи», тогда, возможно я смогу помочь.
Пока могу высказать следующие соображения, которые могут натолкнуть на верное решение(или не помогут):
1) Подсчитывать в отдельности Число всех немонотонных функций от n переменных и число всех антицепей на множестве булева куба размерности n. — путь неверный, ибо подсчет числа монотонных функций — очень неблагодарное и сложное дело.
2) Существует критерий немонотонности б.ф. на булевом кубе:
б.ф. немонотонна при движении «вверх», «вправо», «влево» от точки (0,0. 0) к (1,1. 1) найдется ребро типа (1,0).
Р.S. По виду вашей формулы не могу проследить за логикой составления, но, похоже, она не верна:
n=2.
Число всех фунций: 2^(2^2)=16;
Число монотонных функций: 2!*(2+2)*2^((2^2)-(2+1))=2*4*2^(4-3)=16. В то время как монотонных функций (n=2) равно 6.
05.01.2005 07:29
Пусть в множестве А задано отношение порядка.
Антицепь — это подмножество А, в котором все элементы попарно несравнимы.
Для n=2 подсчёт монотонных функций не верный. там 10 функций!
x1 x2 f.
0 0 0001000110
0 1 0011001101
1 0 0000111110
1 1 0111011110
05.01.2005 11:33
Я ошибся с формулировкой
Число всех монотонных булевых функций от n переменных равно числу всех антицепей на множестве булева куба размерности n.
05.01.2005 13:02
Дата регистрации:
19 лет назад
Не могу согласиться.
Пусть задано множество E=<0,1>.
E^n — множество векторов длины n, состоящее из нулей и единиц.
An принадлежит E^n => An=(a_1,a_2. a_n);
Bn принадлежит E^n => Bn=(b_1,b_2. b_n);
Введем бинарное отношение порядка An a_iОпределение: Функция f(x_1,x_2. x_n) называется монотонной, если для любого набора An и Bn из An
Таких функций для n=2 все же 6:
0000,1000,1100,1010,1110,1111.
Например ваша функция(N4) не обладает таким свойством: f(x_1,x_2)=1011.
(00) f(10)=0.
Что касается антицепей, я так не совсем понял, как их применить относительно булева куба. Опишите для наглядности все антицепи булева куба размерности n=2, а дальше посмотрим.
05.01.2005 18:11
Дата регистрации:
21 год назад
Число монотонных функций (вопрос).
Уважаемый Trotil! А известно ли Вам что-нибудь о формуле для числа монотонных булевых функций от n переменных?
Вообще есть ли какой-нибудь ответ на данный день?
05.01.2005 20:34
вот блин я дурак. 🙂 Да, при n=2 там 6 монотонных функций.
У меня правильно только то, что число возможных цепей в булевом кубе n!. Длина какждой цепи n+1.
Для последовательности элементов каждой цепи имеем варианты значений функций 000. 0, 000. 1, . 011. 1, 111. 1.
Но ведь для каждой функции нужно учитывать и то, что элементам, не входящим в цепь могут соответствовать 0 или 1.
Но вот например, для цепи 000-001-011-111 не нужно учитывать возможные варианты возможных функций для 000 и 111, чтобы не повторяться.
05.01.2005 22:38
Каждой монотонной булевой функции f поставим в соответствие множество M — максимальных элементов множества нулей f. Очевидно, M образует антицепь, причем эта антицепь максимальна во множестве нулей f.
Наоборот, по данной антицепи M определим функцию f следующим образом. Если n-мерный булевый вектор v сравним с каким-то элементом M и не больше его, то положим f(v)=0; если же v не сравним ни с одним из элементов M или сравним и больше какого-то элемента, то положим f(v)=1.
Нетрудно проверить, что определенное соответствие f M взаимно-однозначно.
06.01.2005 01:56
Да, конечно 🙂 Трудности остались (экзамен).
Что такое множество нулей f? Это те наборы, при которых f = 0? А! Понял.
Я считаю, что лучше не использовать понятия «Очевидно» и «Нетрудно». Т.к. очевидно — это когда очами видно :)) Ну да ладно, разберусь.
В булевом кубе размерности n=2 я насчитал только 5 антицепей почему-то: , , , , . А монотонных функций там 6:
x1 x2 f
0 0 0 0 0 0 0 1
0 1 0 0 1 0 1 1
1 0 0 0 0 1 1 1
1 1 0 1 1 1 1 1
Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).
Вот я копал в сторону численного решения: найти число этих функций и антицепей. Что-то там было много запутано и пока нормально не додумался.
Построение у вас верное, насколько до меня дошло 🙂
Меня интересуют методы догадки до таких построений. Очень интересно.
06.01.2005 02:07
Дата регистрации:
19 лет назад
Нет, мне ничего неизвестно об этой формуле(но это не значит, что ее нет). Вопрос очень интересный, но просто подсчитывать комбинаторно это число — это достаточно кропотливая работа. Смотрите сами:
F_i — число монотонных функций, для которой не существует набора A веса (n-i-1), при котором f(A)=1 (и существует такой набор веса (n-i)).
Для примера: F_1 — не существует набора А веса (n-1), в котором f(А)=1. С терминологией разобрались.
F_1: Такая функция всего одна: f(11. 1)=1, f(все остальные)=0, F_1=1;
F_2: C(n,1)+C(n,2)+. +C(n,n)=2^n-1. (таких наборов может быть 1, 2, . n).
F_3: Здесь по порядку:
C(n,2) * ( C(n-2,0)+C(n-2,1)+C(n-2,2)+. C(n-2,n-2)) + (выбрали 1 один набор на уровне F_3, так как ф-ция монотонна, на уровне F_2 обязательно существуют два набора А1 и А2 таких что f(A1)=f(A2)=1. Кроме них могут быть 0, 1, 2, (n-2) дополнительных набора, значение функции в которых будет равны 1) +
С(n,2)*C(n-2,2)*(C(n-4,0)+C(n-4,1)+C(n-4,2)+. C(n-4,n-4))/2! +
C(n,2)*(2*C(n-2,1))*(C(n-3,0)+C(n-3,1)+C(n-3,2)+. C(n-3,n-4))/2!+ (здесь мы выбирали два набора) +
С(n,2)*C(n-2,2)*С(n-4,2)*(C(n-6,0)+C(n-6,1)+C(n-6,2)+. C(n-6,n-6))/3!+С(n,2)*C(n-2,2)*С(n-4,1)*(C(n-5,0)+C(n-5,1)+C(n-5,2)+. C(n-5,n-5))/3!+С(n,2)*C(n-2,1)*С(n-3,1)*(C(n-4,0)+C(n-4,1)+C(n-4,2)+. C(n-4,n-4))/3!(здесь мы вибирали три набора) + .
Дальше продолжать как-то неохота, но уже видно, какое громадное выражение тут получается. И это только начало. Конечно, суммы эти можно будет потом свернуть, но времени все это просчитать у меня просто нету. Возможно существует такое взаимнооднозначное отображение, при котором число таких функций будет просто подсчитать, не знаю.
06.01.2005 03:52
> Я считаю, что лучше не использовать понятия «Очевидно» и «Нетрудно».
Расписывать в деталях каждый шаг у меня нет ни времени, ни желания. Раз разобрались — значит, все действительно было «очевидно» и «нетрудно».
> Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).
Правильно. Пустая антицепь соответствует тождественной 1 в моем построении.
> Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).
Ничего сложного нет. Надо просто хорошо понимать, что стоит за словами «монотонная функция» и «антицепь» и искать связь между ними. Кроме того, редко когда доказательство равенства количест тех или иных объектов требует прямого подсчета этих количества. Чаще гораздо проще найти взаимно-однозначное соответствие между объектами.
06.01.2005 14:44
Дата регистрации:
19 лет назад
Нашел ссылочку: http://www.allmath.ru/highermath/algebra/algebra7/algebra.htm
В частности там есть статья: «А. Д. Коршунов. О числе и строении монотонных булевых функций»
Формула там есть, но она по сути — запись алгоритма перебора по всем булевым функциям. ЖУТЬ! 🙂
Определение булевой функции
Элементы булева множества [math]1[/math] и [math]0[/math] обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения [math]B^n[/math] называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается [math]P_2[/math] , а от n переменных — [math]P_2(n)[/math] . Булевы функции названы так по фамилии математика Джорджа Буля.
Основные сведения
| Определение: |
| А́рность (англ. arity) функции — количество ее аргументов. |
Каждая булева функция арности [math]n[/math] полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины [math]n[/math] . Число таких векторов равно [math]2^n[/math] . Поскольку на каждом векторе булева функция может принимать значение либо [math]0[/math] , либо [math]1[/math] , то количество всех n-арных булевых функций равно [math]^n[/math] . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
| Таблица истинности |
| [math]x_1[/math] |
[math]x_2[/math] |
[math]\ldots[/math] |
[math]x_n[/math] |
[math]f(x_1,x_2,\ldots,x_n)[/math] |
| [math]0[/math] |
[math]0[/math] |
[math]\ldots[/math] |
[math]0[/math] |
[math]f(0,0,\ldots,0)[/math] |
| [math]1[/math] |
[math]0[/math] |
[math]\ldots[/math] |
[math]0[/math] |
[math]f(1,0,\ldots,0)[/math] |
| [math]0[/math] |
[math]1[/math] |
[math]\ldots[/math] |
[math]0[/math] |
[math]f(0,1,\ldots,0)[/math] |
| [math]1[/math] |
[math]1[/math] |
[math]\ldots[/math] |
[math]0[/math] |
[math]f(1,1,\ldots,0)[/math] |
| [math]\vdots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math] |
| [math]0[/math] |
[math]1[/math] |
[math]\ldots[/math] |
[math]1[/math] |
[math]f(0,1,\ldots,1)[/math] |
| [math]1[/math] |
[math]1[/math] |
[math]\ldots[/math] |
[math]1[/math] |
[math]f(1,1,\ldots,1)[/math] |
Практически все булевы функции малых арностей ( [math]0, 1, 2[/math] и [math]3[/math] ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).
Нульарные функции
При [math]n = 0[/math] количество булевых функций равно [math]^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.
Унарные функции
При [math]n = 1[/math] число булевых функций равно [math]^1 = 2^2 = 4[/math] .
Таблица значений булевых функций от одной переменной:
| Функции от одной переменной |
| [math]0[/math] |
[math]x[/math] |
[math]\neg x[/math] |
[math]1[/math] |
| 0 |
[math]0[/math] |
[math]0[/math] |
[math]1[/math] |
[math]1[/math] |
| 1 |
[math]0[/math] |
[math]1[/math] |
[math]0[/math] |
[math]1[/math] |
| Сохраняет 0 |
✓ |
✓ |
| Сохраняет 1 |
✓ |
✓ |
| Самодвойственная |
✓ |
✓ |
| Монотонная |
✓ |
✓ |
✓ |
| Линейная |
✓ |
✓ |
✓ |
✓ |
Названия булевых функций от одной переменной:
| Обозначение |
Название |
| [math]0[/math] |
тождественный ноль, тождественная ложь, тождественное «НЕТ» |
| [math]x[/math] |
тождественная функция, логическое «ДА», «YES»(англ.) |
| [math]\bar x,\ \neg x,\ x'[/math] |
отрицание, логическое «НЕТ», «НЕ», «НИ», «NOT»(англ.), «NO»(англ.) |
| [math]1[/math] |
тождественная единица, тождественная истина, тождественное «ДА», тавтология |
Бинарные функции
При [math]n = 2[/math] число булевых функций равно [math]^2 = 2^4 = 16[/math] .
Таблица значений булевых функций от двух переменных:
| Функции от двух переменных: |
| x |
y |
[math]0[/math] |
[math]x \land y[/math] |
[math]x \nrightarrow y[/math] |
[math]x[/math] |
[math]x \nleftarrow y[/math] |
[math]y[/math] |
[math]x \oplus y[/math] |
[math]x \lor y[/math] |
[math]x \downarrow y[/math] |
[math]x = y[/math] |
[math]\neg y[/math] |
[math]x \leftarrow y[/math] |
[math]\neg x[/math] |
[math]x \rightarrow y[/math] |
[math]x \triangledown y[/math] |
[math]1[/math] |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
| 1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
| Сохраняет 0 |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
| Сохраняет 1 |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
| Самодвойственная |
✓ |
✓ |
✓ |
✓ |
| Монотонная |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
| Линейная |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
✓ |
Названия булевых функций от двух переменных:
| Обозначение |
Другие обозначения |
Название |
| [math]0[/math] |
тождественный ноль, тождественная ложь, тождественное «НЕТ» |
| [math]x \land y[/math] |
[math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x [/math] И [math]y,[/math] И [math](x, y)[/math] |
2И, конъюнкция |
| [math]x \nrightarrow y[/math] |
[math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math] |
больше, инверсия прямой импликации |
| [math]x[/math] |
[math]YES1(x,y),[/math] ДА1 [math](x, y)[/math] |
первый операнд |
| [math]x \nleftarrow y[/math] |
[math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math] |
меньше, инверсия обратной импликации |
| [math]y[/math] |
[math]YES2(x, y),[/math] ДА2 [math](x, y)[/math] |
второй операнд |
| [math]x \oplus y[/math] |
[math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math] |
сложение по модулю 2, не равно, ксор, исключающее «или» |
| [math]x \lor y[/math] |
[math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] [math]x [/math] ИЛИ [math]y,[/math] ИЛИ [math](x, y)[/math] |
2ИЛИ, дизъюнкция |
| [math]x \downarrow y[/math] |
[math]x\ NOR\ y,\ NOR(x,y)[/math] [math]x [/math] ИЛИ-НЕ [math]y,[/math] ИЛИ-НЕ [math](x, y)[/math] |
НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса |
| [math]x = y[/math] |
[math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math] |
равенство, эквивалентность |
| [math]\neg y[/math] |
[math]NOT2(x, y),\ y’,\ \bar,[/math] НЕ2 [math](x, y)[/math] |
отрицание (негация, инверсия) второго операнда |
| [math]x \leftarrow y[/math] |
[math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math] |
больше или равно, обратная импликация (от второго аргумента к первому) |
| [math]\neg x[/math] |
[math]NOT1(x,y),\ x’,\ \bar,[/math] НЕ1 [math](x, y)[/math] |
отрицание (негация, инверсия) первого операнда |
| [math]x \rightarrow y[/math] |
[math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math] |
меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) |
| [math]x \triangledown y[/math] |
[math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] [math]x [/math] И-НЕ [math]y,[/math] И-НЕ [math](x, y)[/math] |
НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера |
| [math]1[/math] |
тождественная единица, тождественная истина, тождественное «ДА», тавтология |
Тернарные функции
При [math]n = 3[/math] число булевых функций равно [math]^3 = 2^8 = 256[/math] . Некоторые из них определены в следующей таблице:
| Таблица истинности некоторых тернарных функций |
| [math]x[/math] |
[math]y[/math] |
[math]z[/math] |
[math]x \downarrow y \downarrow z[/math] |
[math]\neg (\geq 2(x,y,z))[/math] |
[math]x \not = y \not = z[/math] |
[math]x \mid y \mid z[/math] |
[math]min(x,y,z)[/math] |
[math]x=y=z[/math] |
[math]x \oplus y \oplus z[/math] |
[math]\geq 2(x,y,z)[/math] |
[math]f_1[/math] |
[math]f_2[/math] |
[math]max(x,y,z)[/math] |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
| 0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
| 1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
| 1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Названия булевых функций трех переменных:
| Обозначения |
Другие обозначения |
Названия |
| [math]x \downarrow y \downarrow z[/math] |
[math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math] |
3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса |
| [math]\neg (\geq 2(x,y,z))[/math] |
Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией |
| [math]x \not = y \not = z[/math] |
[math][\not =(x,y,z)] = NE(x,y,z)[/math] |
Неравенство |
| [math]x \mid y \mid z[/math] |
[math]\mid(x,y,z)[/math] |
3-И-НЕ, штрих Шеффера |
| [math]x \land y \land z[/math] |
[math]\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z) = \lt br/\gt (x[/math] И [math] y[/math] И [math] z) = [/math] И [math](x,y,z)[/math] |
3-И, минимум |
| [math]x=y=z[/math] |
[math][=(x,y,z)] = EQV(x,y,z)[/math] |
Равенство |
| [math]x \oplus y \oplus z[/math] |
[math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math] |
Тернарное сложение по модулю 2 |
| [math]\geq 2(x,y,z)[/math] |
[math](x [/math] И [math]y) [/math] ИЛИ [math](y[/math] И [math] z)[/math] ИЛИ [math](z [/math] И [math] x)[/math] |
переключатель по большинству, 3-ППБ, мажоритарный клапан |
| [math]f_1[/math] |
Разряд займа при тернарном вычитании |
| [math]f_2[/math] |
Разряд переноса при тернарном сложении |
| [math]x+y+z[/math] |
[math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) = (x [/math] ИЛИ [math] y [/math] ИЛИ [math] z) = [/math] ИЛИ [math](x,y,z)[/math] |
3-ИЛИ, максимум |
Представление функции формулой
| Определение: |
| Если выбрать некоторый набор булевых функций [math]A[/math] , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula). |
Например, если [math]A = \left\<\land,\neg\right\>[/math] , то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]
Тождественность и двойственность
| Определение: |
| Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. |
Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
| [math]\overline=1[/math] |
[math]\overline=0[/math] |
[math]\overline<\overline>=x[/math] |
[math]x \land y=y \land x\![/math] |
[math]x\lor y=y \lor x[/math] |
| [math]0 \land x=0\![/math] |
[math]1 \land x=x\![/math] |
[math]0 \lor x=x[/math] |
[math]1\lor x=1[/math] |
[math]x \land x=x \lor x=x[/math] |
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
| [math]x \land \overline=0[/math] |
[math]x \lor \overline=1[/math] |
| [math]\overline=\overline\lor\overline[/math] |
[math]\overline\land\overline=\overline[/math] |
(законы де Моргана) |
[math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)
| Определение: |
| Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной (англ. duality) функции [math]f(x_1,x_2,\dots,x_n)[/math] , если [math]f(\overline,\overline,\dots,\overline)=\overline[/math] . |
Легко показать, что в этом равенстве [math]f[/math] и [math]g[/math] можно поменять местами, то есть функции [math]f[/math] и [math]g[/math] двойственны друг другу. Из простейших функций двойственны друг другу константы [math]0[/math] и [math]1[/math] , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Суперпозиции
Основная статья: Суперпозиции
| Определение: |
| Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. |
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций [math]K[/math] . Получить новую функцию, являющеюся композицией функций из [math]K[/math] , мы можем следующими способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Полнота системы, критерий Поста
Основная статья: Теорема Поста о полной системе функций
| Определение: |
| Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества. |
| Определение: |
| Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций. |
Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
- самодвойственныые функции [math]S[/math] ,
- монотонные функции [math]M[/math] ,
- линейные функции [math]L[/math] .
Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \[/math] . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math] , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Основная статья: ДНФ
| Определение: |
| Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов. |
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
Примеры ДНФ:
[math]f(x,y,z) = (x \land y) \lor (y \land \neg )[/math] .
[math]f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg) \lor (x \land \neg ) [/math] .
Конъюнктивная нормальная форма (КНФ)
Основная статья: КНФ
| Определение: |
| Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. |
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.
[math]f(x,y,z) = (x \lor y) \land (y \lor \neg)[/math]
[math]f(x,y,z,t) = (x \lor t) \land (y \lor \neg) \land (\neg \lor \neg) \land (\neg \lor \neg \lor z)[/math]
[math]f(x,y,z,t,m) = (x \lor m \lor \neg) \land (y \lor \neg) \land (y \lor t \lor \neg)[/math]
Полином Жегалкина
Основная статья: Полином Жегалкина
| Определение: |
| Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math] , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. |
Полином Жегалкина имеет следующий вид:
[math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_ x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math]
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] , который, в свою очередь, по теореме Поста является полным.
[math]f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 [/math]
[math]f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 [/math]
[math]f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 [/math]
Тождественные функции. Выражение функций друг через друга
| Определение: |
| Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения. |
Приведение тождественной функции есть выражение булевой функции через другие.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
| Пример: |
| Выразим следующие функции через систему функций [math]\ <\land, \lor, \lnot \>[/math] . |
[math] x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]
Подстановка одной функции в другую
| Определение: |
| Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math] |
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:
| 1. [math] x_, \ldots, x_[/math] |
— аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math] |
| 2. [math] x_, \ldots, x_ [/math] |
— используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math] |
| 3. [math] x_, \ldots, x_ [/math] |
— аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math] |
- [math] f(a,b) = a \vee b [/math]
- [math] g(a) = \neg a [/math]
Отождествление переменных
| Определение: |
| Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_, \ldots, x_, x_, \ldots, x_) = f(x_, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math] |
Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .
| Пример: |
| [math] f(a,b) = a \vee b [/math] — исходная функция |
[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами
Схемы из функциональных элементов
Основная статья: Реализация булевой функции схемой из функциональных элементов
| Определение: |
| Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе [math]B[/math] , в котором: |
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Некоторые логические элементы:
| И |
ИЛИ |
НЕ |
Штрих Шеффера |
Стрелка Пирса |
| |
|
|
|
|
Стандартный базис
| Определение: |
| Стандартный базис — система булевых функций: [math]\ <\land, \lor, \lnot \>[/math] |
Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math] , то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
[math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]
[math] x \rightarrow y = \lnot x \lor y [/math]
[math] 0 = x \land \lnot x [/math]
Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.
[math] x \mid y = \lnot \left ( x \land y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]
Тождественность функций можно доказать с помощью таблицы истинности.
Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math] .
[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]
Полнота стандартного базиса
Стандартный базис является полной системой булевых функций
[math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]
[math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
[math] \ < \land , \lnot \>[/math] (конъюнктивный базис Буля)
[math] \ < \lor , \lnot \>[/math] (дизъюнктивный базис Буля)
Теоремы о числе функций в базисе
Максимально возможное число булевых функций в безызбыточном базисе — четыре.
Рассмотрим произвольный безызбыточный базис [math] X[/math] . Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):
[math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math] , где [math] T_0, T_1, S, M, L[/math] — классы Поста.
Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\[/math] — полная, то [math]\left | X \right | \le 5[/math]
Рассмотрим [math]f_0[/math] . Возможны два случая:
1. [math] f_0(1, 1, \ldots, 1) = 0 [/math] , тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.
[math] f_0 = f_1 = f_m [/math] . Значит, [math]\left | X \right | \le 3[/math] .
2. [math] f_0(1, 1, \ldots, 1) = 1 [/math] , тогда [math]f_0[/math] несамодвойственная, т.е.
Для любого числа [math]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math] , что [math]\left | X \right | = k[/math] .
Приведём примеры базисов для каждого [math]k[/math] :
[math]k = 1 \Rightarrow X = \< \downarrow \>[/math] ;
[math]k = 2 \Rightarrow X = \< \lnot, \land \>[/math] ;
Докажем, что последняя система является базисом:
[math] 0 \notin T_1[/math] ;
[math] 1 \notin T_0[/math] ;
[math] x\land y \notin L\ и\ S[/math] ;
[math] x\oplus y\oplus z \notin M[/math]
См. также
- Специальные формы КНФ
- Сокращенная и минимальная ДНФ
- Пороговая функция
- Cумматор
- Полные системы функций. Теорема Поста о полной системе функций
Примечания
Источники информации
- Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
- Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
- Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
- Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
- Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
- Учебные пособия кафедры математической кибернетики ВМиК МГУ
- Булева функция — Википедия
- http://psi-logic.narod.ru/bool/bool.htm
- Дискретная математика и алгоритмы
- Булевы функции
