02.1. Логика высказываний

Логика высказываний

Значение математических абстракций не ограничивается лишь использованием их для построения моделей реальных процессов или решения чисто математических проблем. Математическое абстрагирование необходимо и при формировании умозаключений, с помощью которых строится научная теория. Проведение логически верных рассуждений – путь к достижению правильных представлений об окружающем мире. МАТЕМАТИЧЕСКАЯ ЛОГИКА – это раздел математики, основанный на использовании методов алгебры для изучении объектов нечисловой природы и являющийся средством научного исследования.

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

Знать – это установить при помощи доказательств. Аристотель

Впервые логические принципы построения умозаключений выделил Аристотель, положив начало развитию МЕТОДА ДЕДУКЦИИ, состоящего в выделении некоторых первоначальных, НЕОпределяемых ПОНЯТИЙ И постулатов, на основе которых строится научная теория. И лишь спустя две тысячи лет логика приобрела новый импульс в своем развитии благодаря идее ее математизации, высказанной Г. Лейбницем – великим немецким математиком, чье имя связано со многими выдающимися открытиями. В нашем курсе мы столкнемся не один раз с достижениями его могучего интеллекта. Интересны теологические труды И. Ньютона – результат его духовных исканий, заставивших его неожиданно прекратить занятия математикой и физикой в начале 1670 г. для поисков истинной религии и истинной картины мира. Увидев первоосновой всему принципы морали, он сформулировал пятнадцать правил интерпретации пророчеств. Эти правила он применил при изучении истории человеческой цивилизации, заменяя многозначность смысловых оттенков языка строгой конкретикой научного доказательства.

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

· «приписывать каждому отрывку только одно значение»;

· сохранять в процессе интерпретации некий фиксированный смысл слов во всех фрагментах;

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

· принимать те смыслы слов и фраз, которые наиболее естественным образом вытекают из языка и контекста;

· предпочитать наиболее простые интерпретации («истина всегда должна заключаться в простоте»).

К середине XIX века математическая логика сформировалась как наука благодаря трудам английского математика Д. Буля, сумевшего применить к логике язык символов и формул. Сейчас можно уже с уверенностью утверждать, что любая современная ЭВМ, лишенная возможности выполнять логические операции, будет напоминать всего лишь быстродействующий арифмометр, не способный решать сколь-либо серьезные задачи.

Необходимость достижения максимальной логической строгости рассуждений приводит нас к принятию первичных основополагающих предложений – АКСИОМ. Это позволяет создать целостную формализованную систему знаний. Аксиоматический метод построения математических теорий знаменитый немецкий математик Д. Гильберт назвал теорией доказательства. Математика стала изучать саму себя, пытаясь сформулировать принципы построения математических теорий. Две тысячи лет «Начала» Евклида (III в. до н. э.) служили образцом строгости аксиоматического построения геометрии. Однако появление неевклидовой геометрии Н. И. Лобачевского (1793–1856) породило проблему непротиворечивости аксиоматики, так как аксиомы этой новой геометрии не соответствовали привычным пространственным представлениям, положенным в основу геометрии Евклида. Истинность геометрии Н. И. Лобачевского после долгого неприятия была подтверждена уже после его смерти работами многих ученых.

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

Итак, назовем ВЫСКАЗЫВАНИЕМ любое утверждение, которое может быть либо истинным, либо ложным. Высказывания принято обозначать заглавными буквами латинского алфавита. Рассмотрим в качестве примера некоторые утверждения и выделим среди них высказывания. Пусть утверждение А означает: «Марс является планетой». Это утверждение можно рассматривать с позиции истинности или ложности, а значит, следует считать высказыванием. Утверждение «Кислород является металлом» – также высказывание, оно ложно. А вот выражения: «Который час?», «Война и мир» – нельзя считать высказываниями, так как эти утверждения не представляется возможным рассматривать с позиций их истинности или же ложности. По этой же причине определение «Часть плоскости, ограниченная окружностью, называется кругом» не может быть высказыванием.

«» – высказывание, но “” – не высказывание, а выражение, содержащее переменную х.

Обычно значение истинности высказывания принято обозначать 1, а ложности – 0. Исходные, ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ, могут образовывать СЛОЖНЫЕ путем выполнения над ними логических операций. Истинность сложных высказываний зависит от истинности простых, а также от вида логических операций, выполняемых над простыми высказываниями.

A
1	0
0	1

Таблица 1. Отрицание Высказывания.

