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

Потопахин Виталий Валерьевич, методист ХКЦТТ

Искусство логического мышления

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

Любая наука, начинается с точного определения понятий с которыми она имеет дело.

Определим основные понятия и мы:

Посылка - это утверждение, из которого мы исходим в своих рассуждениях.

Следствие - это утверждение являющееся результатом наших рассуждений.

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

Гипотеза - это утверждение, истинность которого требуется доказать.

Противоречие - это ситуация, когда в процессе наших рассуждений получились два взаимоисключающих утверждения.

Суждение - это единица мышления.

Основные законы:

Закон тождества. Всякий предмет, есть то, что он есть. Что это означает: Если мы, в своих рассуждениях, используем какое - либо понятие, то на любом этапе рассуждений, это понятие должно означать одно и тоже. Иногда за соблюдением закона тождества надо специально следить. Например, при использовании многозначных слов. Нарушение закона может завести в тупик. К примеру, понятием энергии часто обозначаются совершенно разные явления. Например, физическая энергия и психическая энергия. Если мы опустим, тот факт, что это два разных явления, то законы, которым подчиняется физическая энергия, можно будет автоматически переносить на явления связанные с проявлением психической энергии, что и будет ошибкой. Приведём более простой пример: Предположим, вы изучили правила дорожного движения принятые в России. Закон тождества говорит, что правила принятые в России, это совсем не те правила, которые приняты во Франции. Если же вы пренебрежёте законом тождества, то будучи во Франции вы рискуете попасть в аварию.

Закон противоречия. Ход рассуждений не должен быть противоречивым. На этом законе основан метод доказательства утверждений, так называемый метод "От противного". Применение метода рассматривается ниже в задачах о принцессах. Суть его заключается в следующем правиле. В начале рассуждений, мы принимаем некоторое утверждение за истину. Если мы будем рассуждать, не нарушая правила и законы логики, то на любом шаге наших рассуждений должны получаться только истинные утверждения. Если же мы когда либо получим ложное утверждение, то это будет означать, что исходное утверждение не может быть истинным.

Закон исключенного третьего. Если есть два суждения и одно исключает другое, то одно из них истина, а другое ложь. В реальной жизни это не всегда так. Приведём пример: Первое утверждение "Я пользуюсь методами математической логики каждый день моей жизни.", второе утверждение "Я никогда не пользуюсь методами математической логики". Очевидно, что они противоречат друг другу, однако они вполне могут оказаться одновременно ложными. Например, если вы специалист по математической логике, то вы должны часто пользоваться её методами, но вряд ли они нужны вам каждый день вашей жизни. Закон исключенного третьего предназначен для использовании в области точных наук, в которых такие ситуации не встречаются или встречаются достаточно редко.

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

Методы мышления

Пользуясь законами, можно строить методы правильного мышления. Их существует довольно много, но мы приведём в качестве примера только два из них.

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

Очень яркий литературный пример использования дедуктивного метода это герой А. Конан-Дойля Шерлок Холмс. Конечно, применение дедукции Холмсом далеко от математической точности и строгой критики рассказы о нём не выдерживают, но суть метода в рассказах Конан-Дойля демонстрируется очень наглядно.

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

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

1 Комната	2 Комната
В этой комнате находится принцесса, а в другой комнате сидит тигр.	В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр.

Кроме того, принцу было сказано, что на одной табличке написана правда, а на другой нет.

Начнем рассуждения. Для каждой из табличек возможны только два варианта, либо ложь, либо истина. Рассмотрим с этой позиции табличку на первой комнате.

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

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

Задача для самостоятельного решения:

1 Комната	2 Комната
По крайней мере в одной из комнат находится принцесса	Принцесса в другой комнате.

Дополнительно было известно следующее: Если в первой комнате находится принцесса, то утверждение на табличке истинно, если же там тигр, то утверждение ложно. Относительно правой комнаты все было наоборот: утверждение на табличке ложно, если в комнате находится принцесса, и истинно, если в комнате сидит тигр.

Математическая логика

Вышеизложенная логика хорошо описывает законы человеческого мышления, но исходной задачи "вычисления истины", она не решает. Она не может решить её в принципе, потому что в ней почти нет математики. А следовательно следующий разумный шаг, это создание теории которая описывала бы процесс мышления с математической точностью.

Как создать такую теорию?

Ответ: точно так же, как и любую другую математическую теорию. Надо предельно точно описать используемые понятия и определить над ними операции. Первым кто проделал такую работу и создал первую математическую логику был Джорж Булль. Эта математика по его имени стала называться булевой алгеброй или логикой высказываний. И сейчас мы ей займемся. Итак.

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

