Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » Колмогоров, Драгалин - Введение в математическую логику

Колмогоров, Драгалин - Введение в математическую логику, страница 13

DJVU-файл Колмогоров, Драгалин - Введение в математическую логику, страница 13 Математика (232): Книга - в нескольких семестрахКолмогоров, Драгалин - Введение в математическую логику: Математика - DJVU, страница 13 (232) - СтудИзба2013-09-15СтудИзба

Описание файла

DJVU-файл из архива "Колмогоров, Драгалин - Введение в математическую логику", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "математика" в общих файлах.

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 13 - страница

Например, если в формуле ЗуР(х, у, г) мы решим заменить переменную у на переменную х, то получится фор. мула ~хР(х, х, г), которая имеет совершенно иной смысл, чем исходная формула. Прежде всего, ~хР(х, х, й) зависит уже лишь от одного параметра г, а не от двух, и' задает всегда истинный предикат от г. Причина неприятности -состоит в том, что после неудачного переименования связанной переменной у первое вхождение переменной х,' которое раньше было свободным, стало связанным.

Указанное явление мы назовем коллизией переменных при переименовании связанных переменных. Коллизия переменных недопустима. По существу, эта ситуация хорошо известна и в обыденной математике. В сумме !о ~, ау переменная ! связана «квантороы суммы» Х, а переменная 1 остается свободной — параметром суммы. Вместо 1 мож- бз но подставить конкретное значение и рассмотреть сумм ~о например ~~, а„, в то время как вместо ( бессмысленн к=~' подставлять конкретные значения. Переменную ! можно з го менить на другую, например, ~, аы — это будет, в су о-! ности, та же самая сумма (иногда говорят, что индекс «немой» и допускает переименование). Однако если вмест ( подставить /, то произойдет коллизия переменных — сум ы ма ~' ап имеет уже совсем другой смысл (говорят, что пе с-з ременная ) «уже занята» и нельзя вместо г' подставить )).

Аналогично,,в интеграле ~ хоуйх о переменная у во всех вхождениях свободна, а переменная х связана «кванторной приставкой» йх. Переменную х мож- но заменить на переменную х — интеграл от этого не изме- нится, но отнюдь не на переменную у! !2. Уточним теперь, что именно означает ситуация, ког- да две формулы А и А' отличаются друг от друга лишь пра. вильным (т. е. без коллизий переменных) переименованием связанных переменных. В этом случае мы будем говорить, что формулы А и А' коигруэнтны, или, что формула А' яв- ляется вариантом формулы А, и писать А-А'. Рассмотрим некоторую формулу, например, 'р'х(Р(~(х) ) Л ~ хЯ(х, х) =э~ у)т(х, у) ) ~/Я(х, у). Отметим линиями связанные переменные этой формулы и кванторы, от которых происходит связывание: 1 1 1 1 Чх( (Пх)) ЛЭ.()(.,г) Эуя(х,у)) Л(г,у).

