В математической логике , пропозициональной логике и логике предикатов правильно сформированная формула , сокращенно WFF или wff , часто просто формула , представляет собой конечную последовательность символов из заданного алфавита , которая является частью формального языка . [1]
Аббревиатура wff произносится как «вуф» или иногда «вифф», «вефф» или «уифф». [12]
Формальный язык можно определить с помощью набора формул в языке. Формула — это синтаксический объект, которому можно придать семантическое значение посредством интерпретации . Два основных применения формул — в пропозициональной логике и логике предикатов.
Формулы используются в основном в пропозициональной логике и логике предикатов, например, в логике первого порядка . В этих контекстах формула — это строка символов φ, для которой имеет смысл спросить «истинно ли φ?», как только будут инстанциированы все свободные переменные в φ. В формальной логике доказательства могут быть представлены последовательностями формул с определенными свойствами, а последняя формула в последовательности — это то, что доказывается.
Хотя термин «формула» может использоваться для письменных знаков (например, на листе бумаги или доске), точнее его понимать как последовательность символов, которые выражаются, причем знаки являются условным экземпляром формулы. Это различие между неопределенным понятием «свойства» и индуктивно определенным понятием правильно сформированной формулы имеет корни в статье Вейля 1910 года «Uber die Definitionen der mathematischen Grundbegriffe». [13] Таким образом, одна и та же формула может быть записана более одного раза, и формула в принципе может быть настолько длинной, что ее вообще невозможно записать в пределах физической вселенной.
Формулы сами по себе являются синтаксическими объектами. Им придаются значения посредством интерпретаций. Например, в пропозициональной формуле каждая пропозициональная переменная может интерпретироваться как конкретное предложение, так что общая формула выражает связь между этими предложениями. Однако формула не обязательно должна интерпретироваться, чтобы рассматриваться исключительно как формула.
Формулы исчисления высказываний , также называемые пропозициональными формулами , [14] являются выражениями, такими как . Их определение начинается с произвольного выбора множества V пропозициональных переменных . Алфавит состоит из букв в V вместе с символами для пропозициональных связок и скобок "(" и ")", все из которых, как предполагается, отсутствуют в V . Формулы будут определенными выражениями (то есть строками символов) над этим алфавитом.
Формулы индуктивно определяются следующим образом:
Это определение можно также записать в виде формальной грамматики в форме Бэкуса–Наура , при условии, что набор переменных конечен:
< альфа-множество > ::= p | q | r | s | t | u | ... (произвольное конечное множество пропозициональных переменных) < форма > ::= < альфа-множество > | ¬ < форма > | ( < форма > ∧ < форма > ) | ( < форма > ∨ < форма > ) | ( < форма > → < форма > ) | ( < форма > ↔ < форма > )
Используя эту грамматику, последовательность символов
является формулой, потому что она грамматически правильна. Последовательность символов
не является формулой, поскольку не соответствует грамматике.
Сложная формула может быть трудной для чтения, например, из-за обилия скобок. Чтобы облегчить это последнее явление, правила приоритета (сродни стандартному математическому порядку операций ) предполагаются среди операторов, делая некоторые операторы более обязательными, чем другие. Например, предполагая приоритет (от наиболее обязательных к наименее обязательным) 1. ¬ 2. → 3. ∧ 4. ∨. Тогда формула
может быть сокращено как
Однако это всего лишь соглашение, используемое для упрощения письменного представления формулы. Если бы приоритет предполагался, например, как лево-право ассоциативный, в следующем порядке: 1. ¬ 2. ∧ 3. ∨ 4. →, то та же самая формула выше (без скобок) была бы переписана как
Определение формулы в логике первого порядка относительно сигнатуры рассматриваемой теории. Эта сигнатура определяет константные символы, предикатные символы и функциональные символы рассматриваемой теории, а также арности функциональных и предикатных символов.
Определение формулы состоит из нескольких частей. Во-первых, набор терминов определяется рекурсивно. Термины, неформально, являются выражениями, которые представляют объекты из области дискурса .
Следующим шагом является определение атомных формул .
Наконец, набор формул определяется как наименьший набор, содержащий набор атомарных формул, такой, что выполняется следующее:
Если формула не содержит вхождений или для любой переменной , то она называетсябез квантификаторов . Экзистенциальная формула — это формула, начинающаяся с последовательности экзистенциальных квантификаций, за которой следует бескванторная формула.
Атомарной формулой называется формула, не содержащая логических связок и квантификаторов , или, что эквивалентно, формула, не имеющая строгих подформул. Точная форма атомарных формул зависит от рассматриваемой формальной системы; для пропозициональной логики , например, атомарные формулы являются пропозициональными переменными . Для предикатной логики атомы являются предикатными символами вместе со своими аргументами, причем каждый аргумент является термином .
Согласно некоторой терминологии, открытая формула образуется путем объединения атомарных формул с использованием только логических связок, за исключением квантификаторов. [15] Это не следует путать с формулой, которая не является закрытой.
Замкнутая формула , также основная формула или предложение , это формула , в которой нет свободных вхождений какой-либо переменной . Если A является формулой языка первого порядка , в которой переменные v 1 , …, v n имеют свободные вхождения, то A , которому предшествует ∀ v 1 ⋯ ∀ v n , является универсальным замыканием A .
В более ранних работах по математической логике (например, Чёрча [16] ) формулы относились к любым цепочкам символов, и среди этих цепочек правильно сформированными формулами были те цепочки, которые следовали правилам формирования (правильных) формул.
Некоторые авторы просто говорят «формула». [17] [18] [19] [20] Современные способы использования (особенно в контексте компьютерной науки с математическим программным обеспечением, таким как программы проверки моделей , автоматизированные программы доказательства теорем , интерактивные программы доказательства теорем ) имеют тенденцию сохранять понятие формулы только в алгебраическом смысле и оставлять вопрос о корректности , т. е. о конкретном строковом представлении формул (использование того или иного символа для связок и квантификаторов, использование того или иного соглашения о скобках , использование польской или инфиксной записи и т. д.) как простую проблему обозначений.
Выражение «хорошо сформированные формулы» (WFF) также проникло в массовую культуру. WFF является частью эзотерического каламбура, использованного в названии академической игры « WFF 'N PROOF : The Game of Modern Logic» Леймана Аллена [21], разработанной во время его учебы в Йельской школе права (позже он был профессором Мичиганского университета ). Набор игр предназначен для обучения детей принципам символической логики (в польской нотации ). [22] Его название является отголоском whiffenpoof , бессмысленного слова, используемого в качестве подбадривания в Йельском университете и ставшего популярным в песнях «Песня о Whiffenpoof» и «Семейка Whiffenpoofs» . [23]