1611678155-8e243485e0094ed4164786c6208411db (П.Е. Алаев - Краткий конспект лекций), страница 5

. . , tm — термы,то f (t1 , . . . , tm ) — терм.21Формула ИПΣ — слово в этом алфавите, которое строится по правилам:1) если P — предикатный символ из Σ местности n, а t1 , . . . , tn — термы,то P (t1 , . . . , tn ) — формула;2) если t1 , t2 — термы, то t1 = t2 — формула;3) если A, B — формулы, то ¬A, (A&B), (A ∨ B), (A → B) — тоже формулы;4) если A — формула, x — переменная, то ∃xA и ∀xA — тоже формулы.Формулы из пунктов (1) и (2) называются атомными.

Две последние формулымогут читаться так: “существует x такой, что верно A” и “для всех x верно A”.Как и для ИВ, подформулой формулы A называется её подслово, которое самоявляется формулой. Отметим без доказательства, что для формул ИПΣ нетруднополучить аналоги ряда утверждений, доказанных для формул ИВ в Части 1.Лемма. Если A, B — формулы ИПΣ и слово A является началом слова B, тоA = B.Предложение (о представлении термов и формул ИП). a) Любой термИПΣ может быть единственным образом представлен в одной из формx, c, f (t1 , . .

. , tk ),где x — переменная, c — константный символ, f — функциональный символ, ti —термы ИПΣ ;b) любая формула ИПΣ единственным образом может быть представлена в однойиз формP (t1 , . . . , tk ), t1 = t2 , ¬A, (A&B), (A ∨ B), (A → B), ∃xA, ∀xA,где P — предикатный символ, ti — термы, A, B — формулы ИПΣ , x — переменная.Как правило, в дальнейшем мы будем работать с некоторой фиксированнойсигнатурой Σ. До конца Части 3 термы и формулы ИПΣ будем называть простотермами и формулами. Если нужно будет подчеркнуть то, что их сигнатурныесимволы лежат в Σ, они будут называться термами и формулами сигнатуры Σ.Предложение (о подформулах формулы ИП).

Пусть A — формула, B —её подформула.a) Если A — атомная формула, то B = A.b) Если A = (A1 ◦ A2 ), где ◦ ∈ {&, ∨, →}, и при этом B 6= A, то любое вхождениеB в A является вхождением либо в A1 , либо в A2 .c) Если A = ¬A1 , A = ∃xA1 или A = ∀xA1 , и при этом B 6= A, то любое вхождениеB в A является вхождением в A1 .Из этих утверждений легко следуетЗамечание. В любой формуле для каждого вхождения квантора ∀ или ∃ существует единственное вхождение подформулы, которое начинается с этого квантора.22Это вхождение подформулы называется областью действия данного квантора.Квантор, за которым следует переменная x, называется квантором по переменнойx.

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

Формула, у которой нет свободных переменных, называется предложением. Обозначимчерез Fv(A) множество свободных переменных формулы A.Лемма (о свободных переменных). a) Если A — атомная формула, то Fv(A)состоит из всех переменных, входящих в A;b) если A = (A1 ◦ A2 ), где ◦ ∈ {&, ∨, →}, то Fv(A) = Fv(A1 ) ∪ Fv(A2 );c) если A = ¬A1 , то Fv(A) = Fv(A1 );d) если A = ∃xA1 или A = ∀xA1 , то Fv(A) = Fv(A1 ) \ {x}.3.2. Алгебраические системыПусть A — множество, n > 1 — натуральное число. Любое отображениеP : An → {и, л} называется n-местным предикатом на множестве A, а любаяфункция f : An → A — n-местной функцией на множестве A.Пусть фиксирована сигнатура Σ. Алгебраическая система A сигнатуры Σ —это пара вида A = (A, ΣA ), где A — непустое множество, а ΣA — интерпретациясигнатуры в A. Интерпретация сигнатуры — это соответствие, которое каждомусимволу из Σ сопоставляет его интерпретацию по следующим правилам:1) P ∈ PrΣ и ν(P ) = n ⇒ его интерпретация P A — n-местный предикат на A;2) f ∈ FnΣ и ν(f ) = m ⇒ его интерпретация f A — m-местная функция на A;3) c ∈ CnΣ ⇒ его интерпретация cA — элемент A.Множество A называется носителем системы A.

