Понятие высказывания; логические операции над высказываниями

ЧАСТЬ I. АЛГЕБРА ВЫСКАЗЫВАНИЙ §1. Понятие высказывания. Логические операции над высказываниями. Понятие «высказывания» является основным (неопределяемым) понятием математической логики. Под высказыванием понимают всякое повествовательное предложение, относительно которого мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь». Приведем примеры высказываний: 1) «Число - четное» 2) «Число делится на » 3) «< » 4) «Пифагор – математик» 5) «Самара – город на Днепре» 6) «Собака – животное» Высказывания - истинны, а высказывания - ложны. Будет обозначать конкретные высказывания начальными заглавными буквами латинского алфавита а их значения, то есть истину и ложь, соответственно И и Л или 1 и 0. В алгебре высказываний все высказывания рассматриваются только с точки зрения их логического значения, а от их содержания отвлекаются. Считается, что любое высказывание либо истинно, либо ложно и ни одно высказывание не является одновременно истинным и ложным. Высказывания, представляющие собой одно утверждение, принято называть простыми или элементарными. Примерами элементарных высказываний являются высказывания . Высказывания, которые получаются из элементарных с помощью логических связок принято называть сложными или составными. Например: «Число 2 – четное и число 10 делится на 5», «Если Пифагор – математик, то Самара – город на Днепре». Логические операции над высказываниями. Конъюнкция. Конъюнкцией двух высказываний и называется высказывание, которое истинно тогда и только тогда, когда высказывания и истинны. Конъюнкцию высказываний и обозначают & или читают Высказывания и называют членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей. Таблицы такого рода называются таблицами истинности. Например, для высказываний : : их конъюнкцией будет высказывание которое, очевидно, истинно. Дизъюнкция. Дизъюнкцией двух высказываний и называется высказывание, которое истинно тогда и только тогда, когда хотя бы одно из высказываний или истинно. Дизъюнкцию высказываний и обозначают , читают Высказывания и называют членами дизъюнкции. Логические значения дизъюнкции описываются следующей таблицей истинности: Например, для высказываний и их дизъюнкцией будет высказывание которое, очевидно, истинно. Импликация. Импликацией двух высказываний и называется высказывание, которое ложно тогда и только тогда, когда высказывание истинно, а высказывание ложно. Импликацию высказываний и обозначают , читают или Высказывание называют условием или посылкой импликации, а выказывание - следствием или заключением. Логические значения импликации описываются следующей таблицей истинности: Например, для высказываний и их импликацией будет высказывание которое, очевидно, ложно, так как высказывание истинно, а высказывание ложно. Отрицание. Отрицанием высказывания называется такое высказывание, которое истинно, если высказывание ложно, и ложно, если высказывание истинно. Отрицание высказывания обозначают или , читают или Логические значения высказывания описываются следующей таблицей истинности: Например, для высказывания его отрицанием является высказывание или , которое, очевидно, является ложным. Эквиваленция. Эквиваленцией двух высказываний и называется такое высказывание, которое истинно тогда и только тогда, когда высказывания и либо одновременно истинны, либо одновременно ложны. Эквиваленцию высказываний и обозначают , читают Высказывания и называют членами эквиваленции. Логические значения эквиваленции описываются следующей таблицей истинности: Например, для высказываний их эквиваленцией является высказывание тогда и только тогда, когда , которое, очевидно, является истинным. § 2.Формулы алгебры высказываний. Равносильные формулы. Определение. Переменные, вместо которых можно подставить высказывания, называются пропозиционными переменными или переменными высказываниями. Пропозиционные переменные будем обозначать заглавными буквами конца латинского алфавита Определение формулы алгебры высказываний. 1. Каждая пропозиционная переменная есть формула алгебры высказываний. 2. Если и - формулы алгебры высказываний, то выражения , также являются формулами алгебры высказываний. 3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет. Формулы алгебры высказываний будем обозначать Приведем примеры формул . Формулами алгебры высказываний являются выражения Выражения формулами не являются. Для упрощения записи формул примем следующие соглашения. Внешние скобки в окончательной записи формул можно опустить. Будем считать, что конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквиваленция, импликация выполняется раньше, чем эквиваленция. Если над формулой стоит знак отрицания, то скобки можно опустить. В связи с этим формула может быть записана так: Логическое значение формулы алгебры высказываний полностью определяется логическими значениями входящих в нее переменных высказываний. Все возможные логические значения формулы, в зависимости от значений входящих в нее переменных высказываний, могут быть описаны полностью с помощью таблицы истинности. Например, для формулы таблица истинности имеет вид: Равносильные формулы алгебры высказываний. Определение. Две формулы алгебры высказываний и называются равносильными, если они принимают одинаковые значения на любом наборе значений переменных высказываний, входящих в эти формулы. Тот факт, что формулы и равносильны, будем обозначать Основные равносильности алгебры высказываний. 1. закон двойного отрицания 2. коммутативность конъюнкции коммутативность дизъюнкции 3. ассоциативность конъюнкции ассоциативность дизъюнкции 4. дистрибутивность конъюнкции относительно дизъюнкции дистрибутивность дизъюнкции относительно конъюнкции 5. законы идемпотентности 6. законы де Моргана 7. закон противоречия закон исключенного третьего 8. 9. 10. законы поглощения Равносильности, выражающие импликацию и эквиваленцию через другие логические операции 11. 12. . Докажем один из законов де Моргана с помощью таблицы истинности. Из таблицы видно, что формулы и принимают одинаковые значения при всех значениях переменных высказываний, входящих в эти формулы. Это означает, что . Докажем первый дистрибутивный закон с помощью таблицы истинности. Из таблицы видно, что формулы и принимают одинаковые значения при всех значениях переменных высказываний, входящих в эти формулы. Это означает, что . Равносильности указывают, что операции и коммутативны и ассоциативны, как обычные умножение и сложение. Первая из равносильностей указывает, что операция дистрибутивна относительно операции , как обычное умножение дистрибутивно относительно сложения. В силу этой аналогии мы будем операцию называть умножением, а операцию - сложением. Выражение будем называть логическим произведением. Знак иногда опускают. Выражение будем называть логической суммой. Равносильные преобразования формул алгебры высказываний. Используя основные равносильности можно формулу заменить равносильной ей формулой. Такие преобразования формулы называются равносильными. Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул. Упражнения. 2.1. Доказать равносильность . Используя равносильности и получаем: Используя равносильность получаем . Используя равносильности получаем: Этот результат получили, используя равносильность 2.2. Упростить формулу Опустив знак и используя равносильность , получаем Используем равносильности По закону де Моргана и равносильности получаем . Закон двойственности Будем рассматривать формулы, содержащие только операции . Если формула содержит операции и то эти операции, как показано выше, можно выразить через и . Определение. Операция называется двойственной операции , а операция двойственной операции . Формулы и называются двойственными, если одна получается из другой заменой каждой операции на двойственную. Например, формула двойственна формуле а формула двойственна формуле Теорема (Закон двойственности). Если формулы и равносильны, то и двойственные им формулы и также равносильны. В приведенном выше примере (первый дистрибутивный закон), по закону двойственности (второй дистрибутивный закон). Основные равносильности 2-10 представляют собой пары равносильных формул и равносильных двойственных им формул. § 3. Проблема разрешения. Нормальные формы формул алгебры высказываний. Формулы алгебры высказываний подразделяются на типы: выполнимые, тождественно истинные, тождественно ложные. Определение. Формула алгебры высказываний называется тождественно истинной или тавтологией, если она принимает значение при всех значениях входящих в нее переменных высказываний. Для обозначения тавтологии используется знак ╞ , который ставится перед формулой, являющейся тавтологией. Примерами тавтологий являются формулы: Определение. Формула алгебры высказываний называется выполнимой, если она принимает значение хотя бы на одном наборе значений входящих в нее переменных высказываний. Выполнимыми являются формулы: Определение. Формула алгебры высказываний называется тождественно ложной или противоречием, если она принимает значение при всех значениях входящих в нее переменных высказываний. Тождественно ложными являются формулы: Можно поставить следующую задачу: указать единый способ (алгоритм), позволяющий для каждой формулы алгебры высказываний выяснить, является ли формула тождественно истинной, выполнимой, тождественно ложной. Поставленная задача, носит название проблемы разрешения. Очевидно, проблема разрешения алгебры высказываний разрешима. Для каждой формулы алгебры высказываний может быть составлена таблица истинности, которая дает ответ на поставленный вопрос. Пример. Выяснить, какой является формула . Составим для данной формулы таблицу истинности Данная формула тождественно истинная. Однако практическое использование таблицы истинности для формулы при больших затруднительно. Существует другой способ, основанный на приведении формул к так называемой «нормальной форме». Определение. Элементарной конъюнкцией называется конъюнкция переменных высказываний или их отрицаний. Элементарными конъюнкциями являются формулы: . Определение. Элементарной дизъюнкцией называется дизъюнкция переменных высказываний или их отрицаний. Элементарными дизъюнкциями являются формулы: Теорема. (Критерий тождественной истинности элементарной дизъюнкции) Для того, чтобы элементарная дизъюнкция была тождественно истинна, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть отрицание другого. Например, элементарные дизъюнкции являются тождественно истинными, а элементарная дизъюнкция тождественно истинной не является. Теорема. (Критерий тождественной ложности элементарной конъюнкции) Для того, чтобы элементарная конъюнкция была тождественно ложна необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара множителей, из которых один является отрицанием другого. Например, элементарные конъюнкции являются тождественно ложными, а элементарная конъюнкция тождественно ложной не является. Определение. Конъюнктивной нормальной формой (КНФ) формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций. Примерами КНФ являются формулы Определение. Дизъюнктивной нормальной формой (ДНФ) формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций. Примерами ДНФ являются формулы Для каждой формулы алгебры высказываний путем равносильных преобразований можно получить ее КНФ, причем не единственную, а также ее ДНФ, также не единственную. Схема составления КНФ, ДНФ для формулы алгебры высказываний. 1. Избавиться от импликации и эквиваленции . 2. Отрицание отнести к переменным высказываниям по законам де Моргана . 3. Раскрыть скобки по первому дистрибутивному закону или заключить в скобки по второму дистрибутивному закону Теорема. (Критерий тождественной истинности формулы) Для того, чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы каждый множитель ее КНФ содержал хотя бы одну пару слагаемых, из которых одно есть отрицание другого. Например, формула является тождественно истинной, а формула тождественно истинной не является. Теорема. (Критерий тождественной ложности формулы) Для того, чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы каждое слагаемое ее ДНФ содержало хотя бы одну пару множителей, из которых один является отрицанием другого. Например, формула является тождественно ложной, а формула тождественно ложной не является. Сформулированные критерии дают полное решение проблемы разрешения. Действительно, применим к данной формуле критерий тождественной истинности. Если окажется, что формула тождественно истинна, то задача решена. Если окажется, что формула не тождественно истинная, то применим к ней критерий тождественной ложности. Если формула тождественно ложная, то задача решена. Если же формула не тождественно ложная, то формула выполнима. § 4 Совершенные нормальные формы Среди множества ДНФ (равно как и КНФ), которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственная для данной формулы. Это так называемая совершенная ДНФ (среди КНФ – совершенная КНФ). Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы от переменных называется ее дизъюнктивная нормальная форма, обладающая свойствами: а) в ней нет двух одинаковых слагаемых; б) ни одно слагаемое не содержит двух одинаковых множителей; с) никакое слагаемое не содержит переменой вместе с ее отрицанием; д) в каждом слагаемом содержится в качестве множителя либо переменная либо ее отрицание, где Можно доказать, что каждая не тождественно ложная формула имеет единственную, с точностью до порядка расположения множителей и слагаемых СДНФ. Пример. есть СДНФ. Схема составления СДНФ для формулы алгебры высказываний. Пусть дана формула , не являющаяся тождественно ложной. 1. Составим для формулы любую ДНФ 2. Если слагаемое не содержит переменную , то заменим на сумму двух слагаемых . 3. Если в полученной ДНФ формулы есть два одинаковых слагаемых , то лишнее нужно отбросить, так как . 4. Если в некоторое слагаемое переменная входит дважды, то лишнюю переменную нужно отбросить, так как . 5. Если некоторое слагаемое содержит конъюнкцию , то это слагаемое нужно отбросить, так как , а следовательно, а ложное слагаемое из дизъюнкции можно отбросить. Определение. Совершенной конъюнктивной нормальной формой (СКНФ) формулы от переменных называется ее конъюнктивная нормальная форма, обладающая свойствами: а) в ней нет двух одинаковых множителей; б) ни один множитель не содержит двух одинаковых слагаемых; с) ни один множитель не содержит переменной вместе с ее отрицанием; д) каждый множитель содержит в качестве слагаемого или отрицание где есть СКНФ. Можно доказать, что каждая не тождественно истинная формула имеет единственную, с точностью до порядка расположения множителей и слагаемых, СКНФ. Схема составления СКНФ для формулы алгебры высказываний. Пусть дана формула , не являющаяся тождественно истинной. 1) Составим для формулы любую КНФ. 2) Если множитель не содержит переменную то заменим на произведение двух множителей 3) Удалим лишние слагаемые и множители аналогично тому, как это делали при составлении ДНФ.