- Законы алгебры логики и правила преобразования логических выражений
- Законы алгебры логики
- Основы алгебры логики
- Операция НЕ — логическое отрицание (инверсия)
- Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
- Операция И — логическое умножение (конъюнкция)
- Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
- Приоритет логических операций
Законы алгебры логики и правила преобразования логических выражений
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Закон
Формулировка
1. Закон тождества
Всякое высказывание тождественно самому себе.
2. Закон исключенного третьего
Высказывание может быть либо истинным, либо ложным, третьего не дано. Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение “истина”.
3. Закон непротиворечия
Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.
4. Закон двойного отрицания
Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание.
5. Переместительный (коммутативный) закон
Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
6. Сочетательный (ассоциативный) закон
При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
5. Распределительный (дистрибутивный) закон
(X / Y) / Z= (X / Z) / (Y / Z)
(X / Y) / Z = (X / Z) / (Y / Z)
Определяет правило выноса общего высказывания за скобку.
7. Закон общей инверсии Закон де Моргана
Закон общей инверсии.
8. Закон равносильности (идемпотентности)
от латинских слов idem — тот же самый и potens —сильный
9. Законы исключения констант:
10. Закон поглощения:
11. Закон исключения (склеивания):
12. Закон контрапозиции
14. А В = (А / В) / (¬A / ¬B);
15. А В = (¬A / В) / (А /¬B).
Применим законы алгебры логики. Покажем на примере как можно упростить логическое выражение:
1) (A/B) / (A/¬B) = A / (B / B)= A / 1 = A
Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.
¬ (X / Y) / (X / ¬Y) = ¬ X / ¬Y / (X / ¬Y) = ¬ X / X/¬Y /¬Y= 0 ¬Y /¬Y
3) применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией
4) ¬ X / Y / ¬ (X / Y) / X = ¬ X / Y / ¬ X / ¬Y / X= ¬ X / (Y / ¬Y) / X= ¬ X / X= 1
Мы выяснили, как информация представляется в памяти вычислительных устройств и установили алгоритмы проведения операций над этими представлениями.
Теперь, давайте попробуем разобраться, как именно реализуются операции над двоичными представлениями. Для этого, для начала, нам придется разобраться с алгеброй логики.
Алгебра логики является частью дискретной математики – раздела математики, изучающего свойства структур конечного характера.
Сама алгебра логики изучает свойства функций, у которых значения как аргументов, так и самих функций ограничены двумя значениями, например, (<0,1>) .
Отцом алгебры логики считается английский математик Джордж Буль (1815-1864), поэтому алгебру логики иногда называют булевой алгеброй.
Долгое время алгебра логики была известна лишь узкому кругу специалистов, и только в 1938 году американский математик Клод Шеннон (1916-2001), стоявший у истоков современной информатики, показал, что алгебра логики применима для описания самых разных процессов, в том числе релейных и транзисторных схем.
Исследования в области алгебры логики связаны с формальной логикой, а точнее, с понятием высказывания. Высказывание – это некое лексическое образование, которое устанавливает свойства и взаимосвязи между объектами. Высказывания могут быть истинными, если они адекватно описывают объекты, или ложными в противном случае.
Так, примерами высказываний могут служить такие фразы, как “сегодня идет дождь”, или “завтра я не пойду в институт”.
Определение истинности высказывания не всегда тривиально. Так, например:
Для любого натурального числа (n>2) уравнение [ a^n + b^n = c^n] Не имеет решений в целых ненулевых числах (a,,b,,c)
Как известно, сформулированная Пьером Ферма в 1637 году, была окончательно доказана только в 1994.
Введем не совсем формальное, но достаточное для наших целей определение
Высказывание это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.
Это определение было предложено Аристотелем.
Проблема языковых образований в рамках алгебры логики в том, что они могут иметь весьма своеобразную структуру. Например, фраза “это высказывание является ложным” не может считаться высказыванием, поскольку бессмысленно говорить о его истинности или ложности. Причиной парадокса является структура фразы: она ссылается сама на себя. Подобные парадоксы могут быть устранены введением следующего определения:
Элементарное высказывание это такое высказывание, никакая часть которого не является высказыванием.
Следует заметить, что высказыванием в строгом смысле является только утверждение о конкретных объектах. Если речь идет о неких переменных, например, “x – рациональное число”, то мы говорим о неких функциях, имеющих значение “истина” или “ложь”. Такие функции называются предикатами.
Так же следует заметить, что алгебра логики отвлекается от смыслового содержания высказываний, и занимается скорее связями между высказываниями. Если мы договоримся считать за аксиому, что “солнце светит ночью”, то есть, договоримся что это высказывание истинно, то в рамках нашей аксиоматики сможем делать какие-то обоснованные выводы. Эти выводы, конечно, не будут иметь много общего с действительностью.
Примерами таких отвлеченных, на первый взгляд, систем, может служить, например, геометрия Лобачевского, которая имеет не слишком много общего с нашим псевдоевклидовым пространством. 1
Различные языковые связки, такие, как “не”, “если …, то …”, “или”, “и”, и т.п. позволяют строить из элементарных высказываний более сложные.
В алгебре логики существуют соответствующие подобным связкам операции.
Введем некоторые из них.
Конъюнкция, или логическое умножение логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
Конъюнкция обозначается различными способами, в частности, амперсандом (a ,&,b) , точкой (a cdot b) , или “крышкой” (a wedge b) , и соответствует языковой связке “и”. Мы будем в основном использовать амперсанд.
Поскольку оба исходных высказывания имеют по два возможных значения, и конъюнкция имеет два возможных значения, мы можем записать это определение в виде таблицы истинности:
| (p) | (q) | (p,&,q) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Дизъюнкция, или логическое сложение логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда хотя бы одно из исходных высказываний истинно.
Дизъюнкция соответствует союзу “или”, и обозначается плюсом (a+b) , или “галочкой” (avee b) . Мы будем использовать в основном второй вариант.
Таблица истинности дизъюнкции, по определению:
| (p) | (q) | (pvee q) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Строгая дизъюнкция, или сложение по модулю 2 логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда только одно из исходных высказываний истинно.
Строгая дизъюнкция соответствует связке “либо …, либо …”, и обозначается плюсом в кружочке (aoplus b) , или треугольником (avartriangle b) . Будем в основном пользоваться первым обозначением.
Таблица истинности, по определению:
| (p) | (q) | (poplus q) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Импликация логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда первое из исходных высказываний (условие) истинно, а второе (следствие) – ложно.
Импликация соответствует связке “если …, то …”, и обозначается стрелкой (a
ightarrow b) , или (a Rightarrow b)
Таблица истинности, по определению:
| (p) | (q) | (p ightarrow q) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Импликация, на первый взгляд, имеет не очевидное определение: как вдруг из ложных условий получается истинное следствие. Однако, в математике это никакая не новость. Например, возьмем очевидно ложное утверждение “один равен двум”:
Складывая эти равенства, получим очевидно истинный результат:
С другой стороны, из заведомо истинных посылок формально нельзя вывести ложный результат (конечно, человеческий фактор никто не отменял, но человеческий фактор выходит за пределы рассмотрения формальной логики).
Эквивалентность логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Эквивалентность соответствует связке “тогда и только тогда, когда”, и обозначается (a Leftrightarrow b) , или (a equiv b) , или (a sim b) , или (a leftrightarrow b) . Будем в основном пользоваться первыми двумя обозначениями.
Таблица истинности, по определению:
| (p) | (q) | (pequiv q) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Инверсия, или отрицание логическая операция, ставящая в соответствие элементарному высказыванию новое высказывание, являющееся истинным тогда и только тогда, исходное ложно.
Таблица истинности, по определению:
| (p) | (;overline |
|---|
😉
В заключение, таблица истинности основных логических операций:
| (p) | (q) | (;overline |
|---|
😉
ightarrow q)
Законы алгебры логики
Введем некоторые определения, аналогичные алгебре действительных чисел, для алгебры логики.
Логическая переменная Переменная, значением которой может быть любое высказывание. Обозначать будем маленькими латинскими буквами. Логическая формула любая переменная, а так же любая из констант “0” (“ложь”) и “1” (“истина”) Любая комбинация логических формул, составленная с помощью логических операций. Эквивалентные формулы такие формулы, которые зависят от одного и того же набора переменных, и при одинаковых значениях этих переменных, формулы так же имеют одинаковые значения. Обозначать будем знаком равенства.
Существуют следующие “законы” алгебры логики, определяющие некий набор эквивалентных формул:
Все перечисленные законы элементарно доказываются составлением таблиц истинности.
Например, первый закон де Моргана:
| (x) | (y) | (x,&,y) | (;overline;) | (;overline |
(;overline |
(;overline |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
3 и 6 столбец одинаковы, следовательно, соответствующие формулы эквивалентны.
Введем еще одно определение
Тавтология логическая формула, которая всегда истинна.
Например, тавтологией является формула, выражающая закон исключения третьего.
Оказывается, алгебра логики хорошо подходит для решения логических задач. Решение логических задач, конечно, умеренно бессмысленное времяпрепровождение (исключая случаи, когда на их примере рассматриваются более сложные вопросы), однако это хороший способ поработать с алгеброй логики и осмыслить основные концепции.
Итак, формальный способ решения логических задач:
- Из условий задачи выделяются простые высказывания и обозначаются как логические переменные.
- Условия задачи записываются в виде логических формул
- Составляется единое логическое выражение, соответствующее условию задачи. По условию задачи оно является истинным.
- Полученное выражение упрощается, либо составляется таблица истинности для него (либо и то, и другое)
- Выбирается решение задачи (случаи, когда условие истинно)
- Решение формулируется в исходных терминах задачи.
На весеннем фестивале, четыре садовника показывали выращенные ими розы.
Всего розы были четырех цветов и у каждого садовника было по две розы.
- У первого была желтая роза
- У второго не было красной розы
- У третьего была синяя роза, но не было зеленой
- У одного из садовников с зеленой розой не было красной
- Ни у одного из садовников с желтой розой не было зеленой
- Ни у кого нет роз двух одинаковых цветов
Введем переменные, в которых название переменной соответствует цвету, а индекс – садовнику (номеру). Это автоматически учитывает условие “Ни у кого нет роз двух одинаковых цветов”. Тогда условия задачи запишутся в виде:
Дополнительно, у каждого садовника по условиям задачи по две розы: Поэтому, если у садовника есть розы двух цветов, то роз двух других цветов у него нет. Учтем подразумеваемые импликации постфактум.
Далее для простоты записи, амперсанды опускаются (если между переменными нет ничего – значит там амперсанд). В случае отсутствия скобок, сначала применяется конъюнкция, потом все остальное.
Рассматривая последнее условие:
Первая импликация истинна, только если (;overline
(y_1 ;overline
ightarrow;overline
ightarrow;overline
Рассмотрим предпоследнее условие
[ (g_1
ightarrow;overline
ightarrow;overline
ightarrow;overline
ightarrow;overline
Первая импликация всегда истинна, поскольку (;overline
[ 1 oplus 1 oplus 1 oplus(g_4
ightarrow;overline
[ 1 oplus(g_4
ightarrow;overline
Легко показать, что (1 oplus x = ;overline
Импликацию можно представить в виде (x
ightarrow y = ;overline
Применяя закон де Моргана,
Записывая все условия вместе:
[ y_1 ;overline
Учитывая (g_4 (;overline
[ y_1 ;overline
Известно, что зеленые розы должны быть у двух садовников:
[ ;overline
Получаем (g_2) , тогда (g_2 (;overline
Аналогично для желтых:
Получаем (y_3) . Поскольку (y_3 b_3) , можно утверждать (;overline
Для красных тогда:
Получаем (r_1) . Поскольку (r_1 y_1) , можем утверждать (;overline
[ y_1 r_1 g_2 b_2 b_3 y_3 g_4 r_4 ]
Вообще сейчас считается, что у пространства, в котором мы находимся, времеподобная метрика Миньковского.↩︎
Кубанского государственного университета
Основы алгебры логики
Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д. Действия над переменными величинами записываются в виде математических выражений.
Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».
Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.
Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.
Логические выражения могут быть простыми и сложными.
Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».
Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.
В качестве основных логических операций в сложных логических выражениях используются следующие:
• НЕ (логическое отрицание, инверсия);
• ИЛИ (логическое сложение, дизъюнкция);
• И (логическое умножение, конъюнкция).
Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два выска¬зывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении, например:
- таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
- в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
- если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
Операция НЕ — логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.
Для операции отрицания НЕ приняты следующие условные обозначения:
Результат операции отрицания НЕ определяется следующей таблицей истинности:
| A | не А |
| 0 | 1 |
| 1 | 0 |
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.
Приведем примеры отрицания.
1. Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.
2. Высказывание «Уравнение у = 4х + 3 в промежутке -2
3. Высказывание «4 — простое число» ложно. Высказывание «4 — не простое число» истинно.
Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает ее, если лампа не горела — включает ее. Такой переключатель можно счи¬тать электрическим аналогом операции отрицания.
Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое бу¬дет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B.
Результат операции ИЛИ опреде¬ляется следующей таблицей истинности:
| A | B | А или B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.
Приведем примеры логического сложения.
1. Рассмотрим высказывание «В библиотеке можно взять книгу или встретить знакомого». Это высказывание формально мож¬но представить так: С = А ? В, где высказывание А — «В библиотеке можно взять книгу», а В — «В библиотеке можно встретить знакомого». Объединение этих высказываний при помощи операции логического сложения означает, что события могут произойти как отдельно, так и одновременно.
2. Рассмотрим высказывание «Знания или везение — залог сдачи экзаменов». "Успешно сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянут единственный выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет.
Кто хоть однажды использовал елочную гирлянду с параллельным соединением лампочек, знает, что гирлянда будет светить до тех пор, пока цела хотя бы одна лампочка. Логическая операция ИЛИ чрезвычайно схожа с работой подобной гирлянды, ведь результат операции ложь только в одном случае — когда все аргументы ложны.
Операция И — логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А ? В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:
| A | B | А и B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.
Приведем примеры логического умножения.
1. Рассмотрим высказывание «Умение и настойчивость приводит к достижению цели». Достижение цели возможно только при одновременной истинности двух предпосылок — умения И настойчивости.
Логическую операцию И можно сравнить с последовательным соединением лампочек в гирлянде. При наличии хотя бы одной неработающей лампочки электрическая цепь оказывается разомкнутой, то есть гирлянда не работает. Ток протекает только при одном условии — все составляющие цепи должны быть исправны.
Операция «ЕСЛИ-ТО» — логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
если А, то В; А влечет В; if A then В; А? В.
| A | B | А ? B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Приведем примеры операции следования.
1. Рассмотрим высказывание «Если идет дождь, то на улице сыро». Здесь исходные высказывания «Идет дождь» и «На улице сыро». Если не идет дождь и не сыро на улице, результат операции следования — истина. На улице может быть сыро и без дождя, например, когда прошла поливочная машина или дождь прошел накануне. Результат операции ложен только тогда, когда дождь идет, а на улице не сыро.
2. Рассмотрим два высказывания: А <х делится на 9>, В <х делится на 3>. Операция А ? В означает следующее: «Если число делится на 9, то оно делится и на 3». Рассмотрим возможные варианты:
? А — ложно, В — ложно (1-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то и В — ложно». Например, х = 4, 17, 22.
? А — ложно, В — истинно (2-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то В — истинно». Например, х = б, 12, 21.
? А — истинно, В — ложно (3-я строка таблицы истинности). Невозможно найти такие числа, которые делились бы на 9, но не делились на 3. Истинная предпосылка не может приводить к ложному результату импликации.
? А — истинно, В — истинно (4-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — истинно, то и В — истинно». Например, х = 9, 18, 27.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А ? В, А
| A | B | А?B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Приведем примеры операции эквивалентности:
1. День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом;
2. Добиться результата в спорте можно тогда и только тогда, когда приложено максимум усилий.
Приоритет логических операций
- Действия в скобках
- Инверсия
- Конъюнкция ( & )
- Дизъюнкция ( V )
- Импликация ( ? )
- Эквивалентность ( ? )
Основные аксиомы и законы алгебры логики