Математические и логические основы информатики

Элементы логики высказываний

Под высказыванием мы будем понимать повествовательное предложение, относительно которого объективно можно сказать, что оно либо истинно, либо ложно.

Высказывания, подобные приведенным выше, называют простыми высказываниями. Они не могут быть «разложены» на более элементарные высказывания, относительно которых сохранилась бы объективная возможность оценить их истинность.

Из одних высказываний могут составляться (строиться) другие, более сложные высказывания. Такие высказывания мы будем называть составными, или сложными высказываниями.

В русском языке (и не только в русском) составные высказывания строятся из простых с помощью союзов (и, или), частицы (не) и словосочетаний (если…,то...;…тогда и только тогда, когда…; …если, и только если…;…необходимо и достаточно для… и т.д.)

Логические операции над высказываниями

Условимся обозначать простые высказывания большими буквами начала латинского алфавита: A, B, C (возможно с индексами: A1, A2, A3 и так далее), а значения истинности высказываний - буквами И (истина) и Л (ложь)[1]), которые называют логическими константами.

Определим операции над высказываниями, которые будут соответствовать союзам (и, или), частице не, словосочетаниям (если …, то …; …тогда и только тогда, когда ….; …если, и только если …; …необходимо и достаточно для… и т.д.) русского языка. Часто союзы, частицу не, указанные словосочетания называют связками. Соответствующие им операции называют логическими операциями, или логическими связками.

Союзу и соответствует операция конъюнкция, обозначаемая нами с помощью символа & и задаваемая таблицей:

A	B	A&B
Л	Л	Л
Л	И	Л
И	Л	Л
И	И	И

Обоснованием такого способа определения (задания) операции конъюнкции является то, что согласно интуитивному пониманию союза и, составное высказывание типа «A и B» истинно тогда и только тогда, когда истинны оба составляющих его высказывания, на что и указывает последняя строка таблицы. В остальных случаях конъюнкция двух высказываний ложна. Операция конъюнкции обозначается также с помощью символов Ù и × (точка). Иногда знак конъюнкции между высказывания опускают, подобно тому, как в обычной алгебре часто опускают знак операции умножения.

Союзу или соответствует операция дизъюнкция, обозначаемая нами с помощью символа Ú и задаваемая таблицей:

A	B	AÚB
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

Обоснованием такого способа определения (задания) операции дизъюнкции является то, что согласно интуитивному пониманию союза или, составное высказывание типа «A или B» ложно тогда и только тогда, когда ложны оба составляющие его высказывания, на что и указывает первая строка таблицы. В остальных случаях дизъюнкция двух высказываний истинна.

Приведенное определение операции дизъюнкции соответствует употреблению союза или в русском языке в так называемом соединительном смысле. Но часто этот союз употребляется в разделительном смысле, то есть понимается как «либо A, либо B, но не то и другое вместе». Такому пониманию союза или отвечает следующая таблица, определяющая операцию строгой дизъюнкции, обозначаемой с помощью символа Å:

A	B	AÅB
Л	Л	Л
Л	И	И
И	Л	И
И	И	Л

Частице не соответствует операция отрицания, обозначаемая символом и задаваемая таблицей:

A	A
Л	И
И	Л

То есть, высказывание A истинно, если высказывание A ложно, и наоборот, ложно, если A истинно.

Словосочетанию «если …, то …» соответствует операция, называемая материальной импликацией и обозначаемая символом É. Материальная импликация задается следующей таблицей:

A	B	AÉB
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

A называется антецедентом (или условием), B – консеквентом (или следствием) материальной импликации.

Определение материальной импликации (мы будем называть ее просто импликацией) весьма условно можно считать формализацией словосочетания «если …, то …». Дело в том, что словосочетание «если …, то …» выражает в языке не только логическую, но и причинно-следственную связь, которую материальная импликация выразить не может. И, тем не менее, это определение в значительной степени соответствует интуитивному пониманию словосочетания «если …, то …» в смысле логического следования. По крайней мере, высказывание, являющееся импликацией двух высказываний, ложно в том и только том случае, если мы из истины пытаемся сделать (или, как говорят, имплицировать, вывести) ложное заключение (третья строка таблицы).

Словосочетанию «…тогда и только тогда, когда …» (синонимы: «… если и только если …», «… эквивалентно…», «… необходимо и достаточно для …») соответствует логическая операция, называемая эквиваленцией и обозначаемая символом ~. Эквиваленция задается следующей таблицей:

A	B	A~B
Л	Л	И
Л	И	Л
И	Л	Л
И	И	И

То есть, эквиваленция двух высказываний истинна тогда и только тогда, когда высказывания либо оба ложны, либо оба истинны.

Примером эквиваленции двух высказываний является высказывание «Четырехугольник является квадратом тогда и только тогда, когда все его стороны и углы равны между собой».

Свойства логических операций

Для обозначения логической равносильности двух высказываний будем использовать символ º. Приведем здесь лишь свойства основных логических операций: конъюнкции, дизъюнкции и отрицания.

Свойства коммутативности

коммутативность конъюнкции: A&B º B&A,

коммутативность дизъюнкции: AÚB º BÚA.

Свойства ассоциативности

ассоциативность конъюнкции: A&(B&C) º (A&B)&C,

ассоциативность дизъюнкции: AÚ(BÚC) º (AÚB)ÚC.

Свойства дистрибутивности

дистрибутивность конъюнкции относительно дизъюнкции:

A&(BÚC) º (A&B) Ú(A&C),

дистрибутивность дизъюнкции относительно конъюнкции:

AÚ(B&C) º (AÚB)& (AÚC).

Свойства логических констант

свойства константы И: A&И º A, AÚИ º A;

свойства константы Л: A&Л º Л, AÚЛ º A.

Законы Де Моргана: (A&B) º AÚB, (AÚB) º A&ØB.

Закон исключенного третьего

(tertium non datur - третьего не дано): AÚA º И.

Закон противоречия: A&A º Л.

Закон снятия двойного отрицания: A º A.

Законы идемпотентности

идемпотентность конъюнкции: A&AºA,

идемпотентность дизъюнкции: AÚAºA.

Законы поглощения A&(AÚB)ºA, AÚ(A&B)ºA.

Используя теперь приведенные свойства и законы, можно осуществлять эквивалентные (тождественные) преобразования формул логики высказываний, подобно тому, как мы преобразовывали формулы теории множеств. Но прежде уточним некоторые понятия и определения.

Понятие формулы логики высказываний. Значение истинности формулы логики высказываний. Приоритет логических операций

Переменную, которая может принимать значения конкретных высказываний, будем называть пропозициональной переменной. Логические константы И, Л будем называть пропозициональными константами.

Истинностными значениями пропозициональных переменных являются пропозициональные константы И, Л.

Пропозициональные переменные будем обозначать буквами конца латинского алфавита X, Y, Z (возможно с индексами: X1, X2, X3 и так далее).

Дадим индуктивное определение формулы логики высказываний:

1.  Всякая пропозициональная константа и переменная есть формула логики высказываний.

2.  Если F, Ф – формулы логики высказываний, то следующие последовательности символов также будут формулами логики высказываний:

3.  Те и только те последовательности символов будут формулами логики высказываний, для которых это следует из пп.1 и 2 данного определения.[2])

Истинностным значением (или просто значением) формулы логики высказываний является значение истинности, получаемое при вычислении результатов всех логических операций, с помощью которых строится формула, при той или иной комбинации значений пропозициональных переменных и констант, входящих в формулу.

При вычислении значения формулы мы будем руководствоваться (как и в школьной алгебре) круглыми скобками (,) и следующим приоритетом (старшинством) операций:

-  отрицание (Ø),

-  конъюнкция (&),

-  дизъюнкция (Ú), строгая дизъюнкция (Å),

-  импликация (É),

-  эквиваленция (~).

Операции перечислены в порядке убывания приоритета: отрицание (Ø) имеет самый высокий приоритет, а эквиваленция (~) – самый низкий. Старшинство операций учитывается, если скобки не определяют однозначно порядок вычисления.

Вычисление значений истинности формул логики высказываний

Покажем на примерах как вычисляется значение истинности формул логики высказываний при заданных значениях истинности входящих в формулу пропозициональных переменных и констант. Для этого воспользуемся универсальным для логики высказываний методом – методом истинностных таблиц.

Прежде всего, заметим, что порядок вычисления значения истинности этой формулы определяется частично скобками, а частично старшинством операций. Этот порядок и вычисления в соответствии с ним представлены в таблице:

Результирующее значение И представлено в последней строке в столбце, соответствующем последней выполняемой операции отрицания Ø (в выделенной жирной линией клетке).

Предпоследнюю и последнюю строки в будущем будем объединять в одну, чтобы сократить размеры таблицы.

Тождественно-истинные и тождественно-ложные формулы логики высказываний. Логическая равносильность формул. Равносильные преобразования формул

Формулу логики высказываний, принимающую значение истинности И (истина) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-истинной формулой, или тавтологией.

Формулу логики высказываний, принимающую значение истинности Л (ложь) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-ложной формулой, или противоречием.

Формулу логики высказываний, не являющуюся ни тождественно-истинной, ни тождественно ложной, называют выполнимой.

Пусть формулы 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 по правилу modus tollens выводится формула Ø(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-кратное применение теоремы дедукции приведет к утверждению выводимости формулы

Применение логики высказываний к анализу математических

доказательств

Ни у кого не возникает сомнения в том, что математические доказательства являются примерами строгих логических рассуждений.

Аппарат логики высказываний позволяет нам прояснить структуру доказательств многих математических утверждений.

Рассмотрим с точки зрения логики высказываний наиболее типичные методы доказательств в математике.