Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В логике , квантор является оператором , который определяет , как много людей в области дискурса удовлетворяют открытую формулу . Например, универсальный квантор в формуле первого порядка выражает, что все в области удовлетворяет свойству, обозначенному . С другой стороны, квантор существования в формуле выражает, что в области есть что-то, что удовлетворяет этому свойству. Формула, в которой квантификатор имеет самый широкий охват , называется формулой количественной оценки. Количественная формула должна содержать связанную переменную и подформулу. указание свойства референта этой переменной.

Чаще всего используются кванторы и . Эти кванторы обычно определяются как двойственные, и поэтому их можно взаимоопределить с помощью отрицания . Их также можно использовать для определения более сложных квантификаторов, как в формуле, которая выражает, что ничто не имеет свойства . Другие кванторы могут быть определены только в рамках логики второго или более высокого порядка . Кванторы были обобщены, начиная с работ Мостовски и Линдстрёма .

Кванторы первого порядка аппроксимируют значения некоторых кванторов естественного языка, таких как «некоторые» и «все». Однако многие кванторы естественного языка можно анализировать только в терминах обобщенных кванторов .

Отношения к логическому соединению и дизъюнкции [ править ]

Для конечной области дискурса D = {a 1 , ... a n } универсальный квантор эквивалентен логическому соединению предложений с сингулярными терминами a i (имеющим форму Pa i для монадических предикатов ).

Квантор существования эквивалентно логической дизъюнкции высказываний , имеющих такую же структуру , как и раньше. Для бесконечных областей дискурса эквивалентности аналогичны.

Бесконечная область дискурса [ править ]

Рассмотрим следующее утверждение:

1 · 2 = 1 + 1, и 2 · 2 = 2 + 2, и 3 · 2 = 3 + 3, ... и 100 · 2 = 100 + 100, и ... и т. Д.

Это выглядит как бесконечное соединение предложений. С точки зрения формальных языков это сразу проблема, поскольку предполагается, что правила синтаксиса генерируют конечные слова.

Приведенный выше пример удачен тем, что существует процедура для генерации всех конъюнктов. Однако, если бы утверждение было сделано относительно каждого иррационального числа , не было бы возможности перечислить все конъюнкты, поскольку иррациональные числа не могут быть перечислены. Краткая, эквивалентная формулировка, позволяющая избежать этих проблем, использует универсальную количественную оценку :

Для каждого натурального числа п , п · 2 = п + п .

Аналогичный анализ применяется к дизъюнкции ,

1 равно 5 + 5, или 2 равно 5 + 5, или 3 равно 5 + 5, ... или 100 равно 5 + 5, или ... и т. Д.

который можно перефразировать, используя экзистенциальную количественную оценку :

В течение некоторого натурального числа п , п равно 5 + 5.

Алгебраические подходы к количественной оценке [ править ]

Можно разработать абстрактные алгебры , модели которых включают формальные языки с квантификацией, но прогресс был медленным [ требуется пояснение ], и интерес к такой алгебре был ограничен. На сегодняшний день разработано три подхода:

  • Алгебра отношений , изобретенная Августом Де Морганом и развитая Чарльзом Сандерсом Пирсом , Эрнстом Шредером , Альфредом Тарски и учениками Тарского. Алгебра отношений не может представлять формулу с кванторами, вложенными более чем в три раза. Удивительно, но модели алгебры отношений включают аксиоматическую теорию множеств ZFC и арифметику Пеано ;
  • Цилиндрическая алгебра , разработанная Альфредом Тарским , Леоном Хенкиным и другими;
  • Полиадическая алгебра из Халмоша .

Обозначение [ править ]

Двумя наиболее распространенными квантификаторами являются универсальный квантор и квантор существования. Традиционный символ универсального квантора - « ∀ », повернутая буква « A », что означает «для всех» или «все». Соответствующий символ для квантора существования является « ∃ », повернутая буквой « Е », что означает «существует» или «существует». [1] [2] [3]

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

Некоторые другие количественные выражения строятся следующим образом:

[4]    

для формулы P . Эти два выражения (с использованием приведенных выше определений) читаются как «существует друг Петра, который любит танцевать» и «все друзья Петра любят танцевать» соответственно. Обозначения вариантов включают для множества X и членов множества x :

                    [5]                

Все эти варианты также применимы к универсальной количественной оценке. Другие варианты универсального квантора:

    [6]     [ необходима ссылка ]

