ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ПК

Основы алгебры логики

Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.

Алгебра логики — это раздел математической логики, значения всех эле­ментов (функций и аргументов) которой определены в двухэлементном множестве: «Истина» и «Ложь» или “True” и “False” или 1 и 0. Алгебра логики оперирует с логическими высказыва­ниями.

Высказывание — это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каж­дое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.

Например, высказывания: "Сейчас идет снег" — это утверждение может быть ис­тинным или ложным; "Вашингтон — столица США" — истинное утверждение; "Частное от деления 10 на 2 равно 3" — ложное утверждение.

В алгебре логики все высказывания обозначают буквами а, b, с и т.д. Содержание вы­сказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре ло­гики операции, то результаты операций также будут элементами этой алгебры.

Простейшими операциями в алгебре логики являются операции логического ум­ножения (иначе, операция AND (И), операция конъюнкции) и логического сложения (иначе, операция OR (ИЛИ), операция дизъюнкции). Для обозначения операции логического умножения — символы * или & или Ù, а ло­гического сложения используют символы + или ! или Ú.

Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий.

В частности, для алгебры логики выполняются законы:

1) сочетательный:

(а + b) + с = а + (b + с);

(а * b) * с = а * (b * с);

2) переместительный:

а + b = b + а;

а * b = b * а;

3) распределительный:

а * (b + с) = а * b + а * с;

а + b * с = а * b + а * с.

Справедливы соотношения:

а + а = а; а + b = b, если а £ b;
а * а = а; а* b=а, если о £ b;
а + а * b = а; а + b = b, если а ³ b
а + b = а, если а ³ b; и др.

 

Наибольшим элементом алгебры логики является 1, наименьшим — 0.

В алгебре логики также вводится еще одна операция — операция отрицания (иначе, операция NOT (НЕ), операция инверсии), обозначаемая чертой над элементом.

По определению: , , , .

Справедливы, например, такие соотношения: , ,

Функция в алгебре логики — это алгебраическое выражение, содержащее элемен­ты алгебры логики а, b, с ..., связанные между собой операциями, определенными в этой алгебре.

Операции сравнения

Операции отношения производят сравнение двух величин. Резуль­тат сравнения может быть либо истинным, либо ложным.

В табл. 6 перечислены шесть знаков операций сравнения. Сравнение двух ве­личин дает в результате одно из Булевых значений: либо Тгие, либо False. В языках программирования высокого уровня предусмотрены две константы Тгие и False, значения которых соответству­ют -1 и 0. В двоичном представлении — число, в котором все биты обнулены, а -1 — двоичное число, все 16 бит которого установлены (равны 1). Таким образом, значение Тгие противоположно значению False.

Таблица 6

Знак Операция сравнения  
> больше  
< меньше  
>= больше или равно  
<= меньше или равно  
= равно  
<> не равно
       

 

Кстати, операции сравнения называют еще операциями отношения (relation operations), пос­кольку в них осуществляется оценка взаимосвязи (отношений) двух операндов. Приоритет операций сравнения ниже, чем арифметических операций.

 

Логические операции

Логические операторы иногда называют Булевыми операторами, так как взяты из алгебры, применяемой в математической логике и разработанной Джорджем Булем. Операндами в них выступают Булевы величины и возвращают они тоже Булевы значения. В табл. 7 логические операторы приведены в порядке при­оритета. (Их приоритет ниже, чем у операций сравнения.)

 

Таблица 7

Оператор Название

NOT логическое отрицание "НЕ"

AND логическое "И"

OR логическое "ИЛИ"

XOR исключающее "ИЛИ"

EQV логическая эквивалентность

IMP логическая импликация

Простейший логический оператор — NOT. Он предшествует единственному опе­ранду и возвращает его логическую противоположность — иначе говоря, "отри­цает" операнд. Например, выражение NOT False дает в результате Тгие (Булево значение, обратное False); а выражение NOT (4 < 3) — Тгие, так как утверждение, что 4 < 3 ложно. Кроме того, этот оператор обладает наивысшим приоритетом по сравнению с остальными Булевыми операторами.

Следующий (в порядке убывания приоритета) оператор — AND. Он возвращает True , только если оба операнда имеют значение True. По смыслу он соответствует английскому слову and (русскому и), что можно проиллюстрировать, например, таким утвер­ждением: "Он получит эту должность, только если знает английский и разбира­ется в компьютерах".

Оператор OR возвращает Тгие, если любой из двух операндов Тгие или если оба True. И в этом случае логический смысл оператора совпадает с соответствую­щим словом в языке: "Я куплю этого кота, если он не дороже 50 долларовили если он — сиамской породы".

Логиче­ская операция возвращает поразрядный результат, который либо исти­нен ( не 0), либо ложен (0). Результат логической операции определяется согласно табл.8. Операто­ры приведены в порядке приоритета выполнения.

 

Таблица 8