Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 17
Текст из файла (страница 17)
Здесь также вместо 6 (x, y) по традициипишут x 6 y.Аксиомы порядка (рефлексивность, антисимметричность, транзитивность) могут быть записаны формулами этой сигнатуры. Например, требование антисимметричности записывается так:∀x ∀y(((x 6 y) ∧ (y 6 x)) → (x = y)).Иногда в сигнатуру теории упорядоченных множеств вместо символа 6 включают символ <; большой разницы тут нет.39. Как записать с помощью формулы свойство линейной упорядоченности? свойство не иметь наибольшего элемента? свойство плотности(отсутствия соседних элементов)? свойство фундированности (отсутствиябесконечных убывающих последовательностей — или, что эквивалентно,наличия минимального элемента в любом подмножестве)? свойство полной упорядоченности? (Указание: не для всех перечисленных свойств этовозможно.)Сигнатуру теории групп можно выбирать по-разному.
Можносчитать, что (помимо равенства) она имеет двуместный функциональный символ × (который по традиции записывают между множителями), константу (нульместный функциональный символ) 1 и76Языки первого порядка[гл. 3]одноместный функциональный символ inv(x) для обращения.
Тогдааксиомы теории групп записываются с использованием лишь кванторов всеобщности:∀x ∀y ∀z(((x × y) × z) = (x × (y × z))),∀x (((x × 1) = x) ∧ ((1 × x) = x)),∀x (((x × inv(x)) = 1) ∧ ((inv(x) × x) = 1)).Если не включать операцию обращения в сигнатуру, придётсяиспользовать квантор существования и переписать последнюю аксиому так:∀x ∃y (((x × y) = 1) ∧ ((y × x) = 1)).40. Как записать аксиомы теории групп, если в сигнатуре нет константы 1? (Указание: аксиома о существовании обратного станет частьюаксиомы о существовании единицы.)41. Как записать в виде формулы требование коммутативности группы? утверждение о том, что любой элемент (кроме единицы) имеет порядок 11? конечность группы? (Указание: не всё из перечисленного можнозаписать, хотя пока у нас нет средств это установить.)Сигнатура теории множеств содержит два двуместных предикатных символа: для принадлежности и для равенства.
Аксиомы теориимножеств можно записывать в виде формул этой сигнатуры. Чащевсего рассматривают вариант аксиоматической теории множеств, называемый теорией Цермело – Френкеля и обозначаемый ZF. Приведём для примера одну из аксиом теории ZF, называемую аксиомойобъёмности, или экстенсиональности:∀x ∀y ((∀z ((z ∈ x) → (z ∈ y)) ∧ ∀z ((z ∈ y) → (z ∈ x))) → (x = y)).42. Сформулировать словесно эту аксиому.43. Записать в виде формулы аксиому регулярности, или фундирования, которая говорит, что у всякого множества есть минимальный (сточки зрения отношения ∈) элемент, то есть элемент, не пересекающийсяс самим множеством.44. Какова естественная сигнатура для теории полей? Можно ли записать в виде формулы этой сигнатуры утверждение о том, что поле имеетхарактеристику 2? конечную характеристику? алгебраически замкнуто?3.2.
Определение истинностиИз приведённых выше примеров, вероятно, понятен смысл формулы, то есть ясно, в каких интерпретациях данной сигнатуры и[п. 2]Определение истинности77для каких элементов формула истинна. Тем не менее для любителейстрогости мы приведём формальное определение истинности. (Егодетали понадобятся, когда мы будем проверять истинность выводимых формул, см. раздел 4.3.)Прежде всего, определим формально понятие параметра формулы (переменной, от значения которой может зависеть истинностьформулы). Согласно этому определению формула ∀x ∃y A(x, y) неимеет параметров, а формулы ∃y A(x, y) и (A(x) ∧ ∀x B(x, x)) имеютединственный параметр x. Вот как выглядит это определение:• Параметрами терма являются все входящие в него индивидныепеременные.• Параметрами атомарной формулы являются параметры всехвходящих в неё термов.• Параметры формулы ¬ϕ те же, что у формулы ϕ.• Параметрами формул (ϕ ∧ ψ), (ϕ ∨ ψ) и (ϕ → ψ) являются всепараметры формулы ϕ, а также все параметры формулы ψ.• Параметрами формул ∀ξ ϕ и ∃ξ ϕ являются все параметры формулы ϕ, кроме переменной ξ.Параметры иногда называют свободными переменными формулы.
Заметим, что формула может иметь одновременно параметр x ииспользовать (в другом месте) квантор ∀x. Как говорят в этом случае, одна и та же переменная имеет свободные и связанные вхождения. Свободное вхождение переменной — это такое вхождение, которое не входит в область действия одноимённого квантора. Еслиаккуратно определить эту область действия, несложно проверить,что параметры формулы — это как раз переменные, имеющие свободные вхождения.Теперь мы хотим определить понятие формулы, истинной в данной интерпретации при данных значениях параметров. Техническипроще считать, что всем индивидным переменным приписаны какие-то значения, а потом доказать, что переменные, не являющиесяпараметрами, не влияют на истинность формулы.Итак, пусть фиксирована сигнатура и некоторая интерпретацияэтой сигнатуры.
Оценкой назовём отображение, которое ставит в соответствие каждой индивидной переменной некоторый элемент множества, являющегося носителем интерпретации. Этот элемент будемназывать значением переменной при данной оценке.78Языки первого порядка[гл. 3]Определим индуктивно значение терма t при данной оценке π,которое мы будем обозначать [t](π).• Для переменных оно уже определено.• Если t является константой (нульместным функциональнымсимволом), то [t](π) не зависит от π и равно значению этойконстанты при данной интерпретации (напомним, в интерпретации с каждой константой сопоставляется некоторый элементносителя).• Если t имеет вид f (t1 , .
. . , tm ), где f — функциональный символвалентности m, а t1 , . . . , tm — термы, то [t](π) определяется как[f ]([t1 ](π), . . . , [tm ](π)), где [f ] есть функция, соответствующаясимволу f в нашей интерпретации, а [ti ](π) есть значение термаti при оценке π.Теперь можно определить значение формулы ϕ при данной оценке π в данной интерпретации, которое обозначается [ϕ](π) и можетбыть равно И или Л; в первом случае формула называется истинной, во втором — ложной.
Это определение также индуктивно:• Значение атомарной формулы A(t1 , . . . , tm ) определяется как[A]([t1 ](π), . . . , [tm ](π)), где [A] — предикат, соответствующийпредикатному символу A в рассматриваемой интерпретации.Если формула представляет собой нульместный предикатныйсимвол, то её значение не зависит от оценки и есть значениеэтого символа.• [¬ϕ](π) определяется как ¬[ϕ(π)], где ¬ понимается как операция в B. Другими словами, формула ¬ϕ истинна при оценке πтогда и только тогда, когда формула ϕ ложна при этой оценке.• [ϕ ∧ ψ](π) определяется как [ϕ](π) ∧ [ψ](π), где ∧ в правой части понимается как операция в B.
(Другими словами, формула(ϕ ∧ ψ) истинна при оценке π тогда и только тогда, когда обеформулы ϕ и ψ истинны при этой оценке.) Аналогичным образом [ϕ ∨ ψ](π) определяется как [ϕ](π) ∨ [ψ](π), а [ϕ → ψ](π) —как [ϕ](π) → [ψ](π).• Формула ∀ξ ϕ истинна на оценке π тогда и только тогда, когдаформула ϕ истинна на любой оценке π 0 , которая совпадает сπ всюду, кроме значения переменной ξ (которое в оценке π 0[п. 2]Определение истинности79может быть любым). Другими словами, если обозначить черезπ + (ξ 7→ m) оценку, при которой значение переменной ξ равноm, а остальные переменные принимают те же значения, что ив оценке π, то[∀ξ ϕ](π) =^[ϕ](π + (ξ 7→ m)).m∈M(В правой части стоит бесконечная конъюнкция, которая истинна, если все её члены истинны.)• Формула ∃ξ ϕ истинна на оценке π тогда и только тогда, когдаформула ϕ истинна на некоторой оценке π 0 , которая совпадаетс π всюду, кроме значения переменной ξ (которое в оценке π 0может быть любым).
Другими словами,[∃ξ ϕ](π) =_[ϕ](π + (ξ 7→ m)).m∈M(В правой части стоит бесконечная дизъюнкция, которая истинна, если хотя бы один из её членов истинен.)Заметим, что в двух последних пунктах значение переменной ξ воценке π не играет роли. Это позволяет легко доказать (индукциейпо построению формулы) такое утверждение: если две оценки π1 иπ2 придают одинаковые значения всем параметрам формулы ϕ, то[ϕ](π1 ) = [ϕ](π2 ). Другими словами, истинность формулы определяется значениями её параметров.45.
Проведите это индуктивное рассуждение подробно.46. Приведённые выше определения применимы к любой формуле, втом числе и к странной формуле ∀y A(x). Какие у неё параметры? При каких значениях параметров она истинна? (Ответ: она имеет единственныйпараметр x и эквивалентна формуле A(x).)47. В каком случае будет истинна формула ∀x ∃x A(x)? Тот же вопросдля формулы ∃x ∀x A(x).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
