Лекция Булевы функции от 1 и 2 переменных

1.

Булевы функции от одной и
двух переменных
СУПЕРПОЗИЦИЯ

2.

Булевы функции от одной переменной
x
f1 ( x)
f 2 ( x)
f 3 ( x)
f 4 ( x)
0
0
0
1
1
1
0
1
0
1
Очевидно, что функция f1 ( x ) 0 – константа, тождественно равная нулю,
и функция f 4 ( x ) 1 – константа, тождественно равная единице.
Функция f 2 ( x ) x – тождественная функция и
функция f 3 ( x) x – операция отрицания.

3.

Булевы функции от двух переменных
x
y
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15
F16
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
,Λ,
&
x
y
,+ +,V,|
,≡
y
x
1
Очевидно, что функция f1 ( x, y ) 0 – константа, тождественно равная нулю,
и функция f16 ( x, y ) 1 – константа, тождественно равная единице.
Функция f 2 ( x, y ) x y – операция конъюнкция и
Функция f15 ( x, y ) f 2 ( x, y ) – отрицание операции конъюнкция,
которая называется штрихом Шеффера и обозначается x | y .

4.

Функция
Функция
f8 ( x, y ) x y – операция дизъюнкция.
f 9 ( x, y ) f8 ( x, y ) – отрицание операции
дизъюнкция, которая называется стрелкой Пирса и
обозначается x y .
Функция f 4 ( x, y ) x – операция проектирования на
первый аргумент.
Функция f13 ( x, y ) f 4 ( x, y ) – отрицание этой операции
проектирования.
Функция f 6 ( x, y ) y – операция проектирования на
второй аргумент.
Функция f11 ( x, y ) f 6 ( x, y ) – отрицание этой операции
проектирования.

5.

Так как функция
f10 ( x, y ) является функцией
истинностных значений формулы X Y , то она
называется эквивалентностью и обозначается x y.
Функция f 7 ( x, y ) f10 ( x, y ) – отрицание
эквивалентности, она называется суммой Жегалкина
и обозначается x y .
Так как функция f14 ( x, y ) является функцией
истинностных значений формулы X Y , то она
называется импликацией и обозначается x y .
Отрицанием импликации является
функция f3 ( x, y) f14 ( x, y) , которая обозначается x y .

6.

Так как функция f12 ( x, y ) является функцией
истинностных значений формулы Y X , то она
называется обратной импликацией и
обозначается x y.
Отрицанием обратной импликации является
функция f5 ( x, y ) f12 ( x, y ) , которая
обозначается x y .

7.

Поскольку имеется 2n наборов (x1,…,xn) нулей и
n
единиц, то существует ровно22 булевых функций
f(x1,…,xn) от n переменных.
Таким образом, 4 булевых функции от 1
переменной, 16 булевых функций от 2
переменных, 256 булевых функций от 3
переменных и т.д.

8.

Суперпозиция
Из описанных выше простейших булевых
функций можно конструировать более сложные
булевы функции с помощью операции
суперпозиции.
Суперпозицией булевых функций
g ( y1 ,..., ym )
и h1 ( x1,..., xn ) , …, hm ( x1,..., xn ) называется булева
функция f ( x1,..., xn ) , значения которой
определяются по формуле:
f ( x1 ,..., xn ) g h1 ( x1 ,..., xn ),..., hm ( x1 ,..., xn )

9.

Примеры
Суперпозицией булевых функций g ( y1, y2 , y3 ) y1 y2 y3
и h1 ( x1, x2 ) x1x2 , h2 ( x1, x2 ) x1 x2 , h3 ( x1, x2 ) x1 x2 является
булева функция f ( x1, x2 ) x1x2 x1 x2 x1 x2 .
Булева функция
f ( x1 , x2 , x3 ) x1 x2 x3 x1 x2 x3 является
суперпозицией булевых функций g ( y1, y2 ) y1 y2
и h1 ( x1, x2 , x3 ) x1x2 x3 , h2 ( x1, x2 , x3 ) x1 x2 x3 .

10.

При построении суперпозиции булевых функций
необходимо использовать скобки для указания
порядка выполнения операций над
переменными.
Для упрощения записи таких выражений скобки
будут по возможности опускаться с учетом
следующего приоритета выполнения булевых
операций: , и затем все остальные операции.
x y x | y
Например, функцию
можно
записать в виде x y ( x | y) .

11.

Лемма о свойствах булевых функций
Булевы функции от двух переменных
взаимосвязаны следующими свойствами:
1. ( x y ) x y , ( xy ) x y – законы де Моргана;
2. x xy x , x( x y) x – законы поглощения;
3. x x 1 , xx 0 – характеристическое свойство
отрицания;
4. x 1 1 , x 1 x - характеристическое свойство
элемента 1;
5. x 0 x , x 0 0 – характеристическое свойство
элемента 0;

12.

6.
x y ( x y ) , xy ( x y )
– взаимосвязь конъюнкции
и дизъюнкции;
7. x y x y , x y ( xy ) – взаимосвязь
импликации с дизъюнкцией, конъюнкцией и
отрицанием;
8. x y ( x y)( y x) , x y ( x y )( x y ) xy x' y ' –
взаимосвязь эквивалентности с импликацией,
дизъюнкцией, конъюнкцией и отрицанием;
9. x | y ( xy ) , xy ( x | y ) ( x | y ) | ( x | y ) , x y x | y ( x | x) | ( y | y ) ,
x x | x – взаимосвязь штриха Шеффера с
дизъюнкцией, конъюнкцией и отрицанием;

13.

10. x y ( x y) ,
x x x ,
xy x y ( x x) ( y y)
x y ( x y) ( x y) ( x y) ,
– взаимосвязь стрелки Пирса с
дизъюнкцией, конъюнкцией и отрицанием;
11. x y y x , ( x y) z x ( y z ) , x( y z ) xy xz, x x 0 ,
x 0 x – характеристическое свойство суммы
Жегалкина;
12. x y xy x y , x y xy x 1 , x y x y 1
x y ( x 1)( y 1) 1 x y xy – взаимосвязь суммы
Жегалкина с дизъюнкцией, конъюнкцией,
отрицанием, импликацией и эквивалентностью.