Основные понятия алгебры логики
Алгебра логики (булева алгебра) изучает высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.
Основным предметом алгебры логики являются высказывания.
Под высказыванием понимается имеющее смысл языковое выражение, относительно которого можно утверждать, что оно либо истинно, либо ложно.
Пример_1:
· «5 есть простое число». Это высказыванием является истинным.
· «4+х=6». Это уравнение не является высказыванием. Однако, придавая переменной х определенное числовое значение, получим высказывание.
· «роза – цветок». Это высказывание является истинным.
· «все углы – прямые». Это высказывание является ложным.
· «3+5=9». Это высказывание является ложным.
Истинностные значения новых высказываний определяются при этом только истинностными значениями входящих в них высказываний. Построение из данных высказываний (или из данного высказывания) нового высказывания называется логической операцией. Знаки логических операций называются логическими связками.
Пример_2:
· Из высказываний «х>2», «х<3» при помощи связки и можно получить высказывание «x>2 и х<3»;
· из высказываний «у>10», «х<3» при помощи связки или можно получить высказывание «у>10 или х<3»;
Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями.
Одной из основных операций алгебры логики является операция отрицания (инверсия). Отрицание высказывания А (т.е. не А) обозначается и читается: «отрицание А », «не А » или «А с чертой».
В таблице 1 приведены основные бинарные логические операции и связки.
Основные бинарные логические операции и связки
Таблица 1
Обозначение логической операции | Другие обозначения логической операции | Название логической операции и связки | Логические связки |
АÙВ | А&В А×В АВ | конъюнкция, логическое умножение, логическое «и» | А и В |
АÚВ | А+В | дизъюнкция, логическое сложение, логическое «или» | А или В |
А®В | АÊВ АÞВ | импликация, логическое следование | если А, то В; |
АÅВ | АDВ | сумма по модулю 2, разделительная дизъюнкция, разделительное «или» | либо А, либо В |
А~В | АºВ А«В АÛВ | эквиваленция, тождественность равнозначность | А тогда и только тогда, когда В; |
А½В | штрих Шеффера, антиконъюнкция | неверно, что А и В; | |
А¯В | стрелка Пирса, антидизъюнкция, | ни А, ни В; |
Примечание: А и В являются высказываниями.
Инверсия
Пример_3: Дано высказывание А =<Киев-столица Франции>.
Тогда не А =«не Киев-столица Франции». Высказывание не А означает – не верно, что А, т.е. не верно, что <Киев-столица Франции>.
Конъюнкция
Результатом операции конъюнкции для высказывания АÙВ будет истинна только тогда, когда истинны одновременно оба высказывания.
Пример_4: Даны высказывания А =«Москва – столица России» и В =«Рим – столица Италии».
Сложное высказывание АÙВ =«Москва – столица России и Рим – столица Италии» истинно, так как истинны оба высказывания.
Дизъюнкция
Результатом операции дизъюнкции для высказывания АÚВ будет истинна тогда, когда истинно хотя бы одно высказывание, входящее в него.
Пример_5: Даны высказывания А =«2+3=5» и В =«3+3=5».
Сложное высказывание АÚВ =«2+3=5 или 3+3=5» истинно, так как истинно высказывание А.
Эквиваленция
Результатом операции эквиваленции для высказывания А~В будет истинна тогда, когда истинны или ложны одновременно оба высказывания. Отличие эквиваленции от конъюнкции состоит в том, что вне зависимости от смысла, равнозначными являются как истинные, так и ложные высказывания.
Пример_6: Даны высказывания А =«2+2=7» и В =«1–8=5».
Сложное высказывание А~В =«2+2=7 тогда и только тогда, когда 1–8=5» истинно, так как оба высказывания ложны.
Импликация
Результатом операции импликации для высказывания А®В будет ложь только тогда, когда первое высказывание (А) истинно, а второе (В) ложно. При этом А – предпосылка, а В – следствие. В остальных случаях результатом операции всегда будет истина.
Пример_7: Даны высказывания А =«2+2=4» и В =«1–8=5».
Сложное высказывание А®В =«если 2+2=4, то 1–8=5» ложно, так как высказывание А истинно, а В – ложно.
Антиконъюнкция
Результатом операции антиконъюнкции для высказывания А½В будет ложь только тогда, когда оба высказывания истинны. В остальных случаях результатом операции всегда будет истина.
Пример_8: Даны высказывания А =«Москва – столица России» и В =«Рим – столица Италии».
Сложное высказывание А½В =«неверно, что Москва–столица России и Рим–столица Италии» ложно, так как истинны оба высказывания.
Антидизъюнкция
Результатом операции антидизъюнкции для высказывания А¯В будет истинна только тогда, когда оба высказывания ложны. В остальных случаях результатом операции всегда будет ложь.
Пример_9: Даны высказывания А =«Рим – столица России» и В =«Москва – столица Италии».
Сложное высказывание А¯В =«ни Рим–столица России, ни Москва–столица Италии» истинно, так как ложны оба высказывания.
Связки и частица «не» рассматриваются в алгебре логики как операции над величинами, принимающими значения 0 (ложь/false) и 1(истина/true), и результатом применения этих операций также являются значения 0 или 1.
В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности.
В таблице 2 представлена таблица истинности для операции отрицания (инверсия).
Таблица истинности для операции «отрицания»
Таблица 2
А | не А |
Пример_10: Дана переменная А=1 (истина). После применения операции инверсии для переменной А ее значение станет равным 0 ( ложь).
В таблице 3 представлены все наборы значений переменных А и В и значения операций на этих наборах.
Таблица истинности для основных бинарных логических операций
Таблица 3
А | В | Ù | Ú | ® | Å | ~ | ½ | ¯ |
Порядок выполнения логических операций в сложном логическом выражении
Инверсия (отрицание)
Конъюнкция