ОТРИЦАНИЕМ ВЫСКАЗЫВАНИЯ А называется высказывание, обозначаемое , которое истинно, когда А ложно, и ложно, когда А истинно. В русском языке операция отрицания выражается словами «не А». Например, для упомянутого высказывания А «Марс является планетой» его отрицание будет следующим: «Марс не является планетой». Высказывание А было истинно,  – ложно. Высказывание В «Кислород является металлом» имеет отрицание: «Кислород не является металлом». В – ложно,– истинно. Истинность высказываний А и может быть представлена таблицей 1. Логическую операцию отрицания можно трактовать как функцию, у которой аргументом является высказывание А, принимающее значения «истинно» и «ложно», а значениями самой функции являются две характеристики: «ложно», «истинно»; то есть значения функции имеют тот же набор величин. Такое трактование понятия функции является расширенным, так как ее аргумент и она сама принимают значения, имеющие нечисловую природу. Даже если использовать числовые обозначения 1 и 0, характеризующие истинность и ложность высказывания, далеко не всегда можно установить аналогию между обычной алгеброй и алгеброй высказываний. Этого мы коснемся ниже. А сейчас, в силу определения отрицания, можно уже записать:

A	B
1	1	1
1	0	0
0	1	0
0	0	0

Таблица 2. Конъюнкция Высказываний.

КОНЪЮНКЦИЕЙ ВЫСКАЗЫВАНИй А и В называется высказывание, обозначаемое , которое истинно лишь тогда, когда и А, и В истинны. Конъюнкция выражается словами: «А и В». Истинность высказываний А, В и Может быть представлена таблицей 2. Например, сложное высказывание ««Марс является планетой» и «Кислород является металлом»», образованное из введенных выше высказываний А и В, представляет конъюнкцию этих высказываний. Она ложна, так как ложно простое высказывание В. Рассмотренные выше простые высказывания далеки друг от друга по смыслу, но нас в данном случае интересует лишь формальная истинность сложного высказывания, образованного из двух простых.

A	B
1	1	1
1	0	1
0	1	1
0	0	0

Таблица 3. Дизъюнкция Высказываний.

ДИЗЪЮНКЦИЕЙ ВЫСКАЗЫВАНИй А и В называется высказывание, обозначаемое , которое истинно при условии, когда хотя бы одно из высказываний А или В истинно. Дизъюнкция выражается словами: «А или В». Истинность высказываний А, В и представлена таблицей 3. Высказывание ««Марс является планетой» или «Кислород является металлом»», образованное из уже упоминавшихся высказываний А и В, будет истинным, так как одно из них (высказывание А) истинно.

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

ИМПЛИКАЦИЕЙ ВЫСКАЗЫВАНИй А и В называется высказывание, обозначаемое которое ложно лишь при условии, что А истинно, а В – ложно. Импликация выражается словами: «Если А, то В». Истинность высказываний А, В и приводится в таблице 4.

A	B
1	1	1
1	0	0
0	1	1
0	0	1

Таблица 4. Импликация Высказываний.

Высказывание А в импликации называется УСЛОВИЕМ, или посылкой, высказывание В – ЗАКЛЮЧЕНИЕМ, или выводом. Возвращаясь к рассмотренным примерам относительно высказываний А («Марс является планетой») и В («Кислород является металлом»), можно утверждать, что импликация является ложной, так как А – истинно, а В ложно. Из истинных условий заключение может оказаться ложным; из ложных же условий заключение может оказаться истинным или ложным (две нижние строки в табл. 4). Из неверного условия следует все что угодно. Это важный практический вывод о возможностях использования импликации высказываний.

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

A	B
1	1	1
1	0	0
0	1	0
0	0	1

Таблица 5. Эквиваленция Высказываний.

ЭКВИВАЛЕНЦИЕй высказываний А и В называется высказывание, обозначаемое , которое ложно, когда одно из высказываний истинно, а другое ложно, и истинно, когда оба высказывания А и В либо истинны, либо ложны одновременно. Эквиваленция выражается словами: «А тогда и только тогда, когда В». Истинность высказываний А, В и может быть представлена таблицей 5. Высказывания А («Марс является планетой») и В («Кислород является металлом») не могут быть эквивалентными, так как одно из них истинно, а другое – ложно.

Если оперировать числовыми характеристиками 1 и 0, отражающими, соответственно, истинность и ложность высказываний, то, например, для логической операции «импликация высказываний», получим:

Как известно, в математике рассматриваются формулы - символические записи, включающие в себя цифры, буквы и специальные знаки, расположенные в определенном порядке и являющиеся носителями информации. Выглядят привычно формулы: Площади S прямоугольника со сторонами a и b или – для вычисления пути S равномерного прямолинейного движения точки со скоростью u за время t. Однако, возможно и сочетание математических знаков, выражающих некоторое высказывание – логическую формулу, конструирующую составное высказывание из более простых. Например:  – это выражение является схемой, по которой из любых высказываний A, B и C можно построить новое высказывание. Переменные в логических формулах, которые могут принимать в качестве своих значений любые конкретные высказывания, являются высказывательными переменными. Существуют еще две специфические высказывательные переменные И и Л, обозначающие любые, соответственно, истинные или ложные, высказывания. Принимаются следующие соглашения:

1. Любая отдельно взятая высказывательная переменная является формулой. Конкретно взятый логический знак формулой не является.

2. Если A и B – формулы, то формулами будут и выражения

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

Например,  – формулы, а Формулами не являются.

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

Составьте таблицу истинности для формулы

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

Рассмотрим, например, формулу трех переменных вида

.

Каждая из трех переменных A, B и C может принимать два значения: истинно или ложно (1 или 0), поэтому мы будем иметь восемь возможностей, представленных Таблицей 6.

A	B	C
1 1 1 1 0 0 0 0	1 1 0 0 1 1 0 0	1 0 1 0 1 0 1 0	1 0 0 0 1 0 0 0	1 0 0 0 1 1 1 1

Таблица 6. Истинность для формулы .

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

,

Которую называют еще схемой доказательства "от противного", имеет следующую таблицу истинности:

A	B
1 1 0 0	1 0 1 0	0 0 1 1	0 1 0 1	1 1 1 0	1 1 0 1	1 1 0 0	1 1 1 1

Таблица 7. Истинность формулы

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

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

Тождественно-истинных формул может быть составлено сколь угодно много, но есть формулы – их существует несколько десятков, –которые чрезвычайно важны для решения очень многих задач.

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

1. (переместительный закон сложения),

2. (переместительный закон умножения),

3. (сочетательный закон сложения),

4. (сочетательный закон умножения),

5. (распределительный закон).

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

1. (переместительный закон дизъюнкции),

2. (переместительный закон конъюнкции),

3. (сочетательный закон конъ­юнкции),

4. (сочетательный закон дизъюнкции),

5. (распределительный закон).

Если дизъюнкцию считать суммой высказываний, конъюнкцию – их произведением, то можно заметить, что действия над числами и высказываниями подчиняются одним и тем же законам. Вместе с тем, для логических высказываний справедливы и другие важные формулы:

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

7.

Законы де Моргана

8.

(закон контрпозиции).

(правило цепного заключения, или закон силлогизма).

(правило «модус поненс»).

12. (правило доказательства «от противного»).

«To be or not to be – that is a question!» Эта сакраментальная фраза Гамлета вытекает из закона исключенного третьего.

13.  – закон исключенного третьего.

14. .

15. .

16. .

17. .

18. .

19. .

20. .

21. .

22. .

23. .

Приведите примеры умозаключений, подтверждающих сформулированные законы..

В обыденном смысле тавтология означает повтор ранее уже сказанного, а потому не очень интересное рассуждение. Тавтологии в математике являются ключом к построению доказательств теорем, основой выполнения умозаключений. Тавтологии отражают общие особенности понятийного аппарата современной науки, общие законы связей и отношений окружающего мира. Доказательство самих тавтологий можно осуществить путем составления таблиц истинности, как это уже делалось. Однако таблица истинности высказывания, включающего N простых высказываний, должна состоять из 2n строк(!). Поэтому для анализа сложных высказываний формулы 1–23 имеют неоценимое значение как способы упрощения логических выражений. И здесь, конечно, ЭВМ может помочь успешно выполнять логические операции. Использование логических операций в программах позволяет избежать громоздких вложений одного условного оператора в другой.

Рассмотрим в качестве иллюстрации применения тавтологий схему доказательства теории методом «от противного»:

.

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

Приведем в качестве примера доказательство теоремы:

Если в треугольнике два угла равны, то противолежащие им стороны тоже равны.

Пусть в треугольнике KLM углы a и b равны между собой, и LK и MK – противолежащие им стороны. Предположим противное, то есть утверждение, противоречащее выводу теоремы: "стороны LK и MK не равны между собой". Тогда из этого утверждения (согласно теореме о том, что во всяком треугольнике против большего угла лежит большая сторона) следует, что угол A будет больше или же меньше угла B. Но это противоречит условию теоремы. Тогда истинным должно быть утверждение, противоречащее сделанному предположению, то есть вывод теоремы.

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

Две формулы И Равносильны, Если Формула Является Тавтологией. Справедливо и обратное утверждение: Если Формула Является тавтологией, То Формулы И Равносильны.

< Предыдущая		Следующая >