В алгебраической системе. Дадим индуктивное определение истинности формулы φ(x1, ,xn) сигнатуры Σ на элементах a1, ,an А в алгебраической системе t wx:val="Cambria

 

Дадим индуктивное определение истинности формулы φ (x₁, …, x_n) сигнатуры Σ на элементах a₁, …, a_n А в алгебраической системе t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> = (обозначаем φ (a₁, …, a_n)).

1) ⊨ t₁(a₁, …, a_n)=t₂(a₁, …, a_n), где t₁, t₂ T( Σ ), значения термов t₁, t₂ в алгебраической системе на элементах a₁, …, a_n А совпадают;

2) ⊨ P(t₁(a₁, …, a_n), …., t_k(a₁, …, a_n)), где P^(k) Σ, t₁, …, t_k T( Σ ), (t₁(a₁, …, a_n), …, t_k(a₁, …, a_n)) P;

3) ⊨ ψ (a₁, …, a_n)∧ χ (a₁, …, a_n) ⊨ ψ (a₁, …, a_n) и ⊨ χ (a₁, …, a_n);

4) ⊨ ψ (a₁, …, a_n)∨ χ (a₁, …, a_n) ⊨ ψ (a₁, …, a_n) или ⊨ χ (a₁, …, a_n);

5) ⊨ ψ (a₁, …, a_n)→ χ (a₁, …, a_n) если ⊨ ψ (a₁, …, a_n), то ⊨ χ (a₁, …, a_n);

6) ⊨ ψ (a₁, …, a_n) неверно, что ⊨ ψ (a₁, …, a_n);

7) ⊨ xψ (x, a₁, …, a_n) ⊨ ψ (a, a₁, …, a_n) для любого а A;

8) ⊨ xψ (x, a₁, …, a_n) t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> ⊨ ψ (a, a₁, …, a_n) для некоторого а А.

Если не выполняется ⊨ φ (a₁, …, a_n), то будем говорить, что формула φ (x₁, …, x_n) сигнатуры Σ ложна в системе t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> на элементах a₁, …, a_n А.

Пример 7. Записать формулу φ (x), истинную в на элементе a тогда и только тогда, когда a четно.

Решение. φ (x) y(x=y+y).

Пример 8. Записать формулу φ (x, y, z), истинную в на кортеже a тогда и только тогда, когда c ‑ наименьшее общее кратное чисел a и b.

Решение. φ (x, y, z) ψ (x, y, z)∧ χ (x, y, z),

где формула ψ «говорит» о том, что z делится на x и на y, а формула χ «говорит» о том, что z делит все общие кратные х и у, т. е. является наименьшим из всех общих кратных:

ψ (x, y, z) uv(z=x u∧ z=х y),

χ (x, y, z) w( uv(w=x u∧ w=х y)→ w₁(w=w₁ z)).

Таким образом,

φ (х, у, z) uv(z=x u∧ z=х y)∧ w( uv(w=x u∧ w=х y)→ w₁(w=w₁ z)).