Теория групп

Пример

F = {$x1P(x1), $x1($x2|x1)[P(x1)&P(x2)],… } A = {"xP(x)} “Из Г следует А?”

1) Конструктивное док-во: Выберем I: U=Z, P = “х принадлежит натуральным”

2) Существует конечное Г’, Г’ = первые n формул. I: U = {a1,a2,…,an+1} P=[1,1,1,1,…,1,0]

Две формулы A и B равносильны, если A Þ B и B Þ A.

Две различные формулы в языке L (σ) могут оказаться логически равносильными. В качестве примера рассмотрим пару формул A = [$ x P (x) Ú $ y Q (y)] и B = $ x [ P (x) Ú Q (x)],

Формула A называется префиксной (предваренной нормальной), если она имеет вид

Q ₁ y ₁ Q ₂ y ₂... Q_ny_n B, где Q ₁, Q ₂,..., Q _n - кванторы; y ₁, y ₂,..., y _n - индивидные переменные; B - формула из L (σ), не содержащая кванторов.

Существует алгоритм, который для каждой формулы из L (σ) строит логически равносильную ей префиксную формулу.

Действие алгоритма основано на применении следующих правил вынесения кванторов и замены связанной переменной:

а) Ø$ x A º " x Ø A,

б) Ø" x A º $ x Ø A,

в) [$ x A & B ] º $ x [ A & B ],

г) [$ x A Ú B ] º $ x [ A Ú B ],

д) [" x A & B ] º " x [ A & B ],

е) [" x A Ú B ] º " x [ A Ú B ],

ж) [ B & $ x A ] º $ x [ B & A ],

з) [ B Ú $ x A ] º $ x [ B Ú A ],

и) [ B & " x A ] º " x [ B & A ],

к) [ B Ú " x A ] º " x [ B Ú A ],

л) " x A º " y A_x [ y ],

м) $ x A º $ y A_x [ y ],

где A и B - формулы, переменная x не имеет свободных вхождений в B, переменная y (в правилах л), м)) не имеет свободных вхождений в A. Указанные выше равносильности легко доказываются методом построения деревьев.

Две формулы A и B равносильны, если A Þ B и B Þ A.

Две различные формулы в языке L (σ) могут оказаться логически равносильными. В качестве примера рассмотрим пару формул A = [$ x P (x) Ú $ y Q (y)] и B = $ x [ P (x) Ú Q (x)],

Формула A называется префиксной (предваренной нормальной), если она имеет вид

Q ₁ y ₁ Q ₂ y ₂... Q_ny_n B, где Q ₁, Q ₂,..., Q _n - кванторы; y ₁, y ₂,..., y _n - индивидные переменные; B - формула из L (σ), не содержащая кванторов.

Антипрефиксная форма – все кванторы максимально продвинуты вглубь формулы.

Формула называется сингулярной, если все ее нелогические символы являются одноместными предикатами. Сингулярная формула называется примарной, если она имеет вид

" x [~ P ₁(x) Ú ~ P ₂(x) Ú... Ú ~ P _k(x)] или $ x [~ P ₁(x) & ~ P ₂(x) &... & ~ P _k(x)],

где P ₁, P ₂,..., P_k - одноместные предикатные символы, а знак ~ означает наличие или отсутствие в соответствующем месте знака отрицания.

Существует алгоритм, который любую замкнутую сингулярную формулу A преобразует в логически равносильную ей булеву комбинацию примарных формул.

Действие алгоритма основано на следующем преобразовании. В формуле A находится подформула, начинающаяся с квантора, в области действия которого расположена булева комбинация примарных и атомарных формул. Пусть найденная подформула имеет вид " x B. Формула B представляется в виде нормальной конъюнктивной формы (КНФ) вида B ₁ & B ₂ &... & B_s, где каждое B_i (i = 1, 2,..., s) есть дизъюнкция примарных и/или атомарных формул или их отрицаний. Подформула " x B заменяется формулой " x B ₁&" x B ₂&...&" x B_s. Далее, каждая формула B_j (j = 1, 2, …, s) представляется в виде

~ C ₁ Ú ~ C ₂ Ú... Ú ~ C_t Ú ~ P ₁(x)Ú ~ P ₂(x) Ú... Ú ~ P _r(x),

где C_i (i =1, 2,..., t) либо уже обработаны алгоритмом, либо не зависят от х, P ₁, P ₂,..., P_r - одноместные предикатные символы, а знак ~ означает наличие или отсутствие в соответствующем месте знака отрицания.

Затем подформула "x B заменяется подформулой вида

~ C ₁ Ú ~ C ₂ Ú... Ú ~ C_t Ú " x [~ P ₁(x) Ú ~ P ₂(x) Ú... Ú ~ P_r (x)].

Если исходная подформула A имеет вид $ x B, то поступают двойственным образом, используя нормальную дизъюнктивную форму (ДНФ) вместо КНФ.

В математике можно выделить два способа формирования теорий. Один из них называется аксиоматическим и заключается в том, что некоторые утверждения из каких-либо содержательных соображений объявляются аксиомами. Развитие теории в этом случае состоит в изучении ее интерпретаций и в получении следствий из аксиом.

Второй способ формирования теории начинается с изучения какой-либо конкретной математической структуры или класса структур. В таком случае, естественно, возникает вопрос о полной аксиоматизации этого класса/

Естественным методологическим требованием к множеству аксиом при этом является требование его алгоритмической разрешимости. Это требование заключается в том, чтобы существовал способ, позволяющий по любому утверждению отвечать на вопрос, является ли оно аксиомой.

Множество предложений, истинных в заданной структуре S, называют теорией структуры S и обозначают Th (S).

Пусть σ - нелогическая сигнатура и Γ - множество предложений в языке L (σ). Пару T = (σ, Γ) будем называть аксиоматической теорией, а множество Γ - множеством аксиом этой теории. Логические следствия из аксиом, выраженные в сигнатуре σ, называются теоремами теории T. Часто аксиоматическую теорию отождествляют с множеством ее теорем, то есть с логическим замыканием множества Γ. Логическое замыкание множества Γ обозначим через [ Γ ].

В общем случае под элементарной теорией будем понимать любое логически замкнутое множество предложений рассматриваемой сигнатуры.

В качестве первого примера рассмотрим сигнатуру σ = {=, °, e }, где = - предикат равенства, ° - функциональный двуместный символ, e - константа.

Пусть Γ состоит из предложений

1) " x " y " z (((x ° y)° z) = (x °(y ° z))),

2). " x ((x ° e) = x),

3). " x $ y ((x ° y) = e).

Множество всех теорем теории G = (σ, Γ) составляет элементарную теорию групп, являющуюся фрагментом математической теории групп, полную формализацию которой можно провести, например, в рамках теории множеств. Этот вопрос остается за рамками данного пособия.

Дата добавления: 2015-08-31