Часть 2 - Логические основы ЭВМ. Основные понятия алгебры логики (Т.В. Лукьянова - Конспект лекций по информатике), страница 2

Поэтому высказываниеможно представить некоторой переменной величиной, значением которой можетбыть только ложно или истинно.В алгебре логики высказывания принято обозначать прописными латинскими буквами: A, B, X, Y.Действия, которые производятся над высказываниями, записываются в виделогических выражений.Высказывание (логическое выражение) может принимать только одно издвух значений – ИСТИНА (1) или ЛОЖЬ (0).Логические выражения бывают простыми или сложными.Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В нём возможно только два результата – либо «истина», либо «ложь».

Например:На улице светит солнце. (А)На улице идет дождь. (В)Сложное логическое высказывание строится из простых с помощью связок«И», «ИЛИ», «НЕ», которые называются логическими операциями. Примеры:На улице светит солнце и на улице идет дождь. (А И В)На улице светит солнце или на улице идет дождь. (А ИЛИ В)Основная задача логики высказываний заключается в том, чтобы на основании истинности или ложности простых высказываний определить истинностьили ложность сложных высказываний.72.1.3.Основные логические операцииВ алгебре логики существует три основные операции.

Каждая операция надлогическими высказываниями имеет свое название и обозначение.Основные логические операции: И (логическое умножение, конъюнкция); ИЛИ (логическое сложение, дизъюнкция); НЕ (логическое отрицание, инверсия);Операция НЕСамой простой логической операцией является операция НЕ (по-другому ееназывают отрицанием, дополнением или инверсией и обозначают NOT X).

Результат отрицания всегда противоположен значению аргумента.ОТРИЦАНИЕ (инверсия) – операция логического отрицания.Если исходное выражение истинно, то результат его отрицания будетложным, и наоборот, если исходное выражение ложно, то оно будет истинным.Обозначение: не, not, ¬ , ¯.Добавляется частица НЕ или слова НЕВЕРНО, ЧТО… (лат. inversio – переворачиваю).Примеры:А«Земля вращается вокруг Солнца» – истинно¬А«Земля не вращается вокруг Солнца» – ложноЛогическая операция НЕ является унарной. т.е. имеет всего один операнд.Все операции алгебры логики определяются таблицами истинности значений.

Таблица истинности определяет результат выполнения операций для всехвозможных логических значений исходных высказываний. Таблица истинностиможет рассматриваться в качестве одного из способов задания логической функции.8Таблица истинности отрицания:Операция ИЛогическое И называют конъюнкцией, или логическим умножением.КОНЪЮНКЦИЯ (логическое умножение) – это соединение двух логических выражений (высказываний) с помощью союза И (лат.

conjunctio – соединение).Логическая операция конъюнкция истинна только в том случае, еслиоба простых высказывания истинны, в противном случае она ложна.Обозначение: и, and, ×, & , Примеры:А«У меня есть знания для сдачи зачета».В«У меня есть желание для сдачи зачета».AB«У меня есть знания и желание для сдачи зачета».В отличие от логической операции НЕ, операция И является бинарной, таккак представляет собой результат действия над двумя логическими величинами.Таблица истинности конъюнкции:Операция ИЛИЛогическое ИЛИ называют дизъюнкцией, или логическим сложением.ДИЗЪЮНКЦИЯ (логическое сложение) – соединение двух логическихвысказываний с помощью союза ИЛИ (лат. disjunctio – разделение).9Логическая операция дизъюнкция ложна, если оба простых высказывания ложны.

В остальных случаях она истинна.Обозначение: или, or, +, Примеры:A«Летом я поеду на море».B«Летом я поеду на дачу».A  B «Летом я поеду на море или поеду на дачу».Операция ИЛИ, как и операция И, является бинарной, так как представляетсобой результат действия над двумя логическими величинами.Таблица истинности дизъюнкции:2.1.4.Дополнительные логические операцииОперации И, ИЛИ, НЕ образуют полную систему логических операций, изкоторой можно построить сколь угодно сложное логическое выражение. Кромебазовых операций в логике также часто используются следующие дополнительные операции: ИМПЛИКАЦИЯ (логическое следование); ЭКВИВАЛЕНТНОСТЬ (логическое тождество, равнозначность); Исключающее ИЛИ (исключающая дизъюнкция); Операция И-НЕ (штрих Шеффера); Операция ИЛИ-НЕ (стрелка Пирса).ИМПЛИКАЦИЯЛогическую операцию ИМПЛИКАЦИЯ называют логическим следованием. Операция связывает два логических выражения, из которых первое явля-10ется условием, а второе – следствием из этого условия (лат.

implico – тесно связаны).ИМПЛИКАЦИЯ (логическое следование) – бинарная логическая операция,соответствующая связке «если … , то …».Результат импликации будет ложным тогда и только тогда, когда условие (А) истинно, а следствие (В) – ложно, в остальных случаях результат –истина.Обозначение: →, , (A → B; A  B)Пример:А«Идёт дождь».В«На улице сыро».А → В «Если идёт дождь, то на улице сыро».Таблица истинности импликации:ЭКВИВАЛЕНТНОСТЬЛогическуюоперациюЭКВИВАЛЕНТНОСТЬ называют логическимтождеством или равнозначностью. Операция определяет результат сравнениядвух логических выражений (лат. aequivalens – равнозначный, равноценный).ЭКВИВАЛЕНТНОСТЬ (логическое тождество, равнозначность) – бинарная логическая операция, соответствующая связке «Тогда и только тогда,когда …».Результат операции эквивалентность истинен только тогда, когда А иВ одновременно истинны или одновременно ложны.Обозначение:  ,  ,  , ~ (AB; AB; A B; A~ B)11Операция обозначается словами: «тогда и только тогда», «необходимо идостаточно», «...

равносильно ...».Пример:А«День сменяет ночь».В«Солнце скрывается за горизонтом».А ~ В «День сменяет ночь тогда и только тогда, когда солнце скрывается загоризонтом».Таблица истинности эквивалентности:Исключающее ИЛИИсключающее ИЛИ называют Исключающей дизъюнкцией, неэквивалентностью (XOR).Исключающая дизъюнкция – бинарная логическая операция, соответствующая связке «Либо ... , Либо … ».Результат исключающей дизъюнкции будет истинным тогда и толькотогда, когда значение одного из операндов истина, а другого – ложно.Обозначение:  , XOR (A  B, A XOR B)Таблица истинности исключающей дизъюнкции:AB00110101AB0110Как видно из таблицы истинности, операция XOR фактически сравниваетна совпадение два двоичных разряда.12Операция И-НЕДругое название этой операции – штрих Шеффера.Операция И-НЕ – бинарная логическая операция, результат которой будетложным тогда и только тогда, когда значения обоих операндов истинны.Обозначение: , ‘ (апостроф) (A B, A ‘ B)Таблица истинности операции И-НЕ:A0011B0101AB1110Таким образом, высказываниеA B означает, что АиВнесовмест-ны, т.

е. не являются истинными одновременно.Операция ИЛИ-НЕДругое название этой операции – стрелка Пирса.Операция ИЛИ-НЕ – бинарная логическая операция, результат которой будет истинным тогда и только тогда, когда значения обоих операндов ложны.Обозначение:  (A  B)Таблица истинности операции ИЛИ-НЕ:A0011B0101AB1000Таким образом, высказывание «X ↓ Y» означает «ни X, ни Y».2.1.5.Составление таблиц истинности сложных логическихвыраженийТаблица истинности составляется по следующему алгоритму:1) определить число простых логических выражений (n);132) определить число строк в таблице истинности (q=2n);3) определить количество логических операций (m);4) определить количество столбцов: количество простых логических выражений + количество операций (n + m);4) записать все возможные значения простых логических выражений;5) определить порядок логических операций;6) записать логические операции в таблицу истинности и определить длякаждой значение.Пример для логической функции с таблицей истинности.Функция: A&(BC)Количество простых логических выражений (A, B, C) n = 3  количествострок = 2n =23 = 8.Количество логических операций (, &,  ) m= 3  количество столбцов =n + m = 3 +3 = 6.Таблица истинности состоит из 8 строк (не считая строки-заголовка) и 6столбцов:АВСA00001111001100110101010111110000BC01110111 A&(BC)01110000Из таблицы видно при каких наборах переменных функция принимает значение истина, а при каких ложь.142.1.6.Логические формулыС помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой.Определение логической формулы:1.

Всякая логическая переменная и символы «истина» («1») и «ложь»(«0») – формулы.2. Если А и В – формулы, то,А.В,АВ,АB,АВ – формулы.3. Никаких других формул в алгебре логики нет.В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог». Это высказывание формализуется ввиде (A  B)C. Такая же формула соответствует высказыванию «если Игорьзнает английский или японский язык, то он получит место переводчика».Как показывает анализ формулы (A  B)C, при определённых сочета-ниях значений переменных A, B и C она принимает значение «истина», а принекоторых других сочетаниях – значение «ложь».

Такие формулы называютсявыполнимыми.Некоторые формулы принимают значение «истина» при любых значенияхистинности входящих в них переменных. Таковой будет, например, формула А , соответствующая высказыванию «Этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный,и тогда, когда треугольник не прямоугольный. Такие формулы называютсятождественно истинными формулами или тавтологиями. Высказывания,которые формализуются тавтологиями, называются логически истинными высказываниями.В качестве другого примера рассмотрим формулу А ., которой соответ-ствует, например, высказывание «Катя самая высокая студентка в группе, и в15группе есть студентки выше Кати». Очевидно, что эта формула ложна, так каклибо А, либообязательно ложно.

Такие формулы называются тождественноложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.Если две формулы А и В одновременно, то есть при одинаковых наборахзначений входящих в них переменных, принимают одинаковые значения, то ониназываются равносильными.Равносильность двух формул алгебры логики обозначается символом «=».Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.2.1.7.Упрощение логических выраженийВ алгебре высказываний любую логическую функцию можно выразить через основные логические операции, записать ее в виде логического выражения иупростить, применяя законы логики и свойства логических операций.