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

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

Напомним, что п-местпным предикатом (отношением) на множестве А называется любое подмножество множества А_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}.