Дискретная математика (998286), страница 21

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

Текст из файла (страница 21)

В атоме (или атомарной формуле) Р(гы..., г„) предикат Р должен быть п-местным. Вхождения переменных в атомарную формулу называются свободными. Свободные вхождения переменных в формулах А и В остаются свободными в формулах ~А и А — + В. В формулах Ых А и Лх А формула А как правило имеет свободные вхождения переменной х. Вхождения переменной х в формулы Ых А и Л х А называются связанныии. Вхождения других переменных (отличных от х), которые были свободными в формуле А, остаются свободными и в формулах Ы х А и 3 х А.

Одна и та же переменная может иметь в одной 'опущены.' В то же время уделено. внимание прагматическим аспектам теории, то есть ответу на вопрос, что выразимо и что невыразимо в исчислении предикатов. 120 Глава 4. Логические исчисления и той же формуле как свободные, так и связанные вхождения. Формула, не содержащая свободных вхождений переменных, называется замкнутой. Пример Рассмотрим формулу Ых (Р(х) -| Бу Я(х,у)) и ее подформулы. В подформулу В у Я(х, у) переменная х входит свободно, а оба вхождения переменной у связана| (квантором существования).

Таким образом, эта подформула не замкнутж С другой стороны, то же самое вхождение переменной х в подформулу Я(х,у) является связанным вхождением в формуле Ых (Р(х) + Бу |е(х,у)). В этой формуле все вхождения всех переменных связаны, а потому формула замкнута. ЗАМЕЧАНИЕ Язык теории Г не содержит квантороэ, поэтому понятия свободного и связанного.вхокдеиия перемеш|ых не применимы непосрелствешю. Обычно длл удобства полагают, что эсе формулы теории Г. замкнуты. Формулы вида А и — А, где А — атом, называются литеральными формулами (или литералами). В формулах Ых А и Б х А подформула А называется областью действия кван- тора по х.

Обычно связки и кванторы упорядочивают по приоритету следующим образом: -,Ы, Э, вэ, Ы,-+. Лишние скобки при этом опускают. Терм г называется свободным для переменной х в формуле А, если никакое свободное вхождение переменной х в формулу А не лежит в области действия никакого квантора по переменной у, входящей в терм й В частности, терм г свободен для любой переменной в формуле А, если никакая переменная терма не является связанной переменной формулы А.

Пример 1. Терм у свободен для переменной х в формуле Р(х), но тот же терм у не свободен для переменной х в формуле Ыу Р(х). 2. Терм Дх, э) свободен для переменной х в формуле Ыу Р(х, у) -ь | |(х), но тот же терм Г(х, э) не свободен для переменной х в формуле Б э Ыу Р(х, у) -+ |)(х). й Аксиомы (логические): любая система аксиом исчисления высказываний, плюс Р| '. ЫХ А(х) -+ А(т), Рэ: А(Г) -+ Ях А(х), где терм т свободен для переменной х в формуле А. 121 4.4. Исчисление предикзтов 4.

Правила вывода: А, А — ~В В-+А(х) А(х)-+В + В ' В +Чх А(х) ' 3х А(х) -+'В где формула А содержит свободные вхождения переменной х, а формула В их не содержит. Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Исчисление предикатов, которое содержит предметные константы и/или функторы и/или предикаты и связываюшие их собственные аксиомы, называется прикладным.

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

Практика показывает, что прикладного исчисления предикатов первого порядка оказывается достаточно для формализации содержательных теорий во всех разумных случаях. 4.4.2. Интерпретация Интерпретация 1 (прикладного) исчисления предикатов Х с областью интер- претации (или носителем) М вЂ” это набор функций, которые сопоставляют м каждой предметной константе а элемент носителя 1(а), 1(а) е М; м каждому п-местному функтору / операцию 1Я на носителе, 1(У): М" — > М; м каждому п-местному предикату Р отношение 1(Р) на носителе, 1(Р) с М". Пусть х = (хы... ) — набор (последовательность) переменных (входящих в формулу), а в = (вы...

) — набор значений из М. Тогда всякий терм Д(гы..., г„) имеет значение на в (из области М), то есть существует функция в': (г) -+ М, определяемая следуюшим образом: в'(а):=1(а), в'(х;):=в,, в*(У(гы...~г„)):=1УНв (гг) в (гд)). Всякий атом Р(гы..., г„) имеет на в истинностное значение и'(Р), определяемое следующим образом: в'(Р(гы..., г„)): =(в'(г1),..., в'(г„)) Е 1(Р).

Если в'(Р) = И, то говорят, что формула Р выполнена на в. Формула - А выполнена на в тогда и только тогда, когда формула А не выполнена на ж Формула А -+ В выполнена на в тогда и только тогда, когда формула А не выполнена на в или формула В выполнена на в, Глава 4. Логические исчисления 12г Формула Чх1 А выполнена на в тогда и только тогда, когда А выполнена на любом наборе в', отличающемся от в, возможно, только г'-м компонентом. Формула Вх; А выполнена на в тогда и только тогда, когда А выполнена на каком-либо наборе в', отличающемся от в, возможно, только г-м компонентом. Формула называется истинной в данной интерпретации Х, если она выполнена на любом наборе в элементов М. Формула называется ложной в данной интерпретации 1, если она не выполнена ни на одном наборе в элементов М. Интерпретация называется моделью множества формул Г, если все формулы из Г истинны в данной интерпретации.

