Колмогоров, Драгалин - Введение в математическую логику (947386), страница 10
Текст из файла (страница 10)
Если же к Т. присоединить в качеств аксиомы формулу Р(Рь,ь, Р„), то по шравилу подстановк (5) из нее мбжно вывести формулу Р(Вь ..., В,) и полу чить, таким образом, противоречие в расширенной теории 48 $9. О ЛОГИКЕ ПРЕДИКАТОВ 1. Язык логики предикатов является расширением языка логики высказываний. Теперь мы употребляем два набора исходных символов. Это, прежде всего, индивидныв (или предметные) переменные иь иь, которые мы обозначаем через х, у, г, ..., и, кроме того, предикатные буквы вида Р~ь где й 1'=О, 1, 2, ...
Буква Рг~ называется (-местной (1-арной) предикатной буквой. ° Нульместные преднкатные буквы назовем пропозициональными, Преднкатные буквьг обозначаем через Р, (г, В, .... Формулы логики предикатов определяются индуктивно с помощью следующих ниже трех пунктов. Первый пункт— базис этой индукции, а остальные' — порождающие правила.
1) Всякая пропозициональная буква есть формула; если Р есть и-местная предикатная буква, п)0, и хь ..., х„— индивидные переменные, то Р(хь „х„) есть формула. 2) Если А и  — формулы, то формулами являются и следующие комбинации символов: (АЛВ), (А~/В), (А:эВ), ") А. 3) Если А — формула и х — индивидная переменная, то у'хА н й хА суть формулы. Все формулы строятся из формул нида 1) с помощью последовательного применения правил 2) и 3). Например, формулой является выражен~не (Д и1Р~~(иь из)~Р'1(из)), которое, используя метаобозначения, будем записывать (опуская также внешние скобки) как ~хР(х, у):о1е(у).
Вхождение предметной переменной х в формулу А может быТь свободным или связанным. 1) В формулу Р(х„... х,) переменные хь ..., х„входят свободным образом. 2) Свободное вхождение переменной х в формулы А н В остается свободным и в формулах (АЛВ), (А~/В), (А:э В), ) А, у'уА, й уА, если переменная у отлична от х. 3) Свободное вхождение переменной х в формулу А де-- лается связанным в формулах у'хА, ЗхА. 4) Связанные вхождения в А и В остаются связанными в формулах (АЛВ), (ЮВ), (А~В), ) А, )~хА, ДхА.
Формула называется замкнутой, или предложением, если в ней нет свободных вхождений предметных переменных.. Одна и та же переменная может входить в формулу в разных, местах и свободно, и связанно. Если переменная входит свободно (хоть один раз) в формулу, она называет- ся параметром формулы. Предложения суть формулы, не содержащие параметров. 2.
Формула логики предикату получает определенную интерпретацию, если указано непустое множество М и за- даны истинностные значения каждого из входящих в фор- мулу предикатных символов как функций (со значениями О и 1) от элементов М; (Р(уп-.,у )! =)'(уп-.,у.), где 1:М" 1У. Если задана интерпретация формулы, то можно вычис- .лить и ее исти~нностное значение как функцию от парамет- ров индукцией по построению формулы. При этом значения кванторов вычисляются следующим образом: ! ~ хА (х, у,, ..., у„) ) = ппп ( А (х, у„..., у„) ), еем (ДхА(х, у,,...,у„) ( =гпах! А(х, ум ..., у„) !.
*ем При данной интерпретации замкнутая формула имеет .определенное ист~инностное значение. Как и в логике высказываний, особый интерес,представ- .ляют общезначимые формулы (тождества, логические зако- ны), истинностное значение которых равно единице в лю- бой интерпретации (в случае незамкнутых формул надо еще добавить: при подстановке любых значений свободно вхо- дящих переменных из множества М).
Читатель должен владеть достаточно богатым запасом тождеств логики предикатов и уметь их обосновывать при .помощи содержательных теоретико-множественных сообра- жений. Ряд таких формул появится в гл. П. Формула, ложная в любой интерпретации, называется противоречием. Если формула не является противоречием, то она выполнима: ее истннностное значение равно едини- це хотя бы при одной интерпретации (и, для незамкнутых формул, при каком-либо наборе значений свободных пере- менных). Рассмотрим в виде примера такую формулу: )ух ) Р(х, х) Л ух~ура (Р(х, у) Л Р(у,г) ~ Р(х г)) Л~х 3уР(х, у), Зта формула выполнима, тзк как она истинна в интерпрета.ции, где множество М есть множество натуральных чисел, а преднкат Р(х, у) интерпретируется как х(у.
-50 Вместе с тем зта формула не,может быть выполнима ни на каком конечном множестве М. В самом деле, из истинности формулы в М следует существование ~последовательности аь аз, ..., а„, ... элементов М, для которых Р(аь а~) при ~'(1, но 1 Р(аь а;), если а;=аь так что все элементы а~ различны. Можно показать, что из выполнимости формулы в некоторой интерпретации следует ее выполнимость и в счетной интерпретации, так что для решения вопросов об общезначимости или выполнимости формул исчисления предикатов нет необходимости выходить за,пределы интерпретаций с конечными или счетными множествами М.
3. Можно формализовать теорию общезначимых формул логики прединатов и получить исчисление иредикатов, аналогичное исчислению высказываний. Оказывается, что такое исчисление также будет полным: всякая общезначимая формула будет в нем выводима. Аккуратному изложению этого круга вопросов посвящены следующие главы. Глава П ЛОГИКО-МАТЕМАТИЧЕСКИЕ ЯЗЫКИ. ЛОГИЧЕСКИЕ ЗАКОНЫ 5 Ъ ЯЗЫК ПЕРВОГО ПОРЯДКА. ФОРМУЛЫ И ТЕРМЪГ Теперь мы дадим точные определения ряда понятий, которых шла речь в первой части. При,исследовании некоторой математической теории об щий подход состоит в том, что следует, прежде всего, фикси ровать логика-математический язык, формулы которого бу дут выражать суждения и отношения рассматриваемой тео рии. Начнем с изучения самого распространенного вида ло гико-математических языков — языков первого порядк (языков первой ступени).
1. Язык первого порядка задается набором из четырех множеств И=( Зг(, Спз1, Гп, Рг ) (этот набор из четырех множеств иногда называется сиен турой языка 11, мы будем отождествлять язык с его сиги атурой). Здесь 1) Зг( — непустое множество, элементы которого назы ваются сортами объектов (сортами индивидов, или прост сортами). Для каждого сорта пйБг1 мы фиксируем счетны набор символов и",, и",..., и'„',.... Эти символы называются переменными сорта и, или предметными (индивидными) переменными сорта и. Переменные (произвольного сорта) мы будем обозначать через х, у, г, ..., иногда указывая их сорт х", у", г", ... Разумеется, мы считаем, что перемен ные как символы отличаются от других символов языка.
В частности, любые две переменные различных сортов различны. С каждой переменной х языка фиксированным образом связан определенный сорт языка. Наиболее часто встречаются языки' с одиим-единственным сортом, односортные языки. В этом случае множество ЗГ1 состоит из единственного элемента. 2) Спз1 — множество (может быть, и,пустое) константг языка й (в другой терминологии — предметных констант, индивидных констант, индивидных символов). Каждой кон-' станте сяСпз1 языка приписан определенный сорт пяЗГЕ Константы различных сортов различны.
3) гп — множество (может быть, и пустое), элементы которого называются функциональными символами языка д (функциональными буквами). С каждой функциональной буквой (еиРп однозначно связан некоторый объект — вид данной функциональной буквы. Вид функциональной буквы есть выражение (пь ..., пь- и), где п„п суть сорта языка, А)0. Число й,называется ко- личеством.аргументных мест ( (арностью символа (). Сорт ги называется сортом (-го аргументного места символа ), а сорт и называется сортом самого символа ~ (или сортом значений символа )). Как всегда, символы различных видов различны. В наиболее популярном случае односортного языка для задания вида функционального символа достаточно указать количество его аргументов.
4) Рг — непустое множество, элементы которого пазы; ваются предикатными символами (предикатными буквами) языка й. С каждой предикатной буквой Р~Рг связан не- который объект — вид данной предикатной буквы. Вид пре- днкатной буквы Р есть выражение (пь ..., и,), где и, суть сорта языка, йъО. Число й называется количеством аргу- ментных мест символа Р (арностью символа Р). Сорт и, называется сортом (-го аргументного места символа Р. В отличие от случая функциональных символов, здесь мы не исключаем возможности й=О. Нульместные предикатные символы называются пропозициональными переменными (пропозициональными буквами или символами). 2. Если задан язык Я, то можно определить некоторые правильно построенные тексты, составленные из символов ьг, скобок, запятых и некоторых дополнительных символов (ло- гических символов). Эти тексты называются вырагкениями языка Й и подразделяются на термы и формулы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
