Результирующее значение И представлено в последней строке в столбце, соответствующем последней выполняемой операции отрицания Ø (в выделенной жирной линией клетке).
Предпоследнюю и последнюю строки в будущем будем объединять в одну, чтобы сократить размеры таблицы.
Тождественно-истинные и тождественно-ложные формулы логики высказываний. Логическая равносильность формул. Равносильные преобразования формул
Формулу логики высказываний, принимающую значение истинности И (истина) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-истинной формулой, или тавтологией.
Формулу логики высказываний, принимающую значение истинности Л (ложь) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-ложной формулой, или противоречием.
Формулу логики высказываний, не являющуюся ни тождественно-истинной, ни тождественно ложной, называют выполнимой.
Пусть формулы F и Ф логики высказываний содержит пропозициональные переменные X1, X2, … , Xn. Будем считать эти формулы логически равносильными, если они принимают одинаковые значения истинности на соответствующих наборах значений для пропозициональных переменных X1,X2,…,Xn, входящих в эти формулы.
Если множества пропозициональных переменных, входящих в формулы F и Ф не совпадают, то можно добиться этого совпадения, введя в ту или другую формулу недостающую переменную в качестве "фиктивной". Пусть, например, формула F не содержит пропозициональной переменной Xi. Тогда эту переменную можно ввести в формулу F "фиктивно", заменив формулу F на формулу FÚ( Xi&ØXi) или на формулу F&( XiÚØXi), которые на основании закона противоречия, закона исключенного третьего и свойств логических констант Л и И, равносильны F. Аналогично можно "фиктивно" ввести в формулы F и Ф все другие недостающие переменные. Это соображение легко распространить на любое число формул.
Как мы условились выше, тот факт, что формулы F и Ф логически равносильны будем обозначать FºФ.
Отношение равносильности формул, очевидно, обладает свойством транзитивности: если FºФ и ФºY, то FºY.
Приведенные выше свойства операций и законы логики высказываний, как легко проверить с помощью таблиц истинности, выражают логическую равносильность (эквивалентность) тех или иных формул.
Кроме приведенных выше равносильностей в логике высказываний большое значение имеют и другие, среди которых отметим следующие:
Логические равносильности играет важную роль в логике высказываний. Они фактически являются правилами и законами логических рассуждений, законами правильного мышления.[3]) Ниже мы покажем их применение, например, к анализу структуры математических доказательств.
На основании перечисленных выше равносильностей, к которым относятся свойства логических операций, логические законы и т.д., осуществляются равносильные (тождественные) преобразования формул логики высказываний с целью упрощения выражений или приведения к определенному виду (подобно тому, как это делается в школьной алгебре на основании свойств арифметических операций, алгебраических законов и иных тождественных соотношений).
Вывод следствий в логике высказываний
Пусть дана совокупность формул логики высказываний F={F1,F2,F3,…,Fm}. Формулы множества F называют посылками (или гипотезами). Определим понятие логического вывода формулы Ф из множества посылок (гипотез) F.
Вначале определим содержательно понятие логического следствия.
Будем говорить, что формула Ф является логическим следствием множества формул F1,F2,F3,…,Fn, если формула F1&F2&F3&…&FnÉФ является тождественно-истинной (или тавтологией).
Например, формула X является логическим следствием формул (ØXÉY) и (ØXÉØY), поскольку формула (ØXÉY)&(ØXÉØY)ÉX тождественно истинна, в чем легко убедиться с помощью таблицы истинности:
Ясно, что если две формулы равносильны, то каждая из них является логическим следствием другой.
Построение логического вывода некоторой формулы основывается на применении в процессе вывода специальных правил, называемых правилами вывода
Наиболее часто используются следующие правила вывода:
1. Правило замены формулы равносильной. В процессе вывода в любой момент любую формулу (или подформулу) можно заменить равносильной ей формулой.
Например, формулу Ø(AÚB) в любой момент можно заменить равносильной ей формулой ØA&ØB (второй закон Де Моргана), а формулу AÚØA- пропозициональной константой И (закон исключенного третьего).
2. Правило подстановки. Если в формулу F вместо всех вхождений пропозициональной переменной Xi подставить одну и ту же формулу F, то полученная в результате формула будет логическим следствием формулы F.
3. Правило modusponens. Это правило позволяет из двух формул X и XÉY выводить третью формулу Y.
4. Правило modustollens. Это правило формулируется так: из формул X&Y и ØY выводится формула ØX.
Формула ØX является логическим следствием формул X&Y и ØY в смысле приведенного выше определения, поскольку формула ((X&Y)&ØY)ÉØX является тождественно-истинной (тавтологией), в чем можно убедиться с помощью следующей таблицы истинности:
Например, из формул (AÚB)&C и ØC по правилу modustollens выводится формула Ø(AÚB).
Итак, можно следующим образом более формально определить понятие логического вывода (и логического следования):
Логическим выводом (или просто, выводом) формулы Ф из множества посылок (гипотез) F={F1, F2, F3, … , Fm} называют последовательность формул вида: Ф1,Ф2,…,Фi-1,Фi,…,Фn=Ф, таких, что либо Фi - тавтология, либо ФiÎF, либо Фi является конъюнкцией формул из F, либо Фi получена из формул множества F, или тавтологий логики высказываний, или ранее выведенных в данном выводе формул Ф1, Ф2, …,Фi-1 с помощью правил вывода.
Формулу Ф будем называть в этом случае логическим следствием множества формул F={F1,F2,F3,…, Fm}.
Тот факт, что формула Ф выводима из множества посылок F={F1,F2,F3,…, Fm} будем обозначать: F1,F2,F3,…, Fm|¾ Ф.
Заметим, что в соответствии с определением вывода все тавтологии логики высказываний считаются выводимыми формулами, притом из пустого множества посылок, то есть, если A - тавтология, то |¾A.
Примем без доказательства следующую теорему, которая называется теоремой дедукции.
Теорема дедукции:
Если F1,F2,F3,…, Fm|¾ Ф, то F1,F2,F3,…, Fm-1 |¾ (FmÉФ), и наоборот.
Эта теорема говорит о возможности переноса формул логики высказываний через знак выводимости |¾.
Замечание: m-кратное применение теоремы дедукции приведет к утверждению выводимости формулы
Применение логики высказываний к анализу математических
Ни у кого не возникает сомнения в том, что математические доказательства являются примерами строгих логических рассуждений.
Аппарат логики высказываний позволяет нам прояснить структуру доказательств многих математических утверждений.
Рассмотрим с точки зрения логики высказываний наиболее типичные методы доказательств в математике.
1. Доказательство с помощью построения цепочки импликаций.
Этим методом пользуются при доказательстве теорем, выраженных в форме импликации: "Если высказывание A истинно, то и высказывание B истинно", то есть AÉB.
Доказательство строится как последовательность тождественно-истинных импликаций вида: AÉA1, A1ÉA2, … , An-1ÉAn, AnÉB, где A1, A2, A3, … , An- некоторые вспомогательные высказывания.
Отсюда делается вывод (в силу транзитивности импликации) о справедливости теоремы AÉB.
Такое доказательство называется прямым доказательством.
Прежде, чем рассмотреть другие типы доказательств напомним классификацию теорем из средней школы, которую иллюстрирует рис.2.1
Как легко проверить, используя метод истинностных таблиц, прямая теорема оказывается равносильной обратной противоположной, а обратная теорема - противоположной. И в то же время, таких равносильностей в общем случае не существует между прямой и обратной теоремами, между прямой и противоположной, между обратной и обратной противоположной, между противоположной и обратной противоположной.
Из указанных равносильностей вытекает следующий метод доказательства.
2. Доказательство от противного.
Этот метод используется при доказательстве теорем вида AÉB и основывается на законе контрапозиции XÉYºØYÉØX, который фактически гласит, что доказательство теоремы AÉB может быть заменено доказательством эквивалентной ей теоремы, которая формулируется как ØBÉØA . Последняя теорема называется обратная противоположной (или противоположная обратной).
Доказательство теоремы ØBÉØA осуществляется прямым путем, то есть как цепочка импликаций: ØBÉB1, B1ÉB2, …, Bn-1ÉBn, BnÉØA, из которой делается вывод (в силу транзитивности импликации) о справедливости теоремы ØBÉØA. А в силу закона контрапозиции заключается о справедливости теоремы AÉB.
3. Доказательство приведением к абсурду.
Пусть требуется доказать истинность некоторого утверждения A. Предположим, что A ложно, тогда ØA - истинно, поскольку закон противоречия (X&ØXºЛ), имеющий место в логике высказываний, означает, что одновременно не могут быть истинными утверждение и его отрицание.
После этого показывается, что тогда имеется некоторое утверждение B такое, что истинными являются одновременно два утверждения: ØAÉB и ØAÉØB.[4]) Это и есть то, что называют абсурдом.
В логике высказываний тождественно-истинной является формула: (ØAÉB)&(ØAÉØB) ÉA (проверку чего мы предоставляем читателю).