В некоторых версиях обозначений прямо упоминается диапазон количественной оценки. Всегда необходимо указывать диапазон количественной оценки; для данной математической теории это можно сделать несколькими способами:

  • Предположим фиксированную область дискурса для каждой количественной оценки, как это делается в теории множеств Цермело – Френкеля ,
  • Заранее зафиксируйте несколько областей дискурса и потребуйте, чтобы каждая переменная имела объявленный домен, который является типом этой переменной. Это аналогично ситуации в статически типизированных языках программирования , где переменные имеют объявленные типы.
  • Укажите явно диапазон количественной оценки, возможно, используя символ для набора всех объектов в этом домене (или тип объектов в этом домене).

Можно использовать любую переменную в качестве количественной переменной вместо любой другой, при определенных ограничениях, при которых захват переменной не происходит. Даже если в нотации используются типизированные переменные, можно использовать переменные этого типа.

Неформально или на естественном языке «∀ x » или «∃ x » могут появляться после или в середине P ( x ). Однако формально фраза, вводящая фиктивную переменную, помещается впереди.

Математические формулы смешивают символьные выражения для кванторов с кванторами естественного языка, такими как,

Для любого натурального числа x ...
Существует такой x , что ...
По крайней мере, для одного x ....

Ключевые слова для количественной оценки уникальности включают:

Ровно для одного натурального числа x ...
Есть один и только один x такой, что ....

Кроме того, x можно заменить местоимением . Например,

Произведение каждого натурального числа на 2 равно его сумме с самим собой.
Некоторое натуральное число является простым.

Порядок квантификаторов (вложенность) [ править ]

Порядок кванторов имеет решающее значение для смысла, что иллюстрируется двумя следующими утверждениями:

Для любого натурального числа n существует натуральное число s такое, что s = n 2 .

Это явно правда; он просто утверждает, что каждое натуральное число имеет квадрат. Смысл утверждения, в котором порядок кванторов обратный, различен:

Там существует натуральное число s такое , что для любого натурального числа п , ев = п 2 .

Это явно неверно; он утверждает, что существует единственное натуральное число s, которое является квадратом каждого натурального числа. Это связано с тем, что синтаксис указывает, что никакая переменная не может быть функцией введенных впоследствии переменных.

Менее тривиальным примером из математического анализа являются концепции равномерной и точечной непрерывности, определения которых различаются только заменой позиций двух кванторов. Функция f из R в R называется

  • Точечно непрерывный, если
  • Равномерно непрерывно, если

В первом случае конкретное значение, выбранное для δ, может быть функцией как ε, так и x , переменных, которые ему предшествуют. В последнем случае δ может быть функцией только от ε (т. Е. Его нужно выбирать независимо от x ). Например, f ( x ) = x 2 удовлетворяет поточечной, но не равномерной непрерывности. Напротив, замена двух исходных универсальных кванторов в определении точечной непрерывности не меняет смысла.

Максимальная глубина вложения кванторов в формулу называется ее « рангом квантификатора ».

Эквивалентные выражения [ править ]

Если D является областью определения x и P ( x ) является предикатом, зависящим от объектной переменной x , то универсальное предложение может быть выражено как

Это обозначение известно как ограниченная, релятивизированная или ограниченная количественная оценка . В равной степени можно написать:

Экзистенциальное предложение может быть выражено с ограниченной квантификацией как

или эквивалентно

Вместе с отрицанием для выполнения обеих задач необходим только один из универсальных или экзистенциальных кванторов:

что показывает, что для опровержения утверждения «для всех x » нужно всего лишь найти x, для которого предикат ложен. По аналогии,

Чтобы опровергнуть утверждение «существует x », нужно показать, что предикат ложен для всех x .

Диапазон количественной оценки [ править ]

Каждая количественная оценка включает одну конкретную переменную и область обсуждения или диапазон количественной оценки этой переменной. Диапазон количественной оценки определяет набор значений, которые принимает переменная. В приведенных выше примерах диапазон количественной оценки - это набор натуральных чисел. Спецификация диапазона количественной оценки позволяет нам выразить разницу между, скажем, утверждением, что предикат выполняется для некоторого натурального числа или для некоторого действительного числа . В пояснительных соглашениях часто сохраняются некоторые имена переменных, такие как « n » для натуральных чисел и « x"для действительных чисел, хотя полагаться исключительно на соглашения об именах не может работать в целом, поскольку диапазоны переменных могут изменяться в ходе математического аргумента.

Более естественный способ ограничить область дискурса использует осторожную количественную оценку . Например, осторожная количественная оценка

Для некоторого натурального числа n , n четное и n простое

средства

Для некоторого четного числа п , п является простым.

В некоторых математических теориях предполагается заранее зафиксированная единственная область дискурса. Например, в теории множеств Цермело – Френкеля переменные применяются ко всем множествам. В этом случае можно использовать ограниченные квантификаторы для имитации меньшего диапазона количественной оценки. Таким образом, в приведенном выше примере, чтобы выразить

Для любого натурального числа n , n · 2 = n + n

в теории множеств Цермело – Френкеля можно было бы написать

Для любого n , если n принадлежит N , то n · 2 = n + n ,

где N - множество всех натуральных чисел.

Формальная семантика [ править ]

Математическая семантика - это приложение математики для изучения значения выражений на формальном языке. Он состоит из трех элементов: математической спецификации класса объектов через синтаксис , математической спецификации различных семантических областей и отношения между ними, которое обычно выражается как функция от синтаксических объектов к семантическим. В этой статье рассматривается только вопрос о том, как интерпретируются элементы квантификатора. Синтаксис формулы может быть задан синтаксическим деревом. У квантификатора есть область действия , и вхождение переменной x является бесплатным, если оно не входит в область действия количественной оценки этой переменной. Таким образом, в

вхождение как x, так и y в C ( y , x ) свободно, в то время как вхождение x и y в B ( y , x ) связано (т. е. несвободно).

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

Интерпретация для первого порядка исчисления предикатов предполагает , как указана в области лиц X . Формула , свободные переменные которой х 1 , ..., х п интерпретируется как логическое значной функции F ( v 1 , ..., v п ) от п аргументов, где каждый аргумент пробегает области X . Логическое значение означает, что функция принимает одно из значений T (интерпретируется как истина) или F (интерпретируется как ложь). Интерпретация формулы

является функция G из п -1 аргументов такие , что G ( v 1 , ..., v п -1 ) = Т тогда и только тогда , когда F ( v 1 , ..., v п -1 , ш ) = Т для каждый вес в X . Если F ( v 1 , ..., v n -1 , w ) = F хотя бы для одного значения w , то G ( v1 , ..., v п -1 ) = F . Аналогично интерпретация формулы

- это функция H от n -1 аргументов такая, что H ( v 1 , ..., v n -1 ) = T тогда и только тогда, когда F ( v 1 , ..., v n -1 , w ) = T для хотя бы один w и H ( v 1 , ..., v n -1 ) = F в противном случае.

Семантика количественной оценки уникальности требует исчисления предикатов первого порядка с равенством. Это означает, что задан выделенный двузначный предикат «=»; семантика также изменяется соответствующим образом, так что «=» всегда интерпретируется как два-место равенство отношение на X . Интерпретация

то функция n -1 аргументов, которая является логической и интерпретацией

Каждый вид количественной оценки определяет соответствующий оператор замыкания в наборе формул путем добавления для каждой свободной переменной x квантификатора, связывающего x . [7] Например, экзистенциальная замыкание в открытой формуле п > 2 ∧ х п + у п = г п является замкнутой формулы ∃ пхуг ( п > 2 ∧ х п + у п = г п); последняя формула, интерпретируемая над натуральными числами, как известно, неверна в соответствии с последней теоремой Ферма . В качестве другого примера, эквациональные аксиомы, такие как x + y = y + x , обычно предназначены для обозначения их универсального замыкания , например ∀ xy ( x + y = y + x ) для выражения коммутативности .

Паукальные, множественные и другие кванторы степеней [ править ]

Ни один из ранее обсуждавшихся количественных показателей не применим к количественной оценке, такой как

Существует много целых чисел n <100, таких что n делится на 2, 3 или 5.

Один из возможных механизмов интерпретации может быть получен следующим образом: Предположим, что в дополнение к семантической области X мы дали вероятностную меру P, определенную на X, и числа отсечения 0 < ab ≤ 1. Если A - формула со свободными переменными x 1 , ..., x n , интерпретация которой является функцией F переменных v 1 , ..., v n, то интерпретация

является функцией v 1 , ..., v n -1, которая является T тогда и только тогда, когда

и F в противном случае. Точно так же интерпретация

является функцией v 1 , ..., v n -1, которая является F тогда и только тогда, когда

и T в противном случае. [ необходима цитата ]

Другие квантификаторы [ править ]

Со временем было предложено несколько других количественных показателей. В частности, квантификатор решения [8] : 28 отметил § ( знак раздела ) и прочитал «те». Например,

читается «те n из N такие, что n 2 ≤ 4 находятся в {0,1,2}». Та же самая конструкция может быть выражена в нотации создателя множеств как

В отличие от других кванторов, § дает набор, а не формулу. [9]

