Лекция № 6. Линейные диофантовы уравнения.

Уравнения с n неизвестными сводятся заменой переменных к уравнению с меньшим числом неизвестных

Пример.

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

Уравнение с n неизвестными имеет общее решение в видеn линейных функций -целочисленного параметра.

Замечание. (Геометрическая интерпретация)

Уравнение задаёт в пространствегиперплоскость (линейное многообразие) и если, то решение диофантова уравнения задают точки этой гиперплоскости, имеющие целочисленные координаты.

Замечание.

Таким же образом можно решать и системы линейных диофантовых уравнений.

Пример.

Замечание.

Общее решение диофантова уравнения или системы уравнений может быть записано не единственным образом, но число параметров постоянно .

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

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

Если рефлексивно, антисимметричнои транзитивно, то отношениеназывается частичным порядком на множестве А, а само множествоназывается частично упорядоченным множеством.

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

Если и(или), тоиназываются сравнимыми по отношению частичного порядка элементами, иначе – не сравнимыми.

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

Если любая пара множества А сравнима, то частичный порядок называется линейным, а множество А называется линейно упорядоченным или цепью.

Пример.

цепь.

Пример.

, где | – отношение делимости, т. е. –делится на.

Рефлексивность:

Антисимметричность:

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

2 и 3 не сравнимы.

–частично упорядоченное множество.

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

Пусть – частично упорядоченное множество.

Рассмотрим и введём на множестве векторов отношение на .

Это отношение рефлексивно, антисимметрично и транзитивно является частичным порядком.

Пример.

() – цепь.

() – не цепь.

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

Пусть есть частично упорядоченное множество

называется доминирующим над , если.

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

Диаграмма частично упорядоченного множества – граф, в котором вершины соответствуют элементам множества А.

вершина находится выше вершины.

и соединены ребром.

Пример.

Множество делителей числа

Лекция № 7. Отношение частичного порядка.

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

Пусть – частично упорядоченное множество.

Элемент называется верхней (нижней) гранью множества В, если.

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

Множество всех верхних (нижних) граней В называется верхним (нижним) конусом множества В и обозначается .

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

Элемент называется максимальным (минимальным) в множестве В, если не.

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

Элемент называется максимумом (минимумом) в множестве В, если он максимальный (минимальный) и принадлежит верхнему (нижнему) конусу.

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

Точная верхняя грань .

Точная нижняя грань

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

Если , тоM – единственный максимальный элемент множества В.

Если , тоm – единственный минимальный элемент множества В.



1.

2. Предположим . Т. к.не является максимальным.



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

Если есть , то.

Если есть , то.

1. . Покажем, что, если это не так, то, тогдамаксимальный элемент В (получили противоречие) .

2. Покажем, что , т. е.. Если это не так, то, но т. к.(получили противоречие) .