Современные компьютеры, основанные на «древних» электронно-вычислительных машинах, в качестве базовых принципов работы опираются на определенные постулаты. Они называются законы алгебры логики. Впервые подобная дисциплина была описана (конечно, не столь подробно, как в современном виде) древнегреческим ученым Аристотелем.
Представляя собой отдельный раздел математики, в рамках которого изучается исчисление высказываний, алгебра логики имеет ряд четко выстроенных выводов и заключений.
С тем чтобы лучше разобраться в теме, разберем понятия, которые помогут в дальнейшем узнать законы алгебры логики.
Пожалуй, основной термин в изучаемой дисциплине - высказывание. Это некое утверждение, которое не может быть одновременно ложным и истинным. Ему всегда присуща лишь одна из этих характеристик. При этом условно принято истинности придавать значение 1, ложности - 0, а само высказывание называть некой A, B, C. Иначе говоря, формула A=1 означает, что высказывание А истинно. С высказываниями можно поступать самым различным образом. Вкратце рассмотрим те действия, которые можно с ними совершать. Отметим также, что законы алгебры логики невозможно усвоить, не зная этих правил.
1. Дизъюнкция двух высказываний - результат операции «или». Может быть или ложной, или истинной. Используется символ «v».
2. Конъюнкция. Результатом подобного действия, совершаемого с двумя высказываниями, станет новое лишь в случае, когда оба исходных высказывания истинны. Используется операция «и», символ «^».
3. Импликация. Операция «если А, то В». Результатом является высказывание, ложное лишь в случае истинности А и ложности В. Применяется символ «->».
4. Эквиваленция. Операция «A тогда и только тогда В, когда». Данное высказывание истинно в случаях, когда обе переменные имеют одинаковые оценки. Используется символ «<->».
Существует также ряд операций, близких к импликации, но в данной статье они рассмотрены не будут.
Теперь подробным образом рассмотрим основные законы алгебры логики:
1. Коммутативный или переместительный гласит, что перемена мест логических слагаемых в операциях конъюнкции или дизъюнкции на результате не сказывается.
2. Сочетательный или ассоциативный. Согласно этому закону, переменные в операциях конъюнкции или дизъюнкции можно объединять в группы.
3. Распределительный или дистрибутивный. Суть закона в том, что одинаковые переменные в уравнениях можно вынести за скобки, не изменив логики.
4. Закон де Моргана (инверсии или отрицания). Отрицание операции конъюнкции равносильно дизъюнкции отрицания исходных переменных. Отрицание от дизъюнкции, в свою очередь, равно конъюнкции отрицания тех же переменных.
5. Двойное отрицание. Отрицание некоего высказывания дважды дает в результате исходное высказывание, трижды - его отрицание.
6. Закон идемпотентности выглядит следующим образом для логического сложения: x v x v x v x = x; для умножения: x^x^x^=x.
7. Закон непротиворечия гласит: два высказывания, если они противоречивы, одновременно быть истинными не могут.
8. Закон исключения третьего. Среди двух противоречивых высказываний одно - всегда истинное, другое - ложное, третьего не дано.
9. Закон поглощения можно записать таким образом для логического сложения: x v (x^y)=x, для умножения: x^ (x v y)=x.
10. Закон склеивания. Две соседние конъюнкции способны склеиться, образовав конъюнкцию меньшего ранга. При этом та переменная, по которой исходные конъюнкции склеивались, исчезает. Пример для логического сложения:
(x^y) v (-x^y)=y.
Мы рассмотрели лишь наиболее используемые законы алгебры логики, которых по факту может быть многим больше, поскольку нередко логические уравнения приобретают длинный и витиеватый вид, сократить который можно, применив ряд схожих законов.
Как правило, для удобства подсчета и выявления результатов используются специальные таблицы. Все существующие законы алгебры логики, таблица для которых имеет общую структуру сеточного прямоугольника, расписывают, распределяя каждую переменную в отдельную клеточку. Чем больше уравнение, тем проще с ним справиться, используя таблицы.
Для преобразования функций, упрощения формул, полученных при формализации условий логических задач, в алгебре логики производятся эквивалентные преобразования, опирающиеся на основные логические законы. Некоторые из этих законов формулируются и записываются так же, как аналогичные законы в арифметике и алгебре, другие выглядят непривычно.
Законы алгебры логики называют иногда теоремами .
В алгебре высказываний логические законы выражаются в виде равенства эквивалентных формул.
В справедливости всех законов можно убедиться, построив таблицы истинности для левой и правой частей записанного закона. После упрощения выражения с применением законов алгебры логики таблицы истинности совпадают.
Справедливость части законов можно доказать, применяя инструментарий таблиц истинности.
Рисунок 1.
Рисунок 3.
Упростим исходное выражение, используя основные законы алгебры логики:
Рисунок 4.
(закон Де Моргана, распределительный закон для И, закон идемпотенции, операция переменной с её инверсией).
Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.2 принимает значение $1$, то есть является тождественно истинной.
Рисунок 6.
Из таблицы видно, что Исходное выражение принимает такие же значения, что и Упрощенное выражение на соответствующих значениях переменных $x$ и $y$.
Упростим выражение на рис.5, применяя основные законы алгебры логики.
Рисунок 7.
(закон Де Моргана, закон поглощения, распределительный закон для И).
Рисунок 9.
Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.8 принимает значение $0$, то есть является тождественно ложной.
Упростим выражение, применяя законы алгебры логики:
Рисунок 10.
Рисунок 12.
(закон Де Могргана, распределительный).
Составим таблицу истинности для выражения на рис.11:
Рисунок 13.
Из таблицы видно, что выражение на рис.11 в некоторых случаях принимает значение $1$, а в некоторых - $0$, то есть является выполнимым.
(правило де Моргана, выносим за скобки общий множитель, правило операций переменной с её инверсией).
(повторяется второй сомножитель, что возможно используя закон идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).
(вводим вспомогательный логический сомножитель
В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы позволяют производить равносильные (эквивалентные) преобразования логических выражений. Преобразования называются равносильными, если истинные значения исходной и полученной после преобразования логической функции совпадают при любых значениях входящих в них логических переменных.
Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.
1. Закон противоречия:
2. Закон исключенного третьего:
3. Закон двойного отрицания:
4. Законы де Моргана:
5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.
6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A.
7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0.
8. Законы склеивания:
9. Закон контрапозиции: (A ? B) = (B ? A).
Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:
1. Коммутативный закон: A & B = B & A; A ? B = B ? A.
2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.
3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C).
Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция (&), дизъюнкция (v), импликация (?), эквиваленция (?)
Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
Опрос законов алгебры логики (на доске).
Перечислим наиболее важные из них:
1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.
Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.
Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.
Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание.
“ Неверно, что 2*24”
Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.
Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.
Смысл законов де Моргана (Август де Морган (1806-1871) — шотландский математик и логик) можно выразить в кратких словесных формулировках:
— отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
— отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.
1. Установить эквивалентны ли высказывания.
3. С помощью таблиц истинности доказать законы поглощения и склеивания.
I. Подача нового материала.
Доказать законы логики можно:
Докажем законы склеивания и поглощения с помощью равносильностей:
П. Практическая часть
1. Упрощение формул.
Пример 1. Упростить формулу (А+В)·* (А+С)
2. Преобразования “поглощение” и “склеивание”
Пример 2. Упростить выражение А+ A*B
Решение. A+A*B A (1 + B) A — поглощение
Пример 3. Упростить выражение A*B+A*
Решение . A*B + A* A (B + ) A — склеивание
3. Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний — все отрицания будут применяться только к простым высказываниям.
Пример 4. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.
4. Любую формулу можно тождественно преобразовать так, что в ней не будут использованы:
Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.
Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.
Вывод: В алгебре логики всякую логическую функцию можно выразить через другие логические функции, но их должно быть по меньшей мере 2 операции, при этом одной из них обязательно должно быть отрицание.
Все операции можно выразить через конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание. Через эквиваленцию и отрицание остальные операции выразить нельзя.
Задание 1.
Установить истинность высказывания .
Задание 2
Установить является ли высказывание тавтологией?
Задание 3.
Установить эквивалентны ли высказывания.
1. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое сложение:
2. Формулы данных высказываний преобразовать в эквивалентные, исключить логическое умножение.
lunina.21205s09.edusite.ru
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Закон
Формулировка
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 -сильный
Тема 3. Основы математической логики
1. Логические выражения и логические операции.
2. Построение таблиц истинности и логических функций.
3. Законы логики и преобразование логических выражений.
Лабораторная работа № 3. Основы математической логики.
3. Законы логики и правила преобразования логических выражений
Закон двойного отрицания (двойное отрицание исключает отрицание):
А = = Ú
Закон идемпотентности (от латинских слов idem - тот же самый и potens - сильный; дословно - равносильный):
для логического сложения: А Ú A = A ;
для логического умножения:A & A = A .
Закон означает отсутствие показателей степени.
для логического умножения:A & 1 = A, A & 0 = 0 .
A & = 0 .
Невозможно, чтобы противоречащие высказывания были одновременно истинными.
A Ú = 1 .
Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.
для логического умножения:A & (A Ú B) = A .
Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие — основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.
Пример 1. Упростить формулу (А Ú В) & (А Ú С) .
Таким образом, мы доказали закон дистрибутивности.
Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний — все отрицания будут применяться только к простым высказываниям.
Пример 2. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.
Решение:
Дискретная математика: Математическая логика
Закон идемпотентности (одинаковости)
Закон коммутативности
a b = b a
Закон ассоциативности
a + (b + c) = (a + b) + c
a (b c) = (a b) c
Законы дистрибутивности
Дистрибутивность конъюнкции относительно дизъюнкции
A (b + c) = a b + a c
Дистрибутивность дизъюнкции относительно конъюнкции
A + b c = (a + b) (a + c)
акон двойного отрицания
Законы де Моргана
Законы поглощения
a + a b = a
a (a + b) = a
Законы, определяющие действия с логическими константами 0 и 1
| a + 0 = a a 0 = 0 | a + 1 = 1 a 1 = a |
| 1 = 0 |
|
Дополнительные законы алгебры Буля являются следствиями из основных законов и очень полезны при упрощении записи логических функций.
Закон склеивания
Доказательство этого тождества проводится с использованием первого закона дистрибутивности:
Доказательство этого тождества проводится с использованием второго закона дистрибутивности:
Закон Блейка-Порецкого
Применяя законы действия с логическими константами, идемпотентности и склеивания, данное тождество можно доказать следующим образом:
Закон свертки логического выражения
Данное тождество можно доказать, последовательно используя законы работы с логическими константами, дистрибутивности, идемпотентности и склеивания:
Задачи.
Упростить СДНФ следующих функций:
1. (a b ) c
2. (a b ) c
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
3.
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
СДНФ = 
Дальнейшее упрощение невозможно.
4. 
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
СДНФ =
5. 
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
Минимизация логических функций можно проводить с помощью метода Квайна-МакКласски, который состоит из четырех шагов:
Двоичные эквиваленты истинных наборов следующие:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Упорядочим двоичные наборы по ярусам и проведем склейки, до тех пор, пока это возможно
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Затем строим таблицу Квайна:
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
В нашей таблице наборы 0001 и 1011 покрываются единственно возможным образом, следовательно, покрывающие их минимальные интервалы называются обязательными
и образуют ядро покрытия
, т.к. должны входить в любое покрытие. В таблице соответствующие единицы подчеркнуты, интервалы {0- -1,- -11} образуют не только ядро покрытие, но и покрывают всю таблицу Квайна.
Таким образом, мы получили минимальную форму исследуемой функции в виде:
МДНФ = {0 - - 1, - - 1 1} = 
Рассмотрим несколько примеров.
Задачи.
1. Найти МДНФ функции f 1 =
f1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
Совершенная ДНФ исследуемой функции имеет вид:
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
Строим таблицу Квайна:
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Определим ядро покрытия, в которое войдут обязательные интервалы:
{0100, -0-1, -01-, --11}. В данном случае, ядро покрытия покрывает и всю таблицу в целом.
Минимальная дизъюнктивная нормальная форма f1 имеет вид:
2. Найти МДНФ функции f 2( x 1, x 2, x 3), которая принимает единичные значения на наборах 0,2,3,6 и 7.
Построим таблицу истинности для f 2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
СДНФ =
Упорядочим двоичные наборы по ярусам и проведем склейку:
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
ЛИТЕРАТУРА
