Реферат: Структура исчисления предикатов построение логического вывода

Язык, логика иисчисление предикатов

Введение

Приступая к изучению языка логики предикатов (сокращенно — ЯЛП),полезно вспомнить основные особенности языков этого типа В ЯЛП явно должны бытьпредставляемы субъектно-предикатные структуры высказываний, от которых происходилоотвлечение при введении пропозициональных символов. Выражаемыми должны быть,например, высказывания видов. «aобладает свойством Р», «а иb находятся в отношении Р», «Для всякого предмета из некоторого множества Sверно, что он обладает свойством Р», «Для всякогопредмета из множества Sсуществует предмет этогомножества такой, что эти предметы находятся в отношении R»,«Если неверно, что всякие два предмета некоторого множества находятся вотношении R,то существуют по крайней мере два предмета этого множества, не находящиеся вэтом отношении», «Если во множестве S существует предмет х, который находится в отношении R с любым предметом уэтого множества, то для всякого предмета утого же множества существует предмет х такой,что последний находится в отношении Rк первому» и т. п.

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

₁,x₂,...и т.д. Потребность в общихименах при употреблений ЯЛП сохранится лишь для описания областей возможныхзначений этих переменных, что относится уже не к самому языку, а к метаязыку.Нужны также знаки свойств и отношений. Для выражения высказываний вида «Объемтела а больше объема тела b» или «Синус х меньше косинуса y» и т. п. необходимы,конечно, и предметные функторы. Впрочем, перечислим систематически основныетипы выражений описываемого языка, каковыми являются: исходные символы, термыи формулы. Описание этих выражений составит синтаксис ЯЛП.

СИНТАКСИС ЯЗЫКА ЛОГИКИПРЕДИКАТОВ (ИСХОДНЫЕ СИМВОЛЫ, ТЕРМЫ, ФОРМУЛЫ)

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

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

<img src="/cache/referats/16309/image002.jpg" v:shapes="_x0000_s1026">
(бесконечное счетноемножество).

<img src="/cache/referats/16309/image004.jpg" v:shapes="_x0000_s1028">
2. Предметные константы (аналоги собственных имен естественногоязыка): (также бесконечное счетноемножество).

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

P¹

, Q ¹, R¹, S¹, ...;

Р2, Q2, R2, S²

, ...;

…………………..

Pⁿ,Qⁿ,Rⁿ,Sⁿ

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

P

¹₁, P¹₂, P¹₃, …

P

²₁, P²₂, P²₃, … и т.д.

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

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

f

¹₁, f¹₂, …

f

²₁ ,f²₂, …

………….

f

ⁿ₁, fⁿ₂, …

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

5.Логические константы: ⊃,&,

",∃,∨,¬соответственно —импликация, конъюнкция, квантор общности, квантор существования, дизъюнкция иотрицание. (Зачастую вводят лишь некоторые из этих символов. Из кванторовдостаточны только ∀или ∃, из остальных, называемыхлогическими связками, достаточно: ⊃ и ¬, или ∨ и ¬, или & и ¬. Другие константы, как,впрочем, и другие знаки, могут вводиться по определению.)

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

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

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

Определение:а) любая предметная переменная и предметная константа есть терм; б) если <img src="/cache/referats/16309/image006.gif" v:shapes="_x0000_i1025">f¸

ⁿ есть n-местный предметный функтор, то f¸ⁿ (<img src="/cache/referats/16309/image006.gif" v:shapes="_x0000_i1026"> есть терм; в) ничто, кроме указанного в пунктах а) и б),не есть терм.

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

Определение:а) если <img src="/cache/referats/16309/image006.gif" v:shapes="_x0000_i1027"> термы и P

¸ⁿ n-местный предикатор, тоP¸ⁿ (<img src="/cache/referats/16309/image006.gif" v:shapes="_x0000_i1028">) есть формула(атомарная);

б)если А и В — формулы, то (А⊃

В), (А&В), (AvB), ¬A— формулы;в) если х есть предметная переменнаяи А — формула, то ∀ x A и ∃ xA— формулы; г) ничто, кроме указанного в пунктах а) — в), не естьформула.

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

А &В.

Использованныев определениях терма и формулы символы <img src="/cache/referats/16309/image006.gif" v:shapes="_x0000_i1029"> f¸

ⁿ, P¸ⁿ, A, B, x(и в дальнейшем возможно x₁, x ₂и т. д.) — знаки метаязыканазываемые также синтаксическими переменными, возможными значениями которыхявляются выражения соответствующей категории описываемого (объектного) языка.

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

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

СВОБОДНЫЕ ИСВЯЗАННЫЕ ВХОЖДЕНИЯ ПЕРЕМЕНЫХ В ФОРМУЛЫ

Каждыйслучай, когда в последовательности знаков, представляющей собой формулу А, встречается предметная переменная x,называется вхождением этой переменной; каждое вхождение в формулу А предметнойпеременной xв часть вида ∀

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

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

