Правильная формула - Well-formed formula

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

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

Вступление

Ключевой использование формул в логике высказываний и логики предикатов , такие как логики первого порядка . В этих контекстах формула представляет собой строку символов φ, для которой имеет смысл спросить «истинно ли φ?» После того, как были созданы экземпляры любых свободных переменных в φ. В формальной логике доказательства могут быть представлены последовательностями формул с определенными свойствами, и окончательная формула в последовательности - это то, что доказано.

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

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

Исчисление высказываний

Формулы исчисления высказываний , также называемые формулами высказываний , представляют собой такие выражения, как . Их определение начинается с произвольным выбором множество V из пропозициональных переменных . Алфавит состоит из букв в V вместе с символами для пропозициональных связок и скобок «(» и «)», все из которых , как предполагается , чтобы не быть в V . Формулы будут определенными выражениями (то есть строками символов) над этим алфавитом. ${\ Displaystyle (А \ земля (В \ лор С))}$

Формулы индуктивно определяются следующим образом:

• Каждая пропозициональная переменная сама по себе является формулой.
• Если φ формула, то ¬φ формула.
• Если φ и ψ формулы и • любая бинарная связка, то (φ • ψ) формула. Здесь • могут быть (но не ограничиваются ими) обычные операторы ∨, ∧, → или ↔.

Это определение также может быть записано как формальная грамматика в форме Бэкуса – Наура , при условии, что набор переменных конечен:

<alpha set> ::= p | q | r | s | t | u | ... (the arbitrary finite set of propositional variables)
<form> ::= <alpha set> | ¬<form> | (<form>∧<form>) | (<form>∨<form>) | (<form>→<form>) | (<form>↔<form>)

Используя эту грамматику, последовательность символов

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

это формула, потому что она грамматически правильна. Последовательность символов

(( p → q ) → ( qq )) p ))

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

Сложные формулы могут быть трудночитаемыми из-за, например, большого количества скобок. Чтобы смягчить это последнее явление, для операторов используются правила приоритета (аналогичные стандартному математическому порядку операций ), что делает некоторые операторы более обязательными, чем другие. Например, если принять приоритет (от наиболее обязательного до наименее связующего) 1. ¬ 2. → 3. ∧ 4. ∨. Тогда формула

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

может быть сокращено как

p → q ∧ r → s ∨ ¬ q ∧ ¬ s

Однако это всего лишь соглашение, используемое для упрощения письменного представления формулы. Если бы приоритет предполагался, например, лево-правым ассоциативным, в следующем порядке: 1. ¬ 2. ∧ 3. ∨ 4. →, то та же формула выше (без скобок) была бы переписана как

( p → ( q ∧ r )) → ( s ∨ ((¬ q ) ∧ (¬ s )))

Логика предикатов

Определение формулы в логике первого порядка зависит от сигнатуры рассматриваемой теории. Эта сигнатура определяет постоянные символы, предикатные символы и функциональные символы рассматриваемой теории, а также арности функциональных и предикатных символов. ${\ displaystyle {\ mathcal {QS}}}$

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

1. Любая переменная - это термин.
2. Любой постоянный символ из подписи является термином
3. выражение формы f ( t ₁ ,…, t _n ), где f - n- мерный функциональный символ, а t ₁ ,…, t _n - члены, снова является термом.

Следующим шагом является определение атомарных формул .

1. Если t ₁ и t ₂ являются членами, то t ₁ = t ₂ является атомарной формулой
2. Если R - n -арный предикатный символ, а t ₁ ,…, t _n - термы, то R ( t ₁ ,…, t _n ) - атомарная формула

Наконец, набор формул определяется как наименьшее множество, содержащее набор элементарных формул, для которых выполняется следующее:

1. ${\ displaystyle \ neg \ phi}$ это формула, когда это формула ${\ displaystyle \ phi}$
2. ${\ Displaystyle (\ фи \ земля \ пси)}$ и являются формулами, когда и являются формулами; ${\ Displaystyle (\ фи \ лор \ пси)}$${\ displaystyle \ phi}$${\ displaystyle \ psi}$
3. ${\ Displaystyle \ существует х \, \ фи}$ - формула, когда - переменная, и - формула; ${\ displaystyle x}$${\ displaystyle \ phi}$
4. ${\ displaystyle \ forall x \, \ phi}$ - это формула, когда - переменная, и - формула (в качестве альтернативы может быть определено как сокращение для ). ${\ displaystyle x}$${\ displaystyle \ phi}$${\ displaystyle \ forall x \, \ phi}$${\ Displaystyle \ neg \ существует х \, \ neg \ phi}$

