Правильно составленная формула

В математической логике , высказываний и логике предикатов , правильно построенная формула сокращенно WFF или wff , часто просто формула , представляет собой конечную последовательность символов логике из данного алфавита , являющуюся частью формального языка . ^[1]

Аббревиатура wff произносится как «гав», ^[2]^[3]^[4]^[5] или иногда ^[6] "вифф", ^[7]^[8]^[9], "вэфф", ^[10]^[11] или «дух». ^[12]

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

Введение

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

Хотя термин «формула» может использоваться для письменных знаков (например, на листе бумаги или классной доске), более точно он понимается как последовательность выражаемых символов, при этом отметки являются лексемным экземпляром формулы. Это различие между расплывчатым понятием «свойство» и индуктивно определенным понятием правильно построенной формулы уходит корнями в статью Вейля 1910 года «Uber die Definitionen der mathematischen Grundbegriffe». ^[13] Таким образом, одна и та же формула может быть записана более одного раза, и в принципе формула может быть настолько длинной, что ее вообще нельзя будет записать в физической вселенной.

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

Пропозициональное исчисление

Формулы исчисления высказываний , называемые также формулами высказываний , ^[14] представляют собой такие выражения, как $(A\land (B\lor C))$ . Их определение начинается с произвольного выбора множества V пропозициональных переменных . Алфавит состоит из букв V, а также символов пропозициональных связок и круглых скобок «(» и «)», которые, как предполагается, не входят в V . Формулы будут представлять собой определенные выражения (то есть строки символов) над этим алфавитом.

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

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

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

<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>)

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

((( п → q ) ∧ ( р → s )) ∨ (¬ q ∧ ¬ s ))

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

(( п → q )→( qq )) п ))

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

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

((( п → q ) ∧ ( р → s )) ∨ (¬ q ∧ ¬ s ))

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

п → q ∧ r → s ∨ ¬ q ∧ ¬ s

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

( п → ( q ∧ р )) → ( s ∨ (¬ q ∧ ¬ s ))

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

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

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

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

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

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

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

$\neg \phi$ это формула, когда $\phi$ это формула
$(\phi \land \psi )$ и $(\phi \lor \psi )$ являются формулами, когда $\phi$ и $\psi$ являются формулами;
$\exists x\,\phi$ это формула, когда $x$ является переменной и $\phi$ это формула;
$\forall x\,\phi$ это формула, когда $x$ является переменной и $\phi$ представляет собой формулу (альтернативно, $\forall x\,\phi$ можно определить как сокращение от $\neg \exists x\,\neg \phi$ ).

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

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

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

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

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

, Замкнутая формула также основная формула или предложение , — это формула, в которой нет свободных вхождений какой-либо переменной . Если A — формула языка первого порядка, в которой переменные $v 1, \dots, v n$ имеют свободное вхождение, то A , перед которым стоит $\forall v 1 \dots \forall v n,$ универсальным замыканием A является .

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

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

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

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

Некоторые авторы просто говорят «формула». ^[17]^[18]^[19]^[20] Современные обычаи (особенно в контексте информатики с математическим программным обеспечением, таким как средства проверки моделей , автоматизированные средства доказательства теорем , интерактивные средства доказательства теорем ) имеют тенденцию сохранять понятие формулы только как алгебраическое понятие и оставлять вопрос о правильности формулировки , т.е. конкретное строковое представление формул (с использованием того или иного символа для связок и кванторов, с использованием того или иного соглашения о заключении скобок , с использованием польской или инфиксной записи и т. д.) как просто проблема нотации.

Выражение «правильно сформированные формулы» (WFF) также проникло в массовую культуру. WFF — это часть эзотерического каламбура, используемого в названии академической игры « WFF 'N PROOF : The Game of Modern Logic», автором которой является Лэйман Аллен. ^[21] разработал, когда он учился на юридической школе Йельского университета (позже он был профессором Мичиганского университета ). Комплекс игр предназначен для обучения детей основам символической логики (в польских обозначениях ). ^[22] Его название является отголоском слова «wiffenpoof» , бессмысленного слова, используемого в качестве приветствия в Йельском университете и ставшего популярным в песнях «Whiffenpoof Song» и «The Whiffenpoofs» . ^[23]

См. также

Примечания

^ Формулы являются стандартной темой вводной логики и рассматриваются во всех вводных учебниках, включая Enderton (2001), Gamut (1990) и Kleene (1967).
^ Генслер, Гарри (11 сентября 2002 г.). Введение в логику . Рутледж. п. 35. ISBN 978-1-134-58880-0 .
^ Холл, Корделия; О'Доннелл, Джон (17 апреля 2013 г.). Дискретная математика с помощью компьютера . Springer Science & Business Media. п. 44. ИСБН 978-1-4471-3657-6 .
^ Аглер, Дэвид В. (2013). Символическая логика: синтаксис, семантика и доказательство . Роуман и Литтлфилд. п. 41. ИСБН 978-1-4422-1742-3 .
^ Симпсон, РЛ (17 марта 2008 г.). Основы символической логики - третье издание . Бродвью Пресс. п. 14. ISBN 978-1-77048-495-5 .
^ Все источники поддерживают «гав». Источники, цитируемые для «wiff», «weff» и «wiff», представили это произношение как альтернативу «гав». Источник Генслера приводит слова «дерево» и «вуфер» в качестве примеров того, как произносить гласную в слове «гав».
^ Ладерут, Карл (24 октября 2022 г.). Карманный справочник по формальной логике . Бродвью Пресс. п. 59. ИСБН 978-1-77048-868-7 .
^ Маурер, Стивен Б.; Ралстон, Энтони (21 января 2005 г.). Дискретная алгоритмическая математика, третье издание . ЦРК Пресс. п. 625. ИСБН 978-1-56881-166-6 .
^ Мартин, Роберт М. (6 мая 2002 г.). Словарь философа — третье издание . Бродвью Пресс. п. 323. ИСБН 978-1-77048-215-9 .
^ Дэйт, Кристофер (14 октября 2008 г.). Словарь реляционных баз данных, расширенное издание . Апресс. п. 211. ИСБН 978-1-4302-1042-9 .
^ Дата, CJ (21 декабря 2015 г.). Новый словарь реляционных баз данных: термины, концепции и примеры . «О'Рейли Медиа, Инк.». п. 241. ИСБН 978-1-4919-5171-2 .
^ Симпсон, Р.Л. (10 декабря 1998 г.). Основы символической логики . Бродвью Пресс. п. 12. ISBN 978-1-55111-250-3 .
^ У. Дин, С. Уолш, Предыстория подсистем арифметики второго порядка (2016), стр.6
^ Логика первого порядка и автоматическое доказательство теорем, Мелвин Фиттинг, Springer, 1996 [1]
^ Справочник по истории логики (Том 5, Логика от Рассела до Черча), логика Тарского Кейта Симмонса, Д. Габбея и Дж. Вудса Eds, стр. 568 [2] .
^ Алонзо Чёрч, [1996] (1944), Введение в математическую логику, стр. 49
^ Гильберт, Дэвид ; Акерманн, Вильгельм (1950) [1937], Принципы математической логики, Нью-Йорк: Челси.
^ Ходжес, Уилфрид (1997), Более короткая теория модели, Cambridge University Press, ISBN 978-0-521-58713-6
^ Барвайз, Джон , изд. (1982), Справочник по математической логике, Исследования по логике и основам математики, Амстердам: Северная Голландия, ISBN 978-0-444-86388-1
^ Кори, Рене; Ласкар, Дэниел (2000), Математическая логика: курс с упражнениями, Oxford University Press, ISBN 978-0-19-850048-3
^ Эренбург 2002
^ Более технически, пропозициональная логика с использованием исчисления в стиле Fitch .
^ Аллен (1965) признает каламбур.

Ссылки

