Булевы функции. Булевы функции
 Скачать 54.01 Kb.
|
|
| x1 | x2 | … | xn-1 | xn | f(x1,x2,…,xn) |
| 0 | 0 | … | 0 | 0 | 0 |
| 0 | 0 | … | 0 | 1 | 0 |
| 0 | 0 | … | 1 | 0 | 1 |
| 0 | 0 | … | 1 | 1 | 0 |
| {\displaystyle \vdots }  | {\displaystyle \vdots } | {\displaystyle \vdots } | {\displaystyle \vdots } | {\displaystyle \vdots } | {\displaystyle \vdots } |
| 1 | 1 | … | 0 | 0 | 1 |
| 1 | 1 | … | 0 | 1 | 0 |
| 1 | 1 | … | 1 | 0 | 0 |
| 1 | 1 | … | 1 | 1 | 0 |
| | Значение | Обозначение | Название |
| | 0 | F0,0 = 0 | тождественный ноль |
| | 1 | F0,1 = 1 | тождественная единица, тавтология |
Унарные функции
При n = 1 число булевых функций равно 221 = 22 = 4. Определение этих функций содержится в следующей таблице.
Таблица значений и названий булевых функций от одной переменной:
| x0=x | 1 | 0 | Обозначение | Название |
| 0 | 0 | 0 | F1,0 = 0 | тождественный ноль |
| 1 | 0 | 1 | F1,1 = x = ¬x = x' = NOT(x) | отрицание, логическое «НЕТ», «НЕ», «НИ», инвертор, SWAP (обмен) |
| 2 | 1 | 0 | F1,2 = x | тождественная функция, логическое "ДА", повторитель |
| 3 | 1 | 1 | F1,3 = 1 | тождественная единица, тавтология |
Бинарные функции
При n = 2 число булевых функций равно 222 = 24 = 16.
Таблица значений и названий булевых функций от двух переменных:
| x0=x | 1 | 0 | 1 | 0 | | |
| x1=y | 1 | 1 | 0 | 0 | Обозначение функции | Название функции |
| 0 | 0 | 0 | 0 | 0 | F2,0 = 0 | тождественный ноль |
| 1 | 0 | 0 | 0 | 1 | F2,1 = x ↓ y = x NOR y = NOR(x,y) = x НЕ-ИЛИ y = НЕ-ИЛИ(x,y) = NOT(MAX(X,Y)) | стрелка Пи́рса - "↓" (кинжал Куайна - "†"), функция Ве́бба - "°"[5], НЕ-ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, инверсия максимума |
| 2 | 0 | 0 | 1 | 0 | F2,2 = x > y = x GT y = GT(x,y) = x → y = x ↛ y | функция сравнения "первый операнд больше второго операнда", инверсия прямой импликации |
| 3 | 0 | 0 | 1 | 1 | F2,3 = y = y' = ¬y = NOT2(x,y) = НЕ2(x,y) | отрицание (негация, инверсия) второго операнда |
| 4 | 0 | 1 | 0 | 0 | F2,4 = x < y = x LT y = LT(x,y) = x ← y = x ↚ y | функция сравнения "первый операнд меньше второго операнда", инверсия обратной импликации |
| 5 | 0 | 1 | 0 | 1 | F2,5 = x = x' = ¬x = NOT1(x,y) = НЕ1(x,y) | отрицание (негация, инверсия) первого операнда |
| 6 | 0 | 1 | 1 | 0 | F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR(x,y) | функция сравнения "операнды не равны", сложение по модулю 2, исключающее «или», сумма Жегалкина[6] |
| 7 | 0 | 1 | 1 | 1 | F2,7 = x | y = x NAND y = NAND(x,y) = x НЕ-И y = НЕ-И(x,y) = NOT(MIN(X,Y)) | штрих Ше́ффера, НЕ-И, 2И-НЕ, антиконъюнкция, инверсия минимума |
| 8 | 1 | 0 | 0 | 0 | F2,8 = x ∧ y = x · y = xy = x & y = x AND y = AND(x,y) = x И y = И(x,y) = min(x,y) | конъюнкция, 2И, минимум |
| 9 | 1 | 0 | 0 | 1 | F2,9 = (x ≡ y) = x y = x ↔ y = x EQV y = EQV(x,y) | функция сравнения "операнды равны", эквивалентность |
| 10 | 1 | 0 | 1 | 0 | F2,10 = YES1(x,y) = ДА1(x,y) = x | первый операнд |
| 11 | 1 | 0 | 1 | 1 | F2,11 = x ≥ y = x >= y = x GE y = GE(x,y) = x ← y = x ⊂ y | функция сравнения "первый операнд не меньше второго операнда", обратная импликация (от второго аргумента к первому) |
| 12 | 1 | 1 | 0 | 0 | F2,12 = YES2(x,y) = ДА2(x,y) = y | второй операнд |
| 13 | 1 | 1 | 0 | 1 | F2,13 = x ≤ y = x <= y = x LE y = LE(x,y) = x → y = x ⊃ y | функция сравнения "первый операнд не больше второго операнда", прямая (материальная) импликация (от первого аргумента ко второму) |
| 14 | 1 | 1 | 1 | 0 | F2,14 = x ∨ y = x + y = x OR y = OR(x,y) = x ИЛИ y = ИЛИ(x,y) = max(x,y) | дизъюнкция, 2ИЛИ, максимум |
| 15 | 1 | 1 | 1 | 1 | F2,15 = 1 | тождественная единица, тавтология |
При двух аргументах префиксная, инфиксная и постфиксная записи, по экономичности, почти одинаковы.
Некоторые функции, имеющие смысл в цифровой технике, например функции сравнения, минимум и максимум, не имеют смысла в логике, так как в логике, в общем случае, логические значения TRUE и FALSE не имеют жёсткой привязки к числовым значениям (например в TurboBasic'е, для упрощения некоторых вычислений, TRUE = -1, а FALSE = 0) и невозможно определить, что больше TRUE или FALSE, импликации же и др. имеют смысл и в цифровой технике и в логике.
Тернарные функции
При n = 3 число булевых функций равно 2(23) = 28 = 256. Некоторые из них определены в следующей таблице:
Таблица значений и названий некоторых булевых функций от трех переменных, имеющих собственное название:
| x0=x | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | | |
| x1=y | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | | |
| x2=z | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | Обозначения | Названия |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | F3,1 = x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) = NOR(x,y,z) | 3ИЛИ-НЕ, функция Вебба, стрелка Пирса, кинжал Куайна - "†" |
| 23 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | F3,23 = {\displaystyle \neg (>=2(x,y,z))} = ≥2(x,y,z) | Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией |
| 126 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | F3,126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z) | Неравенство |
| 127 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | F3,127 = x|y|z = |(x,y,z) = NAND(x,y,z) | 3И-НЕ, штрих Шеффера |
| 128 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | F3,128 = x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z) | 3И, минимум |
| 129 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | F3,129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z) | Равенство |
| 150 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | F3,150 = x⊕y⊕z = x⊕2y⊕2z = ⊕2(x,y,z) | Тернарное сложение по модулю 2 |
| 216 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | F3,216 = f1 | Разряд займа при тернарном вычитании |
| 232 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | F3,232 = f2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x И y) ИЛИ (y И z) ИЛИ (z И x) | Разряд переноса при тернарном сложении, переключатель по большинству, 3ППБ, мажоритарный клапан |
| 254 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | F3,254 = (x+y+z) = +(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z) = max(x,y,z) | ИЛИ, максимум |
При трёх и более аргументах префиксная (и постфиксная) запись экономичнее инфиксной записи.
Обычный вид записи функций — префиксный (перед операндами). При инфиксной (между операндами) записи функций функции называются операторами, а аргументы функции — операндами.
Полные системы булевых функций
Основная статья: Замкнутые классы булевых функций
Суперпозиция и замкнутые классы функций
Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции {\displaystyle f(x,y,z)={\overline {x({\overline {y}}\lor z)}}}
(суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:| {\displaystyle x_{2}=x} | {\displaystyle x_{1}=y} | {\displaystyle x_{0}=z} | | {\displaystyle f(x,y,z)} |
| 0 | 0 | 0 | | 1 |
| 0 | 0 | 1 | | 1 |
| 0 | 1 | 0 | | 1 |
| 0 | 1 | 1 | | 1 |
| 1 | 0 | 0 | | 0 |
| 1 | 0 | 1 | | 0 |
| 1 | 1 | 0 | | 1 |
| 1 | 1 | 1 | | 0 |
Говорят, что множество функций замкнуто относительно операции суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это же множество. Замкнутые множества функций называют также замкнутыми классами.
В качестве простейших примеров замкнутых классов булевых функций можно назвать
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее, чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций {\displaystyle \Sigma =\{f_{1},\ldots ,f_{n}\}}
. Тогда каждая булева функция может быть представлена некоторым термом в сигнатуре {\displaystyle \Sigma } , который в данном случае называют также формулой. Относительно выбранной системы функций полезно знать ответы на следующие вопросы:Как построить по данной функции представляющую её формулу?
Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
В частности: существует ли способ приведения произвольной формулы к эквивалентной ей канонической форме такой, что две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Классификация булевых функций[править | править код]
По количеству n входных операндов, от которых зависит значение на выходе функции, различают нульарные (n = 0), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов.
По количеству единиц и нулей в таблице истинности отличают узкий класс сбалансированных булевых функций (также называемых уравновешенными или равновероятностными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2) от более широкого класса несбалансированных булевых функций (так же называемых неуравновешенными, поскольку вероятность получения на выходе значения 1 отлична от 1/2). Сбалансированные булевы функции в основном используются в криптографии.
По зависимости значения функции от перестановки её входных битов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её входных бит).
По значению функции на противоположных друг другу наборах значений аргументов отличают самодвойственные функции (значение которых инвертируется при инвертировании значения всех входов) от остальных булевых функций, не обладающих таким свойством. Нижняя часть таблицы истинности для самодвойственных функций является зеркальным отражением инвертированной верхней части (если расположить входные комбинации в таблице истинности в естественном порядке).
По алгебраической степени нелинейности отличают линейные булевы функции (АНФ которых сводится к линейной сумме по модулю 2 входных значений) и нелинейные булевы функции (АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции входных значений). Примерами линейных функций являются: сложение по модулю 2 (исключающее «ИЛИ», XOR), эквивалентность, а также все булевы функции, АНФ которых содержит лишь линейные операции сложения по модулю 2 без конъюнкций. Примерами нелинейных функций являются: конъюнкция («И», AND), штрих Шеффера («НЕ-И», NAND), стрелка Пирса («НЕ-ИЛИ», NOR), а также все булевы функции, АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции.