Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Доклад - Математическая логика - файл 1.doc


Доклад - Математическая логика
скачать (309.5 kb.)

Доступные файлы (1):

1.doc310kb.02.12.2011 11:03скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Содержание:
Математическая логика в лицах………………………………….2

Введение…………………………………………………3

Язык логики предикатов………………………………..6

Синтаксис языка логики предикатов ………………….7

Семантика языка логики предикатов…………………..9

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

Исчисление предикатов………………………………..15

Определение формулы логики предикатов………….16

Свободные и связные вхождения

переменных в формулы…………………………………3

Логические и кванторные операции

над предикатами………………………………………..18

Применение языка логики предикатов для

записи математических предложений,

определений, построения отрицания предложений…..20

Заключение………………………………………………23

Литература……………………………………………….24


^ Математическая логика в лицах:
Андрей Николаевич Колмогоров (1903-1987)

Выдающийся российский математик, академик. Родился в 1903 году в Тамбове. В 1925 году окончил Московский университет, профессором которого работал с 1931 года. Заведовал различными кафедрами, был деканом механико-математического факультета МГУ. Автор фундаментальных работ по теории функций действительного переменного, теории множеств, топологии, конструктивной логике, функциональному анализу, механике, теории алгоритмов, теории информации. Основополагающее значение имеют результаты А.Н.Колмогорова в области теории вероятности. Широко известна его деятельность по разработке методики и организации математического образования. А.Н.Колмогоров был председателем Московского математического общества, почетным доктором зарубежных университетов, иностранным членом многих академий и научных обществ, лауреатом международных премий и кавалером правительственных наград. Умер в Москве в 1987 году.

^ Альберт Григорьевич Драгалин (1941-1998)

Видный представитель российской школы математического конструктивизма. Родился 10 апреля 1941 года на острове Моржевец Архангельской области. Окончил механико-математический факультет МГУ им.М.В.Ломоносова, где работал с 1966 года. С 1983 года жил в Венгрии, заведовал кафедрой вычислительной математики университета им.Л.Кошута (г.Дебрецен). В 1988 году Венгерской Академией наук ему была присвоена степень доктора наук. Умер 18 декабря 1998 года в г.Дебрецен. А. Г. Драгалин - автор фундаментальных трудов по теоретико-модельным и теоретико-доказательственным основаниям интуиционистской логики, конструктивным методам нестандартного анализа.




^ НЕЙМАН Джон (Neumann John 1903-1957)-

американский математик, логик, физик, инженер -изобретатель.

Выдающийся немецкий математик ^ Г. В. Лейбниц

(1646-1716) использовал термин логистика в значении "исчисления умозаключений", или математической логики

Введение

Логика - наука очень старая. Она возникла тогда, когда развитие специальных наук и вообще человеческого мышления сделало актуальным вопрос о том, как надо рассуждать, чтобы получить правильные выводы. Несомненен интерес к логике среди математиков и философов эпохи расцвета греческой культуры в VI-IV вв. до н.э. Но первое дошедшее до нас большое сочинение, посвященное специально логике ("Аналитики" Аристотеля, 384-322 гг. до н.э.), принадлежит уже позднегреческой эпохе. Независимо возникла буддистская логика, но дальнейшее развитие логики в Европе имеет своим исходным пунктом изучение Аристотеля.

Математическая логика с внешней стороны отличается от "обычной" тем, что она широко пользуется языком математических и логических знаков, исходя из того, что в принципе они могут совсем заменить слова обычного языка и принятые в обычных живых языках способы объединения слов в предложения. Довольно рано возникла идея о том, что, записав все исходные допущения на языке специальных знаков, похожих на математические, можно заменять рассуждение вычислением. Точно же сформулированные правила таких логических вычислений можно перевести на язык вычислительной машины, которая тогда будет способна автоматически выдавать интересующие нас следствия из введенных в нее исходных допущений. Своего рода "логическую машину" сконструировал еще в средние века Раймунд Луллий (1235-1315), дав ей, впрочем, лишь совершенно фантастические применения. Более определенный и близкий к реально осуществленному впоследствии замысел универсального логического исчисления развивал Лейбниц (1646-1716). Лейбниц надеялся даже, что в будущем философы вместо того, чтобы бесплодно спорить, будут брать бумагу и вычислять, кто из них прав.

