Учебное пособие: Математические и логические основы информатики
Формулу логики высказываний, не являющуюся ни тождественно-истинной, ни тождественно ложной, называют выполнимой.
Пусть формулы 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. Правило modus ponens . Это правило позволяет из двух формул X и XÉY выводить третью формулу Y.
4. Правило modus tollens . Это правило формулируется так: из формул 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.
Примем без доказательства следующую теорему, которая называется теоремой дедукции.