* = ¬¬f ( ¬¬x 1 ,...,¬¬x n ) =
* = f ( x 1 ,...,x n )
*
В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на (гипер-) плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаться должны функции, область определения которых – дискретное множество * . Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. * Так мы и приходим к понятию булевой функции.
Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n -ой степени множества { 0, 1 } в множество { 0, 1 }.
Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B .
Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B . При этом алгебра <B; W >, где W – множество всевозможных булевых функций, называется алгеброй логики .
Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:
| x 1 | x 2 | ... | x n- 1 | x n | f |
|---|---|---|---|---|---|
| 0 | 0 | ... | 0 | 0 | f(0,0,...,0,0) |
| 0 | 0 | ... | 0 | 1 | f(0,0,...,0,1) |
| 0 | 0 | ... | 1 | 0 | f(0,0,...,1,0) |
| 0 | 0 | ... | 1 | 1 | f(0,0,...,1,1) |
| ... | ... | ... | ... | ... | ... |
| 1 | 1 | ... | 0 | 0 | f(1,1,...,0,0) |
| 1 | 1 | ... | 0 | 1 | f(1,1,...,0,1) |
| 1 | 1 | ... | 1 | 0 | f(1,1,...,1,0) |
| 1 | 1 | ... | 1 | 1 | f(1,1,...,1,1) |
Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f (0,0,...,0,0) , f (0,0,...,0,1) , f (0,0,...,1,0) , f (0,0,...,1,1),..., f (1,1,...,0,0) , f (1,1,...,0,1) , f (1,1,...,1,0) , f (1,1,...,1,1). Этот набор называют вектором значений функции .
Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2 n * . А их 2 в степени 2 n .
Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1 .
Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция , т.е. функция, значение которой совпадает с аргументом и так называемая функция `` отрицание ''. Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:
| x | 0 | x | ¬ x | 1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих ``добавочных'' переменных. Такие переменные называются фиктивными , в отличие от остальных – существенных .
Определение 2 (Фиктивные и существенные переменные). Переменная x i называется фиктивной (несущественной) переменной функции f ( x 1 ,···,x n ), если
Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций (только те, которые существенно зависят от обеих переменных) мы приводим в следующей таблице:
| x 1 | x 2 | x 1 & x 2 | x 1 Ъ x 2 | x 1 Й x 2 | x 1 Е x 2 | x 1 є x 2 | x 1 | x 2 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Эти функции записываются как бинарные операции в инфиксной нотации. x 1 & x 2 называется конъюнкцией , x 1 Ъ x 2 – дизъюнкцией , x 1 Й x 2 – импликацией , x 1 є x 2 – эквивалентностью , x 1 Е x 2 – суммой по модулю 2 , x 1 | x 2 – штрихом Шеффера .
Значения 0 и 1 часто интерпретируют как ``ложь'' и ``истину''. Тогда понятным становится название функции ``отрицание'' – она меняет ``ложь'' на ``истину'', а ``истину'' на ``ложь''. Отрицание читается как ``не''. Конъюнкция читается обычно как ``и'' – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная. * Кроме x 1 & x 2 часто используют обозначение x 1 Щ x 2 или x 1 · x 2 или x 1 x 2 или min( x 1 ,x 2 ). Дизъюнкция читается ``или'' – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная. * Импликация выражает факт, что из x 1 следует x 2 . * Импликацию часто также обозначают x 1 ® x 2 .
Определение 3 (Суперпозиция функций). Суперпозицией булевых функций f 0 и f 1 ,...,f n называется функция f ( x 1 ,...,x m ) = f 0 ( g 1 ( x 1 ,...,x m ) ,...,g k ( x 1 ,...,x m )), где каждая из функций g i ( x 1 , ...,x m ) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f 1 ,...,f n .
Пример 1 (суперпозиция функций).
Функция f ( x,y ) = ¬ ( x & y ) является суперпозицией функций ¬ и &. Функция g ( x,y ) = x Е ( x Ъ y ) является суперпозицией функций Е и Ъ . Функция h ( x,y,z ) = ( x & y ) Е z является суперпозицией функций Е и &. Построим таблицы этих функций.
Суперпозицию ( x & y ) Е ( ¬x Ъ ¬y ) можно прочитать как `` x и y плюс не x или не y ''.
Следующие соотношения могут быть проверены прямым сравнением значений функций в левой и правой части соотношения на всевозможных наборах аргументов.
Определение 4 (Двойственная функция). Функция g ( x 1 ,...,x n ) = ¬f ( ¬x 1 ,...,¬x n ) называется двойственной функцией к функции f и обозначается f * .
Пример 2 (двойственные функции).
( x & y ) * = ¬ ( ¬x & ¬y ) = x Ъ y .
Предложение 1 (Двойственная к двойственной функции). Функция, двойственная к двойственной функции f равна самой функции f.
Доказательство. f
* ( x 1 ,...,x n )
* = ( ¬f ( ¬x 1 ,...,¬x
n )) * =
*
= ¬¬f ( ¬¬x 1 ,...,¬¬x n
) =
*
= f ( x 1 ,...,x n )
*
Рассмотрим, что происходит с таблицей двойственной функции. Замена набора ( x 1 ,...,x n ) на ( ¬x 1 ,...,¬x n ) соответствует ``переворачиванию'' таблицы. Действительно, наборы ( x 1 ,...,x n ) и ( ¬x 1 ,..., ¬x n ) расположены симметрично относительно середины таблицы. Теперь остаётся применить операцию ¬ к результату функции, т.е. поменять 0 на 1 и 1 на 0. Т.о. вектор значений функции, двойственной к исходной, получается из вектора исходной функции переворачиванием и заменой 0 на 1, а 1 на 0.
Пример 3 (вектор двойственной функции).
Функции x & y и x Ъ y , задаваемые векторами значений (0,0,0,1) и (0,1,1,1) двойственны друг к другу. Также двойственными являются x Е y и x є y , задаваемые векторами (0,1,1,0) и (1,0,0,1). Каждая из функций x и ¬x (векторы (0,1) и (1,0) соответственно) двойственна сама себе.
Теорема 1 (Принцип двойственности). Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:
Доказательство. f
0 ( f 1 ( x 1 ,...,x
n ) ,...,f m ( x 1
,...,x n )) * =
| = ¬f 0 ( f 1 ( ¬x 1 ,...,¬x n ) ,...,f m ( ¬x 1 ,...,¬x n )) = | * |
| = ¬f 0 ( ¬¬f 1 ( ¬x 1 ,...,¬x n ) ,...,¬¬f m ( ¬x 1 ,...,¬x n )) = | * |
| = ¬f 0 ( ¬f 1 * ( x 1 ,...,x n ) ,...,¬f m * ( x 1 ,...,x n )) = | * |
| = f 0 * ( f 1 * ( x 1 ,...,x n ) ,...,f m * ( x 1 ,...,x n )) | * |
.
x s =
м
¬x, если s =0
н
о
x, если s =1
Теорема 2 (Разложение в дизъюнкцию). Любую функцию f ( x 1 ,...,x m ) для любого n (1 Ј n Ј m ) можно представить в виде
x
1 s 1 & ...
& x n s n
& f ( s 1 ,..., s
n ,x n+ 1 ,...,x m )
Доказательство. Покажем, что для любого набора значений переменных ( x 1 ,...,x n ,x n+ 1 ,...,x m ) значения левой и правой частей совпадают. Возьмём фиксированный набор ( x 1 ,...,x n ,x n+ 1 ,...,x m ). Рассмотрим выражение x 1 s 1 & ... & x n s n . Если одно из значений x i s i равно 0, то и всё выражение равно 0. Тогда и выражение x 1 s 1 & ... & x n s n & f ( s 1 ,..., s n ,x n+ 1 ,...,x m ) равно 0. Единице же выражение x 1 s 1 & ... & x n s n равно только в том случае, если s 1 = x 1 , ..., s n = x n . При этом f ( s 1 ,..., s n ,x n+ 1 ,...,x m ) = f ( x 1 ,...,x n ,x n+ 1 ,...,x m ) Таким образом, значение правой части всегда равно равно f ( x 1 ,...,x m ), то есть значению левой части.
Теорема 3 (Разложение в конъюнкцию). Любую функцию f ( x 1 ,...,x m ) для любого n (1 Ј n Ј m ) можно представить в виде
x
1 ¬ s 1
Ъ ... Ъ x n ¬ s
n Ъ f ( s
1 ..., s n ,x n+ 1
,...,x m )
Разложения по всем переменным дают суперпозицию конъюнкции, дизъюнкции и отрицания.
Следствие 1 (Совершенная дизъюнктивная нормальная форма).
Любая функция f может быть представлена в следующей форме: *
| f (
x 1 ,...,x m ) =
x 1 s 1
& ... & x m s
m & f ( s 1 ,...,
s m ) =
* |
= 
x 1 s 1
& ... & x m s
m |
Следствие 2 (Совершенная конъюнктивная нормальная форма).
Любая функция f может быть представлена в следующей форме: *
x
1 ¬ s 1
Ъ ... Ъ x m ¬ s
m
Таким образом, любая булева функция может быть представлена суперпозицией конъюнкции, дизъюнкции и отрицания. Разложение по всем переменным в дизъюнкцию называется совершенной дизъюнктивной нормальной формой функции, а в конъюнкцию – совершенной конъюнктивной нормальной формой . *
Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания если у нас есть таблица значений функции.
Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.
Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.
Пример 4 (совершенная дизъюнктивная нормальная форма).
Построим совершенную дизъюнктивную нормальную форму функции, заданной следующей таблицей.
| x | y | z | f |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Наборы, на которых функция равна 1 – это (0,1,1), (1,0,1), (1,1,0), (1,1,1). Первый набор даёт конъюнкцию ¬x & y & z , второй – x & ¬y & z , третий – x & y & ¬z , четвёртый – x & y & z . В результате получаем ( ¬x & y & z ) Ъ ( x & ¬y & z ) Ъ ( x & y & ¬z ) Ъ ( x & y & z ).
