Лекции по СЯП, страница 4

= < |[b]| σ  |[S; while b do S od]| σ, |[skip]| σ >

= < |[b]|σ  |[while b do S od]| |[S]| σ, σ >

= |[while b do S od]| σ.

2) Программы

P: if b₁ and b₂ then S₁ else S₂

Q: if b₁ then (if b₂ then S₁ else S₂) else S₂

эквивалентны.

В самом деле,

|[P]| = |[if b₁ and b₂ then S₁ else S₂]| σ

= < |[ b₁ and b₂ ]| σ  |[S]| σ,| [ S2]| σ >

= < |[ b₁ ]| σ |[b₂ ]| σ  |[S]| σ,| [ S₂]| σ ,

|[Q]| = |[if b₁ then (if b₂ then S₁ else S₂) else S₂]|

= < |[ b₁|] σ  |[ if b₂ then S₁ else S₂]| σ, |[ S₂]| σ >

= < |[ b₁|] σ  < |[ b₂|] σ  |[S₁]| σ, |[ S₂]| σ >

= < |[ b₁ and b₂ ]| σ  |[S]| σ,| [ S2]| σ >.

Таким образом, |[P]| = |[Q].|

2. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ

МНОЖЕСТВА И РЕШЕТКИ

Семантика рекурсивных программ использует понятия и результаты теории частично упорядоченных множеств.

Определение. Частично упорядоченным множеством (ч.у.м.) называется множество А вместе с бинарным отношением , удовлетворяющим условиям:

(рефлексивность): х х

(антисимметричность): х у, у х х=у

(транзитивность): x y, y z x z

для всех x,y,z A.

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

Утверждение 2. Пусть А – ч.у.м. и Х А. Элемент с А (d A) называется верхней (нижней) гранью для Х, если х с (x d) для всех х Х.

Если верхняя грань с (нижняя грань d) принадлежит Х, то с (соответственно d) называется наибольшим (наименьшим) элементом для Х. В этом случае используются обозначения:

с = max X и d = min X.

Определения. Пусть Х А. Рассмотрим множества

Y = {y | y – верхняя грань для Х },

Z = {z | z – нижняя грань для Х }.

Если множество Y (множество Z) имеет наименьший (наибольший) элемент, то этот элемент называется супремумом (инфимумом) для Х и обозначается sup X (соответственно, inf X). Таким образом,

sup X = min Y = min{y | y – верхняя грань для Х },

inf X = max Z = max{z | z – нижняя грань для Х }.

Элементы sup X и inf X называются, соответственно, наименьшей верхней гранью и наибольшей верхней гранью для Х.

Очевидно, что справедливы соотношения:

sup{a} = a, inf{a} = a;

sup{a,b} = b и inf{a,b} = a, если a b.

Вместо sup{а,b} и inf{a,b} можно также писать a b и a b.

Z₁ = {u | u – верхняя грань для X},

Z₂ = {u | u – верхняя грань для Y}.

Тогда sup X = min Z₁ и sup Y = min Z₂

Утверждение 1. Если существуют sup{a,b}, sup{b,c}, sup{a,b,c}, то

sup{a, sup{b,c}} = sup{sup{a,b},c}} = sup{a,b,c},

inf{a, sup{b,c}} = inf{inf{a,b},c}}} = inf{a,b,c}.

Другими словами, операции sup{x,y} inf{x,y} ассоциативны.

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

sup{a,b,c} = sup{{a} {b,c}} = sup{sup{a}, sup{b,c}}

= sup{a, sup{b,c}}.

sup{a,b,c} = sup({a,b} {c}} = sup{sup{a,b}, sup{c}}

= sup{sup{a,b},c}.

Двойственным образом получаем соотношения для инфимумов.

Ч.т.д.

Определения. Ч.у.м. А называется решеткой, если для каждого его непустого конечного множества Х А существуют sup X и inf X. Если это верного для любых множеств Х, то решетка А называется полной.

Супремум пустого множества является наименьшим элементом ч.у.м., а инфимум пустого множества – наибольшим элементом:

sup =_┴, inf = T. В самом деле,

sup = min{x | x – верхняя грань для },

x – верхняя грань для ( y ) x y y (y → x y).

Но так как y ложно, то y (y → x y) истинно. Следовательно, любой элемент х является верхней гранью для и, значит, sup =_┴ . Аналогично получаем inf = T.

Замечание. Решетка, содержащая наименьший и наибольший элемент называется ограниченной. Таким образом, ограниченная решетка – это ч.у.м., в котором любое конечное множество имеет супремум и инфимум. В дальнейшем мы предполагаем, что рассматриваемые решетки являются ограниченными (если не сказано явно, что решетка не ограничена).

В определении решетки можно рассматривать супремумы и инфимумы только двуэлементных множеств. Обычно обозначают

x y = inf{x,y} и x y = sup{x,y}.

В самом деле,

sup{a₁,a₂,…,a_n} = sup{a₁, sup{a₂, sup{a₃,…sup{a_n–1,a_n}…}}

= (a₁ (a₂ (… (a_n–1 a_n)…))).

Ч.у.м. А называется верхней (нижней) полурешеткой, если для каждого его конечного множества Х А существуют sup X (соответственно, inf X). Если это верного для любых множеств Х, то полурешетка А называется полной.если А имеет наибольший (наименьший) элемент и любые два элемента А имеют супремум (инфимум). Ч.у.м. А является верхней (нижней) полурешеткой, если А имеет наибольший (наименьший) элемент и любые два элемента А имеют супремум (инфимум).

Понятие решетки можно определить в алгебраических терминах.

Определение. Решеткой называют алгебру <A; _┴, T, , > с константами _┴ и T и двумя бинарными операциями, удовлетворяющими соотношениям:

(идемпотентность): x x = x и x x =x,

(коммутативность): х у = у х и х у = у х,

(ассоциативность): (x y) z = x (y z) и (x y) z = x (y z),

(поглощение): х (х у) = х и х (х у) = х,

(свойства _┴ и T) : х T = х, х T = T, х _┴ = _┴, х _┴ = х.

Утверждение 3. Два определения понятия решетки эквивалентны.

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

А) Первое определение Второе определение.

Идемпотентность и коммутативность очевидны. Ассоциативность была уже доказана. Поглощение следует из того, что x y x и x x y.

Б) Второе определение Первое определение.

Отношение порядка в множестве А можно определить двумя способами: x y _df x y = y или x y _df x y = х. На самом деле мы получаем одно и то же отношение порядка, так как

x y = y  x y = х.

В самом деле,

x y = y х (х у) = х у (поглощение) х = х у,

x y = х у (х у) = у х (поглощение) у = х у,

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

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

х х, так как х х = х

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

х у, у х х у = у, у х = х (коммутативность) у = х.

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

x y, y z x y = y, y z = z (x y) z = z (ассоциативность) x (y z) = z x z = z x z

Докажем теперь, что sup{x,y} = x y.

х sup{x,y}, у sup{x,y}

х sup{x,y} = sup{x,y}, у sup{x,y} = sup{x,y}

(х sup{x,y}) (у sup{x,y}) = sup{x,y} sup{x,y}

(х y) sup{x,y} = sup{x,y} х y sup{x,y}.

Таким образом, х y sup{x,y}.

x (x y) = x, y (x y) = y x x y, y x y sup{x,y} x y.

Таким образом, sup{x,y} x y.

Ч.т.д.

Утверждение 4. Если А и В – решетки, то их декартово произведение А В также является решеткой. Если А и В – полные решетки, то А В – полная решетка.

Доказательство. Если А и В – решетки в смысле первого определения (т.е. рассматриваемые как ч.у.м.), то декартово произведение решеток есть множество А В с порядком

(х,у) (х’,y’) _df x x’ и y y’.

Пусть Х – произвольное подмножество множества А В. Положим X₁ = {x A | ( y) (x,y) X} и X₂ = {у A | ( х) (x,y) X}. Ясно, что для любого элемента с = (a,b) А В имеет место:

с – верхняя грань для Х a – верхняя грань для X₁ и

b – верхняя грань для X₂.

Отсюда следует, что sup X = (sup X₁) (sup X₁). Аналогично имеем inf X = (inf X₁) (inf X₁).

Если для решетки взять второе определения (т.е. рассматривать ее как алгебру), то в декартовом произведении А В определяем

(х,у) (х’,y’) =_df (х х’, у y’) и (х,у) (х’,y’) =_df (х х’, у y’).

Эти два определения декартова произведения эквивалентны, так как (ввиду независимости компонент пары) имеет место:

(х,у) (х’,y’) (х,у) [(х,у) (х’,y’)] = (х,у)

(х,у) [(х,у) (х’,y’)] = (х,у)

Ясно, что (ввиду независимости компонент пары) в алгебре <А В; , > для операций и выполняются соотношения идемпотентности, коммутативности, ассоциативности и поглощения. Поэтому эта алгебра является решеткой.

Ч.т.д.

Пример. Рассмотрим тривиальную решетку В, состоящую из двух элементов _┴ и T с отношение порядка _┴ < T. Диаграммы Хассе для декартовых степеней В² = В В и В⁴ = В² В² показаны на рис.

TT

В² _┴T T_┴

_┴┴

TT

aT Ta Tb b T

В⁴ aa ab _┴T T_┴ ba bb

a_{┴ ┴}a b_{┴ ┴}b

_┴┴

Рис. 5

Определение. Пусть А и В – ч.у.м. Функция f : A B называется монотонной, если для любых х, у А.

x y f(x) f(y).

Примеры: 1) В множестве N = {0,1,2,…} зададим порядок:

х у _df х – делитель у.

Функция f(x) = 2x является монотонной:

х у х – делитель у 2х – делитель 2у 2х 2у.

Функция g(x) = x+2 не является монотонной: 3 9, но не верно, что 3+2 9+1.

Функция h(x,y) = xy, h : N² N, является монотонной:

(x,x’) (y,y’) x y, x’ y’ x – делитель y, x’ – делитель y’

xy – делитель x’y’ ху x’y’, т.е. h(x,y) h(x’,y’).

2) Пусть A – произвольное множество и P(A) = {X | X A} – множество всех подмножеств множества А. В P(A) имеется естественный порядок – теоретико-множественное включение.

Функция f (X,Y) = X Y, f : P(A) P(A) P(A) монотонна:

(X,Y) (X’,Y’) X X’, Y Y’ X X’ Y Y’ f (X,Y) f (X,Y).

Функция f (X,Y) = X Y монотонна.

Функция f (X,Y) = X \ Y не монотонна.

1. Пусть А – произвольное ч.у.м. Следующие функции моно-

тонны:

• f (x) = x, f : A A (тождественная функция);

• f (x₁,x₂,…,x_n) = a , f : Aⁿ A (постоянная функция);

• f (x₁,x₂,…,x_n) = x_i , f : Aⁿ A (проекция);