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

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

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

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

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

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

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

Начнем с определения термов языка зг. Это определение индуктивное и содержит три пункта. Первые два пункта являются базисом индукции: в них непосредственно указа- но, какие из объектов языка следует считать термами. Тре- тий пункт представляет собой шаг индукции — он задает порождающие правила: если уже построены некоторые тер- мы, то разрещается построить из них новый терм по ука- занному правилу.

Каждый терм имеет либо вид, указанный з первых двух пунктах определения, либо получен,по по- рождающему правилу третьего пункта из термов, построен- ных на более раннем этапе. Каждому терму в силу определения будет однозначно приписан некоторый сорт языка — сорт данного герма (в ' другой терминологии — сорт значений данного терма). Итак, приведем индуктивное определение терма данного сорта языка И: 1) каждая переменная х сорта и языка й есть терм сор- та и; 2) константа с сорта и языка й есть терм сорта гц 3) если 1 — фУнкциональный символ .вила (пь ..., и» н) языка й и 1, — терм сорта пь 㻠— терм сорта пм ...„ »» — терм сорта и„, то выражение )((ь ..., 1») есть'терм сор- та и; коротко этот пункт запишем в виде правила вывода 6»,г», ...,г» 1(й, ...,ц) ' Множество всех термов сорта и языка й обозначим через.

Тш"„множество всех терман всевозможных сортов — че- рез Тт,. Таким образом, каждый терм имеет одни и только один 'из следующих двух видов. А. Константа или переменная языйа й; Б. 1(гь ..., 1»), где 1 — функциональный символ языка й и 1ь ..., г» суть термы соответствующих сортов. Например, термом некоторого языка может быть выра- жение д(й(с, х),д(х, Ь(с, у))), где у и й — двумерные функциональные символы, с — кон- станта, х и у — переменные. При этом сорта выражений должны быть надлежащим образом согласованы. Роль термов в языке состоит в том, чтобы описывать именные формы и .имена предметов.

Так, в некотором язы- ке переменные могут рассматриваться как пробегающие множество О, 1, 2,... натуральных чисел, у(х, у) описывает сумму х+у, а й(х. у) — произведение х у натуральных чи- сел. Константа с обозначает натуральное число О. Тогда вышеприведенный терм задает именную форму О х+(х+О у). Подчеркнем, однако„что сами по себе термы — суть. просто строчки символов и ничего не выражают. Чтобы уз- нать, какую именную форму задает терм, необходимо до- полнительно объяснить, что обозначают символы„встречаю- щиеся в терме, т.

е., как говорят логики, задать семантику языка, задать интерпретацию языка. Одной из наших даль- нейп»их задач и будет точное оформление этой идеи. Индуктивный характер определения множества Тша предполагает возможность использовать следующий способ рассуждения: принцип индукции по построению множества термов (языка й). А именно пусть мы желаем доказать, что некоторое свойство Х выполняется для всех термов языка й. С этой целью достаточно установить', что: 1) каждая переменная языка й обладает свойством Х, 2) каждая константа языка (г обладает свойством Х, 3) если 1,, ..., 1 суть термы, обладающие свойством Х, н 1(1ь ..., 1 ) — терм, то 1(1ь ..., 1 ) также обладает свой-.

ством Х. В таКой ситуации в силу индуктивного определения множества Тш, можно быть уверенным, что всякий терм языка () обладает свойством Х. Зтот при~нцип индукции естественно обобщает известный школьный принцип полной математической индукции. Действительно, натуральные числа можно трактовать как индуктивно порождаемые объекты: они порождаются из объекта О последовательным применением операции прибавления единицы. Поэтому если мы установим, что: 1) О обладает свойством Х, 2) если п есть натуральное число, обладающее свойством Х, то а+1 также обладает свойством Х, то можно быть уверенным, что всякое натуральное число обладает свойством Х.

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

Наше утверждение следует теперь из принципа индукции по построению термов языка. Упражнение, Индукцией по построению термов докажите, что количество запятых в терме равно т — й, где т— сумма арностей всех вхождений функциональных символов, а й —,количество вхождений функциональных символов в терм. Аналогично, индуктивный характер определения Тщ„ дает возможность задавать функции, определенные на множестве Тгп, индукцией по построению множества термов языка 11 (иногда в таких случаях говорят о возможности задавать функции рекурсией (примитивной рекурсией) по построению множества термов). А именно: 1) пусть с каждой переменной х языка 12 мы связали некоторый объект Р(х), 2) с каждой константой с языка Й мы связали некоторый объект Р(с), 3) нусть задано правило, в,соответствии с которым ес- лн термам 1ь ..., 1 уже приписаны объекты Р(1~), ..., Р(1 ), то правило позволяет отыскать объект РЩ(ь ..., 1 )) для терма 1(1ь ..., 1 ).

