Учебное пособие для студентов педагогичес ких вузов. М. Карпов Е. В., 2016. 152 с

• Название: Учебное пособие для студентов педагогичес ких вузов. М. Карпов Е. В., 2016. 152 с
• Дата: 13.02.2022
• Размер: 3.75 Mb.
• Имя файла: 40958_629a8142b77ee5d90a57935e839147e7 2.pdf
• Тип: Учебное пособие; #360641
• страница: 3 из 7

Глава 2. Логические основы ЭВМ
§ 4. Элементы алгебры логики
При записи тех или иных логических выражений используется спе- циальный язык, который принят в математической логике. Основопо- ложником математической логики является великий немецкий матема- тик Готфрид Вильгельм Лейбниц (1646−1716). Он сделал попытку по- строить универсальный язык, с помощью которого споры между людьми можно было бы разрешать посредством вычислений. На заложенном
Лейбницем фундаменте в XIX веке ирландский математик Джордж Буль построил здание новой науки – алгебры логики (Булевой алгебры),

ко- торая в отличие от обычной алгебры оперирует не числами, а высказы- ваниями. Это система обозначений и правил, которая может применять- ся к всевозможным объектам от чисел и букв до предложений. Пользу- ясь этой системой, Дж. Буль мог закодировать высказывания – утвер- ждения, истинность или ложность которых требовалось доказать, – с помощью символов своего языка, а затем манипулировать ими подобно тому, как в математике манипулируют обычными числами. Продолжил эту работу американский логик Чарлз Сандерс Пирс (1867).
4.1.
Основные операции Булевой алгебры
В булевой алгебре используется двоичная переменная x , которая может принимать значения «0» или «1», т.е.:
x
=1, если x

0,
x =0, если x

1.
Основными операциями являются:
1) инверсия (логическое отрицание) – НЕ,
2) дизъюнкция (логическое сложение) – ИЛИ,
3) конъюнкция (логическое умножение) – И.
Логическую операцию, как и логическую функцию, можно задать с помощью условного обозначения, таблицы истинности, аналитически, а реализовать с помощью ключевой или электронной схемы.
4.1.1. Базовые логические функции
1. Логический элемент «НЕ» – отрицание или инверсия.
Операция «НЕ» выполняется над однойпеременной и ее результа- том является логическое значение противоположное исходному.

39
Значение функции y истинно в том случае, когда переменная x принимает значение «0».
Логическую функцию «НЕ» можно представить: а) аналитическим выражением:
x
y

; б) таблицей истинности:
x
y
0 1
1 0 в) условным обозначением:
X
Y
X
Y
Покажем простейшую схему реализации логического элемента
«НЕ» на ключах:
X
1 0
1 2. Логический элемент «ИЛИ» или дизъюнкция (

; +)
Значение функции y истинно в том случае, когда хотя бы одна пе- ременная
i
x
принимает значение «1».
Логическую функцию «ИЛИ» можно представить: а) аналитическим выражением:
2 1
2 1
x
x
x
x
y




; б) таблицей истинности:

40
2
x
1
x
y
0 0
0 0
1 1
1 0
1 1
1 1 в) условным обозначением:
1
X
1
X
2
Y
X
1
X
2
Y
Покажем простейшую схему реализации логического элемента
«ИЛИ» на ключах:
X
1
X
2 0
1 0
1 3. Логический элемент «И» или конъюнкция (

;

)
Значение функции y истинно только в том случае, когда все пере- менные
i
x
принимают значение «1».
Логическую функцию «И» можно представить: а) аналитическим выражением:
2 1
2 1
x
x
x
x
y




; б) таблицей истинности:
2
x
1
x
y
0 0
0

41 0
1 0
1 0
0 1
1 1 в) условным обозначением:
&
X
1
X
2
Y
X
1
X
2
Покажем простейшую схему реализации логического элемента «И» на ключах:
X
1
X
2 0
1 0
1
4.1.2. Универсальные логические функции
Универсальными логическими устройствами, с помощью которых можно реализовать любую логическую операцию, являются логические элементы «ИЛИ

НЕ» и «И

НЕ». Рассмотрим эти операции.
1. Логический элемент «ИЛИ

НЕ» – стрелка Пирса
Логическую функцию «ИЛИ−НЕ» можно представить: а) аналитическим выражением:
2 1
2 1
x
x
x
x
y




; б) таблицей истинности:
2
x
1
x
y
0 0
1 0
1 0
1 0
0 1
1 0

42 в) условным обозначением:
X
1
X
2
Y
1
X
1
X
2
Y
Покажем простейшую схему реализации логического элемента
«ИЛИ−НЕ» на ключах:
X
1 0
1
X
2 0
1 2. Логический элемент «И

НЕ» – штрих Шеффера
Логическую функцию «И−НЕ» можно представить: а) аналитическим выражением:
2 1
2 1
/ x
x
x
x
y



; б) таблицей истинности:
2
x
1
x
y
0 0
1 0
1 1
1 0
1 1
1 0 в) условным обозначением:
&
X
1
X
2
Y
X
1
X
2

43
Покажем простейшую схему реализации логического элемента
«И−НЕ» на ключах:
X
1 0
1
X
2 0
1
4.1.3. Логическая функция «ИСКЛЮЧАЮЩЕЕ ИЛИ»
Логический элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» – неравнознач- ность.
Эта операция дает возможность сравнить два одноразрядных дво- ичных числа и используется при построении арифметических устройств.
Логическую функцию «ИСКЛЮЧАЮЩЕЕ ИЛИ» можно предста- вить: а) аналитическим выражением:
2
1
2
2
2
1
x
x
x
x
x
x
y






; б) таблицей истинности:
2
x
1
x
y
0 0
0 0
1 1
1 0
1 1
1 0 в) условным обозначением:
X
1
X
2
Y
= 1
X
1
X
2
Y
Покажем простейшую схему реализации логического элемента
«ИСКЛЮЧАЮЩЕЕ ИЛИ» на ключах:

44
X
1 0
1
X
2 0
1
Операция «ИСКЛЮЧАЮЩЕЕ ИЛИ» широко используется при ре- ализации схем сравнения – сумматора, вычитателя и т.д.
4.2.
Тождества. Основные законы и соотношения Булевой
алгебры
4.2.1. Тождества
а)
1
x
x
1
1
x
x
x
x
x
0
x








б)
0
x
x
x
1
x
x
x
x
0
0
x








в)
x
x
y


– двойное отрицание

это есть отсутствие отрицания.
Докажем основные тождества с помощью таблицы истинности
x
x
0

x
x
x

1

x
x
x

0

x
x
x

1

x
x
x

x
0 1
0 0
1 1
0 0
0 0
0 1
0 1
1 1
1 0
1 1
0 1
Задача 1. Перепишите тождества для двух переменных.
Задача 2. Докажите тождество
2 1
2 1
1
x
x
x
x




,
используя таблицу истинности.
4.2.2. Принцип двойственности
2
1
2
1
x
x
y
x
x
y




2
1
2
1
x
x
y
x
x
y




Из сопоставления операций дизъюнкции («ИЛИ») и конъюнкции
(«И») можно выявить следующую закономерность: операции «И» и
«ИЛИ» можно поменять местами, если значения «1» поменять на «0 »,

45 значения «0» − на «1», а знак «

» − на знак «·» и наоборот. Это свой- ство называется принципом двойственности.
Проверим справедливость принципа двойственности с помощью приведенных ниже таблиц истинности.
«ИЛИ»
2
x
1
x
y
y
2
x
1
x
2
1
x
x

0 0
0 1
1 1
1 0
1 1
0 1
0 0
1 0
1 0
0 1
0 1
1 1
0 0
0 0
«И»
2
x
1
x
y
y
2
x
1
x
2
1
x
x

0 0
0 1
1 1
1 0
1 0
1 1
0 1
1 0
0 1
0 1
1 1
1 1
0 0
0 0
4.2.3. Законы и правила Булевой алгебры
В алгебре логики используют следующие законы и соотношения.
Законы:
а) Переместительный или коммутативный закон (устанавливает пе- рестановочность переменных в операции). Это правило справедливо благодаря тому, что таблица истинности симметрична, т.е.
1
x
и
2
x
мож- но поменять местами, получив при этом правильную таблицу истинно- сти. Запись закона
− для логического сложения
1
2
2
1
x
x
x
x



,
− для логического умножения
1
2
2
1
x
x
x
x



; б) Сочетательный или ассоциативный закон (переменные можно группировать в любом порядке как для операции «ИЛИ», так и для опе- рации «И»). В математике скобки показывают, над какими переменными производят действие в первую очередь. Это справедливо и для булевой алгебры. Запись закона
− для логического сложения


3
2
1
3
2
1
x
x
x
x
x
x





,
− для логического умножения


3
2
1
3
2
1
x
x
x
x
x
x





;

46 в) Распределительный или дистрибутивный закон (допускает выне- сение общего множителя за скобки). Запись закона
− для логического сложения


3
1
2
1
3
2
1
x
x
x
x
x
x
x






,
− для логического умножения


)
x
x
(
)
x
x
(
x
x
x
3
1
2
1
3
2
1






; г) закон общей инверсии (правила де Моргана) (справедливость этого закона вытекает непосредственно из принципа двойственности)
− для логического сложения (дополнение суммы равно произ- ведению дополнений)
2
1
2
1
x
x
x
x



,
− для логического умножения (дополнение произведения рав- но сумме дополнений)
2
1
2
1
x
x
x
x



Доказательство. Может быть предложено следующее доказатель- ство закона общей инверсии. Пусть
1 1

x
и
1 2

x
, тогда
1 2
1


x
x
, а
0 2
1


x
x
, и, следовательно,
0 2
1


x
x
. Тогда верно выражение
2 1
2 1
x
x
x
x



. Если
0 1

x
и
0 2

x
, то
0
x
x
2
1


,
1
x
x
2
1


, а
1
x
x
2
1


. И верно выражение
2 1
2 1
x
x
x
x



. Что и требовалось дока- зать.
Более простое доказательство этого закона может быть сделано с помощью таблицы истинности для двух переменных
2
x
1
x
2 1
x
x

2 1
x
x

2
1
x
x

2 1
x
x

0 0
0 0
1 1
0 1
1 0
1 1
1 0
1 0
1 1
1 1
1 1
0 0
Задача 3. Докажите тождество
𝑥
1
+ 𝑥̅
1
𝑥
2
= 𝑥
1
+ 𝑥
2
Задача 4. Докажите теорему де Моргана для трех переменных
3 2
1 3
2 1
x
x
x
x
x
x





Правила:
д) правило поглощения
─ для логического сложения
1
2
1
1
x
x
x
x



,
─ для логического умножения


1
2
1
1
x
x
x
x



е) правило склеивания
─ для логического сложения
2
2
1
2
1
x
x
x
x
x




─ для логического умножения

 

2
2
1
2
1
x
x
x
x
x





47
Примеры
1)

 
 
 

3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
y












3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
y












3
1
2
1
x
x
x
x
y





 

3
1
2
1
x
x
x
x
y




2) Покажем, что справедливость закона де Моргана непосредствен- но вытекает из принципа двойственности: а)
2
1
2
1
x
x
y
x
x
y





2
1
x
x
y


б)
2
1
2
1
x
x
y
x
x
y





2
1
x
x
y


Задача 5. Используя тождества и законы булевой алгебры, докажи- те свойства функции «ИСКЛЮЧАЮЩЕЕ ИЛИ»: а)
1
2
2
1
x
x
x
x



б)
3
2
1
3
1
2
3
2
1
x
x
x
x
)
x
x
(
)
x
x
(
x








в) дистрибутивность относительно операции конъюнкции
3
1
1
2
3
2
1
x
x
x
x
)
x
x
(
x




г)
)
x
x
(
)
x
x
(
x
x
x
x
x
x
2
1
2
1
2
1
2
1
2
1







д)
1
1
x
0
x


1
1
x
1
x


0
x
x
1
1


1
x
x
1
1


е) «ИСКЛЮЧАЮЩЕЕ ИЛИ

НЕ» (равнозначность)



2
1
2
1
2
1
2
1
2
1
2
1
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y













Задача 6. Рассмотрите реализацию основных логических элементов на универсальном элементе: а) «И

НЕ», б) «ИЛИ

НЕ».
Решение
а) «И

НЕ»
&
X
1
X
2
Y

48 1) «НЕ»
x
y

НЕ
X
Y = X
&
2) «И»
2
1
x
x
y


