Учебников Мухачева, Бочарова+Маркина 23. 02. 03




Скачать 437.77 Kb.
НазваниеУчебников Мухачева, Бочарова+Маркина 23. 02. 03
страница1/3
Дата публикации26.08.2013
Размер437.77 Kb.
ТипУчебник
shkolnie.ru > Математика > Учебник
  1   2   3
Катречко С.Л.

Кванторные правила в логике предикатов

(+ фрагменты из учебников Мухачева, Бочарова+Маркина)

23.02.03.

Из работы А.М. Анисова «Современная логика» (стр.171): «Логика предикатов первого порядка основана на онтологии, в которой имеется два слоя объектов: объекты (индивиды — К.С.) и первопорядковые предикаты. Никаких свойств свойств, никаких предикатов от предикатов. Выдающийся математик и логик Д. Гильберт выдвинул тезис, который гласит: Нет логики, кроме логики первого порядка.» (см. о тезисе Гильберта в «Справочная книга по мат. Логике» (тт.1-4), т.1??)

Т.е. расселовская теория типов, предназначенная для устранения парадоксов, слишком «сильна» (налагает слишком много запретов), т.к. не устраняет иерархию (возникающую в рамках теоретико-множественного подхода), а лишь упорядочивает ее. Гильбертовский же подход более «слабый»: за счет более аккуратного формулировки формальной системы, можно всю многоэтажную иерархию «редуцировать» к гомогенной области предикатов первого порядка.

Из четырех правил (введения и исключения) кванторов два (см. В.А. Смирнов «Формальный вывод и логические исчисления», стр.217 — 218; В.А. Бочаров, В.И. Маркин «Основы логики». —М., Инфра-М, 2002, стр.147) из них:

-исключения xAx // At (здесь знак «//» соответствует логическому следованию)

-введения At // xAx

в классической логике воспроизводят отношение логического следования, т.е. при истинности посылок гарантируют истинность заключения.