В такой ситуации для всякого терма 1 языка однозначно определен объект Р(1). Определим, например, функцию 1 на множестве всех термов языка»з рекурсией: 1) если х — переменная языка, то положим 1(х) =О, 2) если с — константа языка, то,положим Цс) =О, 3) если терм имеет вид ~(1ь ..., 1»), то определим, Ц)'(1ь ..., 1») ) =Ц1,) +.,+ Ц1»)+1. На последнее равенство следует смотреть ка~к на прави.ло, в силу которого мбжнр вычислить Ц1(1ь ..., 1»)), если уже известны значения 1(Я, ..., Ц1»). Указанное определение дает рецепт для вычисления 1 от любого терма. Например 1(Ду(х, у), с, г, х) ) =2. Значение Ц1) называется функциональной сложностью терма 1.

У п р а ж н е н и е. Индукцией по построению термов до- ' кажите, что для всякого терма 1 значение Ц1) равно количеству вхождений функциональных символов в терм 1. Таким образом, можно было,бы дать и не .индуктивное, явное определение функции 1. Оба определения математически эквивалентны: приняв одно из них, второе можно доказать как математическую теорему. Такая ситуация еще не раз у нас встретится. Заметим, что множество Тшл, всегда бесконечно, так как содержит переменные сорта н (даже если в языке отсутствуют функциональные символы и константы).

3. Атомарные формулы языка »1 (в другой терминологии — элементарные формулы языка ьз) определяются следующим образом.' Если Р— предикатный символ языка И вида (пь ..., н»), а 1ь ..., 1» суть термы, причем терм 1~ имеет сорт нь то выражение Р(1ь ..., 1») есть атомарная формула. В частности, если Р— пропозициональная буква (т. е. нульместная буква), то Р сама по себе является атомарной формулой. Множества всех атомарных формул языка Й обозначи м через А1 Гт,. 4. Формулы языка ь) определяются нндуктивно с помощью следующих ниже семи пунктов.

Первый пункт представ:: -. собой базис индукции, а остальные шесть цунк тов суть порождающие правила, позволяющие строить но- вые формулы из уже построенных. Прн построении формул используются новые символы, которые называются логическими символами, Они делятся на две категории — логические связки и кванторы. Мы употребляем следующие четыре логические связки: Л вЂ” конъюнкция, «и», Ч вЂ” дизъюнкция, «или», :э — импликация, «если, то», «влачет», 1 — отрицание, «не». Мы используем .два ивантора: у' — всеобщность (генерализация), «для всех», и' — существование (экзистенция), «существует». Итак, приведем индуктивное определение формулы язы- ка Й: 1) каждая атомарная формула есть формула; 2) — ', т.

е. если уже построены формулы А и В, то А,В (АЛВ) ' разрешается построить новую формулу (АЛВ); подобным образом следует трактовать и следующие три пункта: 3) — ' А,в (А)/В) 4) — ' А;В (А~В) 5) —; А )А' 6) — ', т. е. если уже построена формула А и х — про- А,х нкА извольная переменная языка ь), то разрешается построить новую формулу )/ хА; подобным образом следует трактовать и следующий пункт: 7) — ' А,х йкА Множество всех формул языка Я обозначим через Еш,.

Таким образом, каждая формула имеет один и только один иэ следующих трех видов: А. атомарная формула языка ().„ Б. (АЛВ), где А, В суть формулы языка ьг, а Ь— логическая связка, один из символов Л, ~/, ~ или А, где А формула языка (); В. ЯхА, где А — формула языка й, х — переменная языка Й и я — квантор, один из символов )/, 3.

4 за«. 478 57 Например, формулой некоторого языка может быть вы- ражение Ч З ((Ра , у))ИЭ е(», )) З у(1( ° у)). Читая логические связки и кванторы, мы можем «про- честь» ету формулу: «для всякого х существует г, такое, что если РЦ(х, у)) и существует х, для которого Я(х, г), то существует у, для которого Я(х, у)». Выражением зайка й мы назовем формулу языка й или терм языка Р. Множество всех выражений языка»« обозначим Ехр,.

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