Lektsii_po_Diskretnoy_Matematike / Глава 1

Лекции.Дискретная математика.4 семестр. Логические исчисления.

Преподаватель – Налютин Никита Юрьевич. Составители – Кононов Василий, Сагитова Адиля и Главатских Павел.

Глава 1.Алгебраические структуры.

Абстрактная алгебра.

//Это мои примечания.

||Это промежуточные действия и комментарии преподавателя.

Абстрактная алгебра – это раздел математики, который изучает свойства алгебр (алгебраических систем, таких как группы, кольца, поля, частично

упорядоченные множества, решётки и отображения между этими структурами).

Определение. Абстрактная алгебра – это система

операций

, 2, … ,

,

состоящая из непустого множества

и конечного набора

= , 1

над этим множеством.

1, 2, … ,

В данном определении множество

– это носитель алгебры, т.е.

множество объектов, над которыми

осуществляются

операции.

Сигнатура

алгебры – это совокупность операций

, всюду2, … ,

.

Будем считать,

что операции1

определены,

однозначны

и,

, т.е. результат

операций

над

соответственно, замкнуты на множестве

.

объектами множества

так же содержится в

Операции, в зависимости от количества операндов (аргументов операций),

делятся на нульарные, унарные, бинарные, тернарные и т.д. (мультиарные).

||Нульарная операция – это операция, которая не зависит от операндов. Аналог –

||функция константа.

= , ,

2, … ,

являющаяся подмножеством алгебры

,

Определение. Подалгебра

алгебры

– это алгебра

,

замкнутым относительно всех1

операций

этой алгебры. Её носитель

, а

сигнатура

.

сложения, = , +

– = , +

– множество≤натуральных

,

Примеры алгебр:

чисел с операцией

множество

целых чисел с

операцией

сложения

= , +, −,×,÷							Глава 1
Кононов Василий, Сагитова Адиля и Главатских Павел
	– множество действительных чисел с основными операциями.
Соответственно, алгебры			и		являются подалгебрами алгебры .

Определение. Группоиды– ,полугруппы,группы.

||В дальнейшем под знаком

" "

будем понимать любую операцию.

Группоид

это

алгебра

.

Операция

“ ”

называется

Определение. Абелев (или, коммутативный=)

группоид= – это группоид, в

умножение

(на письме обычно опускается) и является,

бинарной

. Обладает

свойством замкнутости, т.е. для

.

котором операция умножения коммутативна:

.

Определение. Полугруппа – это группоид= ,

для

которого

выполняется

свойство ассоциативности для операции умножения:

.

= =

(т.е. нейтральный относительно

( : )для= ( )

Определение. Если существует элемент

выполняется

операции умножения), то элемент

называется единицей (или нейтральным элементом).

Определение. Моноид – это полугруппа, в которой существует единица.

Теорема. Во множестве

существует одна единица.

свойство единицы:

.

Т.к≠.

– единица, то

. С

Доказательство

(методом

от противного). Предположим существование

же единица, т.е.

=. Значит, (т.к.

)

′ = ′

.

′

другой единицы

′,

т.е.

′

. Рассмотрим

произведение

′ и

используем

Определение

.=Если

для элементов=

′

=справедливо= равенство

,

′

′

′

– так

другой стороны,

).

обратным

элементу

и

обозначается

−1

то

элемент

называется

к ,

=(т.е.

−1

=Определение

. Группа – это моноид, в котором для любого элемента

существует обратный.

коммутативна, т.е. для , выполняется = .

Определение. Абелева группа

– это группа, в которой операция умножения

Пример. Дано: = . Найти обратный элемент

−1.

=

=

.

−1

= ( )

−1

=

−1

−1

= (

−1

)

−1

=

−1

=

−1

−1

−1

−1

Если есть алгебра, являющаяся группой, то в ней линейное уравнение имеет

только одно решение. Т.е. уравнения

= и

= имеют ровно одно решение:

=				=			Глава 1
Кононов Василий, Сагитова Адиля и Главатских Павел
	−1		и		−1	соответственно. Таким образом, можно рассматривать ещё и

обратную операцию на группе (несмотря на то, что введена одна операция). Эта

обратная операция будет так же замкнута на этой группе.

=

=

одно и только одно решение, то данная

,

уравнения

и

имеют

Теорема. Если в полугруппе для

полугруппа является группой.

Доказательство. Пусть существуют и единственны решения данных

решения –

и

, т.е.

и

и

.

=

=

′

и ′ и

уравнений –

′

соответственно. Т.к.

′

– любые, то выберем

′

′

′

′

′

′

и

. Пусть их

рассмотрим уравнения

(«подмножество

уравнений»)

′

′

′

′

′

=

′, умножим

на

′ :

′=′

′

′

=

′

=

′. Следовательно, существует

и

=

=

Возьмём произвольный элемент

правая единица. Аналогично показывается, что существует левая единица. Вопрос:

отличаются ли они?

Рассмотрим:

′ ′

′

(по свойству правой единицы),

т.е.

левая

единица

будет

с правой. Таким образом, существует и

совпадать =

единственна единица.

′

и ′′

=

′′

=

,

По условию мы можем утверждать, что такие

и

(т.к.

).

Смотрим на исходные уравнения и запишем:

′

′′

′

= (

′′

)

′

=

′

=.

′,

с

другой

′

=

′′

(

) =

′′

=

′′

′′

′

′

′′

существуют.

Рассмотрим:

стороны

.

Следовательно,

Значит, существует и единственен обратный элемент.

Кольцо

– это алгебра

, состоящая из множества

,

Определение=.

и

на котором заданы 2 бинарные

операции

(сложение и умножение)

со

= , +,

свойствами:

+ = + ;

+

1)

