Закон поглощения для трех переменных
Содержание
Операции с константами и закон повторения легко проверяются по таблицам истинности операций «И» и «ИЛИ». Переместительный и сочетательный законы выглядят вполне привычно, так же, как и в арифметике. Почти везде «работает» аналогия с алгеброй чисел, нужно только помнить, что в логике 1 + 1 = 1, а не 2.
Закон двойного отрицания означает, что операция «НЕ» обратима: если применить ее два раза, логическое значение не изменится. Закон исключённого третьего основан на том, что в классической (двузначной) логике любое логическое выражение либо истинно, либо ложно («третьего не дано»). Поэтому если А = 1, то А = 0 (и наоборот), так что произведение этих величин всегда равно нулю, а сумма — единице.
Правила, позволяющие раскрывать отрицание сложных выражений, названы в честь шотландского математика и логика Огастеса (Августа) де Моргана. Обратите внимание, что при этом не просто «общее» отрицание переходит на отдельные выражения, но и операция «И» заменяется на «ИЛИ» (и наоборот). Доказать законы де Моргана можно с помощью таблиц истинности.
С чего начать? Прежде всего, разобраться с порядком действий: здесь отрицание применено к целой скобке, которая «скреплена» с высказыванием «чуть более слабой» конъюнкцией. По существу, перед нами логическое произведение двух множителей: . Из двух оставшихся операций низшим приоритетом обладает импликация, и поэтому вся формула имеет следующую структуру: .
Сначала составим таблицу истинности для левой части. Поскольку дизъюнкция находится в скобках, то в первую очередь выполняем именно её, после чего отрицаем столбец :
Далее составим таблицу истинности для правой части . Здесь тоже всё прозрачно – в первую очередь проводим более «сильные» отрицания, затем применяем к столбцам правило И:
Результаты совпали, таким образом, тождество доказано.
Давайте на этой веселой ноте проведём доказательство. В данную формулу входят уже элементарных высказывания , а значит, всего будет: различных комбинаций нулей и единиц (см. три левых столбца таблицы). Заодно, кстати, записал вам общую формулу; с точки зрения комбинаторики, здесь размещения с повторениями.
Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если – Студент ответил на 1-й вопрос и – Студент ответил на 2-й вопрос. Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос.
Задание 1 Решение: составим таблицу истинности для формулы :
(подробные инструкции по заполнению таблицы находятся после условия задачи)
Полученный результат совпадает с эквиваленцией высказываний и , таким образом:
Закон поглощения для трех переменных
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства. x `vv` 0 = x, x & 1 = x;
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой , а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
Закон поглощения для трех переменных
Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие — основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
- Раскроем скобки: (А Ú В) & (А Ú С) = A & A Ú A & C Ú B & A Ú B & C;
- По закону идемпотентности A & A =A, следовательно,
A & A Ú A & C Ú B & A Ú B & C = A Ú A & C Ú B & A Ú B & C; - В высказываниях А и А & C вынесем за скобки А и используя свойство А + 1= 1, получим
A Ú A & C Ú B & A Ú B & C = A & (1 Ú C) Ú B & A Ú B & C = A Ú B & A Ú B & C; - Аналогично предыдущему пункту вынесем за скобки высказывание А.
A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C.
Закон поглощения для трех переменных
Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу. Закон непротиворечия: В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
А. де Моргана. Один из этих законов можно выразить так: отрицание конъюнкции эквивалентно дизъюнкции отрицаний. В терминах символики логической (р, q — некоторые высказывания; & — конъюнкция; v — дизъюнкция; — отрицание, «неверно, что»; = — эквивалентность, «если и только если») данные два закона представляются формулами: q), неверно, что р и q, если и только если неверно р и неверно q;
11. Штрих Ше́ффера — бинарнаялогическая операция,булева функциянад двумя переменными. Введена в рассмотрениеГенри Шефферомв 1913 г. (вотдельных источниках именуется как Пунктир Чулкова) Штрих Шеффера, обычно обозначаемый /, эквивалентен операции И-НЕ и задаётся следующей таблицей истинности:
Закон поглощения для трех переменных
Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.
Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.
Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.
15 Мар 2023 uristinhome 221