X
1
X
2
&
&
Y
3) «ИЛИ»
2
1
x
x
y


2
1
2
1
2
1
x
x
x
x
x
x
y






Y
X
1
X
2
&
&
&
4) «ИСКЛЮЧАЮЩЕЕ ИЛИ»
2
1
2
1
x
x
x
x
y




Используя данную функцию и схемы пп. 2) и 3), построим «ИС-
КЛЮЧАЮЩЕЕ ИЛИ» на элементах «И−НЕ».

49
&
&
&
&
&
&
X
1
X
2
&
&
&
   
2 1
2 1
1 2
2 1
2 1
2 1
x
x
x
x
x
x
x
x
x
x
x
x
y












В результате получаем следующую схему.
&
&
X
1
X
2
&
&
&
Задача 7. Докажите, что приведенная схема эквивалентна рассмот- ренной выше.
&
X
1
X
2
&
&
&
0 1
1

50 б) «ИЛИ

НЕ»
1) «НЕ»
x
y

X
Y = X
1 2) «И»
2
1
x
x
y


Y
1 1
1
X
1
X
2 3) «ИЛИ»
2
1
x
x
y


2
1
2
1
2
1
x
x
x
x
x
x
y






1 1
X
1
X
2 4) «ИСКЛЮЧАЮЩЕЕ ИЛИ»
2
1
2
1
x
x
x
x
y





51
X
1
X
2
y
1 1
1 1
1
Задача 8. Докажите, что схема п. 4, выполняет операцию «ИС-
КЛЮЧАЮЩЕЕ ИЛИ».

52
4.3
. Составление логической функции по таблице
истинности
Введем ряд понятий:
1) элементарная конъюнкция

минтерм принимает единичные значения только при одном из всех возможных наборов входных пере- менных
)
x
x
(
)
x
x
x
(
)
x
x
x
(
y
3
1
3
2
1
3
2
1








;
2) элементарная дизъюнкция

макстерм принимает нулевые зна- чения только при одном из всех возможных наборов входных перемен- ных

 
 

3
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
y








;
3) если логическая функция представлена дизъюнкцией, конъюнк- цией, инверсией, то такая форма представления называется нормальной.
4) дизъюнктивная нормальная форма

это сумма минтермов
3 2
1 2
1
x
x
x
x
x
минтермов
y







;
5) конъюнктивная нормальная форма

это произведение макстер- мов

 

3 2
1 2
1
x
x
x
x
x
макстермов
y







;
6) совершенная дизъюнктивная нормальная форма (СДНФ)

нет двух одинаковых элементарных конъюнкций;

элементарная конъюнкция не содержит двух одинаковых пере- менных;

элементарная конъюнкция не содержит переменную вместе с ее инверсией;

все элементарные конъюнкции имеют один и тот же ранг.
3 2
1 3
2 1
3 2
1 3
2 1
3 3
2 1
3 2
1 2
1
)
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y






















;
7) совершенная конъюнктивная нормальная форма (СКНФ)

нет двух одинаковых элементарных дизъюнкций;

элементарная дизъюнкция не содержит двух одинаковых пере- менных;

элементарная дизъюнкция не содержит переменную вместе с ее инверсией;

все элементарные дизъюнкции имеют один и тот же ранг.
В алгебре логики строго доказывается, что любая логическая функ- ция, кроме функции тождественно равной нулю, может быть представ-

53 лена в СДНФ, и любая логическая функция, кроме функции тожде- ственно равной единице, может быть представлена в СКНФ.
Составим логическую функцию по таблице истинности.
Пусть таблицей истинности задана некоторая логическая функция.
3
x
2
x
1
x
y
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
*
Запишем эту функцию в совершенной дизъюнктивной нормальной форме (СДНФ) и совершенной конъюнктивной нормальной форме
(СКНФ). а) СДНФ (*)
3
2
3
2
3
2
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y
















б) СКНФ (+)
)
x
x
x
(
)
x
x
x
(
)
x
x
x
(
)
x
x
x
(
y
3
2
1
3
2
1
3
2
1
3
2
1












)
x
x
x
(
)
x
x
x
(
)
x
x
x
(
)
x
x
x
(
y
3
2
1
3
2
1
3
2
1
3
2
1












3
2
3
2
3
2
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y








3
2
x
x
y




54