95998

Relacją liniowego porządku na zbiorze A nazywamy relację /?, która posiada następujące własności:

—    jest relację częściowego porządku, tzn jest zwrotna, przechodnia i antysymetryczna,

—    spełnia warunek spójności:

(Va,be A) ( aRb v bRa)

Przykładem relacji Urnowego porządku jest relacja „mniejszy lub równy" (<) określona na zbior ze nieujemnych liczb całkowitych.

Domknięcia relacji:

k-ty stopień /?* relacji R na zbiorze A określamy następująco: aR°b <=> a=b aR'b «=> aRb

aR^kb <=> (3ceA)(aRc a cR^klb) czyli np.

aR^:b <=> (3ceA)(aRc a cRb)

aR³b <=> (3cieA)(aRcr a cR‘b) <=> (3ci,C2£ A) (aRci a C1RC2 a c_:Rb) Przykład:

R c NxN

N = {0,1,2,...} - zbiór liczb naturalnych (z zerem) nRm <-> n = m+2

nR^n <=> n = pt-2 a p = m+2 <=> n = m+4 nR³m <=> n = pi+2 a pi=p2+2 a p_; = in+2 « n = nr+6 (8, 6) e R (8, 4) e R^:

(8, 2) e R³

Przechodnie domkiuęcie R' relacji R na zbiorze ,4 definiujemy następująco: aR⁺b <=> (3i>l)(aR'b)

Pizechodnie i zwrotne domknięcie i?' relacji R na zbiorze A defiruujemy następująco: aR'b <=> (3i>0) (aR'b )

Inna (rekurencyjna) definicja domknięcia przechodniego/?*

(1)    aRb =»aR⁺b

(2)    (aR*b a bR c) => aR*c

(3)    nic iruiego nie należy do/?* poza tym, co wynika z punktów (1) i (2). Niektóre użyteczne zależności:

aR b <=> aR*b v a=b

R* = R* u R°

R* = U R'

121

R* = IJ R‘

i20