! 1 Сотрем теперь все связанные переменные, оставляя линии 1 1 1 !У(РЧ()) ~ЗЕ(, ) З)~(.»Ча(, р). 1' ) ! Полученную фигуру можно назвать скелетом исходной формулы. 64 Две формулы жонгруэнтны тогда В только тотда, когда ях скелеты совпадают. Упражнение. Укажите несколько вариантов формулы 'ух(Р(х)/~ ~ гЯ(х, х)~~уй(г, у))~/Я(х, х). Какие переименования связанных переменных ведут к коллизии? Можно дать и аккуратное математическое определение отношения А А' индукцией по логической сложности 1(А) формулы А.

А именно: А. Единственным вариантом атомарной формулы является она сама. Б. Если А имеет вид (ВАС), то всякий вариант А' формулы А имеет вид (В'АС'), где В~ В' и С С'. Если А имеет вид 1В, то всякий вариант А' формулы А имеет вид ~В', где В В'. В. Если А имеет вид ЯхВ, то всякий вариант А' формулы А имеет вид ЯуС, где у и С таковы, что для всякой новой переменной х '(т. е. не входящей ни свободно, ни связанно в формулы ЯхВ и ЯуС) имеем В, С",.

Здесь через В»» обозначен результат замещения всех свободных вхождений переменной х в В на переменную х. Аналогично понимается С«,. Предполагается еще, конечно, что все три переменные х, у, х имеют один и тот же сорт. Приведенное определение дает возможность точно доказывать различные свойства вариантов формулы А индукцией ~по логической сложности ((А) формулы А. Например; нетрудно доказать, что если Аж А', то !(А) =1(А'), Еч(А) = =Гч(А') и А н А' имеют один и тот же главный (т. е. последний в построении) логический символ. Отношение ж 'является отношением эквивалентности между формулами рассматриваемого языка„и с точки' зрения смысла формул конгруэнтные формулы можно считать «несущественно отличающимися друг от друга». Можно 'ска.

зать, что математическая логика изучает скорее не отдельные формулы, а классы конгруэнтных между собой формул. 5 2. О ПРАВИЛЬНОЙ ПОДСТАНОВКЕ,ТЕРМОВ В ФОРМУЛЫ Е Формальной подстановкой (или просто подстановкой) назовем функцию О, определенную на конечном (может быть, и пустом) множестве переменных языка (г и перерабатывающую каждую переменную х из областиопределения 0 в некоторый терм 0(х) языка, причем х и 0(х) имеют один и тот же сорт. Формальную подстановку можно изображать в виде дву мерной таблицы '('Хм Хм ..., Х») где в верхней строке указана область определения функции О: догп 0=(хь ..., х») и, кроме того, 0(х;) =(ь Здесь х; и г; имеют один и тот же) сорт. Порядок столбцов в двумерной таблице несуществен.", Таблица может.

быть и пустой, если функция О имеет пу-1 етую область определения, 2. Пусть Т вЂ” выражение языка (з (т. е. формула или, терм) и 8 — формальная подстановка ~"1 ''' ~"'). Через (ТО) мы обозначим результат одновременного замещения, всех-свободных вхождений переменных хь ..., х» в Т на тер-' мы 1ь ..., г» соответственно. Конечно, при этом некоторые х; могут и не входить свободно в Т. Тогда соответствующие 6~ никуда не подставляются и просто не играют никакой роли. Подчеркнем, что замещаются только свободные вхождения д в Т.

Вместо (ТО). будем иногда употреблять одно из следую= щих обозначений: . ТО, т Ч'"""') Т' к1 " ° к» п,....1»' Дадим теперь индуктивный рецепт для вычисления под- становки в формулу. Этот рецепт можно рассматривать и как самостоятельное индуктивное определение подстановки. Можно убедиться с помощью индукции, что оно эквивалент- но данному ранее определению. л. (ррь ..., ( ) О) =Р((,о, ..., (.8), Б. (Адв)е=(АОАВО), ( ~АО)=' 1(АО), В. (Вве) =а (в(8 — (г))). Здесь через 0 — (а) обозначен результат квыбрасывания» пе- ременной г из области определения О, т. е. 0 — (а) есть та- -кая подстановка О', что хогне'=скоте~(а) и 0'(х)=8(х) для всякой переменной хыдогп 0'.

3. Уп р а жн'е н не, Вычислите результаты подстановок: 1) (пуР(х,у, г)( " )); 2) (~УР(х, у, г) ( У )) ° 3) (~УР(х, у, г)) 4) (пг'УУР(х, У)=э(г(х))7(х г)' 5) (\ф УР (х, у) '-> Я (х)) б) (Р(х, у):э'у'У0(у)) )Р(х. У),г' 7) (~l уР (у, г)',4 и уй (х' у) ) р(х у) г' 4. Заметим теперь, что не все подстановки одинаково пригодны с точки зрения логики. Пусть, например, в некотором языке атомарная формула Р(х, у, г) выражает ~преднкат х+у=г, где переменные пробегают натуральные числа О, 1,-2, .... Формула 3 УР(х, у, г) выражает уже предикат от переменных х и г', а именно х~г, Пусть в этом же языке терм 7(х, у) задает операцию умножения натуральных чисел х у.

Теперь мы желали бы подставить )(х, у) в ~УР(х, у, г) вместо свободной переменной х с целью выразить предииат от трех переменных. х у<г. Однако ошибочно было.. бы рассмотреть с этой целью формулу Я УР (х, у, 'г) '( " ) ), т. е. формулу ((х, у)) П УР(7(х, у), у, г). Эта послсдняя формула выражает совсем,иную мысль (в частности, она зависит от двух параметров х и г, а не от трех).

Причина затруднения состоит в том, что переменная у была свободна в терме 1(х, у), а оказалась связанной в результирующей формуле. Как говорят, ~произошла коллизия переменных и ри подстановке. Правильный выход из положения состоит в том, что сна. чала следует переименовать связанную переменную у, например образовать формулу АР(х, и, г), которая выра. жает тот же предикат, а уже затем произвестл подстановку, так что в результате получим формулу ПиР(((х, у), и, г), которая,и выражает нужный предикат. 5.

Выделим теперь клясс подстановок, которые заведомо не приводят к коллизии переменных. Подстановка О называется свободной для выражения (или допустимой для выражения Т), если для всякой пере менной хыдотО любое свободное вхождение х в Т не по, падает в область действия кванторов:по переменным, сво бодно входящим в терм О(х). Упражне.нне. Выясните, какие;из подстановок п. ' свободны. Как всегда, мы укажем и индуктивное определение сво бодной подстановки: А.

Если Т вЂ” терм или атомарная формула, то всякан подстановка является допустимой для Т. Б. О свободна для (АЛВ)~=:-О свободна для А и О сво бодна для В. 0 свободна для 1А~=~О свободна для А. В. 8 свободна для ЯгВ с=~ подстановка 0 †(х) свободна' для В, и, кроме того, для всякой переменной хобот 0() ()Е»ЯхВ) терм 0(х) не содержит свободно переменной г.: б. Если для всех хыйотО выражение Т новое не содержит кваиторов по параметрам терма О(х), то О допустима для Т. Просто обстоит дело и в том случае, если для всякой переменной х~йош(О) терм О(х) является замкнутым.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее