3. Элементы математической логики

3.1. Моделирование высказываний

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

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

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

В математической логике элементарные высказывания моделируются элементами некоторого произвольного (непустого) множества М. Будем называть М множеством элементарных высказываний, а его элементы – элементарными высказываниями, и обозначать, как это принято в математической логике, большими латинскими буквами (иногда с индексами). При анализе способов построения сложных высказываний в разговорной речи можно выделить основные связки: «не», «и», «или», «если ..., то...», «тогда и только тогда» и др. В математической модели им соответствует некоторое множество, элементы которого называются логическими (пропозициональными) связками. Множество логических связок включает в себя следующие связки:

– отрицание («не»),

& – конъюнкция («и»),

 – дизъюнкция («или»),

 – импликация («если ..., то ...»),

 – эквивалентность («тогда и только тогда»).

Кроме того, в математической логике используются и другие связки в частности,  – квантор всеобщности («каждый», «любой», «всякий»),  - квантор существования («существует», «найдется»). Множество элементарных высказываний и множество логических связок никогда не пересекаются.

Заметим, что в литературе встречаются другие обозначения логических связок. Например, конъюнкцию обозначают «», импликацию – «», а эквивалентность – «».

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

Определение 1 Множество Ф является множеством логических формул, если выполняются следующие условия:

1) всякое элементарное высказывание есть формула, т.е. М  Ф;

2) если F₁ и F₂ – формулы (F₁,F₂Ф), то (F₁), (F₁&F₂), (F₁F₂),

(F₁ -F₂), (F₁ F₂) – формулы;

3) других формул нет.

Пример 1. Записать в виде логической формулы следующее предложение: «если целое число не делится на два, то оно нечетное».

Введем обозначения для элементарных высказываний: А – «целое число делится на два», В – «оно (целое число) нечетное». Тогда сложное предложение описывается формулой: ((А)В). При составлении формулы мы точно следовали определению 1. Действительно, так как А и В –элементарные высказывания, то они формулы (условие 1) определения 1, следовательно по условию 2) формулами являются выражения (А) и ((А)В). Однако, записи (АВ), (А)В нельзя назвать формулами, согласно определению 1, так как в первой не заключено в скобки высказывание (А), а во второй – целиком все высказывание ((А)В). Это противоречит условию 3) определения 1.

Данный пример показывает, что при записи логических формул нужно соблюдать формальные правила, сформулированные в определении 1. Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Кроме того, можно опускать внешние скобки.

Например, формула F = (A((С(A&B)))), учитывая принятые соглашения, может быть записана следующим образом

F = A((СA&B)).

3.2. Таблицы истинности

Рассмотрим высказывания с точки зрения их истинностных значений. В содержательной логике под высказыванием подразумевается повествовательное предложение, о котором можно определенно сказать истинно оно или ложно. Например, предложение «квадрат является ромбом» – высказывание, причем истинное, а предложение «рассмотрим множество всех функций» высказыванием не является, так как нельзя с определенностью утверждать, истинно оно или ложно. Таким образом, в нашей математической модели каждое элементарное высказывание нужно рассматривать как переменную величину (пропозиционную переменную), которая принимает только два значения «истина» и «ложь». Значение «истина» принято обозначать через единицу 1, а «ложь» – через ноль 0. Итак, всякое элементарное высказывание (пропозиционная переменная) формально может принимать одно из значений: 1 или 0.

Формулы логики высказываний, которые мы определили выше, являются высказываниям и, следовательно, тоже должны принимать одно из истинностных значений. Для формул, которые являются таковыми по условию 1) (элементарные высказывания), мы уже приняли соглашения. Чтобы определить истинностное значение любой формулы, которая не является элементарным высказыванием, нужно, прежде всего, определить значения формул: (А), (А&В), (А В), (А В), (А В) в зависимости от значений входящих в них элементарных высказываний. Это делается с помощью так называемых таблиц истинности.

Таблица истинности.

Таблица 1.

А	В	(А)	(А&В)	(АВ)	(АВ)	(АВ)
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Из определения формулы следует, что с помощью таблицы истинности можно определить истинностные значения любой формулы. Ясно, что, если формула содержит n элементарных высказываний, то она имеет 2ⁿ значений, т.е. таблица истинности этой формулы содержит 2ⁿ строк. Рассмотрим пример построения таблицы истинности для логической формулы.

Пример 2. Найти истинностные значения формулы

F=((AB)((A)&B)).

Убедимся, что F формула. По определению 1 (условие 2) высказывания (A), (A B) являются формулами. Тогда в силу этого же условия формулами являются ((A)&B) и F = ((AB)((A)&B)). Рассмотренные нами выше составные части формулы F, которые сами являются формулами, называются подформулами формулы F.

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

Таблица 2.

А	В	(А)	(АВ)	((А)&В)	((АВ)((А)&В))
0	0	1	1	0	0
0	1	1	0	1	1
1	0	0	0	0	1
1	1	0	1	0	0

Логические связки: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность можно рассматривать как функции, которые определены на двухэлементном множестве В={0,1} со значениями в этом же множестве. Их называют логическими (булевыми) функциями или операциями. Операция отрицания – унарная, а все остальные – бинарные. Таблицу истинности для каждой из операций можно рассматривать как определение этой операции.

3.3. Равносильные формулы

Рассмотрим таблицы истинности для двух формул F=AB и Н=(A)B.

Таблица 3.

А	В	(А)	АВ	(А)В
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

Из таблицы 3 видно, что при всех наборах значений элементарных высказываний А и В формулы F и Н принимают одинаковые значения.

Определение 2 Две логические формулы F и H называются равносильными, если они принимают одинаковые значения на любом наборе значений входящих в них элементарных высказываний.

Тот факт, что формулы F и H равносильны, обозначают F = H.

Таким образом, с помощью таблицы 3 установлена равносильность

AB = (A)B (1)

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

Определение 3 Формула А называется тавтологией (тождественно- истинной формулой), если при любых значениях входящих в нее переменных она принимает значение «истина» (А = 1).

С помощью таблицы истинности тавтологию можно определить как формулу, для которой соответствующий ей в таблице истинности столбец целиком состоит из 1. Таким образом, построение таблицы истинности это эффективная процедура для решения вопроса о том, является ли данная формула тавтологией.

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

Из определения конъюнкции легко получаем, что формула &() всегда принимает значение 0 («ложь»). Тогда формула (&()) принимает только одно значение – 1 («истина»), т.е. является тавтологией.

Мы встретились с формулой &(), которая всегда принимает ложное значение. Такие формулы называют тождественно-ложными формулами (противоречиями). Очевидно, что формула А является тавтологией тогда и только тогда, когда формула () – противоречие.

Сформулируем несколько утверждений общего характера о тавтологиях.