Продолжим рассмотрение раздела «Логика высказываний». Ознакомиться с основными понятиями этого раздела можно по ссылкам:
В этой лекции будет представлен перечень различных законов логики высказываний, а также рассмотрена методика получения формул логики высказываний по заданной таблице истинности.
В результате изучения этой лекции предполагается, что обучающийся ознакомится законами, позволяющими производить эквивалентные преобразования, например, приводящие к сокращению записи формулы.
Законы логики высказываний.
В предыдущей лекции (https://zen.yandex.ru/media/id/603a418d1684900aa2499416/logika-vyskazyvanii-postroenie-tablic-istinnosti-6239460b8d70de4bf0b7ac3f ) было сформулировано понятие «Таблица истинности» и представлены таблицы истинности рассмотренных ранее логических операций.
В этой лекции будут представлены часто использующиеся законы логики высказываний, а также рассмотрены некоторые специальные формулы логики высказываний.
В таблице ниже представлены Законы, которые содержат базовые логические операции: логическое отрицание, логическую конъюнкцию и логическую дизъюнкцию. Пусть P, Q, R – произвольные высказывания логики высказываний, тогда справедливы следующие законы: законы коммутативности (они же называются переместительными законами), законы ассоциативности (они же называются сочетательными законами), и законы дистрибутивности (также они называются распределительными законами).
Законы коммутативности и ассоциативности также выполняются и в случае рассмотрения логических операций: эквивалентность, «исключающее или», Штрих Шеффера и Стрелка Пирса.
Относительно коммутативности можно вспомнить стихотворение Бориса Заходера «Вопросительная песенка», текст стихотворения приведён на рис. ниже.
На рисунке ниже в таблице представлены Законы, которые также содержат базовые логические операции: логическое отрицание, логическую конъюнкцию и логическую дизъюнкцию. Пусть P, Q, R – произвольные высказывания логики высказываний, тогда справедливы следующие законы: законы идемпотентности, законы поглощения, закон двойного отрицания и законы расщепления.
На рисунке ниже (в теореме 2) показаны законы, которые позволяют выражать одни логические операции через другие, особенно важными являются законы, которые выражают импликацию, эквивалентность и логическую операцию «исключающее или» через базовые операции: логическое отрицание, логическую конъюнкцию и логическую дизъюнкцию.
Пусть P, Q и R – произвольные высказывания логики высказываний, тогда справедливы следующие законы. Перечень законов будет представлен на рисунке ниже. Обратите внимание на указанные законы де Моргана, они часто применяются для приведения сложных формул логики высказываний к упрощённому виду.
В перечне ниже представлены законы, выражающие одни логические операции через другие, а именно через Штрих Шеффера в левой части таблицы, и Стрелку Пирса – в правой части таблицы.
Прежде, чем перейти к следующей группе законов логики высказываний сформулируем пару определений.
Для того чтобы построить противоречие из тавтологии, необходимо взять отрицание тавтологии.
Ниже представлены некоторые примеры формул логики высказываний, являющихся тавтологиями.
Сформулируем в виде теоремы законы логики высказываний, использующие понятия тавтологии и противоречия.
Итак, для любого высказывания P справедливо, что конъюнкция высказывания P с тавтологией даёт в результате само высказывание P.
Конъюнкция высказывания Pс противоречием даёт в результате противоречие.
Также выполняется, что для любого высказывания P дизъюнкция высказывания P с тавтологией даёт в результате тавтологию, а дизъюнкция высказывания P с противоречием даёт в результате само высказывание P.
Также ниже показаны закон противоречия, заключающийся в том, что конъюнкция высказывания P и его отрицания даёт в результате противоречие, а также записан закон исключенного третьего, согласно которому дизъюнкция высказывания P и его отрицания даёт в результате тавтологию. Итак, на формальном языке эти законы записываются как показано на картинке далее.
Составление формулы по заданной таблице истинности.
Рассмотрим важную тему, связанную с построением формул логики высказываний по заданной таблице истинности.
Сформулируем сначала несколько определений.
Итак, рассмотрим первый способ составления формулы по заданной таблице истинности. В результате использования этого способа получается формула в виде дизъюнктивной нормальной формы, т.е. представляет собой дизъюнкцию элементарных конъюнкций.
Рассмотрим второй способ составления формулы по заданной таблице истинности.
В результате использования этого способа получается формула в виде конъюнктивной нормальной формы, т.е. представляет собой конъюнкцию элементарных дизъюнкций.
Перед рассмотрением практического примера отметим ещё пару определений.
Для примера рассмотрим таблицу истинности, как показано на картинке ниже.
Сначала выберем строки, где значения F(x, y, z) = 1, это строки с номерами 2, 3 и 6.
Следовательно, совершенная дизъюнктивная нормальная форма будет состоять из 3 слагаемых, при этом в каждом слагаемом будет три переменных x, y, z (2, 3 и 4 столбцы). Можно сразу сделать заготовки формул, как показано внизу картинки.
Аналогичную заготовку делаем для совершенной конъюнктивной нормальной формы, она будет состоять из 5 слагаемых, потому что значений в заданной таблице истинности, равных нулю, ровно 5.
Далее навешиваем отрицания: в СДНФ по правилу: если переменная в соответствующей строке имеет ложное значение, то в соответствующем слагаемом она записывается с отрицанием, в СКНФ наоборот.
Получается соответствующий результат (показан ниже).
Таким образом, по любой таблице истинности можно записать формулу с виде СДНФ или СКНФ, после этого, воспользовавшись законами логики высказываний, произвести эквивалентными преобразования для сокращения формулы.
В качестве Упражнений предлагаются следующие варианты.
Упражнение 1.
В комментариях запишите закон логики высказываний, который не упомянут в лекции, естественно, хотелось бы, чтобы законы не повторялись. Обратите внимание, что для выполнения этого Упражнения перспективно рассмотреть законы, относящиеся не к базовым логическим операциям.
Упражнение 2.
Предлагается взять дату написания комментария, число и месяц, сложить два значения, результат перевести в двоичную систему счисления, далее перед получившимся числом в двоичной системе счисления заполнить нулями до восьмизначного числа, затем для этого восьмизначного числа необходимо записать СДНФ и СКНФ.
Например, для 30 марта СДНФ будет состоять из 2 слагаемых, поскольку имеется две единицы в таблице истинности, а СКНФ– соответственно из шести (см. рис. ниже).
Упражнение 3.
Запишите в комментарий под видео СДНФ и СКНФ для следующих формул (по вариантам).