1 Множества. Логика Буля - лекции

Замечание. По аналогии с этим доказательством «докажем» закон поглощения

(x y) y y .

Обе части тождества «умножим» справа на скобку x y : ((x y) y) (x y) y (x y) .

Используя коммутативность конъюнкции и закон идемпотентности, получаем равенство:

y (x y) y (x y) .

Однако такое доказательство ошибочно, так как произвольное «умножение» в логике недопустимо. Возможно только такое «умножение»

что должно доказывать справедливость исходного выражения. Однако с помощью таблиц истинности (табл. 5) легко установить, что это не так. Истинным равенством является:

(x y) (x z) ( y z) (x y) (x z) .

25

ЛЕКЦИЯ 4. КОММУТАЦИОННЫЕ СХЕМЫ

В 1938 году Клод Шеннон10 заметил связь между электрическими цепями и таблицами истинности.

Рассмотрим схему переключения на рис. 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.

Рис. 6

Схема, состоящая из одного переключателя p такого, что лампа горит, когда он разомкнут и не горит, когда он замкнут, соответствует отри-

цанию 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

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.

Рис. 13 Рис. 14

Тогда искомая схема имеет вид, показанный на рис. 17.

p q

r

Рис. 17

◄

Из определения функции штрих Шеффера следует, что p | q p q . Поэтому штрих Шеффера называется логическим элементом «не и». Из определения функции стрелка Пирса следует, что p q p q . Поэтому

стрелка Пирса называется логическим элементом «не или». Логические элементы «не и» и «не или» обозначаются символами, изображѐнными на рис. 18, 19 соответственно.

20.

30

p q

r s

Рис. 20

►Пример. Полусумматор находит сумму двух двоичных чисел 1 и 0 согласно таблице сложения

0 1

0 0 1

1 1 10

Своѐ название полусумматор получил в связи с тем, что при сложении двоичных чисел с более чем одним разрядом суммируются только низшие разряды, поскольку нет возможности учесть в сумме число, которое «переносится». Для удобства суммирования одноразрядных двоичных чисел таблица, приведѐнная выше, преобразована к виду

Пусть p и q означают числа, которые нужно сложить, а d1 и d0 –

первый и второй разряд суммы, тогда получим следующие таблицы истинности:

Рис. 21

31

Поскольку полусумматор даѐт сумму двух чисел, он обозначается символом, показанным на рис. 22.

►Пример. Полный сумматор складывает три одноразрядных двоичных числа. Следовательно, он может сложить два двоичных числа с тем, которое «переносится». Пока это необходимо рассматривать как сложение трѐх одноразрядных двоичных чисел. Если предположить, что p , q и r

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

r

Рис. 23

Самостоятельно постройте подробную схему, соответствующую рис.

23. ◄

Поскольку полный сумматор складывает три числа, его обозначение имеет вид, показанный на рис. 24.

Рис. 24

33

ЛЕКЦИЯ 5. ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ ДВУХ ПЕРЕМЕННЫХ

Формы представления булевых функций двух переменных. Любую булеву функцию двух переменных y f (x1 , x2 ) можно представить некоторой комбинацией областей (смотри лекцию 1)

ституентами») в представлении функции y f (x1 , x2 ) зависит от значения функции:

Такая форма представления булевой функции называется совершен-

ной дизъюнктивной нормальной формой (СДНФ).

В логике Буля действует принцип двойственности: при замене символов « » на « » и «1» на «0» все логические равенства остаются в силе (смотри, например, лекцию 2 пункт «Свойства операций над множествами, свойства булевых функций»). Поэтому СДНФ можно записать следующим образом:

Эта форма представления булевой функции называется совершенной конъюнктивной нормальной формой (СКНФ). Здесь конституенты пред-

ставлены не в виде конъюнктов, а в виде дизъюнктов, соединѐнных конъюнкцией (отсюда и соответствующее название).

СДНФ (СКНФ) обладает следующими свойствами:

1.Не содержит двух одинаковых конъюнкций (дизъюнкций).

2.Ни одна конъюнкция (дизъюнкция) не содержит двух одинаковых переменных.

3.Ни одна конъюнкция (дизъюнкция) не содержит некоторую переменную и еѐ отрицание.

4.Каждая конъюнкция (дизъюнкция) содержит либо переменную

xi , либо еѐ отрицание xi для всех переменных, входящих в формулу.

34