Начало созданию того аппарата математической логики, который теперь мы называем логикой высказываний, положил Джордж Буль (1815-1864). Логико-математические языки и теория их смысла были затем значительно развиты в работах Фреге (1848-1925). Широко задуманное изложение больших разделов математики на языке математической логики было предпринято в работах Пеано (1858-1932) и особенно в фундаментальной трехтомной монографии Рассела и Уайтхеда, изданной в 1910-1913 гг.

В двадцатых годах XX века с программой обоснования математики на базе математической логики выступил знаменитый математик Гильберт (1862-1943). С этого времени и начинается современный этап развития математической логики, характеризующийся применением точных математических методов при изучении формальных аксиоматических теорий.

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

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

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

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

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

Язык логики предикатов (ЯЛП) является искусственным языком его характеризуют обычно как символический язык, потому что здесь используется особая символика, прежде всего для обозначения логических связей и операций. Специальные символы употребляются также в качестве знаков для обозначения предметов, свойств и отношений. Употребление символики способствует сокращению записи высказываний и облегчает, особенно в сложных ситуациях, понимание смыслов соответствующих высказываний.

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект и предикат

Субъект – это то, о чем что-то утверждается в высказывании;

Предикат – это то, что утверждается о субъекте.
^ Язык логики предикатов.
Предложение Р(x1, x2,…,xn), содержащее переменные x1, x2,…,xn, которое при подстановке вместо переменных их значений становится высказыванием, называется предикатом. Дадим несколько определений, относящихся к предикатам.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так:

В ЯЛП явно должны быть представляемы субъектно-предикатные структуры высказываний. Например, «а обладает свойством Р», «а и ^ Ъ находятся в отношении Р», «Для всякого предмета из некоторого множества 5 верно, что он обладает свойством Р», «Для всякого предмета из множества S существует предмет этого множества такой, что эти предметы находятся в отношении . Для выражения подобных высказываний в ЯЛП мы должны иметь в числе его исходных символов общие имена предметов; аналогами последних в ЯЛП будут предметные переменные х, у, z, а также они же с числовыми индексами x1 х2, ... и т.д.
Синтаксис языка логики предикатов.

I. Исходные символы языка.

В логике предикатов будем пользоваться следующей символикой :

1. Предметные переменные х, у, z, а также х с числовыми индексами: x1 x2, ..., хп,... (бесконечное счетное множество).

2. Предметные константы (аналоги собственных имен естественного языка):

а,, а2, .... ап, ... (также бесконечное счетное множество).

3. Знаки свойств и отношений различных местностей — предикатные символы, или предикаторы:

Р1, О1, Я1, 51, ...;

Р2, О2, R2, S2, ...;

и возможно эти символы с нижними индексами:

Р1,Р2, Р2, ... и т. д.

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

4. Знаки предметных функций различных местностей (предметные функторы):

J v Jy •••

f2 f2

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

5. Логические константы: =>, &, v, V, 3 — соответственно — импликация, конъюнкция, дизъюнкция, отрицание, квантор общности и квантор существования. Где квантор (от лат. quantum — сколько) логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате её применения. (Зачастую вводят лишь некоторые из этих символов. Из кванторов достаточны только V или 3, из остальных, называемых логическими связками, достаточно z> и -., или v и - или & и -i. Другие константы, как, впрочем, и другие знаки, могут вводиться по определению.)

6. Технические знаки: ( — левая скобка, ) — правая скоб-

ка, , — запятая.

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


^ II. Термы. Выражения этого типа являются аналогами имен естественного языка.

О п р е д е л е н и е : а) любая предметная переменная и предметная

константа есть терм;

б) если tv t2, ..., tn есть термы и /" есть л-местный

предметный функтор, то /* (tv t2,..., tn есть терм;

в) ничто, кроме указанного в пунктах а) и б), не

есть терм.

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

языке.

О п р е д е л е н и е : а) если tv t2, .... tn термы и Fj n-местный предикатор, то

Р"( (tv t2, ..., tn) есть формула (атомарная);

б) если А и В — формулы, то (AIDВ), (А&В), (AvB), -.A

—формулы; в) если х есть предметная переменная и А —

формула, то\/хАиЗхА — формулы;

г) ничто, кроме указанного в пунктах а) — в), не есть

формула.

Договоримся в дальнейшем опускать, когда это удобно, внешние скобки в отдельно взятых формулах; например, вместо (А & ^ В) писать просто А & В.

Использованные в определениях терма и формулы символы tv t2, ..., tn и f1} , F*, А, В, х (и в дальнейшем возможно xv х2 и т.д.) — знаки называемые также синтаксическим и переменными , возможными значениями которых являются выражения соответствующей категории описываемого (объектного) языка. Формулы А и В, встречающиеся в пунктах б) и в), называются п о д ф о р м у л а м и указанных здесь формул. Введенные понятия исходного символа, терма и формулы языка являются эффективными (иначе: рекурсивными). Последнее означает, что имеется точный способ, с помощью которого всегда можно определить, относится ли некоторый символ к числу исходных символов языка, а для каждой последовательности исходных символов можем определить, представляет ли она терм или формулу. Для термов и формул такой способ заключен в их индуктивных определениях. Так, в каждой формуле, содержащей логические константы (знаки логических операций), имеется главная, или, что тоже, последняя, в построении формулы операции. Выделив ее, мы выделяем тем самым собственные подформулы этой формулы. В последних снова выделяем главную операцию и так далее, пока не дойдем до какой-либо атомарной формулы. Если в процессе такого анализа исходного выражения в

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

Семантику языка при анализе естественного языка, составляет совокупность предметных значений и смысловых содержаний его выражений. Но в данном случае, поскольку речь идет не об анализе уже имеющегося языка, а  о построении — в данном случае логического формализованного языка —то семантикой называют совокупность правил  приписывания значений выражениям этого языка. Точнее говоря, здесь даже не ставится задача построения какого-то определенного языка. Создается лишь некоторая схема языка определенного типа, в данном случае так называемой классической логики предикатов первого порядка. Этот тип языка отличается от языков других типов, даже языков с тем же синтаксисом (например, языка интуиционистской логики предикатов, определенной системы релевантной логики) своей семантикой. Приписывание значений отдельным выражениям языка, составляющим дескриптивным терминам, употребляемым при построении формул, осуществляется лишь в составе тех или иных формул и при этом различно от случая к случаю в зависимости от характера решаемых логических задач, (например, при переводе каких то высказываний с естественного языка на данный формализованный, при анализе логических отношений между формулами данного языка, при аксиоматизации некоторых теорий, а именно при формулировке их аксиом в языке данного типа). Совокупность всех правил приписывания значений выражениям языка разбивается на следующие три группы (I,II,III).

I. Правила определения (задания) возможных значений предметных переменных и правила приписывания предметных значений дескриптивным постоянным в составе рассматриваемых в том или ином случае формул—интерпретация выражений языка. II. Правила приписывания значений свободным переменным в составе тех или иных рассматриваемых формулу. III. Правила приписывания истинностных значений интерпретированным формулам, не содержащим свободных переменных.   I. Интерпретация состоит, во-первых, в выборе некоторого непустого множества D индивидов, предметов того или иного типа, к которым могут относиться образуемые из тех или иных формул языка высказывания. Индивиды любые предметы в широком смысле этого слова, структура которых не учитывается, и которые можно отличать друг от друга. В качестве такой области D можно взять множество людей, растений, городов, чисел и т. д.; возможно, также объединение в одной области множеств различных предметов, например, людей, городов, домов (положим, для выражения высказываний о местах жительства людей). Но при этом все различные предметы, рассматриваются именно как индивиды. Область D — это область возможных значений предметных переменных символы предметных переменных х, у, z, становятся именно переменными лишь при указании области их возможных значений. Предполагается, что на области D определено некоторое множество свойств, отношений и характеристик предметно-функционального типа (то есть возможных значений предикаторов и предметных функторов).

Второй момент интерпретации языка состоит в задании некоторой функции j

 (интерпретационная функция) приписывания значений дескриптивным постоянным (предметным константам, предикаторам, предметным функторам опять-таки в составе рассматриваемых формул). Задание j

 в каждом конкретном случае представляет собой просто указание на то, какие значения должны быть приписаны упомянутым исходным символам языка в составе рассматриваемых формул. При этом предметным константам (простые постоянные термы) приписываются в качестве предметных значений определенные предметы из заданной области D. Предикатному (n-местному) символу P¸ⁿ  при n =1 в качестве значения приписываются некоторые свойства а при n > 1 — n-местное отношение (между предметами В). Например, если область D есть множество целых положительных чисел, то предикатному символу P¹₁  можно приписать в качестве значения свойство «четно», а предикатору P²₁  отношение «больше» или «меньше». Предметному функтору fⁿ₁   в качестве предметного значения функция j

приписывает какую-нибудь n-местную предметную функцию, определенную на области D. Например, для области чисел таковыми могут быть синус, косинус (одноместные функции), сумма, произведение (двухместные функции), для области людей — одноместные (возраст, рост), для области материальных тел — объем, удельный вес.

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

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

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

Однако важно заметить, что формулы со свободными переменными нужны не только для образования высказываний из них. Они представляют собой особые высказывательные формы, называемые предикатами. Это сложные знаковые формы возможных свойств предметов заданной области и возможных отношений среди этих предметов. По типу их предметных значений они должны быть отнесены к категории предакаторов. Можно назвать их сложными предикаторами (в отличие от простых, указанных среди исходных символов). Надо отметить, что эти формы не выделяются и даже не замечаются в естественных языках. Они играют, однако, решающую роль в теории понятия. Имея тот или иной предикат, можно ставить вопрос, для каких предметов, которые могут представлять свободные переменные, этот предикат выполняется или не выполняется. В таком случае мы просто указываем предметы для соответствующих переменных (не осуществляя указанных подстановок предметных констант вместо них). Например, можно сказать, что предикат «(Р2(x, a₁) > ∃yQ2(x, y))», — выражающий свойство какого-то числа х из области натуральных чисел, состоящее в том, что «если это число больше 5 (знаками отношения «больше» и «5» является соответственно Р2 и a₁  то оно делится без остатка (Q2) на некоторое число у», выполняется для чисел 6, 8, 9 и т. д., но не выполняется для 7, 11 и др.

III. Приписывание истинностных значений полностью интерпретированным формулам.

Напомним, что полностью интерпретированная формула — это формула, в которой осуществлена интерпретация дескриптивных постоянных и приписано значение всем свободным переменным, если таковые имеются в ней. Каждая такая формула представляет собой определенное высказывание — с определенным смыслом и истинностным значением — но лишь при условии, если нам известны значения встречающихся в ней — явным или неявным образом — логических констант, (которые и определяются рассматриваемыми правилами III). Явным образом указываются — в сложных формулах — логические константы, перечисленные в списке исходных символов. Простые атомарные формулы видов Pⁿ (t₁, …,tn) по-видимому, не содержат логических констант. Однако, неявным образом здесь присутствует логическое отношение принадлежности свойства Р некоторому предмету t при n= 1 или о наличии отношения Pⁿ  между предметами  t₁, …,tn из области D.

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

Правила эти таковы. Значение простого (атомарного) высказывания Pⁿ (t₁, …,tn), n >= 1, определяется в зависимости от заданных значений термов t₁, …,tn и предикатора Pⁿ   . Оно зависит от характера предметов данной предметной области. Положим, имеем формулу: P²(f¹₁ (a₁), f¹₁(a₂)). Предположим, что согласно заданной интерпретации D — множество людей: Р2 означает «больше»: f¹₁  «возраст»: a₁ — Петров, a₂ — Сидоров. Вся формула представляет собой высказывание «Возраст Петрова больше, чем возраст Сидорова». Высказывание истинно или ложно в зависимости от того, имеет или не имеет место данное отношение между возрастами Петрова и Сидорова.

Заметим, что в части лексики мы перевели здесь высказывание, полученное из определенной формулы рассматриваемого языка (ЯЛП), по существу на обычный естественный русский язык. В самом ЯЛП знаковой формой его является упомянутая формула. Подобные переводы обычно напрашиваются сами собой в силу того, что задание значений отдельных терминов — составляющих формулу — осуществляется посредством выражений естественного языка. Мы говорим «значение Р2 больше, a₁  и a₂  — соответственно Сидоров и Петров» и т. п.). Это значит, что приписывание предметных значений выражениям описываемого языка осуществляется методом перевода их в тот или иной естественный язык. Может показаться, что при упомянутых переводах высказываний данного языка на естественный теряется та самая точность их выражений, ради достижения которой как раз и строятся формализованные языки. Однако точность здесь по сравнению с естественными языками достигается не за счет более точною употребления отдельных терминов, — достаточная точность их уже должна быть обеспечена при осуществлении интерпретации выражений формализованного языка — а за счет определенных, стандартных способов построения высказываний и их логических форм. И она именно сохраняется, или точнее сказать, должна сохраняться при указанных переводах.

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

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

Логика предикатов формируется введением понятий логического следования для формул ЯЛП и закона логики предикатов.

Логическое следование

мы говорим, что для высказываний Ао и Во (выраженных теперь в описанном языке логики предикатов), имеет место отношение логического следования Ао t= Bo, если и только если оно имеет место для формул А1 и В1 представляющих собой логические формы указанных высказываний.

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

Отношение следования между формулами ^ А \= В имеет место е. т. е. при любой интерпретации дескриптивных терминов в А и В и при любых приписываниях значений свободным переменным при истинности первого истинно и второе, иначе говоря, ложно первое или истинно второе. Имеется в виду при этом, что, во-первых, если некоторый дескриптивный термин каким-то образом интерпретирован в А, то таким же образом он интерпретирован и в В (конечно, при наличии его в этой формуле), а, во-вторых, всем свободным вхождениям одной и той же переменной в А и В приписывается одно и то же значение.

А и В — метапеременные для формул ЯЛП.

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

конечное подмножество формул Av ..., Ап {п > 1) такое, что (Aj & ... & An) l= В. Последнее соотношение, как и в логике высказываний, равносильно тому, что из множества высказываний Av A2, ..., Ап следует В, что в свою очередь указывает на отмеченное ранее — в логике высказываний — свойство

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

Закон логики предикатов.

Формула А описанного языка логики предикатов является законом данной логической системы, то есть (t= А) е. т. е. при любой ее интерпретации и при любых приписываниях значений ее свободным предметным переменным в заданной области D. Получаемое высказывание является истинным. Законы логики предикатов называются также универсально-общезначимыми формулами логики предикатов.

Формула А называется общезначимой в некоторой области ^ D е. т. е. она истинна при любых приписываниях значений ее дескриптивным терминам и свободным переменным в этой области D. Формула А называется выполнимой, если она истинна при какой-нибудь интерпретации и при каком-нибудь приписывании значений ее свободным предметным переменным. В противном случае она называется невыполнимой.Поскольку в язык логики предикатов, как это иногда делается, мы не включаем пропозициональные переменные, никакая формула логики высказываний не является формулой логики предикатов. Однако из любого закона логики вы-

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

замена разных пропозициональных переменных одной и той же формулой логики предикатов).

Введением указанных понятий — законов логики предикатов и логиче-

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

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

Л Ant=B е.т. е. ИАр(Л2з(А2э...(АЛэ5)...));n последняя же, как мы видели раньше, равносильна t= ({Al &А2&.... & Ап) ZDB) — при любой расстановке скобок в конъюнкции согласно правилам построения формул. В связи с отмеченной неразрешимостью логики предикатов особое значение приобретает здесь формализация понятий следования и закона логики посредством построения логических исчислений. Именно исчисление дает возможность во многих случаях синтаксическим образом решать вопрос, является ли некоторая формула законом, или соответственно есть ли некоторое отношение следования, когда мы не можем решить этот вопрос посредством семантического анализа. Для логики высказываний исчисление высказываний, вообще говоря, не является необходимым. Оно скорее нужно

как часть логического исчисления для формул ЯЛП.

^ Исчисление предикатов.

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

1. Vx А{х) з A(t) — схема Уи.

2. A(t) з 3 хА{х) — схема Эв.

3. VJC (Вз С{х)) D(BDVX С(Х)) — схема введения V в консеквент. (с англ. на рус. - правая часть условного высказывания, следствие)

4. V* [С{х) з В) з {Зх С{х) з В) — схема введения 3 в антецедент. A{t) — результат правильной подстановки терма t вместо х в А(х)\ В — не содержит х свободно. Правило VB (правило введения квантора общности, иное

A[t) название: правило обобщения): ——г (из А непосредственно VХ/\ выводимо VxA).

Определение формулы логики предикатов.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

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

  1. Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).

  2. Если F(·,·, …,·) – n-местная предикатная переменная или постоянный предикат, а x1, x2,…, xn– предметные переменные или предметные постоянные (не обязательно все различные), то F(x1, x2,…, xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

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

  4. Если А – формула, то – формула, и характер предметных переменных при переходе от формулы А к формуле не меняется.

  5. Если А(х) – формула, в которую предметная переменная х входит свободно, то слова и являются формулами, причем, предметная переменная входит в них связанно.

  6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.


^ Свободные и связанные вхождения переменных

в формулы.

Каждый случай, когда в последовательности знаков, представляющей собой формулу А, встречается предметная переменная х, называется в х о ж д е н и е м этой переменной; каждое вхождение в формулу А предметной переменной х в часть вида \fxB или 3 хВ, называется с в я з а н н ы м . Подформула В формул указанного вида называется о б л а с т ь ю д е й с т в и я соответственно квантора общности V и квантора существования 3 с переменной х. Связанным является вхождение переменной, стоящей непосредственно за квантором, и каждое вхождение ее в область действия

квантора. Всякое вхождение х в отличие от указанного, называется свободным. Переменная х, имеющая связанные вхождения в формулу А, называется с в я з а н н о й в этой формуле; переменная, имеющая свободные вхождения в формулу А, называется с в о б о д н о й в этой формуле. Обратим внимание на то, что согласно определению свободной и связанной переменной одна и та же переменная в одной и той же формуле может быть свободной и связанной. Такова, например, переменная х1 в формуле ^fxlPl{xl)v02(xv x2); переменная х2 является здесь свободной, но не связанной. Мы рассматриваем здесь только такие термы, в которых все переменные могут иметь лишь свободные вхождения и, значит, являются свободными переменными. Формула и терм, не содержащие свободных переменных, называются соответственно з а м к н у т о й ф о р м у л о й и з а м к н у т ы м т е р м о м (очевидно, что для рассматриваемых здесь термов, если терм замкнут, то он вообще не содержит переменных).
^ Логические и кванторные операции над предикатами.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Отрицанием предиката P(x) называется новый предикат или, который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству IP.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным. Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных хi, i= подставить их значения, то получим высказывание.

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

^ 1. Запись математических предложений и определений в виде формул логики предикатов.

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

Пример 1.

Определение предела “” функции ƒ(х), определенной в области E, в точке x0: . Используя трехмесный предикат , запишем: ,

где .

Пример 2.

Определение непрерывности функции в точке.

Функция , определенная на множестве E, непрерывна в точке , если , где .

Пример 3.

Определение возрастающей функции.

Функция , определенная на множестве E возрастает на этом множестве, если .

Здесь использован двуместный предикат .

^ 2. Построение противоположный утверждений.

Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет утверждение .

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

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

Последняя формула дает не негативное, а положительное определение неограниченной функции.

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

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

3 Прямая, обратная и противоположная теоремы.

Рассмотрим четыре теоремы:

, (1)

, (2)

, (3)

. (4)

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

Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

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

Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами.

Например, для теоремы “Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является теорема “Если четырехугольник является прямоугольником, то его диагонали равны” (2). Для теоремы (1) противоположной является теорема “Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником ” (3), а для теоремы (2) противоположной является теорема “Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.

Ясно, что прямая и обратная теоремы , вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны.

Действительно: .

Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

^ 4 Необходимые и достаточные условия.

Рассмотрим теорему

(1)

Как отмечалось, множество истинности предиката есть множество . Но тогда множеством ложности этого предиката будет . Последнее множество будет пустым лишь в случае, когда (см. рисунок).

Итак, предикат является истинным для всех том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x).

Так, в теореме “Если х – число натуральное, то оно целое ” предикат Q(x): “ х – число целое ” логически следует из предиката Р(х): “х – число натуральное” , а предикат “х- число натуральное” является достаточным условием для предиката “ х – целое число”.

В таком случае из теоремы (1)следует, что условия Р(х)являются достаточными для Q(x), а из теоремы (2) следует, что условие Р(х)является необходимым для Q(x).

Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(х)является необходимым и достаточным для Р(x).

Иногда вместо логической связки “необходимо и достаточно ” употребляют логическую связку “тогда и только тогда”.

Так как здесь истинны высказывания (1) и (2), то истинно высказывание

.

Заключение.
Разработанный в современной символической логике ме­тод построения логических исчислений является важнейшим ее результатом. Его теоретическая и практическая значи­мость состоит в том, что благодаря ему возникает возмож­ность доказательства любой формулы, представляющей за­кон логики, из бесконечного множества таких формул, а также осуществлять соответствующий вывод для любого слу­чая — опять-таки из бесконечного множества случаев отношения логического следования. В основе логических ис­числений, как мы видели, лежат специальные логические языки. Наряду с рассмотренными выше возможностями ис­пользования этих языков для решения многих логических вопросов, и в первую очередь для точного определения ос­новных понятий логики (логическое следование и закон ло­гики), следует заметить, что в этих языках имеются, по су­ществу, точные понятия логической формы и логического содержания мыслей, которые мы используем в дальнейшем.
Список литературы

1. Е. К. Войшвилло, М. Г. Дегтярев Логика, Москва, 2001.

2. А.А. Марков, Н. М. Нагорный Теория алгоритмов, Москва, 1984.

3. А.В.Гладкий Математическая логика, 1998.

4. П.С Новиков Конструктивная математическая логика с точки зрения классической, 1977.

5. Верещагин Н.К., Шень А Языки и исчисления, 2000.

6. Новиков Ф.А. Дискретная математика для программистов, 2000.

7. Клини С. Математическая логика, 1973.

8. Сайты в Интернете: http://mathlog.h11.ru

http://www.book-ua.org






Скачать файл (309.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru