Булевы функции
Поскольку значение логической формулы определяется значениями входящих в формулу переменных, логическая формула может рассматриваться как логическая функция.
Булева функция Это функция \(f(x_1, x_2, \ldots, x_n)\) , аргументы которой \(x_1, x_2, \ldots, x_n\) , и сама функция \(f\) принимают значения \(0\) или \(1\) .
Логические функции могут быть заданы таблично, либо аналитически.
В общем случае, булеву функцию от \(n\) переменных можно рассматривать как отображение \(\lbrace 0, 1\rbrace^n \to \lbrace 0, 1 \rbrace\) . Пространство \(\lbrace 0, 1\rbrace^n\) можно интерпретировать как \(n\) -битное двоичное число.
Существует \(2^n\) различных \(n\) -битных двоичных чисел. Так как каждому из них сопоставляется значение функции – 0 или 1, то общее количество различных булевых функций \(n\) аргументов равно \(2^<2^n>\) .
От двух переменных существует 16 различных булевых функций. Особо интересными из них являются:
- Штрих Шеффера \[f(x,y) = \;\overline\; = a | b\]
- Стрелка Пирса \[f(x,y) = \;\overline\; = a \downarrow b\]
Канонические формы логических функций
Ясно, что для определения любой логической функции может существовать бесконечно много различных эквивалентных логических формул.
Одно из основных применений алгебры логики заключается в нахождении канонических форм, то есть, логических формул, взаимно однозначно соответствующих логическим функциям.
Нормальная форма Если логическая функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных, то такая форма записи называется нормальной.
Среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными.
Элементарная конъюнкция Это конъюнкция одной или нескольких переменных, или их отрицаний. Элементарная дизъюнкция Это дизъюнкция одной или нескольких переменных, или их отрицаний. Дизъюнктивная нормальная форма (ДНФ) Это дизъюнкция не повторяющихся элементарных конъюнкций. Конъюнктивная нормальная форма (КНФ) Это конъюнкция не повторяющихся элементарных дизъюнкций.
Среди дизъюнктивных или конъюнктивных нормальных форм, очевидно, существуют совершенные.
Совершенная ДНФ (СДНФ) Это ДНФ, в которой каждая элементарная конъюнкция состоит из \(k\) переменных \(x_1, x_2, \ldots, x_k\) , причем на \(i\) -том месте конъюнкции стоит переменная \(x_i\) или ее отрицание \(\;\overline
Любую логическую функцию можно представить в виде СДНФ или СКНФ. Для обоснования этого утверждения, рассмотрим две теоремы.
Теорема о существовании СДНФ Пусть \(f(x_1, x_2, \ldots, x_n)\) – булева функция от \(n\) переменных, не равная тождественно нулю. Тогда существует СДНФ, выражающая функцию \(f\) . Доказательство
Для начала покажем, что переменную можно “вынести” за знак функции с помощью конъюнкции:
\[f(x_1,\ldots,x_i,\ldots,x_n) = \;\overline
Действительно, если \(x_i = 0\) , то \[f(x_1,\ldots,x_i,\ldots,x_n) = 1 \,\&\,f(x_1,\ldots,0,\ldots,x_n) \vee 0 \,\&\,f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,0,\ldots,x_n)\]
Иначе, если \(x_i = 1\) , \[f(x_1,\ldots,x_i,\ldots,x_n) = 0 \,\&\,f(x_1,\ldots,0,\ldots,x_n) \vee 1 \,\&\,f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,1,\ldots,x_n)\]
Последовательно “вынося” переменные за знак функции, получим следующую формулу (знаки конъюнкции опущены):
\[\begin
Теперь, зная значения функции, можно полностью исключить конъюнкции, содержащие \(f=0\) , по закону поглощения нуля, и опустить в остальных конъюнкциях \(f=1\) по закону поглощения единицы.
Мы получили СДНФ, следовательно, она существует по построению. \(\blacksquare\)
Очевидна причина требования неравенства нулю: для \(f=0\) СДНФ не будет иметь ни одного члена.
Теорема о существовании СКНФ Пусть \(f(x_1, x_2, \ldots, x_n)\) – булева функция от \(n\) переменных, не равная тождественно единице. Тогда существует СКНФ, выражающая функцию \(f\) . Доказательство
Для начала покажем, что переменную можно “вынести” за знак функции с помощью дизъюнкции:
\[f(x_1,\ldots,x_i,\ldots,x_n) = (x_i \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(\;\overline
Действительно, если \(x_i = 0\) , то \[f(x_1,\ldots,x_i,\ldots,x_n) = (0 \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(1 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,0,\ldots,x_n) \]
Иначе, если \(x_i = 1\) , \[f(x_1,\ldots,x_i,\ldots,x_n) = (1 \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(0 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,1,\ldots,x_n) \]
Последовательно “вынося” переменные за знак функции, получим следующую формулу:
Теперь, зная значения функции, можно полностью исключить дизъюнкции, содержащие \(f=1\) , по закону поглощения единицы, и опустить в остальных дизъюнкциях \(f=0\) по закону поглощения нуля.
Мы получили СКНФ, следовательно, она существует по построению. \(\blacksquare\)
Очевидна причина требования неравенства единице: для \(f=1\) СКНФ не будет иметь ни одного члена.
Полные системы булевых функций
По теоремам о существовании СДНФ и СКНФ, система функций \(\lbrace \,\&\,, \vee, \neg \rbrace\) является полной.
Полноту других систем можно обосновать при помощи следующего очевидного утверждения:
Если система \(\lbrace f_1, \ldots, f_n \rbrace\) является полной, и каждая из функций \(f_1, \ldots, f_n\) может быть выражена через функции \(g_1, \ldots, g_n\) , то система \(\lbrace g_1, \ldots, g_n \rbrace\) так же является полной.
Так, несложно доказать, что системы \(\lbrace \vee, \neg \rbrace\) и \(\lbrace \,\&\,, \neg \rbrace\) так же являются полными.
Из всех булевых функций двух переменных, штрих Шеффера и стрелка Пирса образуют полные системы булевых функций сами по себе.
Штрих Шеффера \(x|y\) определяется как
| \(x\) | \(y\) | \(x|y\) |
|---|---|---|
| \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(0\) |
Можно видеть так же, что \(x|y = \;\overline
Через штрих Шеффера легко выражаются конъюнкция, дизъюнкция и инверсия:
Стрелка Пирса \(x\downarrow y\) определяется как
| \(x\) | \(y\) | \(x\downarrow y\) |
|---|---|---|
| \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(0\) |
| \(1\) | \(1\) | \(0\) |
Можно видеть так же, что \(x\downarrow y = \;\overline
Через стрелку Пирса легко выражаются конъюнкция, дизъюнкция и инверсия:
\[x\downarrow x = \;\overline
\[ x \vee y = \;\overline<\;\overline
Возможность выражения любой булевой функции через одну имеет большое значение при разработке элементной базы для реализации алгебры логики в вычислительных машинах. В частности, возможность на одинаковых логических элементах собрать схему произвольной сложности значительно упрощает задачу производства логических схем.
Особенно интересным является тот факт, что СДНФ может быть непосредственно выражена через элементы И-НЕ со многими входами, а СКНФ – через элементы ИЛИ-НЕ со многими входами. Для этого все элементарные конъюнкции/дизъюнкции заменяются на И-НЕ/ИЛИ-НЕ, и их дизъюнкция/конъюнкция так же заменяется на И-НЕ/ИЛИ-НЕ
5.3. Булевы функции от одной и двух переменных
<0,1>. В следующей таблице приведены все четыре булевы функции от одной переменной.
x g 0 ( x ) g 1 ( x ) g 2 ( x ) g 3 ( x )
g 0 ( x )=0 – функция, тождественно равная 0 (тождественный ноль);
g 1 ( x )= x – тождественная функция;
g 2 ( x )=1– x – эта функция соответствует отрицанию и носит то же название; в теории булевых функций отрицание принято обозначать через x ’, поэтому мы будем писать g 2 ( x )= x ’;
g 3 ( x )=1 – функция, тождественно равная 1 (тождественная единица).
Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве <0,1>. В следующей таблице приведены все шестнадцать булевых функции от двух переменных (значения аргументов и функций выписаны в строках, функции перечисляются в столбце). Для некоторых функций указаны используемые обозначения и названия.
0 – тождественный ноль
– сложение по модулю 2
1 – тождественная единица
перечисленные функции (с помощью
суперпозиций), можно строить более сложные булевы функции,
в том числе и большего числа переменных, например, xy → zt и т.п. Булевы отрицание, конъюнкция (умножение), дизъюнкция, импликация обладают свойствами, подобными тем, которыми обладают соответствующие логические операции (с естественной заменой равносильности формул на равенство функций). Например, законы де Моргана принимают следующий вид (знак умножения, как это часто делается, опущен):
( xy )’= x ’ y ’; ( x y )’= x ’ y ’.
Кроме того, имеем:
Приведем некоторые уравнения, в которых одни булевы функции выражены через другие:
x ’ = x → 0 = x | x = x ↓ x = 1 x ;
xy = ( x ’ y ’)’ = x ’ ↓ y ’ = ( x ↓ x ) ↓ ( y ↓ y );
x y = ( x ’ y ’)’ = x ’ → y = =( x → y ) → y = x ’| y ’ = ( x | x )|( y | y ); x → y = x ’ y ;
x ↔ y = ( x → y ) ( y → x ) = xy x ’ y ’; x y = xy ’ x ’ y .
Все эти равенства легко проверяются с помощью таблиц.
Принцип двойственности естественным образом переносится на булевы функции. Приведем необходимые формулировки. Двойственной к булевой функции f ( x , y ,…, z ) называется функция
f * ( x , y ,…, z )= f ’( x ’, y ’,…, z ’).
Если f ( x , y ,…, z ) представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой формуле конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции.
Существует простой способ дать аналитическое представление функции в виде формулы, содержащей конъюнкции, дизъюнкции и отрицания, используя ее табличное задание. Например, пусть функция от трех переменных задана следующей таблицей:
x y z f ( x , y , z )
f ( x , y , z ) = x ’ y ’ z ’ xy ’ z ’ xyz .
Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция принимает значение 1. Каждое слагаемое содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 0 в соответствующем наборе. Так, набору (0,0,0) соответствует слагаемое x ’ y ’ z ’, набору (1,0,0) – слагаемое xy ’ z ’, набору (1,1,1)
– слагаемое xyz . Каждый из дизъюнктивных членов принимает значение 1 на своем наборе значений переменных и значение 0
– на всех остальных. Дизъюнкция этих трех слагаемых принимает значение 1 лишь тогда, когда значение 1 принимает хотя бы одно из слагаемых. Таким образом, функция в правой части записанного равенства принимает значение 1 на тех же трех наборах значений аргументов, что и функция f (на остальных наборах обе эти функции принимают значение 0). Тем самым справедливость равенства установлена.
Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Получаемые при этом формулы называются совершенными дизъюнктивными нормальными формами , сокращенно СДНФ. Считается, что СДНФ тождественного нуля – это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого.
Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме , сокращенно СКНФ. СКНФ рассмотренной ранее функции имеет следующий вид:
f ( x , y , z ) = ( x y z ’)( x y ’ z )( x y ’ z ’)( x ’ y z ’)( x ’ y ’ z ).
Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0. Каждый множитель содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 1 в соответствующем наборе. Так, набору (0,0,1) соответствует множитель xyz ’, набору (0,1,0) –
множитель xy ’ z , и т. д. Каждый из конъюнктивных членов принимает значение 0 на своем наборе значений переменных и значение 1 – на всех остальных. Конъюнкция этих трех множителей принимает значение 0 лишь тогда, когда значение 0 принимает хотя бы один из множителей. Таким образом, функция в правой части записанного равенства принимает значение 0 на тех же трех наборах значений аргументов, что и функция f .
Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.
Теорема. Пусть f ( x 1 , x 2 ,…, x n ) – произвольная булева функция. Тогда
f ( x 1 , x 2 ,…, x n ) = x 1 f (1, x 2 ,…, x n ) x 1 ’ f (0, x 2 ,…, x n );
f ( x 1 , x 2 ,…, x n ) = ( x 1 f (0, x 2 ,…, x n ))( x 1 ’ f (1, x 2 ,…, x n )).
Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух переменных. Доказываемая формула принимает следующий вид:
f ( x , y ) = x f (1, y ) x ’ f (0, y ).
При любом y подстановка в правую часть x =1 и x =0 дает соответственно
1 f (1, y ) 1’ f (0, y ) = f (1, y ) 0 f (0, y ) = f (1, y ) 0 = f (1, y );
0 f (1, y ) 0’ f (0, y ) = 0 1 f (0, y ) = 1 f (0, y ) = f (0, y ).
Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции слева и справа от знака равенства равны. На общий случай доказательство распространяется практически без изменений. Достаточно считать, что y обозначает не одну переменную, а набор переменных. Второе равенство из формулировки теоремы доказывается аналогично (впрочем, его справедливость следует из принципа двойственности).
Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции. Например,
f ( x , y ) = x f (1, y ) x ’ f (0, y ) =
= x ( y f (1,1) y ’ f (1,0)) x ’ ( y f (1,1) y ’ f (1,0)) =
= x y f (1,1) x y ’ f (1,0) x ’ y f (1,1) x ’ y ’ f (1,0).
Функция f ( x , y ) представлена в виде дизъюнкции четырех
дизъюнктивных членов. Те из них, для которых коэффициент f ( α , β ) равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции f ( x , y )= x y имеем f (0,0)= f (1,1)=0
и f (0,1)= f (1,0)=1, поэтому
Элементарной конъюнкцией ( конъюнктом ) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.
Определение булевой функции
Элементы булева множества [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]<2^2>^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]<2^2>^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.
Унарные функции
При [math]n = 1[/math] число булевых функций равно [math]<2^2>^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>^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]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]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]<2^2>^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<0>=1[/math] | [math]\overline<1>=0[/math] | [math]\overline<\overline |
[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 |
[math]x \lor \overline |
| [math]\overline |
[math]\overline |
(законы де Моргана) |
[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 |
Легко показать, что в этом равенстве [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 = \
- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Определение: Дизъюнктивная нормальная форма (ДНФ) (англ. 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] 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_<1>, \ldots, x_ , g(x_, \ldots, x_ Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/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_<1>, \ldots, x_ , x_ ) = f(x_<1>, \ldots, x_, \ldots, x_ , x_, x_ )[/math] Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/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]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] несамодвойственная, т.е.
Сколько всего булевых функций от n переменных?
Теорема о числе булевых функций. Число различных булевых функций, зависящих от n переменных, равно 2 2 n .
Сколько существует булевых функций от одного аргумента принадлежащих к классу t0 сохраняющих константу 0 функций?
Утверждение о числе булевых функций класса T0. Число различных булевых функций, зависящих от n переменных и сохраняющих константу 0, равно 22n –1. Теорема о замкнутости класса T0.
Что такое Булева функция?
Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества < 0, 1 >в множество < 0, 1 >. Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству < 0, 1 >.
Как определить булеву функцию?
Булевой функцией y=f(x1, x2 . xn) от п переменных x1, x2, xn называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т. е. булева функция это правило по которому произвольному набору нулей и единиц (x1, x2 .
Что такое булева переменная?
Булева переменная – это переменная со значениями из булева множества B =<0,1>. Обозначаются булевы переменные символами: a, b, c, …, x, y, z, или теми же символами с индексами: x1 x2, …, xn.
Сколько линейных булевых функций?
Число различных линейных булевых функций, зависящих от n переменных, равно 2n+1. Теорема о замкнутости класса L.
Сколько существует булевых функций от одного аргумента принадлежащих к классу t1 сохраняющих константу 1 функций?
Утверждение о числе булевых функций класса T1. Число различных булевых функций, зависящих от n переменных и сохраняющих константу 1, равно 22n –1. Теорема о замкнутости класса T1.
Сколько существует функций от 2 переменных?
Таким образом, существует 16 различных функций от двух переменных, каждая из которых может быть задана своей таблицей истинности.
Где используются булевы функции?
Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. . Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью
Когда Булева функция линейная?
Функция называется линейной, если каждое элементарное произведение канонического полинома Жегалкина, который представляет эту функцию, имеет не больше одного сомножителя.
Сколько монотонных функций?
Среди функций двух переменных монотонными являются шесть функций: f0, f1, f3, f5, f7, f15.