Законы алгебры логики
Законы алгебры логики — тождества, которые заменяют часть логического выражения на равносильную и не меняют его значения. Главные из них: импликация через ИЛИ, законы де Моргана, распределительные законы и поглощение. С ними упрощают выражения в заданиях 2 и 15, а ответ проверяют таблицей истинности или программой.
Законы алгебры логики
Выражения равносильны, если их значения совпадают на всех наборах. Закон алгебры логики заменяет часть выражения на равносильную, и значение не меняется.
- Импликация: , .
- Эквивалентность: .
- Де Морган: , . Двойное отрицание: .
- , . Поглощение: .
- Упрощение: уберите и , внесите отрицания в скобки, раскройте скобки или вынесите общую часть, сократите, проверьте программой.
Равносильные выражения и тождество
Два выражения равносильны, если их значения совпадают при любых значениях переменных. Так, и равносильны, а и нет: при , первое равно 1, второе 0. Равенство двух равносильных выражений называют логическим тождеством. Законы алгебры логики — тождества, по которым одну часть выражения заменяют другой. Такая замена — равносильное преобразование: значение на любом наборе не меняется.
Равносильность проверяют таблицей: постройте таблицу истинности обоих выражений и сравните столбцы. Одного набора с разными значениями хватит, чтобы выражения не были равносильны. В программе перебор делает product, а функция all проверяет, что значения совпали на каждом наборе.
Пример
Равносильны ли выражения и ?
- 1.Левое выражение равно 0, только когда и , то есть при , , .
- 2.Правое равно 0, только когда и : это тот же набор.
- 3.На остальных семи наборах оба выражения равны 1. Программа перебирает 8 наборов и печатает
True.
Ответ: да, равносильны
Законы для И и ИЛИ
| Закон | Для И | Для ИЛИ |
|---|---|---|
| Переместительный | ||
| Сочетательный | ||
| Распределительный | ||
| Повторения | ||
| Противоречия и исключённого третьего | ||
| Операции с константами | , | , |
| Поглощения | ||
| Де Моргана |
Импликация через ИЛИ
: обе части равны 0 только при , . Отрицание импликации: , это следует из закона де Моргана. Импликация равна своей контрапозиции: .
Замена импликации — первый шаг любого упрощения: после неё в выражении остаются только , и , и к ним применимы законы из таблицы. В задании 15 так переписывают условие : получается , то есть точка не лежит на или лежит на .
Пример
Упростите выражение .
- 1.Отрицание импликации: . Получаем .
- 2.Распределительный закон для ИЛИ: .
- 3., а .
Ответ:
Эквивалентность через И и ИЛИ
: обе части равны 1 или обе равны 0. Другая запись: . Отрицание эквивалентности: , значения частей разные.
Пример
Упростите выражение .
- 1.Заменяем эквивалентность: .
- 2.Выносим из первого и третьего слагаемых: . Остаётся .
- 3.Распределительный закон для ИЛИ: .
Ответ: , то есть
Законы де Моргана
и . Чтобы внести отрицание в скобку, отрицают каждую часть и меняют на , а на . Для многих частей правило то же: . Два отрицания подряд снимаются: .
Знак операции меняется обязательно: не равно , они различаются при , . Отрицание сравнения меняет знак сравнения: — это . Так упрощают условия задания 15 с неравенствами: Тождественная истинность: неравенства.
Пример
Запишите без отрицания перед скобками: .
- 1.Закон де Моргана: .
- 2.Двойное отрицание снимается: .
- 3. — это .
Ответ:
Раскрытие скобок, поглощение и склеивание
Распределительный закон для И раскрывает скобки как в алгебре: . Для ИЛИ есть второй закон, которого в обычной алгебре нет: . Справа налево те же законы выносят общую часть за скобки.
Из них следуют два сокращения. Поглощение: и . Склеивание: и .
Пример
Упростите выражение .
- 1.По приоритету конъюнкции выполняются раньше: .
- 2.Склеивание: . Остаётся .
- 3.Поглощение: .
Ответ:
Порядок упрощения
Упрощают по шагам. 1) Замените и на , , . 2) Внесите отрицания в скобки по законам де Моргана. 3) Раскройте скобки или вынесите общую часть. 4) Уберите , и константы, примените поглощение. 5) Проверьте ответ таблицей истинности или программой: значения исходного и нового выражений совпадают на всех наборах.
Пример
Упростите выражение .
- 1.Импликации через ИЛИ: , .
- 2.Выносим общее : .
- 3., остаётся .
- 4.Программа печатает для каждого набора значение выражения и : третий и четвёртый столбцы совпадают.
Ответ:
Проверьте себя
00