₁в формуле ∀ x₁ P¹(x₁) ∨ Q²(x₁, x₂); переменная x₂

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

СЕМАНТИКАЯЗЫКА ЛОГИКИ ПРЕДИКАТОВ

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

<st1:place w:st=«on»>I.</st1:place>Правилаопределения (задания) возможных значений предметных переменных и правилаприписывания предметных значений дескриптивным постоянным в составе рассматриваемыхв том или ином случае формул—интерпретация выражений языка. 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. Вычисление происходит в соответствии с правилами построения сложноготерма. Сложные термы образуются, как мы видели, с применением предметныхфункторов и строятся индуктивно. Значение такого терма вычисляетсяпоследовательно в соответствии с порядком его построения.

Пример.Имеем терм f

²₁(f²₁(a₁,a₂), f²₂(a₁, a₃)).

Пусть область D — целые положительные числа, a

₁ есть число 3, a₂ =4, a₃ = 5, f²₁ —сумма, f²₂ —произведение.

Тогда

f

²₁(a₁, a₂)=7;

f

²₂(a₁, a₃)=15;

f

²₁(f²₁(a₁, a₂), f²₂(a₁, a₃))=22.

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₂ — соответственно Сидоров и Петров» и т. п.).Это значит, что приписывание предметных значений выражениям описываемого языкаосуществляется методом перевода их в тот или иной естественный язык. Можетпоказаться, что при упомянутых переводах высказываний данного языка наестественный теряется та самая точность их выражений, ради достижения которойкак раз и строятся формализованные языки. Однако точность здесь по сравнению сестественными языками достигается не за счет более точною употребленияотдельных терминов, — достаточная точность их уже должна быть обеспеченапри осуществлении интерпретации выражений формализованного языка — а за счетопределенных, стандартных способов построения высказываний и их логическихформ. И она именно сохраняется, или точнее сказать, должна сохраняться при указанныхпереводах.

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

Формулавида А & В имеет значение «истина» — при данной интерпретации иприписывании значений свободным переменным — е. т. е. А имеет значение И и Вимеет значение И.

ФормулаAvВ — истина е. т. е. значение А равно И или значение В равноИ.

Формулевида А ⊃

В приписывается значение Ие. т. е. А имеет значение Л или Вимеет значение И.

Значениемформул вида ¬

А является И е.т.е. значение А есть Л.

Формулавида ∀

х А(х)имеет значение «истина» е.т. е. для всякого предмета а(i)из D, А(а(i)) — истина (А(а(i)) — результат замещениявсех свободных вхождений х в А(х) константой а(i)¹).

Формулавида ∃

х А(х)имеет значение истина е. т.е. существует предмет а в области Dтакой, что истинна формула A(a(i)).

Если значение некоторой формулы не является И, то она имеетзначение Л, но никакая формула не имеет одновременно значения И и Л.

Как уже говорилось, правила приписывания истинностных значенийполностью интерпретированным формулам неявным образом определяют также значениялогических констант «&», «v», «⊃

», «¬» и кванторов ∀и ∃и вместе стем и смыслы высказываний, образованных посредством соответствующих констант.Например, высказывания вида ∀х А(х),∃ х А(х), относящиеся к некоторой областииндивидов D, мы должны понимать,соответственно, как «для всякого предмета хиз D верно А(х}» и «существует предмет хв D такой, что верно А(х)». Нетрудно видеть, что &, v, ⊃,¬,представляют собой здесь логические связки — знаки функций истинности, —определенные ранее в разделе «Логика высказываний», но теперь применительно кформулам ЯЛП.

Примеры

Определимзначение формулы —

∀

x((P²(x, a₁) & P²((x, a₂))⊃ P²(x,y))

приусловии, что область возможных значений переменных D есть множество целыхположительных чисел, константам a

₁ и a₂приписаны соответственночисла 2 и 3, свободной переменной у —значение 6; предикатный символ Р2 имеет в качестве значенияотношения «делится». Ясно, что при указанной интерпретации данная формулавыражает определенное высказывание: в переводе на русский язык, «Для всякогоцелого положительного числа х верно,что если оно делится на 2 и на 3, то оно делится на 6». Ясно, что это высказываниеи соответственно наша формула истинны. Рассмотрим формулу ∀x ∃yP²(y, x).Если D — множество людей, Р2 — отец, то она представляетсобой высказывание «Для всякого человека хсуществует человек у такой, что онявляется отцом первого».

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

еще рефераты

Еще работы по математике

Реферат по математике

Геометрия Лобачевского

29 Августа 2013

Реферат по математике

Теория информации

20 Июня 2015

Реферат по математике

Древнегреческий учённый-математик АРХИМЕД

20 Июня 2015

Реферат по математике

Представление чисел в виде суммы двух квадратов и ...

20 Июня 2015