Логика предикатов. Алгебраические системы

Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы.

Напомним, что п-местпным предикатом (отношением) на множестве А называется любое подмножество множества А_n; п-местной алгебраической операцией на множестве А называется функция ƒ:A_n→A, где А_n – n-я декартова степень множества А. Отметим, что поскольку операция ƒ является функцией, для любого набора (x₁,…,x_n)єA_nрезультат применения операции ƒ(x₁,…,x_n)однозначно определен. Так как область значений операции ƒ лежит в множестве А, то будем говорить, что операция ƒ замкнута на множестве А.

Сигнатурой Σ называется совокупность предикатных и функциональных символов с указанием их местности. 0-местный функциональный символ называется константным символом или просто константой. Если α‑функциональный или предикатный символ, то его местность обозначается через μ(α)‑п-местные предикатные и функциональные символы часто будем обозначать соответственно через Р(n) и ƒ(n). Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ={≤}, Σ={≤,+, . , 0} и т.д.

Алгебраической системой A = сигнатуры Σ называется непустое множество А, где каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы . Предикаты и функции, соответствующие символам из Σ, называются ихинтерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент из А.

Пример 1.1) Набор является алгебраической системой с двумя двухместными операциями.

2) Набор является алгебраической системой с бинарным отношением ≤, двухместными операциями +, , одноместной операцией ' : п→n+1 и нуль-местной операций 1.

3) Набор не является алгебраической системой, поскольку деление не является операцией на множестве Z, а элемент не принадлежит Z.

4) Набор является алгебраической системой, где т.е. множество всех подмножеств множества

5) Алгебраическая система =(A,Σ) называется подсистемой системы =(В, Σ) (обозначается ), если выполняются следующие условия:

а)А В;

б)для любого функционального символа ƒ⁽ⁿ⁾ Σ соответствующих функций ƒ_A и ƒ _ß и любых элементов a₁,a₂,…,a_n Aвыполняется равенство ƒ_A(a₁,a₂,…,a_n)=ƒ_ß (a₁,a₂,…,a_n), т.е. интерпретации символа ƒ действуют одинаково на элементах из А;

в)для любого предикатного символа Р⁽ⁿ⁾ Σ, соответствующих предикатов и справедливо равенство P= ∩A_n, т.е. предикат содержит в точности те кортежи предиката , которые состоят из элементов множества А.

Теорема 1.Если ‑алгебраическая система, X В, X≠Ø, то существует единственная подсистема (Х) с носителем В(Х) такая, что X В(Х) и (Х) для любой подсистемы ,для которой X А.

Доказательство.В качестве В(Х) рассмотрим пересечение носителей А всех подсистем ,содержащих X. Так как X В(Х), то В(Х)≠Ø. Единственность подсистемы (Х) очевидна.

Подсистема (Х) из теоремы 1 называется подсистемой, порожденной множеством Xв В.

Для описания устройства подсистемы (Х) определим индукцией по построению понятие терма сигнатуры Σ:

1) переменные и константные символы из Σ суть термы;

2) если ƒ Σ‑n-местный функциональный символ, t₁,t₂,…,t_n‑термы, то ƒ(t₁,t₂,…,t_n)‑ терм;

3) никаких термов, кроме построенных по пп. 1,2, нет.
Множество всех термов сигнатуры Σобозначается через Т(Σ).

Пример 2.

1) Термами сигнатуры Σ={+,∙,≤,0} будут, например, 0, x, x+y, z(x+z)+0y, а x+y≤(0+х)xтермом не является.

2) Если Σ={ƒ⁽³⁾, g⁽¹⁾, h⁽²⁾}‑функциональная сигнатура, то выражения h(ƒ(x₁, x₂, x₃), g(x₂)), g(ƒ(h(x₁, x₂), x₁, g(x₂)) – термы, а h(x₁, ƒ(x₁, x₃))не образует терм.

Пусть t(x₁,…, x_k)‑терм из T(Σ), все переменные которого содержатся среди x₁,…,x_k; =(A,Σ)‑ алгебраическая система. Значение терма tпри значениях a₁,…,a_k Aпеременных x₁,…,x_k(t(a₁,…,a_k)) определяется по индукции:

1) если tесть переменная x_i(константный символ с), то значение tесть а_i(с):

2) если терм tесть ƒ(t₁,…, t_n),а значения t₁,…,t_nсуть b₁,…,b_n, то значение терма tесть ƒ(b₁,…, t_n).

Теорема 2.Если =(B,Σ)‑ алгебраическая система, Ø≠x B, то носитель подсистемы (Х) равен {t(a₁,…,a_n)׀t T(Σ), a₁,…,a_n X}.

Доказательство.Индукцией по числу шагов построения терма tполучаем, что если t(x₁,x₂,…,x_n) T(Σ) и a₁,…,a_n X, то t(a₁,…,a_n) А для любой подсистемы , содержащей X. Поэтому достаточно показать, что множество Y={t(a₁,…,a_n)׀t T(Σ), a₁,…,a_n X} замкнуто относительно операций системы . Пустьƒ⁽ⁿ⁾єT(Σ), t₁,…,t_m T(Σ), b_i=t(a₁,…,a_n), i {1,…,m}. Тогдаƒ(b₁,…,b_m) Y, посколькуƒ(t₁,…,t_m) T(Σ).