для

,

+ ;

2)

для

, ,

+ ( + ) = ( + )

3)

для

, существует единственный : + = ;

4)

для

, ,

( ) =

( ) ;

5)

для

, ,

( + ) = + ;

6)

Определение, , .

+

= +

.кольца

– это группа

,

для

Аддитивная( )

подгруппа

совпадает

с

элементами

которой

являются все элемента кольца,

,а+,операция

, +

операцией сложения в кольце.

, =

полугруппа

кольца

Определение.

Мультипликативная

–

это

полугруппа

. Она

не

коммутативна.

Если

операция

умножения

будет

, +,

коммутативной (

), то получим коммутативное кольцо, или абелево кольцо.

Кононов Василий, Сагитова Адиля и Главатских Павел									Глава 1
	Элемент множества , нейтральный относительно операции сложения, в
кольце принято обозначать как				(нуль). А обратный элемент принято обозначать
	и называют его	противоположным			.
−			0
	Если умножить любой			элемент			кольца на	нейтральный	элемент
единственен.						),	0 = 0	нейтральный	элемент
относительно операции сложения (на							то получим
относительно операции сложения,						т.0е.	.	Нейтральный	элемент

Свойства(−) = (противоположного−) = −( ) элемента:

2)(−)(−) = . .

3)+ −( ) = 0.

+ (−) = ( − ) = 0 = 0

4)+ (−) = ( − ) = 0 = 0.

5)Следовательно, из 3-5 свойств элементы. −( ), (−) и (−) являются обратными( ) = (−для) = (элемента−) . . А т.к. обратный элемент единственен, то

В кольцах иногда бывают интересные «оптические явления». Может

нейтральный

≠ 0

≠ 0

= 0

случиться так, что если взять два ненулевых элемента (не нейтральных

относительно сложения)

и

, то

. В результате получился элемент,

относительно сложения. Элементы

и

– это, соответственно, левый

и правый делители нуля.

должно

0 = 0

Мультипликативная полугруппа не может быть группой, потому что

являться группой.

{0},

уравнение

имеет бесконечное множество решений. А для группы решение

быть ровно одно. Если рассмотреть алгебру

, то она будет

Если же мультипликативная полугруппа является0группой= 0 , то правые и левые делители нуля отсутствуют (потому что уравнение имеет только одно решение).

Определение. Идемпотентность – это такое свойство элемента= , что повторное действие на этот элемент не изменяет его, т.е. для .

Определение. Булево кольцо – это кольцо с единицей ( ) и идемпотентным умножением.

Кононов Василий, Сагитова Адиля и Главатских Павел

Глава 1

Теорема. В алгебре «булево кольцо» выполняется свойство + = 0.

= + + +

= + + + = + + + = ( + ) +

( + )

Доказательство. По

свойству

идемпотентности

+

= ( + )( + . Т).=к.

операции сложения.

=

. Значит,

( + )

– нейтральный элемент относительно

по свойству единицы

Теорема. Булево кольцо обладает свойством коммутативности:

.

+

Доказательство. Для операции сложения это очевидно. Пусть = ,

= ( +. )( + ) = + + +

= + + +

+ = 0

тогда,

по

предыдущей

теореме,

= .

Рассмотрим

выражение

+ = 0

=

операцию «дополнение»: . Её свойства:

,

,

.

Введём

Решётка

алгебра

=со свойствами= 0 :+ =

1)

Определение.

– это– коммутативность= , ,.∩

2)

= ,

∩– идемпотентность= ∩

.

4)

( )

= ( ), ( ∩ )–∩законы= ∩поглощения(∩ ) .

3)

= ∩ =

– ассоциативность.

Все эти( ∩свойства) = , обладают∩( )симметричностью=

.

Утверждение:

.

Доказательство. По закону= поглощения∩ =

.

Если доказать это утверждение, то можно= утверждать∩( ) =,

что∩ на множестве

задан

порядок, частичный и неполный, т.е. можно рассматривать отношения

«больше либо равно» и «меньше либо равно».

Определение. Пусть на некотором множестве

порядок

задано отношение

. В этом случае говорят, что оно задаёт частичный{ , , , … }на множестве. При

этом выполняются следующие свойства:

1)

Рефлексивность – для

→

.

2)

Транзитивность – для , ,

→

( )&( ) ( ).

3)

Антисимметричность – для ,

→ ( )&( ) = .

//Где знак “&” – логическое «И».

Кононов Василий, Сагитова Адиля и Главатских Павел

( = )

( ∩ = )

Глава 1

