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

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

Алгебра логики — это раздел математической логики, значения всех эле­ментов (функций и аргументов) которой определены в двухэлементном множестве: «Истина» и «Ложь» или “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 + а * с.

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

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

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

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

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

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

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

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

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

Таблица 6

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

Не нашли, что искали? Воспользуйтесь поиском: