stringtranslate.com

Квантификатор (логический)

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

Таблица истинности для квантификаторов существования и всеобщности. [1]

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

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

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

Отношения к логической конъюнкции и дизъюнкции

Для конечной области дискурса универсально квантифицированная формула эквивалентна логической конъюнкции . Двойственно, экзистенциально квантифицированная формула эквивалентна логической дизъюнкции . Например, если — это набор двоичных цифр , формула сокращает , что равно true .

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

Рассмотрим следующее утверждение ( используя точечную запись для умножения ):

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

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

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

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

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

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

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

Для некоторого натурального числа n , n равно 5+5.

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

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

Обозначение

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

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

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

[4]    

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

    [5]     [6]                            

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

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

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

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

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

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

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

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

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

Далее, x может быть заменено местоимением . Например,

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

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

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

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

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

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

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

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

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

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

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

Эквивалентные выражения

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

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

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

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

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

что показывает, что для опровержения предложения "для всех x " нужно не более, чем найти x , для которого предикат ложен. Аналогично,

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

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

Устранение квантификатора

Устранение квантификаторов — это концепция упрощения, используемая в математической логике , теории моделей и теоретической информатике . Неформально, квантифицированное утверждение « такое, что » можно рассматривать как вопрос «Когда существует такое, что ?», а утверждение без квантификаторов можно рассматривать как ответ на этот вопрос. [9]

Один из способов классификации формул — по количеству квантификации. Формулы с меньшей глубиной чередования квантификаторов считаются более простыми, а формулы без квантификаторов — самыми простыми.

Теория обладает свойством исключения кванторов, если для каждой формулы существует другая формула без кванторов, которая эквивалентна ей ( по модулю этой теории).

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

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

Универсально квантифицированная формула над пустым диапазоном (вроде ) всегда является бессодержательно истинной . Наоборот, экзистенциально квантифицированная формула над пустым диапазоном (вроде ) всегда является ложной.

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

Для некоторого натурального числа n , n является четным и 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. Формула A , свободные переменные которой x 1 , ..., x n , интерпретируется как булевская функция F ( v 1 , ..., v n ) от n аргументов, где каждый аргумент ранжируется по области X. Булева функция означает, что функция принимает одно из значений T (интерпретируется как истина) или F (интерпретируется как ложь). Интерпретация формулы

является функцией G от n -1 аргументов, такой что G ( v 1 , ..., v n -1 ) = T тогда и только тогда, когда F ( v 1 , ..., v n -1 , w ) = T для каждого w из X . Если F ( v 1 , ..., v n -1 , w ) = F хотя бы для одного значения w , то G ( v 1 , ..., v n -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 . [10] Например, экзистенциальное замыкание открытой формулы n >2 ∧ x n + y n = z n является замкнутой формулой ∃ nxyz ( n >2 ∧ x n + y n = z n ); последняя формула, при интерпретации над положительными целыми числами, как известно, является ложной согласно Великой теореме Ферма . В качестве другого примера, аксиомы уравнений, такие как 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 тогда и только тогда, когда

и Т в противном случае.

Другие квантификаторы

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

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

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

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

История

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

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

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

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

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

В работе, которая достигла кульминации в Peirce (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. ^ Кашеф, Арман. (2023), В поисках универсальной логики: краткий обзор эволюции формальной логики, doi : 10.13140/RG.2.2.24043.82724/1
  2. ^ "Предикаты и квантификаторы". www.csm.ornl.gov . Получено 2020-09-04 .
  3. ^ "1.2 Квантификаторы". www.whitman.edu . Получено 04.09.2020 .
  4. ^ KR Apt (1990). "Логическое программирование". В Jan van Leeuwen (ред.). Formal Models and Semantics . Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 493–574. ISBN 0-444-88074-7.Здесь: стр.497
  5. ^ Швихтенберг, Хельмут; Вайнер, Стэнли С. (2009). Доказательства и вычисления. Кембридж: Издательство Кембриджского университета. doi : 10.1017/cbo9781139031905. ISBN 978-1-139-03190-5.
  6. ^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Чтение/MA: Addison-Wesley. ISBN 0-201-02988-X.Здесь: стр.344
  7. ^ Ганс Гермес (1973). Введение в математическую логику . Hochschultext (Springer-Verlag). Лондон: Springer. ISBN 3540058192. ISSN  1431-4657.Здесь: Определ. II.1.5
  8. ^ Глебский, Ю. В.; Коган, Д. И.; Лиогонький, М. И.; Таланов, ВА (1972). «Объем и степень реализуемости формул в ограниченном исчислении предикатов». Кибернетика . 5 (2): 142–154. doi :10.1007/bf01071084. ISSN  0011-4235. S2CID  121409759.
  9. ^ Браун 2002.
  10. ^ в общем случае для квантификатора Q замыкание имеет смысл только в том случае, если порядок квантификации Q не имеет значения, т. е. если Q x Q y p ( x , y ) эквивалентно Q y Q x p ( x , y ). Это выполняется для Q ∈ {∀,∃}, см. #Порядок квантификаторов (вложенность) выше.
  11. ^ Хенер, Эрик CR , 2004, Практическая теория программирования, 2-е издание, стр. 28
  12. ^ Хенер (2004) использует термин «квантор» в очень общем смысле, включая также, например, суммирование .
  13. ^ Джордж Бентам, Очерк новой системы логики: с критическим рассмотрением «Элементов логики» доктора Уотли (1827); Томмес; Факсимильное издание (1990) ISBN 1-85506-029-9 
  14. ^ Питерс, Стэнли; Вестерстол, Даг (2006-04-27). Квантификаторы в языке и логике. Clarendon Press. стр. 34–. ISBN 978-0-19-929125-0.

Библиография

Внешние ссылки