Основы математической логики

Логика - это наука о способах доказательств и опровержений (название происходит от греческого слова “логос” - разум, мысль). Основоположником логики является Аристотель (древнегреческий учёный-философ IV в. до нашей эры). Он изложил в виде стройной системы имевшиеся к тому времени результаты исследований о законах и формах мышления, чётко сформулировал некоторые законы логики, исследовал и описал основные виды понятий, суждений и умозаключений, а также изложил начало теории доказательств. Логика, созданная им, называется в настоящее время формальной или аристотелевской. Математическая (или символическая) логика возникла в результате применения математических методов и специального символического языка к формальной логике. В настоящее время математическая логика представляет собой самостоятельный раздел математики, имеющий важное теоретическое и прикладное значение (в математике, кибернетике, информатике, лингвистике и т.д.).

13. Понятие высказывания, операции над высказываниями

Основным понятием математической логики является понятие высказывания. Под высказыванием понимают повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно. Высказываниями не являются определения, вопросительные и восклицательные предложения, а также субъективные суждения. Например, предложения «В России проживает 256 млрд. человек», «17<3», «сегодня пасмурно», «треугольник правильный, если все его стороны равны» являются высказываниями, а предложения «сегодня плохая погода», «треугольник называется правильным, если все его стороны равны», «Вам нравится это стихотворение?» высказываниями не являются. Как правило, высказывания обозначают большими буквами латинского алфавита. В логике отвлекаются от содержательной стороны высказываний, ограничиваясь рассмотрением их значений истинности (истинностных значений). Если высказывание А истинно, то ему приписывают истинностное значение И (или 1) и пишут [А]=И, а если ложно – истинностное значение Л (или 0) и пишут [А]=Л. Никакое высказывание не может быть одновременно и истинным, и ложным.

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

Определение 1. Отрицанием высказывания А называется такое высказывание, обозначаемое или (читается «не А», «неверно, что А» ), которое истинно тогда и только тогда, когда А ложно.

Например, отрицанием высказывания А: «6 делится на 2» является высказывание : «неверно, что 6 делится на 2» (или «6 не делится на 2»).

Для пояснения логических операций удобно использовать так называемые таблицы истинности (истинностные таблицы):

[A]	[ ]
И Л	Л И

Определение 2. Конъюнкцией высказываний А и В называется высказывание А В (читается «А и В», «А конъюнкция В»), которое истинно тогда и только тогда, когда истинны оба высказывания А и В.

Например, конъюнкцией высказываний А: «2<4» и В: «6 – простое число» является высказывание А В: «2<4 и 6 – простое число», которое ложно, поскольку ложным является высказывание В. Истинностная таблица для конъюнкции имеет вид:

[A]	[B]	[AÙB]
И И Л Л	И Л И Л	И Л Л Л

Определение 3. Дизъюнкцией высказываний А и В называется высказывание А В (читается «А или В», «А дизъюнкция В»), которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А или В.

Союз «или» в данном случае носит неразделительный смысл, поскольку высказывание А В истинно и при истинности обоих высказываний А и В. Например, высказывание «4¹13 или 7 – простое число» истинно, так как является дизъюнкцией двух истинных высказываний «4¹13» и «7 – простое число». Дизъюнкции соответствует следующая таблица истинности:

[A]	[B]	[AÚ B]
И И Л Л	И Л И Л	И И И Л

Определение 4. Импликацией высказываний А и В называется высказывание А В (читается «если А, то В», «из А следует В», «А влечет В», «А импликация В»), которое ложно тогда и только тогда, когда высказывание А истинно, а В ложно. Истинностная таблица для импликации такова:

[A]	[B]	[A→B]
И И Л Л	И Л И Л	И Л И И

В импликации А В высказывание А называется посылкой (или условием), а высказывание В – заключением. Между посылкой и заключением могут отсутствовать причинно-следственные связи, но это не может повлиять на истинность или ложность импликации. Поэтому с точки зрения логики, допустимы, например, такие импликации: «если диагонали ромба пересекаются под прямым углом, то Ю.Гагарин – великий русский поэт», «если город Брянск расположен на берегу Невы, то 3+2=4». В первом случае импликация, согласно определению, является ложной, а во втором – истинной. То обстоятельство, что в случае, когда ложна посылка, импликация будет истинной независимо от истинностного значения заключения, кратко формулируют так: «из ложного следует все, что угодно».

Определение 5. Эквиваленцией высказываний А и В называется высказывание А В (читается «А тогда и только тогда, когда В», «А необходимо и достаточно для В», «А эквиваленция В»), которое истинно тогда и только тогда, когда истинностные значения А и В совпадают.

Например, высказывание «2+7=8 тогда и только тогда, когда 3<0» истинно,

поскольку оно является эквиваленцией двух ложных высказываний «2+7=8» и «3<0». Таблица истинности для эквиваленции имеет вид:

[A]	[B]	[A↔B]
И И Л Л	И Л И Л	И Л Л И

Замечание. Высказывания А и В называются равносильными, если их истинностные значения совпадают. Если высказывания А и В равносильны, то пишут А В. Нетрудно проверить, что ; если , то ; из и следует , для любых высказываний А, В и С. Это означает, что отношение равносильности на множестве высказываний является отношением эквивалентности.

14. Формулы алгебры высказываний. Равносильные формулы, ТИ-формулы, ТЛ-формулы, выполнимые и опровержимые формулы. Необходимое и достаточное условие равносильности формул. Свойства равносильности формул.

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

Определение 6. Формулами алгебры высказываний являются:

1) элементарные формулы;

2) если А и В – формулы, то ( ), (А В), (А В), (А В), (А В) также являются формулами алгебры высказываний;

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

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

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

Определение 8. Часть формулы А алгебры высказываний называется подформулой формулы А, если она сама является формулой алгебры высказываний.

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

Решение. Формула А содержит три атома Х, У и Z. Для того, чтобы получить формулу А, необходимо выполнить следующие операции: 1) ; 2) У Z; 3) ; 4) .Следовательно, r(A)=4. Найдем все истинностные значения формулы А с помощью таблицы истинности. Для этого занесем сначала в таблицу атомы Х, У и Z и заполним столбцы, им соответствующие, так, чтобы таблица содержала все возможные наборы значений Х, У и Z. В оставшиеся столбцы занесем формулы , У Z, , и заполним таблицу, используя определения логических операций:

[X]	[Y]	[Z]	[ ]	[YÙZ]	[ ]	[ ® ]
И И И И Л Л Л Л	И И Л Л И И Л Л	И Л И Л И Л И Л	Л Л Л Л И И И И	И Л Л Л И Л Л Л	Л И И И Л И И И	И И И И Л И И И

Последний столбец содержит все истинностные значения формулы А.

Замечание. Если формула содержит n атомов, то таблица истинности для нее содержит 2ⁿ строк. В частности, при n=3 таблица содержит 8 строк, причем атомам удобно придавать значения следующим образом: первому атому – четыре значения И и четыре значения Л; второму – два значения И, два значения Л, два И, два Л; третьему – значения И и Л, чередуя.

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

Тождественно истинная формула А обозначается следующим образом: ╞А. Формула А в примере 1 не является тождественно истинной, поскольку при [X]=Л, [Y]=И, [Z]=И формула А принимает значение Л.

Определение 10. Формула А называется тождественно ложной (противоречием), если при любых значениях атомов, входящих в формулу А, А принимает значение Л.

Формула А в примере 1 не является тождественно ложной, так как, например, при [X]=И, [Y]=И, [Z]=И имеем [A]=И.

Определение 11. Формула А называется выполнимой, если найдется такой набор

атомов, входящих в формулу А, при котором А принимает значение И.

Определение 12. Формула А называется опровержимой, если найдется такой набор атомов, входящих в формулу А, при котором А принимает значение Л.

Очевидно, что формула А в примере 1 является и выполнимой, и опровержимой.

Определение 13. Формулы А и В называются равносильными, если при любых истинностных значениях атомов, входящих в формулы А и В, истинностные значения А и В совпадают. Равносильные формулы А и В обозначают следующим образом: А В.

Замечание. Отношение равносильности на множестве всех формул алгебры высказываний является отношением эквивалентности.

Теорема 1. Формулы А и В равносильны тогда и только тогда, когда формула А В является тавтологией.

Доказательство. 1.Необходимость. Пусть А В. Тогда, согласно определению 13, при любых значениях атомов, входящих в формулы А и В, истинностные значения А и В совпадают. Последнее, в силу определения 5, означает, что формула А В принимает значение И при любом наборе атомов, в нее входящих, т.е., по определению 10, А В – тавтология.

2. Достаточность. Пусть ╞А В. Это означает, что формула А В принимает значение И при любых значениях атомов, входящих в нее. Согласно определению 5, это означает, что А и В одновременно принимают либо значение И, либо значение Л, т.е. являются равносильными. Теорема доказана.

Теорема 2. Для равносильности формул логики высказываний выполняются следующие свойства:

(1) ; (1') — коммутативность;

(2) ; (2') — ассоциативность;

(3) ; (3') — дистрибутивность;

(4) ; (4') — идемпотентность;

(5) ; (5') — законы де Моргана;

(6) И; (6') Л — закон исключения третьего;

(7) ; (7')

(8) И И; (8') Л Л — законы поглощения;

(9) Л ; (9') И

(10) — закон двойного отрицания;

(11) — исключение эквиваленции;

(12) — исключение импликации.

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

[A]	[B]	[ ]	[A B]	[ ÚB]
И И Л Л	И Л И Л	Л Л И И	И Л И И	И Л И И

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

Теорема 3 (о замене). Пусть - формула . Если в формуле заменить некоторую её подформулу равносильной ей формулой , то получится формула, равносильная формуле .