1 Множества. Логика Буля - лекции
.pdfЗамечание. По аналогии с этим доказательством «докажем» закон поглощения
(x y) y y .
Обе части тождества «умножим» справа на скобку x y : ((x y) y) (x y) y (x y) .
Используя коммутативность конъюнкции и закон идемпотентности, получаем равенство:
y (x y) y (x y) .
Однако такое доказательство ошибочно, так как произвольное «умножение» в логике недопустимо. Возможно только такое «умножение»
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и «сложение», которое отвечает законам нуля и единицы, то есть x |
|
x 0 , |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x x 1. |
|
|
|
|
|
|
|
|
||||||
|
|
Возьмѐм, например, ложное равенство: |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x y) (x z) (x z) (x y) (x z) . |
|
|
|
|||||||||
|
|
Воспользуемся законом поглощения в виде: |
|
|
|
|||||||||
|
|
|
|
|
|
x |
(x z) x . |
|
|
|
||||
|
|
«Сложив» его с исходным выражением, получим: |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
x , |
||||||
|
|
(x y) (x z) (x z) |
x (x y) (x z) (x z) |
что должно доказывать справедливость исходного выражения. Однако с помощью таблиц истинности (табл. 5) легко установить, что это не так. Истинным равенством является:
(x y) (x z) ( y z) (x y) (x z) .
|
|
|
|
|
|
|
|
|
|
Табл. 5 |
|
|
|
|
|
|
|
|
|
|
|
x |
y |
z |
f1 x y |
f2 x z |
f3 x z |
fR f1 |
f2 |
f L f1 f2 f3 |
||
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
|
0 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
|
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
◄ |
25
ЛЕКЦИЯ 4. КОММУТАЦИОННЫЕ СХЕМЫ
В 1938 году Клод Шеннон10 заметил связь между электрическими цепями и таблицами истинности.
Рассмотрим схему переключения на рис. 1, состоящую из источника питания (рис. 2) и электрической лампочки (рис. 3).
p |
q |
|
| |
| |
|
+ |
+ |
|
Рис. 1 |
Рис. 2 |
Рис. 3 |
Присвоим значение 1 переключателям p и q , если они замкнуты (то
есть через них проходит электрический ток). В противоположной ситуации присвоим им значение 0. Присвоим схеме значение 1, когда лампа светится (через неѐ проходит электрический ток). Заметим, что при последовательном соединении элементов цепи p и q (как на рис. 1) лампочка загорается
только в случае, когда оба переключателя замкнуты, то есть схема имеет значение 1, если оба переключателя имеют значение 1. Таким образом, схема на рис. 1 соответствует конъюнкции p q и называется логическим
элементом p и q (схемой логического умножения). Этот логический элемент обозначается символом, показанным на рис. 4.
p
р и q
q
Рис. 4
10 Клод Элвуд Шеннон (1916 – 2001, США) – американский инженер и математик, его работы есть синтез математических идей с конкретным анализом сложных проблем их технической реализации. Основатель теории информации. Внѐс огромный вклад в теорию вероятностных схем, теорию автоматов, теорию систем управления области наук, входящих в кибернетику.
26
Рассмотрим схему параллельного соединения переключателей p и q
(рис. 5).
p
|
q
+
Рис. 5
Теперь лампочка загорается, а значение схемы равно 1, когда один из двух переключателей замкнут или в случае, когда оба переключателя замкнуты, то есть когда переключатели имеют наборы значений 10, 01, 11. Эта схема соответствует дизъюнкции p q и называется логическим эле-
ментом p или q (схемой логического сложения). Логический элемент p или q обозначается символом, показанным на рис. 6.
p |
р или q |
|
|
q |
|
Рис. 6
Схема, состоящая из одного переключателя p такого, что лампа горит, когда он разомкнут и не горит, когда он замкнут, соответствует отри-
цанию p и называется логическим элементом не или инвертором (рис. 7).
p |
не р |
|
Рис. 7 |
►Пример. Схема на рис. 8 содержит логический элемент p и q , за которым следует инвертор так, что схема соответствует выражению p q . Инвертор отрицает всю предшествующую ему схему.
27
p q
Рис. 8
◄
►Пример. Схема на рис. 9 содержит соединение логического элемента p или q с логическим элементом не r посредством логической схе-
мы умножения. Значит, схеме соответствует выражение ( p q) r .
p q
r
Рис. 9
◄
►Пример. Булево выражение, соответствующее схеме на рис. 10, имеет вид ( p q) ( p r) .
p q
r
Рис. 10
◄
►Пример. Булево выражение, соответствующее схеме на рис. 11, имеет вид ( p q) r .
p q
r
Рис. 11 |
◄ |
|
28
►Пример. Булево выражение, соответствующее схеме на рис. 12,
имеет вид (( p q) ( p r)) r .
p q
r
Рис. 12
◄
►Пример. Построим схему трѐхклавишного переключателя, при помощи которого свет включается тремя различными двухпозиционными переключателями. Рассмотрим сначала соответствующее булево выражение. Свет должен включаться, когда все три переключателя замкнуты, то есть нужно иметь p q r . Если один из переключателей разомкнут, то
свет должен быть выключен. Но если разомкнуть другой переключатель, то свет должен включиться. Следовательно, искомое выражение имеет вид:
( p q r) ( p q r) ( p q r) ( p q r) .
Для простоты вместо схемы на рис. 13 для выражения p q r будем использовать схему, представленную на рис. 14.
p |
p |
|
q |
||
q |
||
|
||
r |
r |
|
|
Рис. 13 Рис. 14
А для выражения p q |
r вместо схемы на рис. 15 будем использо- |
|
вать схему, представленную на рис. 16. |
||
p |
p |
|
q |
||
q |
||
|
||
r |
r |
|
|
||
Рис. 15 |
Рис. 16 |
|
29 |
|
Тогда искомая схема имеет вид, показанный на рис. 17.
p q
r
Рис. 17
◄
Из определения функции штрих Шеффера следует, что p | q p q . Поэтому штрих Шеффера называется логическим элементом «не и». Из определения функции стрелка Пирса следует, что p q p q . Поэтому
стрелка Пирса называется логическим элементом «не или». Логические элементы «не и» и «не или» обозначаются символами, изображѐнными на рис. 18, 19 соответственно.
p |
|
|
p |
q |
|
q |
|
Рис. 18 |
|
Рис. 19 |
|
Выражению ( p | q) |
(r | s) соответствует схема, построенная на рис. |
20.
30
p q
r s
Рис. 20
►Пример. Полусумматор находит сумму двух двоичных чисел 1 и 0 согласно таблице сложения
0 1
0 0 1
1 1 10
Своѐ название полусумматор получил в связи с тем, что при сложении двоичных чисел с более чем одним разрядом суммируются только низшие разряды, поскольку нет возможности учесть в сумме число, которое «переносится». Для удобства суммирования одноразрядных двоичных чисел таблица, приведѐнная выше, преобразована к виду
|
|
1 |
|
|
0 |
|
|
|
|
|
|
0 |
00 |
01 |
|
1 |
01 |
10 |
Пусть p и q означают числа, которые нужно сложить, а d1 и d0 –
первый и второй разряд суммы, тогда получим следующие таблицы истинности:
|
случай |
p |
|
q |
|
d0 |
|
d1 |
|||||||||||||
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
0 |
0 |
|
|
0 |
|
0 |
|
|
|
|
||||||
|
2 |
|
|
|
0 |
1 |
|
|
1 |
|
0 |
|
|
|
|
||||||
|
3 |
|
|
|
1 |
0 |
|
|
1 |
|
0 |
|
|
|
|
||||||
|
4 |
|
|
|
1 |
1 |
|
|
0 |
|
1 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Следовательно, d0 ( p q) ( p |
|
q) |
|
( p |
|
q) ( p q) , d1 p q . |
|||||||||||||||
Коммутационная |
|
|
p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
схема для полусуммато- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ра приведена на рис. 21. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 21
31
Поскольку полусумматор даѐт сумму двух чисел, он обозначается символом, показанным на рис. 22.
p |
|
d0 |
|
+ |
|||
q |
d1 |
||
|
|||
|
Рис. 22 |
|
|
|
|
◄ |
►Пример. Полный сумматор складывает три одноразрядных двоичных числа. Следовательно, он может сложить два двоичных числа с тем, которое «переносится». Пока это необходимо рассматривать как сложение трѐх одноразрядных двоичных чисел. Если предположить, что p , q и r
обозначают числа, которые нужно сложить, а d1 |
|
и d0 – первый и второй |
|||||||
разряды их суммы, то получим следующие таблицы истинности |
|||||||||
случай |
p |
q |
r |
|
d1 |
|
d0 |
||
|
|
||||||||
|
1 |
0 |
0 |
0 |
|
0 |
|
0 |
|
2 |
0 |
0 |
1 |
|
0 |
|
1 |
|
|
3 |
0 |
1 |
0 |
|
0 |
|
1 |
|
|
4 |
0 |
1 |
1 |
|
1 |
|
0 |
|
|
5 |
1 |
0 |
0 |
|
0 |
|
1 |
|
|
6 |
1 |
0 |
1 |
|
1 |
|
0 |
|
|
7 |
1 |
1 |
0 |
|
1 |
|
0 |
|
|
8 |
1 |
1 |
1 |
|
1 |
|
1 |
|
d0 – результат сложения d0 с r , где d0 – второй разряд суммы p и
q . Следовательно, его схему легко описать. Значение d1 проще получить с помощью полученной таблицы истинности
d1 ( p q r) ( p q r) ( p q r) ( p q r)
( p q) ( p r) (q r) ( p q) (( p q) r).
Соответствующая схема изображена на рис. 23.
32
4
10
p |
|
d0 |
|
d0 |
q |
+ |
|
+ |
|
|
|
|||
|
|
d1 |
|
|
|
|
|
|
d1 |
r
Рис. 23
Самостоятельно постройте подробную схему, соответствующую рис.
23. ◄
Поскольку полный сумматор складывает три числа, его обозначение имеет вид, показанный на рис. 24.
r |
p |
|
|
d0 |
|
+ |
+ |
||||
|
|
||||
|
q |
d1 |
|||
|
|
|
Рис. 24
33
ЛЕКЦИЯ 5. ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ ДВУХ ПЕРЕМЕННЫХ
Формы представления булевых функций двух переменных. Любую булеву функцию двух переменных y f (x1 , x2 ) можно представить некоторой комбинацией областей (смотри лекцию 1)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C0 x1 x2 , |
C1 |
x1 |
|
x2 , |
C2 x1 |
x2 , C3 |
x1 x2 . |
||||||||||||
Например, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
x2 ) , |
||||||||
f7 (x1 , x2 ) |
x1 |
x2 |
C1 |
C2 |
(x1 |
|
x2 ) (x1 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
f5 (x1 , x2 ) |
x1 \ x2 |
C1 |
x1 x2 . |
|
|||||||||||
Наличие той или иной области Ci , |
i |
0, 1, 2,3 (они называются «кон- |
ституентами») в представлении функции y f (x1 , x2 ) зависит от значения функции:
|
|
|
|
|
|
|
|
|
|
y (x1 x2 f (0,0)) (x1 |
|
x2 |
f (1,0)) (x1 x2 f (0,1)) |
||||||
|
|
|
|
(x1 |
x2 |
f (1,1)) . |
Такая форма представления булевой функции называется совершен-
ной дизъюнктивной нормальной формой (СДНФ).
В логике Буля действует принцип двойственности: при замене символов « » на « » и «1» на «0» все логические равенства остаются в силе (смотри, например, лекцию 2 пункт «Свойства операций над множествами, свойства булевых функций»). Поэтому СДНФ можно записать следующим образом:
|
|
|
|
|
|
|
|
|
|
y (x1 x2 f (1,1)) (x1 |
|
x2 |
f (0,1)) (x1 x2 f (1,0)) |
||||||
|
|
|
|
(x1 |
x2 |
f (0,0)) . |
Эта форма представления булевой функции называется совершенной конъюнктивной нормальной формой (СКНФ). Здесь конституенты пред-
ставлены не в виде конъюнктов, а в виде дизъюнктов, соединѐнных конъюнкцией (отсюда и соответствующее название).
СДНФ (СКНФ) обладает следующими свойствами:
1.Не содержит двух одинаковых конъюнкций (дизъюнкций).
2.Ни одна конъюнкция (дизъюнкция) не содержит двух одинаковых переменных.
3.Ни одна конъюнкция (дизъюнкция) не содержит некоторую переменную и еѐ отрицание.
4.Каждая конъюнкция (дизъюнкция) содержит либо переменную
xi , либо еѐ отрицание xi для всех переменных, входящих в формулу.
34