Последняя договорённость очень важна. Если рассматривать смысл высказываний, то работать с ними будет слишком сложно, так как смысл очень неопределённое понятие. А если мы решим, что важна только истинность высказывания, то проблема значительно упрощается. В этом случае совершенно неважно о чём говорится в высказывании. Отпадает необходимость обозначать высказывание целым предложением, раскрывающим его смысл. Для обозначения вполне достаточно будет одной буквы. Разные высказывания будем обозначать разными буквами. Окончательно объектами нашей математики будут переменные величины обозначаемые буквами или комбинациями букв и имеющие только два значения : Истина и Ложь.

Операции : Операции над высказываниями, это операции над буквенными переменными и могущие принимать в качестве результата только два значения. Далее мы будем называть такие операции логическими.

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

Как можно составить логическую операцию? Очень просто. Приведем пример. Пусть дано высказывание А. Оно может быть либо истинно, либо ложно. Определим высказывание В следующим образом: пусть В истинно когда А ложно и ложно когда А истинно. Мы только что установили соответствие между высказыванием А и высказыванием В. Другими словами мы составили логическую операцию, аргументом которой является высказывание А и результатом высказывание В. Операция определённая таким образом  называется отрицанием и записывается так - ùА. Еще говорят так - “не А”

Определим еще четыре логические операции:

Коньюкция. Это логическая операция устанавливающая  соответствие между высказываниями А и В и высказыванием С  следующим образом: Если А и В истинны то С также истинно. Если же  хотя бы одно из них ложно то С также ложно. Обозначение: АÙВ. Можно сказать так “ А и В “ и еще эту операцию называют логическим умножением.

Дизьюкция. Это логическая операция устанавливающая  соответствие между высказываниями А и В и высказыванием С следующим образом: Если А и В ложны то С также ложно. Если же  хотя бы одно из высказываний А и В истинно то С также истинно. Обозначение: АÚВ. Можно сказать так “ А или В ” и еще эту операцию называют логическим умножением.

Эквиваленция. Это логическая операция устанавливающая  соответствие между высказываниями А и В и высказыванием С следующим образом: Если А и В одновременно ложны или же истинны то С истинно иначе С ложно. Обозначение: А=В

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

если А ложно то С истинно  ( то есть из ложного утверждения может следовать все что угодно)

если А истинно и В истинно то С истинно ( из истинного утверждения можно вывести истинное )

если А истинно и В ложно то С ложно ( из истинного утверждения не может следовать ложное )

Обозначение : А®В

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

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

А	В	не А	А или В	А и В	А следует В	А эквив. В
Истина	Истина	ложь	истина	Истина	Истина	истина
Истина	Ложь	ложь	истина	ложь	Ложь	ложь
Ложь	Истина	истина	истина	ложь	Истина	ложь
Ложь	Ложь	истина	ложь	ложь	Истина	истина

Сложное высказывание

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

А	В	АÚВ	(АÚВ)®А
1	1	1	1
1	0	1	1
0	1	1	0
0	0	0	1

Составьте для тренировки таблицы истинности следующих сложных высказываний:

АÚ(АÚùВ)	А®(ВÙА)
(ВÚА)®А	А®(ВÚВ)
ù(АÚù(В®А))	(ùВÚА)®(ВÚА)
ù(В®А)®(АÙВ)	В®(ù(В®А)®(ùА®В))

Схема умозаключения

Обычно, мы принимаемся строить цепочки логических умозаключений, для того чтобы установить истинность или ложность того или иного утверждения. Можно даже сказать, что нас всегда интересует истинность. Если мы же нам требуется установить ложность утверждения, то это то же самое что устанавливать истинность его отрицания. Иначе говоря, наш мыслительный процесс всегда направлен на получение доказательств теорем каждая из которых строится по следующей схеме: Дано некоторое количество истинных посылок и некоторое утверждение являющееся следствием из них. Теорема говорит, что данное утверждение также истинно, на том основании, что оно является следствием из истинных посылок.

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

Для начала определим два важных понятия:

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

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

Тождественно - истинные высказывания получаются следующим образом: Определяется некоторое количество сложных тождественно - истинных высказываний. Такие высказывания в математике называются аксиомами. Затем составляется очевидная схема умозаключения. Затем над правой частью этой схемы производятся тождественные преобразования приводящие к появлению новых высказываний, которые согласно определению схемы умозаключения также являются истинными.

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

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

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

Заключение

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

Еще несколько вопросов для самостоятельной работы.

Приведите пример дедуктивного рассуждения.

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

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

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

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