Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 49
Текст из файла (страница 49)
Впрочем, схемы А2 — А9 можно заменить конкретными аксиомами (т. е. формулами самой арифметики): А2'. х, х»- х,=х, и т, д., из которых любые формулы вида А2 — А9 можно получить с помощью правила обобщения и схемы аксиом Р1. В заключение суммируем особенности построения прикладных исчислений предикатов и, в частности, посмотрим, в чем здесь проявляется различие между «схемно-аксиомным» и «подстановочным» подходами к построению исчислений.
1. При «схемно-аксиомном» подходе общелогические схемы аксиом, как уже отмечалось, описываются формулами в метапеременных; собственные аксиомы прикладных исчислений могут задаваться либо также схемами (например, А1), либо конкретными аксиомами, т. е. формулами самого исчисления (например, Е1). Однако в любом случае собственные аксиомы, как правило, содержат фиксированные функциональные и предикатные буквы, которые тем самым наделяются некоторыми свойствами, отличающими их ог других букв исчисления (например, свойства предикатной буквы = определяются аксиомами Е! и Е2).
2. При «подстановочном> подходе системы аксиом ! (илн П) и Р!, Р2 являются конечной системой формул самого исчисления. Буква Р в аксиомах Р1 и Р2 — это преди- 237 катная буква исчисления (а не метапеременная, как в случае 1), являющаяся переменным преднкатом, вместо которого по правилу подстановки подставляются формулы исчисления. В собственных аксиомах прикладных исчислений появляются постоянные предикаты (например, равенство), вместо которых подставлять ничего нельзя.
Поэтому в языке исчисления предикатные и функциональные буквы приходится делить на две группы — переменные и постоянные, что не обязательно при первом подходе. 63. А|ЕТАТЕОРИЯ ЛОГИЧЕСКИХ ИСЧИСЛЕНИЙ Под метатеорией логических исследований понимается изучение их общих свойств и соответствия этих свойств целям, ради которых исчисления создавались. Некоторые задачи такого рода (связь между доказуемостью и истинностью) уже рассматривались. Здесь они будут систематизированы и изучены более подробно. Интерпретация и модели. Ценность всякой формальной теории в конечном счете определяется ее способностью описывать какие-то объекты и связи между ними.
Поэтому один из первых для любой теории вопросов — это вопрос о том, для описания каких объектов пригодна данная теория. Конечно, если ставить его как общую проблему соответствия научных знаний о мире самому миру, то он не может обсуждаться средствами лишь математики (поскольку математика в отличие от естественных наук имеет дело ие непосредственно с миром, а с формальными описаниями его различных фрагментов) н становится фундаментальной проблемой философии и методологии науки.
Такого рода проблемы лежат за пределами этой книги. Здесь речь пойдет о более простом случае, когда множество объектов, для которого строится формальная теория, само по себе представляет достаточно строго описанный предмет исследований. Более точно проблема адекватности формальной теории и описываемых ею объектов будет рассматриваться как математическая задача о соответствии между содержательно построенной теорией, рассматриваемой как множество объектов с операциями и отношениями на нем (т. е. как алгебраическая система — см.
гл. 2), и множеством высказываний об этой теории, построенном как формальное исчисление. При такой постановке задачи интуитивно ясное понятие интерпретации приобретает точный математический смысл. Интерпретация формальной теории состоит из множества М и однозначного отображения, которое каждой преликатной букве Р", ставит в соответствие а-местное отношение на М (интерпретирует ее как отношение на М), каждой функциональной букве ),".— н-местную операцию на М, каждой предметной константе — элемент М. Постоянные термы исчисления (не содержащие предметных переменных) при таком определении также отобразятся в элементы М. Таким образом, множество М (называемое областью интерпретации) рассматривается как основное множество алгебраической системы (см.
гл, 2). Всякая замкнутая, т. е, не содержащая свободных переменных, формула теории представляет собой высказывание об элементах, отношениях и функциях М, которое может быть истинным илй ложным. Значения истинности составных формул вычисляются в соответствии с входящими в иих логическими операциями. Открытая формула соозветствует некоторому отношению на М, при подстановке предметных констант она превращается в высказывание о том, что между элементами М, соответствующими подставленным константам выполняется данное отношение. Открытая формула называется еыполнимой' в данной интерпретации, если существует такая подстановка предметных констант, при которой она превращается в истинное высказывание.
Формула называется истинной в данной интерпретации, если она выполняется (т. е. превращается в истинное высказывание) при любой подстановке констант. Формула называется ложной в данной интерпретации, если она невыполнима. Интерпретация (а иногда область интерпретации М) называется моделью для множества формул Г, если любая формула Г истинна в данной интерпретации.
Интерпретация называется моделью теории Т, если она является моделью множества всех теорем теории Т, т. е. если всякая формула, доказуемая в Т, истинна в данной интерпретации. Если в Т доказуема некоторая открытая формула Р (которая, строго говоря, высказыванием не является), то в модели теории Т должны быть истинными все высказывания, получающиеся из Е всеми возможными подстановками констант на место снободных переменных формулы Р, и, следовательно, должно быть истинно высказывание )ух1 ...)(х,Р, где х„..., х„— свободные переменные формулы Р, ' Некоторые пз определяемых здесь понятий уже яспользовзлясь в $34, Это обстоятельство вполне соответствует правилу обобщения в исчислении предикатов и использованию открытых аксиом (например, Е2) в прикладных исчислениях.
Пример 6.б. а. Для теории с равенством, очевидно, моделью является любая интерпретация, при которой предикатной букве = поставлено в соответствие отношение равенства. Возможны и менее тривиальные интерпретации, Возьмем в качестве области интерпретации натуральный ряд Ж, в качестве интерпретации символа = — некоторое отношение 1т' эквивалентности на У (например, сравнимость по глоб 11), а все предикатные буквы теории (будем считать, что их конечное число) проинтерпретируем отношениями, которые не различают эквивалентные числа, т. е.
по существу являются отношениями между классами эквивалентности. В данном конкретном случае такими отношениями будут отношения, сформулированные в терминах остатков от деления на 11, например: «аР,Ь, если остаток от деления а на 11 меньше остатка от деления Ь на 11», «а обладает свойством Рм если остаток от деления а на 11 не превосходит 5» и т. д. Значения истинности высказываний, содержащих только такие отношения, не будут меняться, если в них одно число заменить числом из того же класса эквивалентности, т. е. имеющим тот же остаток от деления на 11. Поэтому аксиома Е2 в такой интерпретации будет истинна, хотя интерпретация символа = не совпадает с обычным отношением равенства. б.
В теории строгого частичного порядка (с аксиомами Ь)Е1 и ХЕ2) моделью будет любая интерпретация, при которой предикатная буква ( интерпретируется отношением «быть меньше». Однако почти столь же очевидно нз аксиом Ь)Е1 и ХЕ2 (хотя и выглядит парадоксально), что моделью этой теории будет и интерпретация, при которой символ ~ интерпретируется как отношение «быть больше»! Последний пример иллюстрирует существо формального подхода: в символы исчисления (даже самые привычные) не вкладывается никакого смысла, пока не введена их явная интерпретация. Но и введенная интерпретация, вообще говоря, не относится к числу средств самого исчисления: она позволяет осмыслить формулы исчисления, но не участвует в формальном выводе теорем. О формальных свойствах самого исчисления, его формул и формальных преобразований иад ними принято говорить как о синтаксисе исчисления; свойства исчисления, описанные в терминах его интерпретаций, — это семантика исчисления.
Например, метатеоремы 6.1, 6.7, 6.8 являются теоремами о синтаксисе, а метатеоремы 6.2 — 6.6 — теоремами о семантике. Непротиворечивость. Напомним, что формула называется общезначимой, если она истинна в любой интерпретации, н противоречивой, если оиа ложна в любой интерпретации, т. е. если ее отрицание общезначимо. Для любого множества общезначимых формул и, в частности, для чистого исчисления преднкатов (по теореме 6.5) любая алгебраическая система и вообще любое множество является моделью.
Напротив, для любого множества формул, содержащего хотя бы одну противоречивую формулу, моделей не существует, Аксиома Е1 теории с равенством не является общезначимой: существуют интерпретации (в смысле, указанном в начале этого параграфа), в которых она ложна. Примером такой интерпретации может служить всякое отображение, ко~орое предикатной букве = ставит в соответствие отношение .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
