Лекция № 4.
Тема: логические основы ЭВМ
В вычислительных машинах коды нуля и единицы представляются электрическими сигналами, имеющими два различных состояния. Наиболее распространенными способами физического представления информации являются импульсный и потенциальный:
импульс или его отсутствие;
высокий или низкий потенциал;
высокий потенциал или его отсутствие.
При импульсном способе отображения код единицы идентифицируется наличием электрического импульса, код нуля — его отсутствием (впрочем, может быть и наоборот). Импульс характеризуется амплитудой и длительностью, причем длительность должна быть меньше временного такта машины.
При потенциальном способе отображения код единицы — это высокий уровень напряжения, а код нуля — отсутствие сигнала или низкий его уровень. Уровень напряжения не меняется в течение всего такта работы машины. Форма и амплитуда сигнала при этом во внимание не принимаются, а фиксируется лишь сам факт наличия или отсутствия потенциала.
Вышесказанное обусловило то, что для анализа и синтеза схем в компьютере при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики, оперирующий также с двумя понятиями «истина» или «ложь».
Элементы алгебры логики
Алгебра логики — это раздел математической логики, значение всех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.
Высказывание — это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, то есть каждое высказывание или истинно, или ложно, и не может быть одновременно и истинным и ложным.
Высказывания:
«Сейчас идет снег» — это утверждение может быть истинным или ложным;
«Вашингтон — столица США» — истинное утверждение;
«Частное от деления 10 на 2 равно 3» — ложное утверждение.
В алгебре логики все высказывания обозначают буквами а, b, с и т. д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.
Простейшими операциями в алгебре логики являются операции логического сложения (иначе: операция ИЛИ (OR), операция дизъюнкции) и логического умножения (иначе: операция И (AND), операция конъюнкции). Для обозначения операции логического сложения используют символы + или V, а логического умножения — символы • или /\. Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий. В частности, для алгебры логики применимы следующие законы.
1. Сочетательный:
(а + b) + с = а + (b + с),
(а ∙ b) ∙ с = а ∙ (b ∙ с).
2. Переместительный:
(а + b) = (b + а),
(а∙ b) = ( b ∙ а).
3. Распределительный:
а ∙ (b + с) = а ∙ b + a ∙ с,
(а + b) ∙ с = а ∙ с + b ∙ с.
Справедливы соотношения, в частности:
а + а = а, а + b = b, если а ≤ b,
а ∙ а = а, a ∙ b = а, если а ≤ b,
а + a ∙ b = a, a ∙ b = b, если а ≥ b,
а + b = а, если а ≥ b,
а + b = b, если а ≤ b.
Наименьшим элементом алгебры логики является 0, наибольшим элементом — 1. В алгебре логики также вводится еще одна операция — отрицания (операция НЕ, инверсия), обозначаемая чертой над элементом.
П о определению:
Справедливы, например, такие соотношения:
Функция в алгебре логики — выражение, содержащее элементы алгебры логики а, b, с и др., связанные операциями, определенными в этой алгебре.
Примеры логических функций:
Для любой операции, определенной в алгебре логики существуют таблицы истинности – таблицы, в которых приведены значения операции в зависимости от значений высказываний над которыми выполняется данная операция.
Поскольку таблица истинности для конъюнкции совпадает с таблицей умножения, если истинному высказыванию приписать значение '1', а ложному - '0', то сложное высказывание можно назвать произведением.
X1
|
X2
|
f1(X1,X2)
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
Функция конъюнкции истинна тогда, когда истинны одновременно оба высказывания.
Дизъюнкция
Это сложное высказывание истинно тогда, когда истинно хотя бы одно высказывание, входящее в него.
X1
|
X2
|
f1(X1,X2)
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
Читается X1 ИЛИ X2: часто это высказывание называют логическим сложением.
Логическая равнозначность
Это сложное высказывание истинно тогда, когда истинны или ложны одновременно оба высказывания.
Отсюда следует, что вне зависимости от смысла, равнозначными являются как истинные, так и ложные высказывания.
Например,
А=<дважды два - пять>
B=<один плюс два - шесть>
А~В равнозначны.
Импликация
Это сложное высказывание ложно только тогда, когда X1 – истинно, а X2 – ложно.
X1
|
X2
|
f1(X1,X2)
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
Читается: если X1, то X2. При этом X1 – посылка, X2 – следствие.
Из ложной посылки может следовать ложное следствие и это можно считать верным: <если Киев – столица Франции>, то <2-квадрат 3>.
Эквивалентности
В некоторых случаях сложное и длинное высказывание можно записать более коротким и простым без нарушения истинности исходного высказывания. Это можно выполнить с использованием некоторых эквивалентных соотношений.
Дизъюнкция:
х  х х х ... х х х= х ,
т.е. истинность высказывания не изменится, если его заменить более коротким, таким образом, это правило приведения подобных членов:
– постоянно истинное высказывание.
0 x = x
x1 x2 = x2 x1
- (переместительный) коммуникативный закон.
x1 х2 х3 = (x1 х2) х3 = x1 (х2 х3)
- сочетательный закон.
Конъюнкция:
х  х х х... х х х= х
правило приведения подобных членов:
1 x = х
0 x = 0 - постоянно ложное высказывание
x x = 0 - постоянно ложное высказывание
Сложение по mod 2
1  х = x
0 x = x
x x = 1
x x x ... x = х – при нечетном числе членов, 0 - при четном числе членов
Правило де Моргана
x1 x2 ... xn = x1 & x2& ... & xn
x1 x2 ... xn = x1 & x2 & ... & xn
Докажем для двух переменных с помощью таблицы истинности:
Х1
|
Х2
|
Х1 Х2
|
X1 & X2
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
Операция поглощения:
Х XY = X или в общем виде X X*f(X,Y,Z...) = X;
Операция полного склеивания:
XY XY = X (по Y)
XY XY = Y (по Х)
Операция неполного склеивания:
XY XY = Х XY XY
|
