Введение

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

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

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

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

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

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

Алгебра высказываний возникла в середине XIX века благодаря работам Дж. Буля и де Моргана. В алгебре высказываний формулы строятся из так называемых высказывательных переменных A, B, C,… и логических связок &, Ú, Ø, ®. Значениями логических переменных могут быть любые высказывания, каждое из которых в определенных условиях можно оценить как истинное или ложное, а перечисленные выше связки можно рассматривать, соответственно, как заменители слов «и», «или», «не верно», «если, то». Перечисленные логические связки называются соответственно конъюнкцией, дизъюнкцией, отрицанием и импликацией.

В качестве высказывательных переменных мы будем использовать большие латинские буквы.

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

1. Присоединение к уже построенному выражению слева знака Ø.
2. Написание двух уже построенных выражений одного за другим с включением между ними любого из знаков &, Ú, Ø, ® и заключением полученного выражения в скобки.

Например, с помощью переменных A, B, C можно построить формулу ((AÚB) ® C). Смысл, который может быть приписан этой формуле, зависит лишь от того, какой смысл приписан переменным A, B, C. Пусть, например,  A, B и C – это высказывания о некотором треугольнике T, заключающиеся в следующем:

A – «В треугольнике T есть два равных угла»,

B – «В треугольнике T есть две равные стороны»,

C – «Треугольник T является равнобедренным».

При такой интерпретации переменных A, B и C приведенная выше формула может быть выражена на русском языке фразой: «Если в треугольнике T есть два равных угла или две равные стороны, то треугольник T является равнобедренным». Очевидно, при такой интерпретации переменных нашу формулу следует считать истинной. Истинными также будут формулы (C ® (AÚB)), (C ® (A&B)), (Ø(A&B) ® ØС), (ØA ® ØС), (A ® B), а формулы (C&(ØAÚ¬B)), (C&(ØA&¬B)) будут представлять ложные высказывания, каков бы ни был треугольник T. С другой стороны, истинность формулы  (AÚС) будет зависеть от треугольника T.

Приведем ещё одну интерпретацию переменных A, B, C как высказываний о некотором натуральном числе x:

A – «Число x делится на 3»,

B – «Число x делится на 5»,

C – «Число x делится на 15».

Тогда формулы ((A&B) ® С), (C ® (A&B)), (C ® A), представляют истинные высказывания при любом числе x, а формула (C&ØA) ложна при любом числе x, истинность формулы ((AÚB) & C) зависит от числа x, например, при x = 30 она истинна, а при  x = 12 она ложна.

Если формула выражает истинное высказывание при некоторой интерпретации высказывательных переменных, то мы говорим, что она принимает значение истина («И») при этой интерпретации, в противном случае она при такой интерпретации принимает значение ложь («Л»).

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

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

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

Так для формулы ((A & B) Ú (A & ØC)) необходимые вычисления можно оформить в виде таблицы

Заметим, что в первых трех колонках перечислены 8 всевозможных наборов истинностных значений высказывательных переменных A, B и C. В остальных колонках – истинностные значения различных подформул исходной формулы.

Видим, что при пяти наборах значений высказывательных переменных наша формула принимает значение «Л» и при трех остальных наборах – значение «И».

Формулы, которые при любых наборах значений переменных принимает значение «И» называются тождественно истинными. Часто их называют тавтологиями или логическими законами.

Простейшим примером тавтологии является формула (AÚ¬A). Нетрудно видеть, что при любом истинностном значении переменной А она принимает значение «И». Эту формулу называют законом исключенного третьего.

Формулы, которые при любых наборах значений переменных принимает значение «Л» называются тождественно ложными. Часто их называют противоречивыми или противоречиями. В качестве простейшего примера противоречия можно привести формулу (A&¬A).

Для обозначения формул будем использовать греческие буквы. Например, выражение вида c = (j Ú y) говорит о том, что формула c, построена из формул j и y путем включения между ними знака дизъюнкции.

Две формулы j и y называются логически равносильными, если формулы (j ® y) и (y ® j) тождественно истинны. Факт логической равносильности формул j и y будем обозначать выражением j º y.

Приведем пример часто используемых логических равносильностей, известных как законы де Моргана.

¬(j Ú y) º (¬j & ¬y)

¬(j & y) º (¬j Ú ¬y)

Справедливость этих законов легко проверить с помощью таблиц истинности. Их можно использовать как правила вывода одних формул из других.

Если нам, например, известно, что истинна формула ¬(j & y), то мы можем вывести в соответствии с законом де Моргана формулу (¬j Ú ¬y). Этот же закон можно применить и в обратном направлении, то есть из формулы (¬j Ú ¬y) вывести ¬(j & y).

Приведем еще одно правило вывода. Если нам известно, что истинны формулы j и j  ® y, то истинна формула y. Этот закон известен в логике как правило modus ponens.

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

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

1.       Логика предикатов

В терминах логики высказываний вводятся и изучаются такие понятия как непротиворечивость, независимость и т.д. Однако существуют такие виды рассуждений, которые не могут быть выражены с помощью формул логики высказываний. С такой ситуацией мы встречаемся, когда рассматриваем высказывания, имеющие одну и ту же форму для разных объектов какого-либо возможно бесконечного множества. Например, выражение «x – простое число» содержит в себе бесконечное множество высказываний, полученных подстановкой вместо x конкретных чисел. Еще пример такого рода: «прямая x параллельна прямой y».

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

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

Приведем  пример рассуждений. Пусть на плоскости даны две параллельные прямые y₁ и y₂. Нам известно, что любая прямая, которая параллельна прямой y₁, параллельна также прямой y₂. Пусть далее нам известно, что прямая y₃ не параллельна прямой y₂, тогда мы делаем вывод, что прямая y₁ не параллельна y₃. Чтобы записать это рассуждение в виде последовательности формул, введем два новых значка " и $, называемые, соответственно, кванторами общности и существования. Выражение "x будем рассматривать как заменитель слов «для любого x», а выражение $x – «существует x». Если теперь выражение «x параллельно y» заменить более коротким выражением P(x, y), то наше рассуждение будет представлено последовательностью формул:

• P(y₁, y₂),
• "x[P(x, y₁) ® P(x, y₂)],
• P(y₁, y₃).

Первая формула говорит, что прямая y₁ параллельна прямой y₂. Вторая – что любая прямая x параллельная прямой y₁ параллельна также прямой y₂. Третья – что прямая y₃ не параллельна прямой y₂. Заключением нашего рассуждения будет формула

• ¬P(y₁, y₃).

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

Рассмотрим подробнее схему построения языка предикатов. Выражения строятся из 4-х видов символов:

• Логические связки и кванторы:  &, →, Ø, ", $.
• Символы для индивидных переменных:  x, y, z, x₁, x₂, … .
• Вспомогательные символы (запятая и скобки).
• Символы для обозначения предикатов и функций.

Из перечисленных символов строятся два вида выражений – термы и формулы. Термы используются для обозначения конкретных объектов, если они не содержат переменных, или как схемы для обозначения новых обозначений через уже введенные. Например, в арифметике выражение «1+2» является термом и обозначает вполне конкретное число 3. Этот терм построен из термов 1, 2 и операции +. Выражение «x+2» тоже является термом, этот терм не обозначает ни какого конкретного числа, но если вместо x подставить обозначение какого-либо конкретного числа, то получим обозначение другого числа.

Далее термы используются для построения формул, которые рассматриваются как конкретные высказывания, либо как высказывательные формы. Так, например, выражение «1+2<4» конкретное высказывание о числах 1, 2, 4, операции + и предикате <. Выражение «x+2<4» это высказывательная форма, которая превращается в конкретные высказывания, если вместо переменной x подставлять обозначения конкретных чисел. Истинность полученного высказывания будет зависеть от того, какое выражение будет подставлено вместо переменной x.

Высказывательная форма может превратиться в высказывание не только путем подстановки обозначений конкретных объектов вместо переменных, но также с помощью кванторов ", $. Так выражения «$x (x+2<4)» является истинным и говорит о том, что существует число x, для которого высказывание x+2<4 истинно. Выражение «"x(4-x>2)» ложно, так как оно говорит, что для любого числа x выполняется неравенство 4-x>2, что опровергается, если в качестве x  взять, например, число 3. Вот примеры других арифметических высказываний «"x$y(x+y=0)», «$x"y(x+y=0)». Первое их них истинно, второе ложно.

В рассмотренных примерах мы использовали известные арифметические предикаты =, < и функции +, -. Так же можно строить термы и формулы с произвольными предикатами и функциями.

Точные правила построения формул мы здесь не указываем. Заметим только, что двухместные предикаты =, < и функции +, - мы в соответствии с традициями в примерах использовали как инфиксы, то есть располагают их между аргументами. В общем случае предикатные и функциональные символы используют как префиксы. Вначале пишется знак предиката или функции, а затем в скобках через запятую список аргументов. Например, выражение «x < y» должно быть записано в виде «< (x, y)».

Приведем пример более общего характера. Пусть x, y – индивидные переменные, принимающие значения из некоторого множества объектов (числа, геометрические фигуры и т.д.). S – одноместная функция, которая каждому объекту x ставит в соответствие объект S(x). M – двухместная функция, которая паре объектов (x, y) ставит в соответствие объект M(x, y). E –двухместный предикат, выражение «E(x, y) принимающий значение «И», если пара (x, y) находится в отношении E и значение «Л» в противном случае.

С помощью введенных обозначений по определенным правилам можно построить выражение

"x"y E(M(S(x), S(y)), S(M(x, y))).

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

Пусть объектами, о которых идет речь, являются точки плоскости: S(x) – точка симметричная точке x относительно некоторой заранее выбранной точки О; M(x, y) – точка, являющаяся серединой отрезка с концами x и y; E(x, y) – обычный предикат равенства. Тогда приведенная формула изображает геометрическое высказывание: «Для любых точек x, y середина отрезка с концами, симметричными точкам x, y, совпадает с точкой, симметричной середине отрезка с концами x, y» (см. Рис. 1)

 

Рис. 1

Рассмотрим другую интерпретацию наших символов M, S, E. Объектами рассмотрения пусть теперь будут действительные числа без нуля, S(x) = x^-1, M(x, y) = x×y, E – предикат равенства чисел, E(x, y) означает x = y. При такой интерпретации наша формула представляет высказывание: «Для любых двух чисел x и y выполняется равенство  x^-1×y^-1 = (x×y)^-1».

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

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

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

"x(P(x)ÚØ P(x)),

($x"yR(x, y) ® "y$x R(x, y))

(Ø"xP(x) ® $xØP(x)),

($xØP(x) ® Ø"xP(x)).

Все эти формулы истинны при любой интерпретации предикатов P и R, такие формулы называются тождественно истинными.

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

Язык предикатов позволяет исследовать не только тождественно истинные формулы, но и математические теории.

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

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

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

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

Литература

1. Столл Р. Р. Множества. Логика. Аксиоматические теории. – М.:Просвещение, 1968. – 231с.