Структура исчисления предикатов - построение логического вывода - курсовая работа

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

Реферат по математической логике и теории алгоритмов выполнили студенты I-го курса Факультета ИВТ: Зубарев А., Столяров А., Докукин А., Китирисов Г.

Марийский Муниципальный Технический Институт

Факультет Информатики и Вычислительной Техники

Кафедра ИВС

Йошкар-Ола, 2003г.

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

Введение

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

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

Синтаксис языка логики предикатов Структура исчисления предикатов - построение логического вывода - курсовая работа (начальные знаки, термы, формулы)

I. Начальные знаки языка.

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


(нескончаемое счетное огромное количество).


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. Термы. Выражения этого Структура исчисления предикатов - построение логического вывода - курсовая работа типа являются аналогами имен естественного языка.

Определение: а) неважно какая предметная переменная и предметная константа есть терм; б) если есть термы и f¸ⁿ есть n-местный предметный функтор, то f¸ⁿ ( есть терм; в) ничто, не считая обозначенного в пт а) и б), не есть терм.

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

Определение: а) если термы и P¸ⁿn-местный предикатор, тоP¸ⁿ ( ) есть формула (атомарная);

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

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

А &В.

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

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

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

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

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

Обратим внимание на то, что согласно определению свободной и связанной переменной одна и та же переменная в одной Структура исчисления предикатов - построение логического вывода - курсовая работа и той же формуле может быть свободной и связанной. Такая, к примеру, переменная x₁ в формуле ∀ x₁ P¹(x₁) ∨ Q²(x₁, x₂); переменная x₂ является тут свободной, но не связанной. Мы рассматриваем тут только такие термы, в каких все переменные могут иметь только свободные вхождения, и, означает Структура исчисления предикатов - построение логического вывода - курсовая работа, являются свободными переменными. Формула и терм, не содержащие свободных переменных, именуются соответственно замкнутой формулой и замкнутым т е р м о м (разумеется, что для рассматриваемых тут термов, если терм замкнут, то он вообщем не содержит переменных).

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

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

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

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

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

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

2) Условная интерпретация. 3) Интерпретация всеобщности Структура исчисления предикатов - построение логического вывода - курсовая работа.

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

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

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

Данные выше объяснения относительно тех смыслов, которые формулы получают при интерпретации, указывают на принципы перевода выражений языка логики предикатов на Структура исчисления предикатов - построение логического вывода - курсовая работа естественный язык. Но в их можно усмотреть решение и оборотной задачки — перевод с естественного на язык логики предикатов, хотя тут требуются и определенные дополнительные объяснения. Сначала они связаны с отсутствием в формулах ЯЛП общих имен. Общие имена тут употребляются только для свойства задаваемой всякий раз при выражении некого выражения области D Структура исчисления предикатов - построение логического вывода - курсовая работа значений предметных переменных. В составе самих формул общие имена — в предложениях обыденного языка — заменяются предикаторами. Так, предложение «Все студенты пединститута готовятся стать преподавателями» может быть переведено на язык логики предикатов двойственно зависимо от выбора значений переменных. Мы можем взять в качестве такой «множество студентов пединститута». Обозначив тогда через P Структура исчисления предикатов - построение логического вывода - курсовая работа1 свойство «готовятся стать преподавателями», получим «∀xP'(x)». С учетом данной области это должно быть прочитано как «всякий студент пединститута х готовится стать преподавателем». Для более полного выражения смысла выражения можем взять в качестве области «студенты» вообщем, а общее имя «студент пединститута» объяснить как предикатор, взяв для него, к примеру Структура исчисления предикатов - построение логического вывода - курсовая работа, символ (предикатор) S 1 получим ∀x(S1 (x) ⊃ P1 (x). Предложение звучит сейчас так: «Для всякого студента х правильно, что если он обучается в пединституте, то он готовится стать преподавателем». Выражение «Некоторые студенты пединститута готовятся стать преподавателями» при том же выборе области D и предикаторов запишется в виде Структура исчисления предикатов - построение логического вывода - курсовая работа ∃x(S(x)&P(x))

Направьте внимание, когда выражение предваряет квантор общности (другими словами начальное выражение является общим), то дальше употребляется логическая связка ⊃; в случае, когда таким является квантор существования (выражение является личным), то для его записи на ЯЛП употребляется связка &.

Для полной записи предложения «Во всяком государстве имеется город, который Структура исчисления предикатов - построение логического вывода - курсовая работа является его столицей» навязывается необходимость ввести предикаторы: правительство с аргументом — х (возьмем для обозначения из начальных знаков предикатор P1 ), город с аргументом — у (обозначим его Q), принадлежит — город у государству х (обозначим R 2 ) и столица — город y страны х (обозначение S2 ). В таком случае появляется трудность Структура исчисления предикатов - построение логического вывода - курсовая работа с чертой области значений переменных х, у. Можно считать, что такой является огромное количество населенных людьми территорий. Взяв в качестве области D огромное количество таких территорий и используя обозначенные предикаторы, получим запись нашего суждения в ЯЛП: ∀x(P(x) ⊃ (∃y(Q(y)&R(y, x)&S(y, x))). Буквальное произнесение его Структура исчисления предикатов - построение логического вывода - курсовая работа таково: «Для всякой населенной местности х правильно, что если х есть правительство, то существует населенная территория у, такая, что у — город и у принадлежит государству х, а у есть столица х.

Как мы лицезрели, выражения естественного языка, подлежащие переводу на ЯЛП, спецефическим образом стандартизируются, верно выделяются части выражения: классы Структура исчисления предикатов - построение логического вывода - курсовая работа либо отдельные предметы, о которых нечто утверждается (либо отрицается). Если это классы, то выясняется, ко всем предметам класса либо только к части их относится утверждение либо отрицание (соответственно употребляются кванторы общности ∀ либо существования ∃). И в конце концов, определяется то, что конкретно в выражении утверждается (либо отрицается). Примеры таких стандартизации Структура исчисления предикатов - построение логического вывода - курсовая работа выражений естественного языка, осуществленные еще до записи их на ЯЛП, читатель может отыскать в самом начале данного параграфа.

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

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

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

Как и в логике выражений, мы говорим, что для выражений A₀ и B₀ (выраженных сейчас в описанном языке логики предикатов), имеет место отношение логического следования A₀ ⊨B₀, если и только если оно имеет место для формул А и В1 представляющих Структура исчисления предикатов - построение логического вывода - курсовая работа из себя логические формы обозначенных выражений.

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

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

Отношение следования меж формулами A₀ ⊨B₀ имеет место е Структура исчисления предикатов - построение логического вывода - курсовая работа. т. е. при хоть какой интерпретации дескриптивных определений в А и В и при всех приписываниях значений свободным переменным при истинности первого поистине и 2-ое, по другому говоря, неверно 1-ое либо поистине 2-ое. Имеется в виду при всем этом, что, во-1-х, если некий дескриптивный термин каким-то образом интерпретирован Структура исчисления предикатов - построение логического вывода - курсовая работа в А, то таким же образом он интерпретирован и в В (естественно, при наличии его в этой формуле), а, во-2-х, всем свободным вхождениям одной и той же переменной в А и В приписывается одно и то же значение. Из огромного количества выражений Г ₀ следует выражение Структура исчисления предикатов - построение логического вывода - курсовая работа B ₀если и только если это отношение имеет место соответственно меж обилием формул Г и В, представляющих из себя логические формы упомянутых выражений. Последнее же отношение Г ⊨В имеет место, е. т. е. в составе Г имеется конечное подмножество формул А1, ..., Аn (n >= 1) такое, что (А1 & ... & Аn) ⊨В. Последнее соотношение, как и Структура исчисления предикатов - построение логического вывода - курсовая работа в логике выражений, равносильно тому, что из огромного количества выражений А1, ..., Аn следует В, что в свою очередь показывает на отмеченное ранее — в логике выражений — свойство дела следования, состоящее в том, что если некое выражение следует из какого-то огромного количества выражений, то оно является следствием также Структура исчисления предикатов - построение логического вывода - курсовая работа хоть какого расширения этого огромного количества.

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

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

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

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

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

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

А1, .... Аn ⊨В е. т. е. ⊨ (А1 ⊃ (А2⊃ (А2 ⊃ ... (Аn⊃В) ... ));

последняя же, как мы лицезрели ранее, равносильна ⊨ ((А1 &А2 & ... &An) ⊃В) — при хоть какой расстановке скобок в конъюнкции согласно правилам построения формул.

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

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

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

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

1. ∀x A(x) ⊃ A(t) — схема∀и .

2. A ( t ) ⊃∃х А(х) — схема ∃в.

3. ∀x(В ⊃С(х)) ⊃(В ⊃∀xС(х)) схема введения ∀ в консеквент .

4. ∀x(С(х) ⊃В) ⊃ (∃x⊃C(x)⊃ В) — схема введения ∃ в антецедент.

A ( t ) — итог правильной подстановки Структура исчисления предикатов - построение логического вывода - курсовая работа терма ( заместо х в А(х); В — не содержит х свободно.

Правило ∀в (правило введения квантора общности, другое

A ( t ) заглавие: правило обобщения): —— (из А конкретно выводимо∀xA).

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

Формула В данного вывода находится в зависимости от некого допущения А, если и только если: а) она есть само допущение А;

б) выходит из неких формул по правилам системы (из С⊃В и С по m. р. либо из С по ∀в Структура исчисления предикатов - построение логического вывода - курсовая работа), какая-нибудь из которых находится в зависимости от А. Более обычным образом понятие зависимости разъясняется в описываемой дальше системе натурального вывода, существенно проще осуществляются там сами выводы и подтверждения.

Натуральная система исчисления предикатов

Постулатами системы (начальными правилами) являются все правила натуральной системы исчисления выражений и правила для кванторов Структура исчисления предикатов - построение логического вывода - курсовая работа.

Правила вывода для выражений с кванторами:

при условии, что никакое допущение из Г не содержит x свободно;

A[Г]

∀x A[Г]

∀в :

∀и :

Итог правильной подстановки терма t заместо x в A(x);

∀x A(x) [Г]

A(t) [Г]


∃в :

A(t) [Г]

∃x A(x Структура исчисления предикатов - построение логического вывода - курсовая работа) [Г]

Тут ∃x A(x) – имеющееся в выводе допущение, а В и никакое допущение из Г не содержат x свободно.

B[Г, A(x)]

B[Г, ∃x A(x)]

∃и :

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

Если в выводе получена формула ∃х А(х} и необходимо вывести В, не выводимую конкретно из имеющихся формул Структура исчисления предикатов - построение логического вывода - курсовая работа, вводим допущение А(х), применяя метод рассуждения согласно ∃и.

Разглядим несколько примеров выводов.

Схема подтверждения формул вида: ¬∃xA(x) ⊃∀x¬A(x):

+ 1. ¬∃x A(x) [1].

+ 2. A(x) [2].

3. ∃x A(x) [2] – из 2, ∃в.

4. ¬ A(x) [1] – из 1,3, ¬в.

5. ∀x¬A(x) [1] – из4, ∀в.

6. ¬∃x A(x) ⊃∀x¬A(x) [ - ] – из Структура исчисления предикатов - построение логического вывода - курсовая работа 5, ⊃в.

Схемы доказательств рассмотренных в аксиоматической системе аксиом «введения ∀ в консеквент» и «введения ∃ в антецедент»:

Подразумевается, что А не содержит х свободно.

+ 1. ∀x (A⊃ B(x)) [1].

+ 2. А [2].

3. A⊃ В(х) [1] —из 1, ∀и.

4. В(х) [1, 2] —из3 и 2, ⊃и.

5. ∀xB(x)[1, 2] —из 4, ∀в.

6. A⊃∀xB ( x ) [1] —из5, ⊃в.

7. ∀x (A⊃ B(x)) ⊃ (A Структура исчисления предикатов - построение логического вывода - курсовая работа⊃∀xB(x)) [ - ]—из 6, ⊃в.

+ 1. A⊃ (В(х) ⊃ A) [1].

+ 2. ∃xB(x) [2].

+ 3. В(х) [З].

4. В(х) ⊃ A [1]—из 1, ∀и.

5. А [1, 3] — из 3, 4, ⊃в.

6. A [1, 2]— из 5, ∃и.

7. ∃xB(x) ⊃ А [1]—из 6, ⊃в.

8. ∃x (B(x) ⊃ А) ⊃ (∃xB(x) ⊃ А) — из 7, ⊃в.

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

Г ⊨ B е. т. е. Г ⊢ B и ⊨ A е. т. е. ⊢ A.

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

I. Взаимовыразимость кванторов:

1. ∀xA(x) ~ ¬∃x¬A(x). 2. ∃xA(x) ~ ¬∀x¬A(x).

II. Законы образования контрадикторной противоположности:

1. ¬∀xA(x) ~ ∃x¬A(x). 2. ¬∃xA(x) ~ ∀x¬A(x).

III. Законыпронесениякванторов:

1. ((∀x Структура исчисления предикатов - построение логического вывода - курсовая работа A(x) & ∀x B(x)) ~ ∀x(A(x) & B(x))).

2. ((∃x A(x) v ∃x B(x)) ~ ∃x (A(x) v B(x))).

3. (∃x (A(x) & B(x)) ⊃ (∃x A(x) & ∃x B(x))).

4. ((∀x A(x) v ∀x B(x)) ⊃ ∀x (A(x) v B(x))).

5. (∀x (AvB(x)) ~ (Av Структура исчисления предикатов - построение логического вывода - курсовая работа∀xB(x))), если x не свободна в A.

6. (∃x (A & B(x)) ~ (A & ∃xB(x))), если х не свободна в А.

7. (∀x A(x) ⊃ B(x)) ⊃ (∀x A(x) ⊃ ∀x B(x))).

