|
Реферат: Конспект по статистике (основные понятия) (Математика)
Статистика- это планомерный и систематический учет массовых, общественных
явлений, которые осуществляются государственными статистическими органами и
дает числовое выражение в проявляющимися закономерностями.
Основные черты, предметы статистической науки.
1) Статистика – наука общества.
2) Статистика изучает количественную сторону общественных явлений в
конкретных условиях места и времени.
3) Статистика изучает массовое явление.
Метод статистики.
Под статистической методологией понимается система принципов и методов их
реализации, направленных на изучение количественных закономерностей.
Три важных состояния элемента метода статистики:
. Массовое статистическое наблюдение- т.е. сбор первичных данных об
изучаемых объектах.
. Сводка и группировка – представляет собой разделение совокупности
данных полученных на этапе наблюдения на однородные группы по
одному или нескольким признакам.
. Вычисление обобщающих статистических показателей (абсолютных,
относительных, средних, показателей вариаций, динамики, индексов)
их анализ.
Отрасли статистических наук
В составе статистики. Как единой науки выделились и получили известные
самостоятельные следующие отрасли.
1) Общая теория статистики , которая разрабатывает понятия
категорий и методов измерения количественной закономерной
общественной жизни.
2) Экономическая статистика, изучающая количественные
закономерности процессов воспроизводства на различных условиях.
3) Социальная статистика, изучающая количественную сторону развития
соц. Инфраструктуры, общества (статистика здравоохранения,
образования, культуры, судебной и др.).
4) Отраслевая статистика (статистика промышленности, агро-
промышленного комплекса, транспорта. Торговли, связи.)
Все отрасли статистики развивая и совершая свою методологию способов
развития статистической науки в целом.
Основные задачи и принципы организации государственной статистики в РФ.
Главным учетным статистическим центром является Государственный комитет РФ
по статистике (ГОСКОМСТАТ РФ).
В соответствии со статьей 71 конституции РФ он осуществляет руководство
делом учёта и статистики на всей территории страны. В соответствии с
административно- территориальным делением России образованна система
местных органов ГОС Статистики. Комитеты ( Республиканские, краевые,
областные) и управления (городские, районные).
ГОСКОМСТАТ России
. Осуществляет сбор, обработку, накопление и анализ статистической
информации. Отображающей экономическое и социальное развитие страны,
процессы становления и развития многоукладочной экономики. Ход
выполнения государственных и региональных программ развития и
эффективности производства.
. Систематически публикует обширную статистическую информацию в
специальных изданиях и сборниках, предоставляет информацию органам
власти.(президенту, правительству)
. Постоянно совершенствует методологию учета и статистики. Разрабатывает
и утверждает формы учёта и отчетности. В том числе и на отчетности всё
большего внедрения ПК.
Основными задачами статистики в условиях развития в РФ рыночных отношений
является следующее:
1) Совершение учета и отчетности и сокращения на это основе
документооборота.
2) Усиление работы по контролю за достоверностью по статистическому
информированию предоставляемой предприятиями, учреждениями и
организациями всех отраслей экономики и форм собственности.
3) Повышение своевременности поступления информации в
статистические органы.
4) Углубление аналитических функций, разрабатывание статистических
данных, формирование тематики проводимых статистических
исследований в соответствии с текущими задачами социально-
экономического развития страны.
5) Дальнейшее развитие и совершенствование статистической
методологии на основе все более широкого внедрения ПК.
Основные категории статистики
Статистический признак. Классификация.
Для изучения общей теории статистики необходимо рассмотреть
основные понятия на которых будет основываться все дальнейшее
изложение материала.
Т.к. статистика имеет дело с массовыми явлениями, то основным
понятием является статистическая совокупность.
Статистическая совокупность – это множество объектов или явлений
изучаемых статистикой, которые имеют один или несколько общих
признаков и различаются между собой по другим признакам. Так
например при определённом объеме различного товарооборота все
предприятия торговли осуществляли продажу товаров населению
рассматриваются как единая статистическая совокупность .
Отдельные объекты или явления образующие статистическую
совокупность называются единицами совокупности. Например при
проведении переписи торгового оборудования единицей наблюдения
является торговое предприятие., а единицей совокупности их
оборудование. (прилавки, холодильники и т.д.)
Явления и процессы в жизни общества изучаются статистикой по
средствам статистических показателей.
Статистический показатель – это количественная оценка свойств
изучаемого явления.
Одной из важных категорий статистической науки является понятие
признака.
Признак – это характерное свойство изучаемого явления, отличающего
его от других явлений.
В разных отраслях статистики изучаются разные признаки так например
объектом изучения является предприятие, а его признаком, вид
продукции . Или объект отдельный человек, его признаки (рост, вес и
т.д.).
Статистические признаки принято делить на две больших группы:
1) Признаки качественные
2) Признаки количественные
Качественные признаки (атрибутивные) – это признак отдельное
значение которого выражаются в виде понятий, наименований
(токарь, слесарь).
Если атрибутивные признаки принимают только одну из двух
противоположных значений, их называют Альтернативными. Например
пол (мужской, женский)
Количественный признак – это признак определяющее значение
которого имеют количественные выражения например (рост – 155
см.)
Каждый объект изучения может обладать целым рядом
статистических признаков, но от объекта к объекту одни признаки
меняются, остаются неизменными.
Меняющиеся признаки от одного объекта к другому принято называть
варьирующимися. Именно эти признаки изучаются статистикой.
Вариация- это многообразие изменения величины признака у
отдельных единиц в совокупности наблюдения (вариации з.п. 5000,
10000, 15000 тыс.)
Отдельные значения признака называют вариантами признака.
Иногда понятие статистического показателя отожествляется с
понятием признака изучаемого явления.
Розничный товарооборот в России в 1995 году составил 553,5
миллиардов рублей.
А изучаемый признак отображает лишь количественную собственность
изучаемого явления. (розничный товарооборот – это релиз товара
населению в обмен на их денежные доходы в размерах торговли.)
Статистическое наблюдение.
Виды и способы статистических наблюдений.
Статистическое наблюдение – это начальная стадия экономико-
статистических исследований.
Оно представляет собой научно-организационную работу по
собиранию массовых первичных данных о явлениях и процессах
общественной жизни, любое статистическое наблюдение
осуществляется с помощью оценки и регистра признаков единой
совокупности в соответствии с учетными документами, таким
образом полученные данные представляют собой факты которые так
или иначе характеризуют явления общественной жизни.
Формы статистических наблюдений
Различают две основные формы статистического наблюдения – это
отчетность и специальное организационное наблюдение.
Отчетность – это такая форма наблюдении при которой предприятие,
организация предоставляет в статистические и вышестоящие органы
постоянные сведения.
Статистическая отчетность чаще всего базируется на данных бух.
Учета. Все формы обязательной статистической отчетности
утверждают органы ГОССТАТИСТИКИ.
По своему содержанию формы отчетности бывают: Типовыми (общими)
и специализированными. По периоду времени за которое
предоставляется отчетность различают: текущую и годовую.
Текущая – делиться на квартальную, месячную, недельную и т.д.
При переходе к рыночной экономике из всех видов статистической
отчетности исключаю показатели отображаются только фактические
данные.
Специально-организационное наблюдение - это наблюдение которое
организуется со специальной целью на определенную дату для
получения данных, которые в силу различных причин не собир.
стат. Отчетностью, а также с целью проверки данных
статистической отчетности. (перепись населения.)
Виды статистического наблюдения
Различные по времени рег. Данных и по степени охвата ед.
совокупности.
По времени рег. Фактов. стат наблюдение может быть непрерывным,
периодическим и единовременным.
Непрерывное (текущее наблюдение) – ведется систематически т.е.
регистрирование фактов ведется по мере их совершения (учета
производства продукции, выручки магазина).
Периодическое наблюдение - повторчерез равные промежутки
времени(ежегодная перепись остатка матер. ценностей на складе на
1 января).
Единовременное наблюдение –производится по мере надобности без
соблюдения определённой периодичности. Оценка и переоценка
основных методов. По охвату ед. совокупности выделяют сплошное
и несплошное наблюдение.
Сплошным называют наблюдение при котором исследованию
подвергаются все единицы изучаемой совокупности.
(инвентаризация).
Несплошное наблюдение – называется такое наблюдение при котором
исследованию подвергаются только часть изучаемой совокупности,
отобранная опред. образом.
Реферат на тему: Конструктивная математика
Министерство образования РФ
СФ ПГУ
Дисциплина “Информатика и математика”
РЕФЕРАТ
«Конструктивная математика»
Студентка:
Группа:
Преподаватель:
Северодвинск
2003
Содержание:
I. Вступление. История конструктивной математики 3 - 4
стр.
II.Основная часть.
1. Характерные черты конструктивной математики. 4 -11
стр.
2. Конструктивная семантика как совокупность способов
понимания суждений в конструктивной математике. 11-15
стр.
3. Структура конструктивной математики.
1).Конструктивное действительное число.
15 стр.
2).Конструктивный объект.
16 -17 стр.
3).Конструктивное метрическое пространство.
17-18 стр.
III.Заключение.Роль «конструирования» в математике. 18-19
стр.
IV. Список литературы.
20 стр.
I.ВСТУПЛЕНИЕ
ИСТОРИЯ КОНСТРУКТИВНОЙ МАТЕМАТИКИ
Конструктивная математика, конструктивное направление в математике,
-математика, строящаяся в соответствии с тем или иным конструктивным
математическим мировоззрением, обыкновенно стремящимся связывать
утверждения о существовании математических объектов с возможностью их
построения и отвергающим в силу этого ряд установок традиционной теоретико
– множественной математики, приводящих к появлению чистых теорем
существования (в частности, абстракцию актуальной бесконечности и
универсальный характер исключенного третьего закона). Конструктивизм в
математике проявлялся на протяжении всей ее истории, хотя, по- видимому,
только К.Гаусс впервые отчетливо выразил принципиальное для конструктивной
математики различие становящейся (потенциальной) и актуальной
математической бесконечности и возразил против употребления последней.
Дальнейшие критические шаги в этом направлении были сделаны Л.Кронекером,
А. Пуанкаре и особенно Л Брауэром. В критике Л. Брауэра, совпавшей по
времени с кризисом оснований математики конца ХIX-начала XX в. в.,
энергично отвергалась как вера в экзистенциональный характер бесконечных
множеств, так и убеждение в допустимости неограниченной экстраполяции
классических логических принципов, в особенности закона исключенного
третьего. В качестве альтернативы теоретико- множественному подходу
Л.Брауэр, а затем и его последователи, разработали оригинальную программу
построения математики, известную ныне под названием интуиционизм.
Интуиционистскую математику Л.Брауэра можно считать первой систематической
попыткой построения математики на конструктивной основе. Параллельно
успехам интуиционистов в созданной Д.Гильбертом с целью обоснования
теоретико – множественной математики доказательств теории был четко выявлен
ряд первоначальных понятий, послуживших впоследствии отправной точкой
отличных от интуиционизма конструктивных течений. Значительная часть
соответствующих работ (при этом обнаружился достаточно широкий спектр
толкования различными исследователями терминов «конструктивный»,
«эффективный» и т. д.) опиралась на успехи, достигнутые (опять – таки под
влиянием идей Д. Гильберта) в изучении математического понятия алгоритма
.Один из наиболее последовательных и законченных подходов к построению
конструктивной математики на этой основе доставляется основанной
А.А.Марковой советской школой конструктивной математики, формирование
основных понятий которой относится к 50-м г.г. ХХ в. Сам термин
«конструктивная математика» часто употребляется в узком смысле слова для
наименования математики, строящейся советским конструктивным направлением.
II.ОСНОВНАЯ ЧАСТЬ.
1. ХАРАКТЕРНЫЕ ЧЕРТЫ КОНСТРУКТИВНОЙ МАТЕМАТИКИ.
Конструктивная математика коротко может быть охарактеризована
следующими основными чертами:
. предметом изучения являются конструктивные процессы возникающие в
результате их выполнения конструктивные объекты;
. рассмотрение конструктивных процессов и объектов производится в
рамках абстракции потенциальной осуществимости с полным исключением
идеи актуальной бесконечности;
. интуитивное понятие эффективности связывается с точным понятием
алгоритма;
. используется специальная, учитывающая специфику конструктивных
процессов и объектов конструктивная логика.
Понятия конструктивного процесса и объекта являются
первоначальными; представления о них имеют своим источником практическую
материальную деятельность человека. Примерами конструктивных процессов
могут служить сборка часов на конвейере, полная или частичная разборка их в
ремонтной мастерской, набор текстов (с корректурами ) в типографии,
формирование и расформирование железнодорожных составов и пр. Характерной
чертой конструктивных процессов является протекающее по отдельным шагам
оперирование в рамках некоторых четко указанных правил с элементарными,
заведомо отличимыми друг от друга объектами, считающимися неразложимыми в
ходе этих процессов. Возникающее в результате фигуры, составленные из
исходных элементарных объектов, и считаются конструктивными объектами.
Конструктивная математика не имеет необходимости углубляться в общее
понятие конструктивного процесса и объекта, поскольку для ее нужд
оказывается вполне достаточным один специальный вид конструктивных объектов
– слова в том или ином алфавите.
Построение слов (это понятие также представляется
первоначальным) происходит на следующей основе.
Вначале фиксируется некоторый алфавит, то есть список
неразложимых, уверенно отличимых друг от друга элементарных знаков (букв).
Каждая буква алфавита может копироваться; возникающие в результате
последовательных актов такого копирования прямолинейные цепочки знаков
считаются словами в исходном алфавите. К словам в данном алфавите удобно
отнести также и пустое слово, то есть цепочку, не содержащую ни одного
знака. Например, цепочки «аввссд» и «книга» являются словами в русском
алфавите. При обращении со словами конструктивная математика – и в этом
проявляется ее абстрактный характер – использует абстракции отождествления
и потенциальной осуществимости. Первая из них позволяет, отвлекая от
различий копий и оригинала, говорить о различных копиях данной буквы и о
ней самой, как об отдельной букве. Например, говорят, что в слово «аввссд»
три раза входит буква «в» русского алфавита, тогда как в действительности
при написании данного слова воспроизводились три различных конкретных копии
исходной буквы. Это соглашение естественным образом распространяется на
одинаковые по написанию (равные графически) слова. Например, о двух
конкретных словах: слове «книга» и слове «книга» говорят как об одном
слове. В допущении абстракции отождествления проявляется предполагаемая
конструктивной математикой первоначальная способность человека к «чтению»
слов, то есть к многократному и устойчивому опознанию знаковых цепочек как
одинаковых или различных. На это обстоятельство как минимальную предпосылку
любой научной деятельности указывал Д.Гильберт. Абстракция потенциальной
осуществимости позволяет пренебрегать в рассуждениях о написании слов
реальными ограничениями в пространстве, времени и материале. Таким образом,
о воображаемых очень длинных словах начинают рассуждать как о реально
существующих, в частности считается возможным к любому данному слову
приписать справа (или слева) любое другое слово. Отсюда вытекает и
возможность рассмотрения сколько угодно больших натуральных чисел, а также
сложения любых двух натуральных чисел, поскольку натуральными числами
можно, например, считать слова вида О, OI, OII и т.д. в алфавите OI. Вместе
с тем абстракция потенциальной осуществимости не позволяет рассматривать
как своего рода завершенные объекты «бесконечные» слова и совокупность
«всех» слов в данном алфавите (в частности, не рассматривается как
завершенный объект и натуральный ряд). Такого рода рассмотрения требуют
привлечения более сильной абстракции – абстракции актуальной бесконечности,
которая отвергается конструктивной математикой.
Принятие абстракции потенциальной осуществимости приводит к
тому, что наряду с элементарными, целиком обозримыми конструктивными
процессами (например, написанием коротких слов) рассматриваются
воображаемые, не подлежащие реальному воспроизведению конструктивные
процессы. Такие процессы задаются своими предписаниями; сами эти
предписания по существу и становятся предметом исследования. Задающее
конструктивный процесс предписание (для простоты речь идет о процессах,
оперирующих со словами) должно быть общепонятным и совершенно однозначно
определять шаг за шагом последовательное построение слов, причем шаги
должны быть элементарными, то есть не предполагать ничего, кроме умения
читать, писать (и стирать) слова. Шаги эти, таким образом, сводятся к
написанию и графическому сравнению некоторых слов, а также к замене
вхождений одних слов в другие третьими словами. Окончание процесса
определяется самим предписанием и может зависеть от результатов, полученных
на шагах, предшествующих заключительному, причем принятие решения о
заключительном характере должно носить описанный только что элементарный
характер. Возможна ситуация, когда никакой шаг не оказывается
заключительным, то есть после каждого совершенного шага данное предписание
требует совершить следующий шаг. Такому предписанию не соответствует
никакой потенциально выполнимый конструктивный процесс, однако здесь
оказывается удобной условная терминология, согласно которой соответствующее
предписание определяет неограниченно продолжаемый (потенциально
бесконечный) процесс. Для оправдания этой терминологии можно было бы также
расширить исходные представления о конструктивных процессах , рассматривая
наряду с потенциально реализуемыми процессами более абстрактные образования
– процессы, отождествляемые с их предписаниями. В связи с появлением
неограниченно продолжаемых конструктивных процессов возникает вопрос о
средствах, при помощи которых можно убедиться в обрабатываемости
задаваемого данным предписанием конструктивного процесса. Конструктивная
математика принимает здесь важный принцип, называемый принципом
конструктивного подбора и позволяющий устанавливать такие факты методом от
противного, то есть приводя к нелепости предположение о неограниченной
продолжаемости соответствующего конструктивного процесса. Примеры
предписаний: (1) написать I; (2) к произвольному слову в алфавите OI
приписать справа I; (3) п.1: написать I и перейти к п.2; п.2: стереть I (то
есть заменить эту букву пустым словом ) и перейти к п.1; (4) п.1: к
произвольному слову в алфавите OI приписать справа I и перейти к п.2; п.2:
если обрабатываемое в данный момент слово совпадает с OII, то закончить
процесс, в противном случае вернуться к п.1; (5) п.1: написать О и перейти
к п.2; п.2: к обрабатываемому в данный момент слову приписать справа I и
перейти к п.3; п.3: если получилось совершенное натуральное число, то
закончить процесс, в противном случае приписать к обрабатываемому в данный
момент слову справа I и перейти к п.2.Предписание «написать I » задает
конструктивный процесс, оканчивающийся за один шаг написанием
однобуквенного слова I. Процесс выполнения (3) неограниченно продолжаем. В
настоящее время неизвестно, заканчивается ли конструктивный процесс,
задаваемый (5) в (5) для краткости использовались теории чисел. Несколько
особый характер имеют предписания (2) и (4) : их выполнение может начаться
с любого слова в указанном алфавите, при этом конструктивный процесс,
определяемый(2), всегда заканчивается, в то время как в случае предписания
(4) он неограниченно продолжается при некоторых исходных словах.
Предписания указанных типов принято называть алгоритмами (в данном
контексте речь идет об алгоритмах, оперирующих со словами).
К необходимости рассмотрения алгоритмов приводит конструктивная
трактовка экзистенциональных утверждений. Утверждение о существовании
конструктивного объекта с данным свойством, то есть утверждение вида ( х А
(х), в соответствии с представлениями о конструктивных объектах как
результат конструктивных процессов считается в конструктивной математике
установленным в том случае, когда указан потенциально выполнимый
конструктивный объект, заканчивающийся построением искомого объекта.
Соответственно установление параметрического утверждения существования ( х
( у А (х, у) («для всякого х существует у такой, что А (х, у)» )
предполагает указание «общего» конструктивного процесса, начинающегося с
произвольного конструктивного объекта х данного исходного типа и
заканчивающегося построением искомого у. Другими словами, ( х ( у А (х, у)
выражает существование алгоритма, находящего у, исходя из х.. Из такой
трактовки существования вытекает и конструктивное понимание дизъюнкции:
суждение « А или В» считается установленным, только если предъявлен
конструктивный процесс, заканчивающийся указанием его верного члена.
Дальнейшее разъяснение смысла суждений более сложной структуры и выработки
правил обращения с ними, соответствующих исходным конструктивным
установкам, составляет задачу конструктивной семантики и конструктивной
логики. Приведенная конструктивная трактовка утверждений существования и
дизъюнкции существенно отличается от традиционной: в теоретико-
множественной математике, например, суждение ( х А (х) может быть
доказано приведением к нелепости его отрицания. Такое доказательство
обыкновенно не содержит никакого способа построения искомого
конструктивного объекта. Конструктивная математика считает, что подобное
рассуждение доказывает не ( х А (х), а его «двойное отрицание», то есть (
( ( х А (х). Последнее суждение рассматривается в конструктивной
математике как, вообще говоря, более слабое, чем ( х А (х). Таким образом,
конструктивная математика не принимает закона снятия двойного отрицания, а,
следовательно, и закона исключенного третьего (на отсутствие оснований для
принятия последнего указывает и конструктивная трактовка дизъюнкции).
Первоначальные математические структуры – натуральные, целые и
рациональные числа – непосредственно могут трактоваться как слова некоторых
простых типов в фиксированном алфавите, при этом соответствующие отношения
равенства и порядка легко сводятся к графическому совпадению и различию
слов. Введение более сложных структур – действительных чисел, функций над
ними и т. д. –осуществляется в конструктивной математике на основе понятия
алгоритма, играющего в ней примерно такую же роль, какую играет в
традиционной математике понятие функции. Считая интуитивные представления
об алгоритмах слишком расплывчатыми для таких построений, конструктивная
математика делает здесь принципиальный шаг, стандартизируя используемые
алгоритмы посредством принятия одного из современных точных определений
этого понятия вместе с соответствующей гипотезой типа Чёрча тезиса,
принципа нормализации и т.д., утверждающей совпадение оперативных
возможностей, доставляемых алгоритмами в интуитивном и точном смысле слова.
Фактически наибольшее применение в конструктивной математике получили
нормальные алгорифмы Маркова. К необходимости уточнения понятия алгоритма
приводит также и конструктивная трактовка существования. Например,
отрицание суждения ( х ( у ( (х,у) есть утверждение о невозможности
некоторого алгоритма, между тем интуитивные представления, достаточные для
опознания в качестве алгоритма того или иного конкретного предписания, в
принципе не позволяют получать сколько-нибудь нетривиальные теоремы
невозможности. На основе изложенных принципов и опираясь на современную
теорию алгоритмов, конструктивная математика строит ряд математических
дисциплин, в том числе и конструктивный математический анализ, включая сюда
элементы функционального анализа, дефференциальные уравнения, теорию
функций комплексного переменного и т.д.. Получаемые таким образом
теоретические модели, основанные на более скромной чем обычносистеме
абстракций, хотя и уступают традиционным в прозрачности и элегантности, тем
не менее, по-видимому, способны обслужить тот же круг приложений.
Имея общий критический источник с интуиционимтической математикой
Л.Брауэра и заимствовав из неё ряд конмтрукций и идей, контруктивная
математика обнаруживает определённое сходство с последней. Вместе с тем,
здесь имеются и принципиальные отличия как общефилософского, так и
конкретно математического характера. Прежде всего констуктивная математика
не разделяет интуиционизму убеждение е первоначальном характере
математической интуиции, считая, что сама эта интуиция формаируется под
влиянием практической деятельности человека. Соответственно абстрагирование
в конструктивной математике идет не от умственных построений как в
интуиционизме. А от простейших реально наблюдаемых, конструктивных
процессов. В математическом плане конструктивная математика не принимает
выходящую за рамки конструктивных процессов и объектов концепцию свободно
становящейся последовательности и основанную на ней интуиционистскую теорию
континуума как среды свободного становления. С другой стороны,
интуиционистическая математика не принимает правила конструктивного подбора
и не считает необходимым элиминировать интуитивные алгоритмы при помощи
соответственных точных определений. Следует заметить, что в последние годы
наметилась определённая тенденция к сближению конструктивного и
интуитивного подходов; в некоторых конструктивных исследованиях, в
особенности относящихся к семантике, используются индуктивные определения и
соответствующие им индуктивные доказательства, напоминающие построения Л.
Брауэра при доказательстве им так называемой бар-теоремы, занимающей одно
из центральных мест в интуиционистской математике.
2. КОНСТРУКТИВНАЯ СЕМАНИТКА КАК СОВОКУПНОСТЬ СПОСОБОВ ПОНИМАНИЯ
СУЖДЕНИЙ В КОНСТРУКТИВНОЙ МАТЕМАТИКЕ.
Небоходимость в особой семантике вызвана различием общих принципов,
лежащих в основе традиционной (классической) и конструктивной математики.
Особое внимание конструктивная семантика уделяет суждениям о конструктивных
объектах в языках первого порядка, то есть, по существу, арифметическим
суждениям. Принципиальные различия с традиционной семантикой в понимании
дизъюнкций (0((1 сформулированы Л. Брауэром. Контструктивное обоснование
таких сужднеий требует решения задачи: найти число i ( 1 такое, что верно
Ai (соответственно найти число n такое, что А(n)). Общие принципы описания
задач, соответствующих более сложным формулам юыли намечены А. Гейтингом и
А.Н.. Колмогоровым. Точная формулировка (которая стала возможна после
появления математического определения алгоритма) была дана С. Клини в виде
понятия реализации замкнутой арифметической формулы. Реализация вернорго
равенства t=r есть фиксированнная константа, например число 0, а ложное
равенство не имеет реализаций. Реализация конъюнкции А&В –это пара
(a,b),где a – реализация А, а b – реализация В. Реализация дизъюнкции
(0((1 - это пара (i,a), где i =0,1 и a - реализация суждения (1.
Реализация суждения ( х ( (х) - это пара (n,a), где n – число, a –
реализация суждения А(n). Реализация суждения ( х ( (х) - это общий метод
(, который по всякому натуральному n выдаёт реализацию ((n) суждения А(n).
Реализация суждения А ( В – это общий метод (, который по всякой
реализации а суждения А выдаёт реализацию ((а) суждения В (и может быть не
определён для аргументов а, не являющихся реализациями А). При этом общий
метод понимается как алгоритм (частично рекурсивная функция). Используя
кодирование алгоритмов числами, можно записать условие «число е есть
реализация формулы А» в виде арифметической формулы (erA), не содержащей
дизъюнкции V и содержащей существование ( только перед равенствами. Такие
формулы называются почти нормальными. Суждение ( e (erA) (читаемое «А
реализуемая») может служить конструктивным разъяснением суждения А. При
таком понимании закон исключённого третьего ( х (( (х) ( ( А (х))
опровергается, например, для A (x) = E y T (x,x,y), где T (e,x,y) означает,
что алгоритм (с кодом) е заканчивает работу над аргументом x за у шагов.
Опровергается и закон двойного отрицания ( х (( ( В (х) ( В (х)), например
для В (х)=( (х) ( ( А (х). Приведенное определение связывает
конструктивную задачу (поиск реализации) со всяким суждением A, даже если
А не содержит (, (. Предложенный Н.А. Шаниным алгоритм выявления
конструктивной задачи не меняет формул без (, ( (нормальных формул) и
эквивалентен реализуемости в формальной интуиционистической арифметике с
бескванторной индукцией. Произвольные формулы сводятся к почти нормальным,
так как основания для почти нормальных формул, содержащих ( и нетривиальное
(.
А.А. Марков определяет истинность для почти нормальных формул с помощью
выводимости по обычным правилам для рассматриваемых логических связок плюс
эффективное (-правило: если имеется общий метод, позволяющий для любого n
устанавливать выводимость А(n) из суждения К, то ( х ((х) выводимо из К..
Истинность определяется постепенно. Язык Я( , состоящий из из формул без
(,(; язык Яn+1, n ( 1, включая Яn и формулы, которые можно построить из
формул языка Яn одним применением импликации и любым числом применений А,
&. Истинность для Я1 – формул – это выводимость по обычным правилам для
&, (, (. Истинность для Я2 -формул определяется через допустимость
соответствующего правила. Например, истинность ( х R (х) ( ( y T (y)
означает наличие алгоритма ( такого, что R (n) ( T (( (n )) для любого
числа n. Для Яn+1 – формул при n>1 истинность конъюкций и ( -формул
определяется обычным образом через истинность компонента, а истинность
импликации А ( В означает выводимость В из А по некоторым правилам Sn, о
которых уже доказано, что они сохраняют истинность Яn – формул. Системы
Sn содержат (-правило, а в качестве аксиом – все истинные Яn – формулы.
Понятие выводимости в Sn вводится обобщенным индуктивным определением, а
для доказательства метатеорем применяется соответствующий принцип индукции.
Индукцией по S2 – выводу доказывается допустимость правила
( ( ( ( ( х R - А ( ( х R . Оно включается в S3 и даёт принцип
Маркова ( ( ( х R ( ( х R.. Системы Sn+3 , n ( 1, состоят из обычных
правил для рассматриваемых связок, включая (-правило. Оказывается, что
почти нормальная формула А истинна по Маркову тогда и только тогда, когда
примитивно рекурсивное дерево Tа поиска вывода формулы А без сечения (но с
(-правилом и принципом Маркова) является выводом в смысле индуктивного
определения. Это эквивалентно (в рамках классической математики)
классической истинности А.
В мажоритальной семантике Н.А. Шанина для каждой почти нормальной
формулы А определяется трансвинитная иерархия {А (} формул простой
структуры, причём А ( ( А доказуемо в подходящей формальной системе.
Формула А ( называется мажоритарной для А,и А считается истинной формулой
ранга (, если А ( верна. Точность аппроксимации растёт с ростом ( : ( < (
(( А ( ( А (). Если отвлечься от технических деталей, то формула А строится
с помощью ( - кратного вынесения кванторов, согласно эквивалентности
( ( (В(( ( ( u( vC (u, v))( ( u( v( ( (B(( ( ( u( vC(u, v) ( C(u, v)),
и сворачивания цепочек кванторов с помощью алгоритма выявления
конструктивной задачи. Это даёт доказуемую в арифметике с транксфинитной
индукцией до ( эквивалентность
А( ( u( v( ( (( ( ( w С ( ( D()
с бесквантовой формулой С (, так что
А ( = ( u( v ( w С ( (u, v, w)
оказывается мажорантой для А. Суждение оказывается с точностью до
технических деталей, эквивалентным утверждению о существовании вывода
высоты | |