Некоторые другие кванторы, иногда используемые в математике, включают:

  • Таких элементов бесконечно много, что ...
  • Для всех элементов, кроме конечного числа ... (иногда выражается как « почти для всех элементов ...»).
  • Существует бесчисленное множество элементов, таких что ...
  • Для всех, кроме бесчисленного множества элементов ...
  • Для всех элементов в наборе положительной меры ...
  • Для всех элементов, кроме тех, что входят в набор с нулевой мерой ...

История [ править ]

Терминологическая логика , также называемая логикой Аристотеля, рассматривает количественную оценку в манере, которая ближе к естественному языку, а также менее подходит для формального анализа. Термин «логика» рассматривал « Все , Некоторое и Нет» в 4 веке до н.э. в отчете, также затрагивающем алетические модальности .

В 1827 году Джордж Бентам опубликовал свой « Очерк новой системы логики» с критическим анализом «Элементов логики» доктора Уэйтли , описывая принцип квантора, но эта книга не получила широкого распространения. [10]

Август де Морган (1806–1871) первым использовал термин «квантор» в современном смысле этого слова.

Уильям Гамильтон утверждал, что ввел термины «количественная оценка» и «количественная оценка», скорее всего, в своих лекциях в Эдинбурге c. 1840. Огастес Де Морган подтвердил это в 1847 году, но современное употребление началось с Де Моргана в 1862 году, когда он делал такие утверждения, как «Мы ​​должны принимать и все, и некоторые-не все в качестве количественных показателей». [11]

Готлоб Фреге в своей книге «Begriffsschrift» 1879 года первым применил квантификатор для связывания переменной, охватывающей область дискурса и появляющейся в предикатах . Он будет универсально количественно определять переменную (или отношение), записывая переменную над углублением на прямой линии, появляющейся в его схематических формулах. Фреге не разработал явных обозначений для экзистенциальной квантификации, вместо этого использовал свой эквивалент ~ ∀ x ~, или противопоставление . Трактовка Фреге квантификации оставалась практически незамеченной до « Основ математики» Бертрана Рассела 1903 года .

В работе, кульминацией которой стал Пирс (1885), Чарльз Сандерс Пирс и его ученик Оскар Ховард Митчелл независимо друг от друга изобрели универсальные и экзистенциальные кванторы, а также связанные переменные . Пирс и Митчелл написали x и Σ x, где мы теперь пишем x и ∃ x . Обозначения Пирса можно найти в трудах Эрнста Шредера , Леопольда Левенхайма , Торальфа Сколема и польских логиков до 1950-х годов. В частности, это обозначение Курт Гёделя знаковой 1930 статьи о присуждении полноты в логике первого порядкаИ 1931 документ о неполноте из арифметики Пеано .

Подход Пирса к количественной оценке также повлиял на Уильяма Эрнеста Джонсона и Джузеппе Пеано , которые изобрели еще одну нотацию, а именно ( x ) для универсальной количественной оценки x и (в 1897 году) ∃ x для экзистенциальной количественной оценки x . Следовательно, на протяжении десятилетий каноническим обозначением в философии и математической логике было ( x ) P, чтобы выразить «все индивиды в области дискурса обладают свойством P », и «(∃ x ) P », поскольку «существует по крайней мере один индивид в область дискурса, обладающая свойством P.»Пеано, который был гораздо более известен , чем Пирса, в сущности диффундируют последнего мышления во всем нотации Европе. Пеано был принят Principia Mathematica из Уайтхед и Рассел , Куайн и Алонзо церкви . В 1935 году генценовского ввел символ ∀, по аналогия с символом Пеано не стала канонической до 1960-х годов.

Примерно в 1895 году Пирс начал разрабатывать свои экзистенциальные графы , переменные которых можно рассматривать как неявно выраженные количественно. Является ли самый поверхностный экземпляр переменной четным или нечетным, определяет, является ли количественная оценка этой переменной универсальной или экзистенциальной. (Неглубокость - это противоположность глубины, которая определяется вложенностью отрицаний.) Графическая логика Пирса в последние годы привлекла некоторое внимание тех, кто исследует разнородные рассуждения и схематический вывод .

См. Также [ править ]

  • Абсолютная общность
  • Почти все
  • Квантификатор ветвления
  • Условный квантификатор
  • Подсчет количественной оценки
  • В конце концов (математика)
  • Обобщенный квантификатор - свойство более высокого порядка, используемое в качестве стандартной семантики количественных выражений существительных.
  • Квантор Линдстрема - обобщенный полиадический квантор
  • Исключение квантора
  • Кванторный сдвиг

Ссылки [ править ]

  1. ^ «Исчерпывающий список логических символов» . Математическое хранилище . 2020-04-06 . Проверено 4 сентября 2020 .
  2. ^ «Предикаты и квантификаторы» . www.csm.ornl.gov . Проверено 4 сентября 2020 .
  3. ^ «1.2 Квантификаторы» . www.whitman.edu . Проверено 4 сентября 2020 .
  4. ^ КР Кв (1990). «Логическое программирование». В Яне ван Леувене (ред.). Формальные модели и семантика . Справочник по теоретической информатике. B . Эльзевир. С. 493–574. ISBN 0-444-88074-7. Здесь: с.497
  5. ^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Чтение / МА: Аддисон-Уэсли. ISBN 0-201-02988-X. Здесь: pp344
  6. Ганс Гермес (1973). Введение в математическую логику . Hochschultext (Springer-Verlag). Лондон: Спрингер. ISBN 3540058192. ISSN  1431-4657 .Здесь: Def. II.1.5
  7. ^ в общем, для квантора Q замыкание имеет смысл только в том случае, если порядокквантификации Q не имеет значения, т.е. если Q x Q y p ( x , y ) эквивалентно Q y Q x p ( x , y ). Это выполнено для Q ∈ {∀, ∃}, ср. # Порядок квантификаторов (вложенности) выше.
  8. ^ Хенер, Эрик CR , 2004, Практическая теория программирования , 2-е издание, стр. 28 год
  9. ^ Хенер (2004) использует термин «квантор» в очень общем смысле, включая, например, суммирование .
  10. ^ Джордж Бентам, Схема новой системы логики: с критическим анализом элементов логики доктора Уэйтли (1827); Thoemmes; Факсимильное издание (1990) ISBN 1-85506-029-9 
  11. ^ Питерс, Стэнли; Вестерстол, Даг (27 апреля 2006 г.). Квантификаторы в языке и логике . Кларендон Пресс. стр. 34–. ISBN 978-0-19-929125-0.

Библиография [ править ]

  • Барвайз, Джон ; и Этчменди, Джон , 2000. Языковое доказательство и логика . CSLI (University of Chicago Press) и New York: Seven Bridges Press. Мягкое введение в логику первого порядка от двух первоклассных логиков.
  • Frege, Gottlob , 1879. Begriffsschrift . Переведено Жаном ван Хейеноортом , 1967. От Фреге до Гёделя: Справочник по математической логике, 1879-1931 гг . Издательство Гарвардского университета. Первое появление количественной оценки.
  • Гильберт, Дэвид ; и Аккерман, Вильгельм , 1950 (1928). Принципы математической логики . Челси. Перевод Grundzüge der Theoretischen Logik . Springer-Verlag. Первое издание 1928 года - это первый случай, когда количественная оценка была сознательно использована в стандартном ныне стиле, а именно в качестве связывающих переменных в некоторой фиксированной области дискурса. Это определяющий аспект логики первого порядка .
  • Пирс, CS , 1885, "Об алгебре логики: вклад в философию обозначений", Американский журнал математики , том 7, стр. 180–202. Перепечатано в Kloesel, N. et al. , Eds., 1993 . сочинения Пирса, Vol. 5 . Indiana University Press. первое появление количественного ни в чем , как и его нынешней форме.
  • Райхенбах, Ганс , 1975 (1947). Элементы символической логики , Dover Publications. Кванторы обсуждаются в главах с §18 «Связывание переменных» по §30 «Выводы из синтетических предпосылок».
  • Вестерстол, Даг, 2001, «Квантификаторы», в Гобле, Лу, изд., Блэквелл: Руководство по философской логике . Блэквелл.
  • Визе, Хайке, 2003. Числа, язык и человеческий разум . Издательство Кембриджского университета. ISBN 0-521-83182-2 . 

Внешние ссылки [ править ]

  • «Квантификатор» , Энциклопедия математики , EMS Press , 2001 [1994]
  • « » Для всех «и„существует“актуальные фразы, предложения и выражения» . Архивировано из оригинала на 1 марта 2000 года.. Из колледжа естественных наук Гавайского университета в Маноа .
  • Стэнфордская энциклопедия философии :
    • Шапиро, Стюарт (2000). «Классическая логика» (охватывает синтаксис, теорию моделей и метатеорию для логики первого порядка в стиле естественной дедукции.)
    • Вестерстол, Даг (2005). «Обобщенные кванторы»
  • Питерс, Стэнли; Вестерстол, Даг (2002). «Квантификаторы»