Аллен, Лэйман Э. (1965), «К автотелическому обучению математической логики с помощью игр WFF 'N PROOF», Математическое обучение: отчет конференции, спонсируемой комитетом по исследованию интеллектуальных процессов Совета социальных наук , монографии Общество исследований развития детей, 30 (1): 29–41.
Булос, Джордж ; Берджесс, Джон; Джеффри, Ричард (2002), Вычислимость и логика (4-е изд.), Cambridge University Press , ISBN 978-0-521-00758-0
Эренберг, Рэйчел (весна 2002 г.). «Он положительно логичен» . Мичиган сегодня . Мичиганский университет. Архивировано из оригинала 8 февраля 2009 г. Проверено 19 августа 2007 г.
Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press , ISBN 978-0-12-238452-3
Гамут, LTF (1990), Логика, язык и значение, Том 1: Введение в логику , University of Chicago Press, ISBN 0-226-28085-3
Ходжес, Уилфрид (2001), «Классическая логика I: логика первого порядка», в Гобл, Лу (редактор), «Руководство Блэквелла по философской логике» , Блэквелл, 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 , МР 1950307
Раутенберг, Вольфганг (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк: Springer Science+Business Media , doi : 10.1007/978-1-4419-1221-3 , ISBN 978-1-4419-1220-6

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

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

[1] Формулы являются стандартной темой вводной логики и рассматриваются во всех вводных учебниках, включая Enderton (2001), Gamut (1990) и Kleene (1967).

[2] Генслер, Гарри (11 сентября 2002 г.). Введение в логику . Рутледж. п. 35. ISBN 978-1-134-58880-0 .

[3] Холл, Корделия; О'Доннелл, Джон (17 апреля 2013 г.). Дискретная математика с помощью компьютера . Springer Science & Business Media. п. 44. ИСБН 978-1-4471-3657-6 .

[4] Аглер, Дэвид В. (2013). Символическая логика: синтаксис, семантика и доказательство . Роуман и Литтлфилд. п. 41. ИСБН 978-1-4422-1742-3 .

[5] Симпсон, РЛ (17 марта 2008 г.). Основы символической логики - третье издание . Бродвью Пресс. п. 14. ISBN 978-1-77048-495-5 .

[6] Все источники поддерживают «гав». Источники, цитируемые для «wiff», «weff» и «wiff», представили это произношение как альтернативу «гав». Источник Генслера приводит слова «дерево» и «вуфер» в качестве примеров того, как произносить гласную в слове «гав».

[7] Ладерут, Карл (24 октября 2022 г.). Карманный справочник по формальной логике . Бродвью Пресс. п. 59. ИСБН 978-1-77048-868-7 .

[8] Маурер, Стивен Б.; Ралстон, Энтони (21 января 2005 г.). Дискретная алгоритмическая математика, третье издание . ЦРК Пресс. п. 625. ИСБН 978-1-56881-166-6 .

[9] Мартин, Роберт М. (6 мая 2002 г.). Словарь философа — третье издание . Бродвью Пресс. п. 323. ИСБН 978-1-77048-215-9 .

[10] Дэйт, Кристофер (14 октября 2008 г.). Словарь реляционных баз данных, расширенное издание . Апресс. п. 211. ИСБН 978-1-4302-1042-9 .

[11] Дата, CJ (21 декабря 2015 г.). Новый словарь реляционных баз данных: термины, концепции и примеры . «О'Рейли Медиа, Инк.». п. 241. ИСБН 978-1-4919-5171-2 .

[12] Симпсон, Р.Л. (10 декабря 1998 г.). Основы символической логики . Бродвью Пресс. п. 12. ISBN 978-1-55111-250-3 .

[13] У. Дин, С. Уолш, Предыстория подсистем арифметики второго порядка (2016), стр.6

[14] Логика первого порядка и автоматическое доказательство теорем, Мелвин Фиттинг, Springer, 1996 [1]

[15] Справочник по истории логики (Том 5, Логика от Рассела до Черча), логика Тарского Кейта Симмонса, Д. Габбея и Дж. Вудса Eds, стр. 568 [2] .

[16] Алонзо Чёрч, [1996] (1944), Введение в математическую логику, стр. 49

[17] Гильберт, Дэвид ; Акерманн, Вильгельм (1950) [1937], Принципы математической логики, Нью-Йорк: Челси.

[18] Ходжес, Уилфрид (1997), Более короткая теория модели, Cambridge University Press, ISBN 978-0-521-58713-6

[19] Барвайз, Джон , изд. (1982), Справочник по математической логике, Исследования по логике и основам математики, Амстердам: Северная Голландия, ISBN 978-0-444-86388-1

[20] Кори, Рене; Ласкар, Дэниел (2000), Математическая логика: курс с упражнениями, Oxford University Press, ISBN 978-0-19-850048-3

[21] Эренбург 2002

[22] Более технически, пропозициональная логика с использованием исчисления в стиле Fitch .

[23] Аллен (1965) признает каламбур.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]