Пример.

. Т.к.

что

,

то

Покажем,

отношение

=

является

отношением

( = )

≤

По

=

,

или

частичного

порядка.

определению

=

(по =

= ( ) =

= ( и ) =

( .)Т.к. = =

выполняется

рефлексивность.

Транзитивность.

Пусть

и

.

Тогда

=

=

=

=

свойству ассоциативности). Далее,

операция “

” коммутативна, то

=

.

Значит, выполняется антисимметричность. Следовательно,

–

это

отношение частичного порядка.

и( ) = (

соответствуют выражениям

≤

∩)(. ∩ ) = ∩

отношения

порядка

≥ ∩

∩ ≤

.

Они

Рассмотрим 2

выражения:

и

(соответственно

=

Следовательно, для

можно найти мажоранту и миноранту

верхняя

и

нижняя

грани).

Это

либо

объединение,

либо

( ) = = ( )

= ( )

= = = .

пересечение. Допустим, что существует несколько мажорант, т.е. ≤

Отношениеinfпорядка{ , } = ∩

и

supтакже{ , }является= решёткой.

Следовательно,

(нижняя и верхняя грани).

Если мы ввели на множестве=

отношение частичного порядка,

то можно

Свойства:

,

→

≤,

,

. Т.е.

нуль

1

≤ 1

найти самый маленький элемент

этого множества. Он обозначается

.

Если он

∩1 =

нейтральным =

∩ =

1 = 1

(

).

существует,

то для

. Соответственно, другой элемент –

является

элементом относительно объединения, а

(единица)

является

нейтральным элементом относительно пересечения.

∩ ≤1 , 1 ≤ 1.

′

, т.е.

и

′

,

′

=

Пусть существует элемент

. Допустим, что

′ :

. Тогда из свойств

отношения:

и

что не верно.

Обратных≤ элементов≤ на решётках= не существует= .

выполняется свойство

( ∩ )

=

( ∩ )

( ∩ ).

Определение.

Решётка

называется

дистрибутивной, если

в

ней

= ( ∩ ) = ( ∩ ) ( ∩ ) = ∩( ) ∩( ) = .

Рассмотрим

алгебру

(расширим

решётку

операцией

дополнения, и пусть решётка

будет дистрибутивной):

= , ,∩,

1)

= ,

∩ = ∩ – коммутативность.

2)

( )

= ( )

,

∩ (∩ )

= ( ∩ )

∩ – ассоциативность.

3)

( ∩ )

= ,

∩( )

=

– законы поглощения.

5)

( ∩ ) = ( ,

) ∩( ) –.

Глава 1

Кононов Василий, Сагитова Адиля и Главатских Павел

4)

дистрибутивность.

Последнюю( аксиому) ∩ = можно( ∩ переписать) =

в виде

≤ . Свойства

операции «дополнение»:

= 1

и ∩ = . ∩ ≤ или

= = ( ∩ ) = ( ) ∩( ) = 1 ∩

( ) = ≤ .

Пример. Пусть известно, что для ∩ = . Чему равно ?

(

По определению = 1, ∩ = , = .

)

: = ∩ , ∩ = .

Законы де Моргана.

Из

этого следует,

что

,

= , +,

по

сути, одно и то

же.

≤ Булева ≤алгебра

и операции

над

множествами,

∩ =

= + +

= +

Введём

следующие

операции:

Рассмотрим

булеву

алгебру

.

1)

и

+ = 0

. Проверим, образуют ли новые

введённые операции решётку (выполняется свойство:

):

2)

= + + , = + +

выполняется коммутативность.

( ) = + + ( ),

= + + + + ( + + ) =

= + + + + + +

аналогично

( ) = + +

+ ( ) = + + + + ( + + ) = + + + + + +

+

( ) = ( )

выполняется ассоциативность.

3) ( ∩ ) = + ∩ + ( ∩ )

= + + ,

( )

∩( )

=

= ( + + ) ∩( + + ) = ( + + )( + + ) = + +

+ + + + + + + = + + + + +

+ + + + = + +

выполняется дистрибутивность.

||Здесь одинаковые члены «сокращаются»:

и , и

, и .

,∩( )

=

4)

( ∩ ) = = + + = + + = ,

= ( ) = ( + + ) = + + = + + =

( ∩ ) = ( + ) = ( + ) = ( + ) = 0 =

выполняются законы поглощения.

Таким= 0 + образом+ 0 =, булева

алгебра

с операциями над множествами

булеву решётку. ∩ = , = + + ,

= + , = ∩ = ( + )

=

есть булево кольцо, мы можем построить

образует булево кольцо. Если у нас = , +,

= + = + = 0, 1 = = .+ + = + + + ( + ) = + +
Кононов Василий, Сагитова Адиля и Главатских Павел			Глава 1
+ + + = + + + + =	= , ,∩,		, то можно
Соответственно, и наоборот, если есть решётка
построить булево кольцо, введя следующие операции:
+ = ∩ ( ∩ ) и = ∩ .

Из всего вышесказанного можно сделать вывод, что булевы кольца и булевы решётки – это одно и то же, называемое общим названием «булева алгебра».