R ⊆ A × A
,
A -
(A, ≥)
(A, ≥) ⊆ .
, b B
a ≥ b.
. . .
(A, ≥) ⊆ .
, b B
b ≥ a.
B,
B.
B,
B.
,
() .
,
() Sup B.
. .
:
(A, ≥) ⊆ .
,
1) a ≥ b b ∈ B
2) a ≥ b b ∈ B a ≠ a, a ≥ a.
,
() Inf B.
L = (A, ≥),
(supremum) (infimum).
. .
R
( a b A
a R b, b R a),
.
(
) ,
(A, >).
(bi ) , ( ).
ψ-
a, b ∈ M ψ(a, b) a ψ b
ψ , a, b, c ∈ M (a ψ b) ψ c = a ψ (b ψ c).
ψ , a ψ b = b ψ a
* ⊆ ψ, a, b ∈ M*
, a ψ b ∈ *
ψ ϕ , ψ ϕ, a ψ (b ϕ ) = (a ψ b) ϕ (a ψ )
. , a ∈ M a ψ e = e ψ a = a ().
z () , a ∈ M a ψ z = z ψ a = z .
^-1 ψ, ψ ^-1=
|
|
́ (. disjunctio ), ́ ́, ́ , ́ ; , , , .
́ ( . conjunctio , ) , "". : ́ "",́ ́, "".
.
Ȼ :
[1][2][3] A ( ), ( ), ( ) : 0 ( ) 1 ( ) , a, b c A :
, (A, , ) . , ,
, ,
,
( ), . .
́
.
, . , . .
, , , .
, , , , . , , .
11
(G) (V, X,?))
V n .
X .
? - , X
V.
? X.
,
.
().
Vj
Vk
?(xi) = (Vj, Vk) Vj Vk.
,
.
xi0
?((x0) = (Vj0, Vj0),
.
1.
|
|
,
.
,
.
.
2.
. ,
.
. ,
.
3.
A(m*n)
m = [V]
n = [X}-
)
Aij = {0, Vi xj, 1, Vi xj)
)
Aij = {0, Vi xj, -1, Vi - xj, 1, Vi -
xj)
.
4. ( )
B(m*m) m = [V]
Bij , (oi, oj)
, .
, , .
,
.
.
K1
K2
K3
K4
K5
, 2
, ,
.
,
.
.
, , .
, , ,
, .
, .
,
.
, , .
, ( ),
.
,
.
,
. .
, .
.
, .
.
.
,
, ,
.
, , .
, , .
.
1. , ,
.
2. , ,
.
3. ,
.
12
. ,
. .
, , ,
.
, .
.
|
|
, ,
, .
.
.
,
.
, .
.
.
xi, 2 ,
, .
, .
.
. .
,
. .
.
.
.
M N + P = 2.
P = 1
P = 1, . .
1.
M = N + 1
N + 1 N + 1 = 2 .
p = k, .
P= k+1
,
. .. , g1 (
) M .
N1 = N 1
P1 = P 1
M = M
k + 1-1 = k
g1 .
M1 + N1 + P1 = 2
M N 1 + K = 2
M N + K 1 = 2
M N + P = 2
.
1.
n <= 3*(m-2)
2.
n <= 2*(m-2)
3.
K5 .
m > 2
, 1.
N <= 3*(m-2)
10 <= 9 .
. , .
4.
K3-3 .
.
, 2.
9 <= 2*(6-2)
9 <= 8 .
, .
:
, ,
.
,
.
.
, ,
.
13
. .
.
, .
(),
, .
.
|
|
() -
-
.
,
x NOT(x).
X Not Y
Z Not X
()
( ) :
, , ,
.
. .
( ),
, , 1
,
( )
,
1.
,
.
.
,
, , -,
.
( ) ,
.
,
( ).
, , .
.
. . ,
.
(V) , V,
.
-1(V) , V,
.
.
1. A 0.
2. (), , = 1.
3. V, () (V) V,
(V), , 2.
4. , .
5. -1(V).
, .
.
.
, , ,
[pic]i = minimum. (r l )
.
1. ?1 0
Vi?i = +() ,
.
L(Vi, Vj) , Vi Vj. .
2. .
?j -?i > L(Vi, Vj) *
, ?j .
?j =?i + L(Vi, Vj) , *.
* , ,
,
.
-1() Vi1, .
?b -?i1 = L(Vi1,B)
-1(V1) V2, ?(V1) -?(V2) = L(V1, V2) ..
.
.
.
, - .
,
, .
1. .
2. , . x1 ,
.
,
. , .
.
14
()
,
,
|
|
.
( ).
,
.
( v w),
c.
S (S) w,
S.
( )
, ,
, S V
[S] <= [(S)].
.
. .
(),
, .
1. .
.
, , .
.
, .
.
,
.
, 2
( 1 , ).
1. .
2. . ,
.
3. , .
4. , .
5. , ..
,
.
6. 2.
1.
() .
.
.
A(M,N)
[V] = M
[W] = N
Aij = 1, ViWj
, Aij = 0.
[pic]
, ,
.
.
90 .
m m .
.
,
,
.
A = (aij) .
(*)
= [pic]
,
,
.
V = M, W = M
.
,
.
.
| |0 |0 |0 |0 |
|4 |1 |2 |3 |4 |
|4 |1 |4 |4 |2 |
|6 |2 |5 |6 |3 |
|6 |1 |6 |4 |4 |
1. Vi i = max .
j 0.
2. ,
Ai + Bj = Aij
,
.
3. .
, . ,
.
4. S V, [S] > (S).
.
Vi S Ai 1, wj (s)
Vj 1.
5. 2 .
15
V
M-(V) , V .
M+(V) , V .
,
1. A, M-() .
.
2. B, M+(B) .
.
3.
, .
2(1) 3(1)
1(1)
6(0)
5(5)
1(1) 4(1)
2(1)
() ,
1. (X) <= C(X), (X) .
.
.
2. V , A B
: ,
, ,
( , ).
[] = val() ,
,
, .
.
1. .
2.
.
3. . ,
, 1.
, 0.
,
Val()? Val(*)
* = maximum
S ,
, , ().
,
S, S.
K
.
K** ,
C(K**)? C(K).
( ).
.
( ).
1. .
2. g* :
g.
, g
0,
.
, (x) > 0 g*
x* x**. x* , x,
c(x*) = c(x) (x).
x** x,
c(x**) = (x).
.
3. g*
. ,
. 4.
( .? min(c(x))
).
4. g ,
:
x g ,
(x) = (x) +?
, (x) = (x) -?
5. 2 .
, A R
A, A.
, , ,
.
. R
, x∈ A (x, x) R, ,
R. , x, y ∈ A
() x, y ∈ R () y,. x ∈ R ,
.