IV. Перестановка кванторов

1. ∀x∀yA(x, y) ~ ∀y∀xA(x, y).

2. ∃x ∃y A(x, y) ~ ∃y ∃x A Структура исчисления предикатов - построение логического вывода - курсовая работа(x, y).

3. ∃x ∀y A(x, y) ⊃ ∀y ∃x A(x, y).

V. Исключение квантора общности и введение квантора существования.

1. ∀x A(x) ⊃ A(t). 2. A(t) ⊃ ∃xA(x).

В обоих случаях А(t) есть итог правильной подстановки терма t заместо х в А(х).

VI. Законы Структура исчисления предикатов - построение логического вывода - курсовая работа устранения вырожденных кванторов. 1. ∀xА ~ А. 2. ∃x А ~ А, где А не содержит х свободно.

VII. Связь кванторов ∀ и ∃.

∀xA(x) ⊃ ∃xA(x).

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

Пример эквивалентных преобразований формулы

∀x (P(x) ⊃ ¬Q(x)) ⊃ ¬ ∃x(P(x) & Q(x)).

с Структура исчисления предикатов - построение логического вывода - курсовая работа внедрением неких из обозначенных в этом и прошлом параграфе схем эквивалентностей:

∀x (P(x) ⊃ ¬Q(x)) ⊃ ¬ ∃x(P(x) & Q(x)) ≡

≡ ¬∀x (P(x) ⊃ ¬Q(x)) v ¬ ∃x(P(x) & Q(x)) ≡

≡ ∃x ¬(P(x) ⊃ ¬Q(x)) v ¬ ∃x(P(x) & Q(x)) ≡

≡ ∃x (P(x) & ¬¬ Q(x)) v Структура исчисления предикатов - построение логического вывода - курсовая работа ¬ ∃x (P(x) & Q(x))≡

≡ ∃x (P(x) & Q(x)) v ¬ ∃x (P(x) & Q(x))≡

≡ ∃x (P(x) & Q(x)) v ∀x¬(P(x) & Q(x))≡

≡ ∃x (P(x) & Q(x)) v∀x(¬P(x) & ¬Q(x)).

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

Перечень литературы

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

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



struktura-mehanizma-upravleniya.html
struktura-metodicheskoj-razrabotki.html
struktura-mezhdunarodnoj-torgovli-tovarami-kurs-lekcij-2-e-izdanie-pererabotannoe-minsk-2006-udk-339-9076-6.html