Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от аргументов — в дискретной математике — отображение , где — булево множество. Элементы булева множества обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число , обозначающее количество аргументов, называется арностью или местностью функции, в случае булева функция превращается в булеву константу. Элементы декартова произведения (-я прямая степень) называют булевыми векторами или булевыми наборами. Множество всех булевых функций от любого числа аргументов часто обозначается , а от аргументов — . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.
При работе с булевыми функциями происходит полное абстрагирование от того содержательного смысла, какой предполагается в алгебре высказываний. Тем не менее между булевыми функциями и формулами алгебры высказываний можно установить взаимно-однозначное соответствие, если: установить взаимно-однозначное соответствие между булевыми и пропозициональными переменными; установить связь между булевыми функциями и логическими связками; оставить приоритет операций без изменений. Раздел математики, изучающий булевы функции, называется теория булевых функций. Он является подразделом теории функций k-значной логики.
Основные сведения Каждая булева функция арности полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины . Число таких векторов равно . Поскольку на каждом векторе булева функция может принимать значение либо , либо , то количество всех n-арных булевых функций равно . Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции.
Практически все булевы функции низших арностей (0, 1, 2 и 3) получили исторически сложившиеся имена. Если значение функции не зависит от одной из переменных (то есть, по сути, для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная, не играя никакого «значения», называется фиктивной. В противном случае переменная называется существенной. Некоторые авторы определяют булевы функции с точностью до добавления/удаления фиктивной переменной. Другие же авторы используют обычное теоретико-множественное равенство функций, а функции, совпадающие с точностью до добавления/удаления существенных переменных, они называют эквивалентными.
Таблицы истинности
Булева функция задаётся конечным набором значений, что позволяет представить её в виде таблицы истинности, например:
+ 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 1 1 … 0 0 1 1 1 … 0 1 0 1 1 … 1 0 0 1 1 … 1 1 0 Иногда, для краткости, таблицу истинности представляют в виде строки значений функции:
Значения функции в этой строке идут в лексикографическом порядке векторов аргументов. Нульарные функции При n = 0 количество булевых функций сводится к двум 220 = 21 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица. Таблица значений и названий нульарных булевых функций: Значение Обозначение Название 0 F0,0 = 0 тождественный ноль 1 F0,1 = 1 тождественная единица
Унарные функции При n = 1 число булевых функций равно 221 = 22 = 4. Определение этих функций содержится в следующей таблице.
Таблица значений и названий булевых функций от одной переменной: {| class="standard" !x0=x||1||0 !Обозначение !Название
!0 ||0 ||0 ||F1,0 = 0 |тождественный ноль
!1 ||0 ||1 ||F1,1 = NOT(x) = = ¬x = x |отрицание, логическое «НЕТ», «НЕ», инвертор, SWAP (обмен)
!2 ||1 ||0 ||F1,2 = YES(x) = x |логическое "ДА", повторитель, тавтология
!3 ||1 ||1 ||F1,3 = 1 |тождественная единица
Бинарные функции При n = 2 число булевых функций равно 222 = 24 = 16.
В таблице значений и названий булевых функций от двух переменных (в зависимости от области применения, функции имеют разные обозначения и разные словесные названия, но один и тот же номерНомера логических функций https://dzen.ru/a/Zn5r7J4wYEgC3ubl): {| class="standard" !x0=x||1||0||1||0 ! rowspan="2" |Обозначение функции ! rowspan="2" |Название функции
!x1=y||1||1||0||0
!0 ||0 ||0 ||0 ||0 ||F2,0 = 0 |тождественный ноль
!1 ||0 ||0 ||0 ||1 ||F2,1 = x ↓ y = x † y = x NOR y = NOR(x,y) = x НЕ-ИЛИ y = НЕ-ИЛИ(x,y) = NOT(MAX(X,Y)) |стрелка Пи́рса - "↓" (кинжал Куайна - "†"), функция Ве́бба - "°", НЕ-ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, инверсия максимума
!2 ||0 ||0 ||1 ||0 ||F2,2 = x > y = x GT y = GT(x,y) = = x y |функция сравнения "первый операнд больше второго операнда", инверсия прямой импликации, коимпликацияИзбранные вопросы теории булевых функций. // А. С. Балюк и др. Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: ФИЗМАТЛИТ, 2001. — 192 с. — С. 13.
!3 ||0 ||0 ||1 ||1 ||F2,3 = = 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 |функция сравнения "первый операнд меньше второго операнда", инверсия обратной импликации, обратная коимпликация
!5 ||0 ||1 ||0 ||1 ||F2,5 = = 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) = XMAX(x,y) = x XMAX y |функция сравнения "операнды не равны", сложение по модулю 2, исключающее «или», сумма Жегалкина, исключающий max
!7 ||0 ||1 ||1 ||1 ||F2,7 = x | y = 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 = x IMP yBorland Turbo BASIC Owners Handbook 1987, p.80 |функция сравнения "первый операнд не больше второго операнда", прямая (материальная) импликация (от первого аргумента ко второму)
!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=x10101010 ОбозначенияНазвания x1=y11001100 x2=z11110000 1 00000001 F3,1 = x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) = NOR(x,y,z) 3ИЛИ-НЕ, функция Вебба, стрелка Пирса, кинжал Куайна - "†" 23 00010111 F3,23 = = Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией 126 01111110 F3,126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z) Неравенство 127 01111111 F3,127 = x|y|z = |(x,y,z) = NAND(x,y,z) 3И-НЕ, штрих Шеффера 128 10000000 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 10000001 F3,129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z) Равенство 150 10010110 F3,150 = x⊕y⊕z = x⊕2y⊕2z = ⊕2(x,y,z) Тернарное сложение по модулю 2 184 10111000 F3,184 = Условная дизъюнкция 202 11001010 F3,202 = MUX(x,y) Мультиплексор 2 в 1 216 11011000 F3,216 = f1 Разряд займа при тернарном вычитании 232 11101000 F3,232 = f2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x И y) ИЛИ (y И z) ИЛИ (z И x) Разряд переноса при тернарном сложении, переключатель по большинству, 3ППБ, мажоритарный клапан 248 11111000 F3,248 = x OR (y AND z) = Gi+1,j+1 = Gi+1,j OR (Pi+1,j AND Gi,j) Оператор G (Genarate) Valency-2 (валентность=2) в параллельно префиксных сумматорах
254 11111110 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) ИЛИ, максимум При трёх и более аргументах префиксная (и постфиксная) запись экономичнее инфиксной записи. Обычный вид записи функций — префиксный (перед операндами). При инфиксной (между операндами) записи функций функции называются операторами, а аргументы функции — операндами.
Представление булевых функций В ряде случаев оказывается намного удобнее представлять булевы функции не таблицами истинности, а формулами над некоторой системой элементарных функций. Какие функции при этом можно будет выразить такой формулой, а какие нет, зависит от того, какие функции будут выбраны в качестве элементарных. Если при помощи формул над некоторой системой функций можно выразить вообще все булевы функции, то такая система называется полной. Относительно выбранной системы функций полезно знать ответы на следующие вопросы: Как построить по данной функции представляющую её формулу? Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию? В частности: существует ли способ приведения произвольной формулы к эквивалентной ей канонической форме такой, что две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают? Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ) Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция правильная, если каждая переменная входит в неё не более одного раза (включая отрицание); полная, если каждая переменная (или её отрицание) входит в неё ровно 1 раз; монотонная, если она не содержит отрицаний переменных. Например — является ДНФ.Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .
Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию , где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является , что можно упростить до .