Похожие презентации:
Системы булевых функций
1.
Системы булевых функций2.
Операции дизъюнкция + и конъюнкция являютсяпримерами двух из шестнадцати булевых функций от
двух переменных, которые перечисляются в следующей
таблице:
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
+
y
x
1
-
штрих
Функция f15 ( x, y ) f 2 ( x, y )
обозначается x | y .
f 9 ( x, y ) f8 ( x, y )
Функция
обозначается x y .
-
Шеффера,
стрелка
Пирса,
3.
Определение. Суперпозицией булевых функцийg ( y1 ,..., ym ) и h1 ( x1 ,..., xn ) , …, hm ( x1 ,..., xn ) называется
булева функция f ( x1,..., xn ) , значения которой
определяются по формуле:
f ( x1 ,..., xn ) g h1 ( x1 ,..., xn ),..., hm ( x1 ,..., xn ) .
Для упрощения записи суперпозиции булевых
функций скобки по возможности опускаются с
учетом следующего приоритета выполнения
булевых операций: , и затем все остальные
операции.
4.
Лемма. Булевы функции от двух переменныхвзаимосвязаны следующими свойствами:
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;
x 0 0 – характеристическое
5) x 0 x ,
свойство элемента 0;
xy ( x y )
6) x y ( x y ) ,
– взаимосвязь
конъюнкции и дизъюнкции;
x y ( xy )
7) x y x y ,
– взаимосвязь
импликации с дизъюнкцией, конъюнкцией и
отрицанием;
5.
8) x y ( x y)( y x) , x y ( x y )( x y ) ;xy ( x | y ) ( x | y ) | ( x | y ) ,
x x | x ,
9) x | y ( xy ) ,
x y x | y ( x | x) | ( y | y ) – взаимосвязь штриха
Шеффера
с
дизъюнкцией,
конъюнкцией
и
отрицанием;
10) x y ( x y) , x x x , x y ( x y) ( x y) ( x y) ,
xy x y ( x x) ( y y) – взаимосвязь стрелки
Пирса с дизъюнкцией, конъюнкцией и отрицанием;
11) x y y x , ( x y) z x ( y z ) , x( y z) xy xz,
x 1 x ,
x x 0,
x 0 x,
x x 1
–
характеристическое свойство суммы Жегалкина;
x y x y 1,
x y xy x 1 ,
12) x y xy x y ,
x y ( x 1)( y 1) 1 x y xy
–
взаимосвязь
суммы Жегалкина с дизъюнкцией, конъюнкцией,
отрицанием, импликацией и эквивалентностью.
6.
Определение. Система булевых функцийF f1 ,..., f k называется полной, если любая булева
функция может быть представлена в виде
суперпозиции функций из этой системы F.
Теорема Жегалкина. Любая булева функция f от
n переменных представима в виде следующего
полинома Жегалкина
f ( x1 ,..., xn )
i1 ,..., ik
xi1 ...xik c
для некоторых значений c 0,1 и 1 i1 ... ik n .
Причем такое представление булевой функции f
единственно с точностью до порядка слагаемых.
7.
Лемма. Булевы функции от двух переменныхвзаимосвязаны следующими свойствами:
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;
x 0 0 – характеристическое
5) x 0 x ,
свойство элемента 0;
xy ( x y )
6) x y ( x y ) ,
– взаимосвязь
конъюнкции и дизъюнкции;
x y ( xy )
7) x y x y ,
– взаимосвязь
импликации с дизъюнкцией, конъюнкцией и
отрицанием;
8.
8) x y ( x y)( y x) , x y ( x y )( x y ) ;xy ( x | y ) ( x | y ) | ( x | y ) ,
x x | x ,
9) x | y ( xy ) ,
x y x | y ( x | x) | ( y | y ) – взаимосвязь штриха
Шеффера
с
дизъюнкцией,
конъюнкцией
и
отрицанием;
10) x y ( x y) , x x x , x y ( x y) ( x y) ( x y) ,
xy x y ( x x) ( y y) – взаимосвязь стрелки
Пирса с дизъюнкцией, конъюнкцией и отрицанием;
11) x y y x , ( x y) z x ( y z ) , x( y z) xy xz,
x 1 x ,
x x 0,
x 0 x,
x x 1
–
характеристическое свойство суммы Жегалкина;
x y x y 1,
x y xy x 1 ,
12) x y xy x y ,
x y ( x 1)( y 1) 1 x y xy
–
взаимосвязь
суммы Жегалкина с дизъюнкцией, конъюнкцией,
отрицанием, импликацией и эквивалентностью.
9.
Определение. Система булевых функцийF f1 ,..., f k называется полной, если любая булева
функция может быть представлена в виде
суперпозиции функций из этой системы F.
Теорема Жегалкина. Любая булева функция f от
n переменных представима в виде следующего
полинома Жегалкина
f ( x1 ,..., xn )
i1 ,..., ik
xi1 ...xik c
для некоторых значений c 0,1 и 1 i1 ... ik n .
Причем такое представление булевой функции f
единственно с точностью до порядка слагаемых.
10.
Определение. Булева функция f называется линейной,если ее представление полиномом Жегалкина не
содержит произведения переменных.
Множество всех линейных булевых функций
обозначим символом L.
Определение. Булева функция f ( x1 ,..., xn ) называется
f
(
x
,...,
x
)
f
(
x
,...,
x
)
самодвойственной, если
.
1
n
1
n
Множество всех самодвойственных булевых функций
обозначим символом S.
Определение. Булева функция f ( x1 ,..., xn ) называется
монотонной, если для любых x1 ,..., xn , y1 ,..., yn 0,1 из
x1 y1 ,..., xn yn следует f ( x1 ,..., xn ) f ( y1 ,..., yn ) .
Множество всех монотонных
обозначим символом M.
булевых
функций
11.
Пусть P0 - класс всех булевых функций f ( x1 ,..., xn ) ,удовлетворяющих условию f (0,...,0) 0 .
Пусть P1 - класс всех булевых функций f ( x1,..., xn ) ,
удовлетворяющих условию f (1,...,1) 1.
Определение. Классы булевых функций L,S,M,P0,P1
называются классами Поста.
Теорема Поста. Система булевых функций в том и
только том случае является полной, если она не
содержится ни в одном из классов Поста.
12.
13.
Пример.Рассмотрим систему F | , состоящую из одной
булевой функции | – штрих Шеффера. Составляем
таблицу, столбцы которой помечены классами
Поста L,S,M,P0,P1 и одна строка – функцией |.
Функция
|
Классы Поста
L
S
M
P0
P1
Нет
Нет
Нет
Нет
Нет
14.
Так как 0 | 0 1 и 1 | 1 0 , то функция | непринадлежит классам P0,P1.
В силу свойств 1 | 0 (0 | 1) , 0 | 0 1 | 1 функция | не
принадлежит классам S,M.
x | y xy 1 xy
Из равенств
следует, что
функция | не принадлежит классу L.
Таким образом, по теореме Поста система
функций F | является полной.
15.
Переключательные схемы16.
Рассматриваютсяэлектрические
ПС,
представляющие собой соединенные проводниками
переключатели и источники тока.
Условимся обозначать символом 1 протекание
тока в проводниках и символом 0 – отсутствие тока
в проводниках.
P2
P1
P3
A
B
P4
P5
17.
Переключатель - электромагнитное реле сконтактами и индукционной катушкой, состояние
которой моделируется булевой переменной x: x=1 - в
катушке идет ток, и x=0 - в катушке тока нет.
Контакты реле – замыкающие или размыкающие.
Через замыкающий контакт реле ток проходит в том
и только том случае, если x=1 - такой контакт
моделируется булевой переменной x.
Через размыкающий контакт реле ток проходит в
том и только том случае, если x=0 - такой контакт
моделируется отрицанием булевой переменной x .
18.
Пример. Пусть в ПС на рис.1 переключателиP1 , P5 имеют общую катушку реле с током x1 и
переключатели P2 , P4 имеют общую катушку реле
с током x2 , причем
контакты P1 , P2 , P4 –
замыкающие и контакты P3 , P5 – размыкающие.
Тогда такая ПС с помощью булевых переменных
x1 , x2 , x3 изображается следующей диаграммой:
x2
x1
x3
x2
x1
19.
Переключатели p,q могут бытьпоследовательно или параллельно.
соединены
p
p
q
q
Рис.3
Рис.4
Через
последовательно
соединенные
переключатели p,q ток проходит в том и только том
случае, если p=q=1 такое соединение
моделируется булевым многочленом pq.
Через параллельно соединенные переключатели
p,q ток не проходит в том и только том случае, если
p=q=0 - такое соединение моделируется булевым
многочленом p+q.
20.
Врезультате
любая
электрическая
ПС
моделируется некоторым булевым многочленом p,
который принимает значение 1 в том и только том
случае, если в ПС идет ток.
Соответствующая такому многочлену p булева
функция p называется функцией проводимости ПС,
так как она показывает, при каких значениях
булевых переменных (т.е. переключателей данной
схемы) в ПС идет электрический ток.
С другой стороны, каждый булев многочлен
p p x1 ,..., xn
моделирует ПС с функцией
проводимости p : эта схема так конструируется из
переключателей x1 , x1 ,..., xn , xn , что в ней при
значениях x1 a1 ,..., xn an проходит ток в том и
только том случае, если p a1,..., an 1.