Таким образом, носитель подсистемы (X) состоит из всех элементов, которые получаются при подстановке элементов из Xв термы.

Пример 3.

1) Найдем носитель подсистемы (Х) системы =(Q , ∙) для множества X={1/2}. Так как сигнатура Σ системы В есть {∙}, то Т(Σ)={x₁, x₁x₂, (x₁x₂)x₃, x₁(x₂x₃),…}. По теореме 2 получаем B(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2ⁿ,n≥1}.

2)Если =(Q\{0}, . , : ) X={1/2}, то, поскольку по срав­нению с предыдущим примером сигнатура дополняется опе­рацией деления, множество В(Х) содержит числа 1/2ⁿ:1/2^m=2^m-n, m, n≥1, т.е. C={2ⁿ׀nєZ} B(X).Так как множество С замкнуто относительно операций умножения и деления. т.е. (C, Σ) является подсистемой системы и содержит множество X, то В(Х) С. Следовательно, B(Х)=С.

Пример 4. Построить подсистему алгебраической системы А, порожденную множеством Х.

= Z; -

X={22;-36}.

Решение.Надо определить какую подсистему порождают

22;-36 “-“. Таке как 2=22-8 (-36)-14 22 и любое число, получаемое из чисел 22, -36 с помощью операции вычитания четное, то

Пример 5. Построить подсистему алгебраической системы , порожденнуюмножеством Х.

= R\{0};:

Х={ ; }.

Решение.

={ z }.

Формулы ЛП

Большинство определений этого параграфа будут индуктивными.

Введем понятие атомарной формулы сигнатуры Σ:

1) если t₁, t₂, T(Σ), то t₁=t₂‑ атомарная формула:

2) если P(n) Σ‑предикатный символ, t₁,t₂,…,t_n T(Σ), то Р(t₁,t₂,…,t_n)‑ атомарная формула;

3) никаких атомарных формул, кроме построенных по пп. 1, 2, нет.

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

1) атомарная формула есть формула;

2) если φ, ψ - формулы, то φ, (φ∧ψ), (φ∨ψ), (φ→ψ), xφ, xφ‑ формулы;

3) никаких формул, кроме построенных по пп. 1, 2, нет.

Символы , использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются "для любого"и "существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x₁… x_nφи x₁… x_nφбудем использовать записи x₁,…,x_nφи x₁,…,x_nφ.

Определим подформулы формулы φсигнатуры Σ:

1) если φ‑атомарная формула, то φ‑ее единственная
подформула;

2) если φимеет вид φ₁, или xφ₁,или xφ₁, то подформула формулы φ–этолибо φ, либо подформула формулы φ₁;

3) если φимеет вид φ₁∧φ₂, или φ₁∨φ₂, или φ₁→φ₂, то подформула формулы φ‑ это либо φ, либо подформула формулы φ₁, либо подформула формулы φ₂;

4) других подформул формулы φ, кроме построенных по
пп. 1, 2, 3, нет.

Пример 1. Пусть Σ={F⁽²⁾,P⁽¹⁾}, φ= x( y(x=F(z,y))∨P(z))‑ формула сигнатуры Σ. Тогда x( y(x=F(z,y))∨P(z)), y(x=F(z,y))∨P(z), y(x=F(z,y)),x=F(z,y)),P(z)‑все подформулы формулы φ.

Говорят, что вхождение переменной х в формулу φ связано в φ, если оно находится в терме или предикате подформулы формулы φвида xψили xψ; в противном случае это вхождение называется свободным в φ. Переменная х называется свободной (связанной), если некоторое вхождение х в φсвободно (связано).

Пример 2. Пусть S={P₁⁽¹⁾,P₂⁽²⁾}. Рассмотрим формулы:

1) P₁(x);

2) Р₂(x,y)→ xP₁(x);
3) x(P₂(x,y)→P₁(x)).

Переменная х в первой формуле является свободной, во второй - и свободной, и связанной, в третьей ‑ связанной: переменная у во всех формулах свободна.

Пример 3.

Выписать все подформулы формулыφ, определить свободные и связанные вхождения переменных.

φ x z y(x y+z) ((z∙2=u)→ u(u=x+z)).

Определить все свободные и связанные переменные формулы φ.

Решение. Выпишем подформулыформулы φ.

1) x y+z,

2) y(x y+z),

3) z y(x y+z),

4) x z y(x y+z),

5) z 2=u,

6) u=x+z,

7) u(u=x+z),

8) (z 2=u)→ u(u=x+z),

9) φ.

Поскольку существуют связанные и свободные вхождения переменной х в формулу φ, то хявляется связанной и свободной переменной. Переменныеuи zтоже связанные и свободные. Переменнаяy связанная.

Предложением или замкнутой формулой сигнатуры Σ называется формула сигнатуры Σ, не имеющая свободных переменных.

Запись φ(x₁,…,x_n)будет означать, что все свободные переменные формулы φсодержатся в множестве {x₁,…, x_n}.