Конгруэнции

Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности , при котором для любого , любого n-местного символа произвольных наборов (a1, a2, … ,an), (b1, b2, … ,bn) An, если a1θb1,a2θb2, …, anθbn, то f(a1, a2, … ,an)θf(b1, b2, … ,bn), т.е. все операции согласованы с отношением эквивалентности θ.

 

Пример. Для двухместной операции сложения это выглядит так: для любых x и y из A и любых , элемент a+b принадлежит классу θ(x+y).

 

Лемма. Отношение является конгруэнцией на алгебре <Z; +, >.

 

Наибольший общий делитель чисел a и b обозначается (a,b)или НОД(a,b). Два целых числа a и b называются взаимно простыми если (a,b) = 1.

Теорема. Тогда и только тогда элемент a кольца Zm имеет обратный (т.е. элемент a-1 такой, что a a-1 = 1), когда (a,m) = 1.

 

Теорема. Кольцо вычетов <Zm; +, > тогда и только тогда является полем, когда m простое число.

 

Замечание

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

δ = ‹ A, S1, S2› (A- символы алфавита, S1- синтаксис, S2- семантика).

2. В рамках формализированных языков строятся логические теории, с помощью которых решаются логические задачи.

3. Во множестве формул языка выделяют класс формул - аксиомы (логич. закон, базис) Например, выражение xне x = 1

4. Выделяют множество переходов, т.е. с помощью переходов от одной формулы к другой находят правильные умозаключения.