Если в формуле нет вхождений или для какой-либо переменной , она называется бескванторной . Экзистенциальная формула представляет собой формулу , начиная с последовательностью экзистенциальной квантификации с последующей формулой бескванторной. ${\ Displaystyle \ существует х}$${\ displaystyle \ forall x}$${\ displaystyle x}$

Атомарные и открытые формулы

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

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

Закрытые формулы

Замкнутая формула , также измельчает формула или фраза , формула , в которой есть нет свободных вхождения любого переменного . Если формула языка первого порядка , в которых переменные v ₁ , ..., V _п есть свободные вхождения, то предшествует v ₁ ⋯ V _п является замыкание A . ${\ displaystyle \ forall}$${\ displaystyle \ forall}$

Свойства, применимые к формулам

• Формула на языке является действительным , если оно верно для любой интерпретации в . ${\ displaystyle {\ mathcal {Q}}}$${\ displaystyle {\ mathcal {Q}}}$
• Формула на языке является выполнимым , если это верно для некоторой интерпретации в . ${\ displaystyle {\ mathcal {Q}}}$${\ displaystyle {\ mathcal {Q}}}$
• Формула от языка арифметики является разрешимым , если оно представляет собой разрешимое множество , то есть , если есть эффективный метод , который, учитывая замещение свободного переменных A , говорит , что либо полученный экземпляр A выводим или его отрицание .

Использование терминологии

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

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

Хотя выражение « хорошо сформированная формула» все еще используется, эти авторы не обязательно используют его в отличие от старого смысла формулы , который больше не используется в математической логике.

Выражение «правильно сформированные формулы» (WFF) также вошло в массовую культуру. WFF является частью эзотерического каламбура, используемого в названии академической игры " WFF 'N PROOF : The Game of Modern Logic", разработанной Лейманом Алленом, когда он учился в Йельской школе права (позже он был профессором Университета Мичиган ). Набор игр предназначен для обучения детей принципам символической логики (в польской системе обозначений ). Его название является отголоском whiffenpoof , бессмысленного слова, которое использовалось в Йельском университете для приветствия и стало популярным в The Whiffenpoof Song и Whiffenpoofs .

Смотрите также

• Основное выражение

Примечания

Рекомендации

• Аллен, Лейман Э. (1965), «К автотелическому изучению математической логики с помощью игр WFF 'N PROOF», Математическое обучение: отчет конференции, спонсируемой Комитетом по исследованию интеллектуальных процессов Совета по исследованиям в области социальных наук , Монографии Общество исследований в области развития ребенка, 30 (1): 29–41.
• Булос, Джордж ; Берджесс, Джон; Джеффри, Ричард (2002), вычислимость и логика (4-е изд.), Cambridge University Press , ISBN   978-0-521-00758-0
• Эренберг, Рэйчел (весна 2002 г.). «Он позитивно логичен» . Мичиган сегодня . Университет Мичигана. Архивировано из оригинала на 2009-02-08 . Проверено 19 августа 2007 .
• Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press , ISBN   978-0-12-238452-3
• Gamut, LTF (1990), логика, язык и значение, том 1: Введение в логику , University Of Chicago Press, ISBN   0-226-28085-3
• Ходжес, Уилфрид (2001), «Классическая логика I: логика первого порядка», в Гобле, Лу (редактор), Руководство Блэквелла по философской логике , Blackwell, ISBN   978-0-631-20692-7
• Хофштадтер, Дуглас (1980), Гедель, Эшер, Бах: вечная золотая коса , Penguin Books , ISBN   978-0-14-005579-5
• Клини, Стивен Коул (2002) [1967], Математическая логика , Нью-Йорк: Dover Publications , ISBN   978-0-486-42533-7 , MR   1950307
• Раутенберг, Вольфганг (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк : Springer Science + Business Media , DOI : 10.1007 / 978-1-4419-1221-3 , ISBN   978-1-4419-1220-6

внешняя ссылка

• Хорошо сформированная формула для логики предикатов первого порядка - включает небольшую викторину по Java .
• Хорошо сформированная формула в ProvenMath