Всякая замкнутая формула истинна нли ложна в данной интерпретации. Открытая (то есть не замкнутая) формула А(х, у, г,... ) истинна в данной интерпретации тогда и только тогда, когда ее замыкание 'ч'х Уу Чг. А(х, у, г,... ) истинно в данной интерпретации. Это обстоятельство объясняет, почему собственные аксиомы прикладных теорий обычно пишутся в открытой форме. 4.4.3. Общезначимость Формула (исчисления предикатов) общвзначима, если она истинна в любой ин- терпретации. ТЕОРЕМА Формула кгх А(х) — к А(г), где терм г свободен для переменной х в формуле А, общезначима, доказатвпьство рассмотрим произвольную интерпретацию 1, произвольную последовательность значений из области интерпретации в и соответствующую функцию в'.

Пусть в*(гг) = аг и пусть г(х) — некоторый терм, а у: = г(... х... )(гг//х). Тогда в'(г) = вг(г'), где в1 имеет значение а1 на месте х. Пусть А(х) — формула, а терм г свободен для х в А. Положим А(г): = А(... х... )(г//х). Имеем: в'(А(г)) = И ч=ь в',(А(х)) = И, где вг имеет значение в'(г) на месте х. Если в'(ч'х А(х)) = И и терм г свободен для х в А, то в*(А(г)) = И. Следовательно, формула Чх А(х) -+ А(г) выполнена на всех последовательностях в произвольной интерпретации.

П ЗАМЕЧАНИЕ Можно показать, что формула А(г) -к Вх А(х), гле терм г свободен для переменной х в формуле А, общезначима. 4.4.4. Полнота чистого исчисления предикатоа Следующие две метатеоремы устанавливают свойства исчисления предикатов, аналогичные тем, которые установлены для исчисления высказываний в подразделе 4.3.8. Теоремы приводятся беэ доказательств, которые технически довольно сложны.

мз 4.4. Исчисление предикатов ТЕОРЕМА Всякая теорема чистого исчисления предикатов первого порядка об- щезначима. ТЕОРЕМА Всякая общезначимая формула является теоремой чистого исчисления предикатов первого порядка. 4.4.5. Логическое следование и логическая эквивалентность Формула В является логическим следствием формулы А (обозначение: А =~ В), если формула В выполнена на любом наборе в любой интерпретации, на котором выполнена формула А. Формулы А и В логически эквивалентны (обозначение; А = В), если они являются логическим следствием друг друга.

Имеют место следующие логические следования и эквавалентности: 4. Чх Чу А(х,у) = Чу Чх А(х,у), 5. Чх (А(х)йС) = Ух А(х)йС, 6. Эх (А(х)йС) = Эх А(х)йС, 7. С-+Чх А(х) = ч'х (С вЂ” + А(х)), 8. Чх А(х) -+ С ь Эх (А(х) -+ С), где формула С не содержит никаких вхождений переменной х. Для всякой формулы А существует логически эквивалентная ей формула А' в предваренной форме: А':=Ягхг...Я х„А(хы...,х„), где Яы..., ߄— некоторые кванторы, а А — бескванторная формула. 4.4.6. Теория равенства Теория равенства Я вЂ” это прикладное исчисление предикатов, в котором имеются: 1. Собственный двухместный предикат = (инфиксная запись х = у).

2. Собственные аксиомы (схемы аксиом): Е1. Чхх=х, Ег ' (х = у) — + (А(х) -+ А(х)(у/х)). ТЕОРЕМА В теории Я выводимы следующие теоремы: 1. Ье 1 = г для любого терма А 2. 1 е х=у-+у=х, 1. Чх А(х) = Эх А(х), 2. Чх (А(х) йВ(х)) = Чх А(х) йЧх В(х), 3. Эх (А(х) й В(х)) =ь Эх А(х) й Эх В(х), Эх А(х) =Ух А(х), Эх (А(х) у В(х)) = = Э х А(х) г Э х В(х), Чх А(х) ~l Чх В(х) =ь ~ Ч х (А(х) Ч В(х)), Эх Эу А(х,у) = Эу Эх А(х,у), Ч х (А(х) и С) = Ч х А(х) у С, Эх (А(х) ЧС) = Эх А(х) ч'С, С-+ Эх А(х) = Эх (С вЂ” ~ А(х)), Э х А(х) -+ С =э Ух (А(х) -+ С), 124 Глава 4. Логические исчисления 3.

мех=у-к(у= -+х= ). ДОКАЗАТЕЛЬСТВО 1. Из Е1 и Р1 по Мр, 2, Имеем: (х = у) — к (х = х -к у = х) из Ег при подстановке (х = х/А(х)). Значит, х = у, х = х Рз у = х. Но Ье х = х, следовательно, х = у 1-з у = х. По теореме дедукции Рз х = у — к у = х.

Характеристики

Список файлов книги