Алгебраические системы называют также моделями или структурами. Для краткости иногда будем называтьих просто системами. Если сигнатура задана в видеΣ = (P1 , . . . , Pt ; f1 , . . . , fs ; c1 , . . . , cr ),то алгебраическая система этой сигнатуры часто будет обозначаться какA = (A, P1A , . . . , PtA , f1A , . . .

, fsA , cA1 , . . . , cAr ).23Пусть A, B — две системы сигнатуры Σ с носителями A и B, соответственно.Функция β : A → B называется изоморфизмом между A и B, если β являетсябиекцией, для каждого символа из Σ удовлетворяющей условию:1) P ∈ PrΣ ⇒ P A (a1 , . . . , an ) = P B (β(a1 ), . . .

, β(an )) для любых ai ∈ A;2) f ∈ FnΣ ⇒ β(f A (a1 , . . . , am )) = f B (β(a1 ), . . . , β(am )) для любых ai ∈ A;3) c ∈ CnΣ ⇒ β(cA ) = cB .Если между A и B существует изоморфизм, они называются изоморфными(A ∼= B). Изоморфные системы являются по сути одной и той же системой, сточностью до замены одного носителя на другой. Свойства носителя системы частопереносят на саму систему: например, мощностью системы называют мощность еёносителя, элементами системы — элементы носителя и т.

д.Замечание. Если две системы изоморфны, то их мощности равны.Система B называется подсистемой системы A, если B ⊆ A и интерпретациялюбого символа из Σ в A и B совпадает на B. Последнее означает, что:1) P ∈ PrΣ ⇒ P A (a1 , . . . , an ) = P B (a1 , . . . , an ) для любых ai ∈ B;2) f ∈ FnΣ ⇒ f A (a1 , . . .

, am ) = f B (a1 , . . . , am ) для любых ai ∈ B;3) c ∈ CnΣ ⇒ cA = cB .Это определение означает, что интерпретация Σ в B — просто сужение интерпретации Σ в A на множество B. В силу этого подсистемой иногда называют исамо множество B.Предложение. Пусть A — алгебраическая система с носителем A, а X ⊆ A.Тогда в A существует наименьшая (по включению) подсистема, содержащая X.Подсистема с указанным свойством называется подсистемой, порождённой множеством X.3.3. Истинность формул в алгебраических системахВведём несколько обозначений, облегчающих работу с формулами и термами.Часто терм бывает удобно обозначать как t(x1 , .

. . , xk ). Договоримся, что такаязапись может быть использована только в том случае, когда все переменные этоготерма входят в набор x1 , . . . , xk , и все переменные из этого набора различны. Аналогичная запись A(x1 , . . . , xk ) может быть использована для формулы, но тольков том случае, когда все её свободные переменные входят в набор x1 , . .

. , xk , и всеего элементы различны. При этом запись A может обозначать как предложение,так и произвольную формулу. Кроме того, набор x1 , . . . , xk часто будем сокращатьдо x̄.24Пусть фиксирована сигнатура Σ и A — система этой сигнатуры. Если дан термt(x1 , . . . , xk ) и a1 , . . . , ak ∈ A, то мы можем определить значение этого терма всистеме A при значениях переменных x1 = a1 , . . . , xk = ak . Обозначим это значениекак tA (a1 , . . .

, ak ). Оно определяется индукцией по длине терма:1) если t(x̄) — переменная xi , то tA (ā) = ai ;2) если t(x̄) — константный символ c, то tA (ā) = cA ;3) если t(x̄) = f (t1 (x̄), . . . , tn (x̄)), то tA (ā) = f A (tA1 (ā), . . . , tAn (ā)).Тем самым значение терма — элемент A.Замечание. Значение терма зависит только от системы и значений входящихв него переменных.Значением формулы ИП в системе является истина или ложь, т.е. она являетсялибо истинной, либо ложной.

Пусть дана формула A(x1 , . . . , xk ) и a1 , . . . , ak ∈ A.Дадим определение того, что эта формула истинна в A при значениях переменных x1 = a1 , . . . , xk = ak . Обозначим это как A |= A(a1 , . . . , ak ). Если формула неявляется истинной, то по определению является ложной, и это обозначается какA 6|= A(a1 , .

. . , ak ). Определим истинность индукцией по длине формулы:1) если A(x̄) = P (t1 (x̄), . . . , tn (x̄)), то A |= A(ā) ⇔ P A (tA1 (ā), . . . , tAn (ā)) = и;2) если A(x̄) — формула t1 (x̄) = t2 (x̄), то A |= A(ā) ⇔ tA1 (ā) = tA2 (ā);3) если A(x̄) = ¬B(x̄), то A |= A(ā) ⇔ A 6|= B(ā);4) если A(x̄) = (A1 (x̄)&A2 (x̄)), то A |= A(ā) ⇔ A |= A1 (ā) и A |= A2 (ā);5) если A(x̄) = (A1 (x̄) ∨ A2 (x̄)), то A |= A(ā) ⇔ A |= A1 (ā) или A |= A2 (ā);6) если A(x̄) = (A1 (x̄) → A2 (x̄)), то A |= A(ā) ⇔ A 6|= A1 (ā) или A |= A2 (ā);7) если A(x̄) = ∃yB(x̄, y), где y 6∈ {x1 , . . . , xk }, тоA |= A(ā) ⇔ существует b ∈ A такой, что A |= B(ā, b);8) если A(x̄) = ∀yB(x̄, y), где y 6∈ {x1 , . .