(соответственно, в секвенциях это минус-правила (минус-кванторные правила)  и , а в аналитических таблицах T и F, т.е. правилу исключения = (соответствует) = стрелка слева (в сукцеденте секвенции), а правилу введения == стрелка справа (в антецеденте секвенции; минус-правила, т.к. эти кванторные комплексы (см. теорему Эрбрана в книге «Математическая теория лог. вывода) имеют знак минус и являются «слабыми», т.к. не вводят новых переменных)

Как пишут Бочаров — Маркин (стр.147): «В основе кванторных правил и и в лежат отношения логического следования. Для и это означает, что переход от формулы xA(x) к A(x/t) оправдан тем, что имеет место логическое следование xA(x) |= A(x/t), а для в переход от A(x/t) к xA(x) оправдан наличием логического следования A(x/t) |= xA(x)

Два других («сильных») кванторных правила:

-введения (, F) Aw // xAx

-исключения (, T ) xAx // At

не воспроизводят отношения логического следования, причем (как пишет В.А. Смирнов) ситуация такова:

-введения (Aw // xAx) в общем случае не гарантирует логического следования. Например, если для каких-то х и у справедливо х<у, то отсюда вовсе не следует утверждение о том, что любой объект (х) меньше (какого-то) у: х<у |— x(х<у). Однако (!) -введения хотя и не гарантирует логического следования, но гарантирует при общезначимости в данной области Aw, общезначимость в этой области и формулы xAx, если рассуждение в общем случае не ограничивает переменную w , т.е. в ходе рассуждения речь ведется о любой (произвольной) переменной w (w используется в интерпретации всеобщности; см. об этом ниже). Поэтому, это правило можно ввести как непрямое правило обобщения:  |— A(w) //  |— wA(w). Так, например, переход у=у |— x(x=х) вполне правомерен (см. Анисов, с.211 + это правило формулируется и при аксиоматическом задании логики предикатов (в системах гильбертовского типа): «Логика и компьютер» (№1; В.А. Смирнов)).

Правило же -исключения (xAx // At) не только не воспроизводит отношения логического следования, но и не гарантирует при универсальной общезначимости посылки универсальную общезначимость заключения (понятно, что из утверждения о (возможном!) существовании какого-то объекта x, удовлетворяющего предикату A(x) не (всегда) следует реальное существование какого-то конкретного объекта, удовлетворяющего предикату A(t): например, из утверждения о существовании некоторого числа, большего любого другого числа мы не знаем (из-за бесконечности числового ряда) конкретное значение этого числа; ср. с критикой интуиционистами теорем о чистом существовании). Например, переход (вывод) x(х<у) |— у < у не правомерен (не воспроизводит отношения логического следования), т.к. из (возможно) истинного высказывания получается заведомая ложь.

Несмотря на это, в исчислении предикатов все же принимаются эти правила, но, чтобы не допустить возможности выведения из истинных утверждений ложных заключений, необходимо каким-то образом «заблокировать» негативное влияние отсутствия логического следования. Это достигается различными способами (см. об этом ниже).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

^ ПРИМЕЧАНИЕ: О смысле кванторных правил в разных системах

1. В аксиоматических системах кванторные правила задаются (см. Войшвилло Е.К «Символическая логика», стр.57—60) с помощью следующих четырех (схем) аксиом и одного правила вывода (правила обобщения):

  1. xA(x)  A(t) — схема и

  2. A(t)  xA(x) — схема в

  3. x(B  C(x))  (B  xC(x)) — схема введения в консеквент.

  4. x(C(x)  B)  (xС(x)  B) — схема введения в антецедент.

где A(t) — результат правильной подстановки терма t вместо x в A(x); B — не содержит x свободно.
Подстановка A(x/t) правильна, если ни одна переменная из t не окажется связанной на местах подстановки, т.е. в тех местах формулы A, где терм t появился вместо переменной x.
++ Правило в (или правило обобщения): Aw // xAx (из Aw непосредственно выводимо xAx; на правило введения квантора (в) <для соблюдения корректности между понятиями формальной (синтаксической) выводимости и (семантического) следования> накладывается следующее ограничение: в может применяться к некоторой формуле Aw для обобщения лишь по таким переменным x, которые не содержатся свободно в допущениях, от которых зависит эта формула).

Вместо правил (3) и (4) могут быть взяты правила Бернайса:

3* B  C(x)) // B  xC(x) — вместо схемы введения в консеквент

или |— B  C(x)) // |— B  xC(x)

4* C(x)  B // xС(x)  B — вместо схемы введения в антецедент

или |— C(x)  B // |— xС(x)  B

=======================

2. В системах натурального вывода (см. Анисов стр.211—213) правила задаются так:

Введение квантора всеобщности (в) Исключение квантора всеобщности (и)

|— A(w) //  |— wA(w) xA(x) // A(t) (или A(x/t))
Введение квантора существования (в) Исключение квантора существования (и)

A(t) // xAx , A(w) |— B // , xAx |— B

Для правила исключения можно ввести прямое правило:

xAx // A(), где — новое квази-имя

При этом для завершенности вывода (см. понятие «завершенного вывода» ниже; Бочаров-Маркин, стр.146) в случае применения правила и вводимая им переменная — квази-имя (псевдо-имя; неопределенная дескрипция), в итоговом (завершенном!) вывода должна быть устранена путем ее замены на (нормальную) квантифицированную переменную по правилам введения кванторов в и в (т.е. в остальном использование переменных квази-имен не отличается от употребления обычных переменных!).
================================

3. Для понимания сути кванторных правил в секвенциях (в аналитических таблицах их формулировка более интуитивно прозрачна) можно предложить следующее пояснение (учитывающее семантические соображения).

Формулы, находящие слева (в антецеденте) секвенции — это посылки рассуждения, т.е. заведомо истинные формулы, а формулы, находящие в сукцеденте секвенции — то, что нужно доказать.

С учетом этого становится понятны правила для квантора . Нахождение выражение (х) в сукцеденте означает, что оно (здесь мы специально опустили предикат, т.к. «предикативное условие» не накладывает никаких ограничений на переменную х) справедливо для любой переменной универсума (т.к. изначально на х никаких ограничений не накладывается, т.е. она трактуется как произвольная — любая — переменная универсума). Поэтому для минус-кванторного правила  «снятие» происходит для любой (потенциально возможной в выводе) переменной. Нахождение выражение (х)P(x) в антецеденте означает, что невозможна ситуация когда какая-то (хотя бы одна!) переменная не удовлетворяет предикату P(x), (здесь х «зависит» от предиката (!!), в частности от других переменных предиката, что и реализуется в «сколемовских функциях») хотя какая эта переменная мы пока не знаем (см. эквивалентность (х)P(x) = хP(x)), или (что наглядно выражено в непрямом правиле введения :  |— A(w) //  |— wA(w)) для доказательства (х)P(x) достаточно доказать для P(а) для какой-либо (одной, но произвольной) переменной универсума (заметим, что правило  «сильнее» с точки зрения возможностей построения (поиска) вывода, поскольку дает возможность при построении «снимать» квантор ). Если же привлечь для объяснения (понимания) идеологию семантических (аналитических) таблиц, то смысл плюс-кванторного правила  (F) заключается в том, что для опровержения (х)P(x) достаточно найти один (фиктивный, как будет видно из дальнейшего построения) контрпример (P(а)), где а (в силу ее возможной фиктивности из-за отсутствия контрпримера) должно как-то отличаться от обычных имен (переменных), т.е. мы предполагаем, «ложность» P(а) для какой-то, ранее не рассматриваемой в выводе переменной (предполагая, что наличествующая формула (х)P(x) выполнялась (была истинной) до этого для всех «старых» (до этого рассмотренных в выводе) переменных).

Обратимся к смыслу правил для квантора . Плюс-кванторное правило  означает, что нам «дана» (в посылках) истинность xA(x), т.е. можно предположить реальное существование (выполнение) предиката A для какого-либо объекта (переменной) (a), однако «снимая» квантор мы пока не знаем, какой этот объект и не противоречит ли его наличие другим условиям (предикатам) нашего универсума (в нашем конкретном случае — строимого нами универсума вывода), все эти «условия» даны в других предикатах вывода (т.е. в «посылках» сукцедента и формулах антецедента), которые мы (в ходе построения) проверяем на совместимость). Поэтому мы сначала «вводим» его квази-объект (расширяющий наш исходный универсум), а после его проверки на совместимость (построение вывода) «превращаем» его в нормальный объект универсума. Если же в исходном предикате уже были другие переменные, то при проверке на совместимость с другими предикатами мы должны учесть «зависимость» — с помощью «сколемовских функций» — нового (квази)объекта (a) от других переменных предиката (A).

<общее замечание: «сильные» кванторные правила сначала (гипотетично) «расширяют» исходный универсум рассмотрения, который после построения вывода (т.е. успешной проверки на его легитимность) оказывается непротиворечивым, т.е. нормальным универсумом, и поэтому этот (квази)объект становится нормальным объектом универсума>.

Смысл минус-правила . Для доказательства же формулы xA(x) (что означает ее наличие (появление) в антецеденте секвенции) мы должны иметь возможность перебрать все переменные универсума для нахождения выполнимости предиката A(x), не ограничивая себя ничем (никаким условиями). Поэтому заменяем переменную данного предиката на мета-переменную, т.е. множество всех (возможных) переменных (универсума) нашего вывода.

Или другими словами. Нахождение этой формулы в антецеденте соответствует нашему (гипотетическому вначале) предположению о ее совместимости с другими формулами. Для проверки этой формулы на совместимость с другими формулами вывода (или проверки на непротиворечивость нашего универсума рассмотрения) мы должны иметь возможность отождествить объект предикативной формулы (подкванторную переменную) с любой переменной нашего вывода.

С учетом идеологии семантических таблиц, (предполагаемая) ложность xA(x) означает невозможность существование в нашем универсуме ни одного объекта, выполняющего данный предикат. Поэтому мы должны квази—отождествить переменную формулы (предиката) с любой (произвольной) переменной универсума нашего вывода (это необходимо для нахождения (возможного) контрпримера, что докажет ложность нашего предположения о ложности xA(x)).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Для решения проблемы корректности (непротиворечивости) системы <соблюдения отношения логического следования> можно выделить три подхода:

  1. Сколемовский (или сколемо-эрбрановский) подход замены «сильных» кванторов на функции (в секвенциальных исчислениях // аналитических таблицах — введение нового параметра (или новой функции от ранее встречающихся переменных — эрбрановский универсум), ранее не встречающего в выводе; ср. с третьим подходом);

  2. Подход Куайна (см. изл. у Войшвилло и Бочарова-Маркина), заключающийся в явном указании условий ограниченности переменных при применении в и и;

  3. Подход Рассела — Гильберта (изложен у Смирнова и Анисова), заключающийся в использовании —выражений (неопределенных дескрипций; или в общем случае, определенных («тот, который..») и неопределенных («некоторый…, удовлетворяющий условию…») дескрипций, которые у Гильберта фиксируются как — и — операторы), которые в завершенном выводе должны быть «удалены», т.е. заменены на нормальные (+ связанные кванторами) переменные (в частности, Д. Гильбертом доказаны следующие результаты (Смирнов, стр.223, 231): (0) Доказана (Д. Гильберт, П. Бернайс «Основания математики», т.1) элиминируемость (устранимость) —операторов, т.е. определенных дескрипций (в основном, — оператор использовался в случаях утверждения единственности объекта, т.е. !x), а Д. Гильбертом (т.2) доказаны: (1) Всякая формула, доказуемая в ИПр доказуема и ИсПр с —выражениями; (2 — NB!) Если в ИсПр с  — выражениями из выводима формула A, и ни посылки , ни заключение A не содержат —термов, то из выводима формула A и в ИсПр <т.е., хотя и не указаны способы элиминации —термов, но их использование допустимо и не выводит за рамки «законных» выводов ИсПр>)

(??: Если введение по правилу в соответствует (промежуточному) использованию определенной дескрипции (определенного артикля the), то снятие по правилу и — «введению» (использованию) неопределенной дескрипции (неопределенному артиклю a)

(++: Синтаксически использование определенных и неопределенных дескрипций как полноценных переменных была развита А. Уемовым в языке тернарного описания)

Суть всех трех подходов — учет всех и предотвращение нежелательных «зацепленностей» вводимых (или исключаемых) переменных, которые нарушают общезначимость получаемых формул (при общезначимости формул-посылок). Заметим, что в большей степени это (формулировка предыдущего предложения) характеризует смысл правила и (xAx // At), где «новая» переменная появляется и может «вступать» в нежелательные «связи» с другими переменными, а в случае с правилом в эта (нежелательная) связь неявно (случайно) уже имела место и не позволяет перейти к обобщению для любой переменной. Например, это имеет место в случае следующих «переходов»: y=y |—x(x=y) (по правилу в) или x(x |— y (по правилу и).
  1   2   3

Похожие:

Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconДля координации методической работы в лицее создана методическая...
Маркина И. В. – 7 печатных работ, Алексеев Р. А, Креховецкая Л. В. Селедцова Г. В., Кушхова С. Х. имеют по одной печатной работе....
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconМбоу «Сиверская основная общеобразовательная школа» на 2012/2013 учебный год 1 ступень
Списки учебников в соответствии с федеральным перечнем учебников, допущенных Министерством образования и науки Российской федерации...
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconПримерный список учебников, составленный в соответствии с федеральным...
Примерный список учебников, составленный в соответствии с федеральным перечнем учебников, рекомендованных к использованию в образовательном...
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconКомплект учебников
Рф от 19. 12. 2012 №1067 «Об утверждении федеральных перечней учебников, рекомендованных (допущенных) к использованию в образовательном...
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconХарактеристика бактерий семейства anaplasmataceae, циркулирующих...
Лаборатория молекулярной генетики, Уральский Государственный Университет им. А. М. Горького
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconАдрес объекта оценки: Алтайский край, г. Бийск, ул. Мухачева, д. 222/2, кв. 18
Стандарты оценки, утвержденные Постановлением Правительства РФ №519 от 06. 07. 2001 г
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconСписок статей из периодических изданий по теме «Современный урок...
Головнер, В. Н. Урок химии по теме «Пространство и время»/ В. Н. Головнер; И. В. Маркина // Практика административной работы в школе....
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconБез учебников, друзья, нам прожить никак нельзя! Театрализованное...
К заднику сцены прикреплены в увеличенном размере обложки учебников для I класса. Звучит мелодия песни «Школьные годы» (муз. Д. Кабалевского)....
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconДворец спорта, рынок "Киевский", ул. Бочарова
Головатого (от Церковной до Пересыпского моста); Николаевская дор, 283; парк Лузановский
Учебников Мухачева, Бочарова+Маркина 23. 02. 03 iconПояснительная записка к системе учебников «Школа России» (для 1-4...
Реализация идеологической основы фгос — Концепции духовно-нравственного развития и воспитания личности гражданина России в системе...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница