Information Technology Reference
In-Depth Information
From
⊛
⊝
h,d
⊞
⊠
=1
w
ʳ
[
k,k,h,d
]
(
a
1
,a
3
)
|
ʲ
k
(
a
1
)
∧
ʲ
k
(
a
2
)
∧
ʲ
k
(
a
3
)
∧
ʳ
[
k,k,h
0
,d
0
]
(
a
1
,a
2
)
with
h
0
=
d
0
and
h
0
=
d
0
respectively we obtain
2
g
(1
,
1) + 2
q
h
(0
,
1) + (2
2
q
−
2
q
−
2)
g
(0
,
1) = 1
(16)
and
h
(1
,
1) + (2
q
1)
h
(0
,
1) + (2
2
q
2
q
)
g
(0
,
1) = 1
.
−
−
(17)
Using (12), (13) and (15) this yields
1
2
+
ʽʾ
1+
ʽ
ʽˇ
1+
ʽ
,
(0
,
1) =
ʽʾ
1+
ʽ
,
(1
,
1) =
h
(0
,
1) =
so (14) holds also for
n
=1.
Now assume (14) holds for
n
. For any
c, e, f
∈
N
with
c
+
e
+
f
=
n
we find
by considering e.g.
w
ʳ
[
k,k,h
1
,d
1
]
(
a
2
,a
3
)
ʔ
∧
ʳ
[
k,k,h
2
,d
2
]
(
a
2
,a
4
)
|
where
ʔ
is the conjunction of
n
+1
j
=1
ʲ
k
(
a
j
)and
c
+1
c
+
e
+1
n
+1
ʳ
[
k,k,h
1
,d
1
]
(
a
1
,a
j
)
∧
ʳ
[
k,k,h
2
,d
2
]
(
a
1
,a
j
)
∧
ʳ
[
k,k,h
3
,d
3
]
(
a
1
,a
j
)
j
=2
j
=
c
+2
j
=
c
+
e
+2
by taking distinct pairs
h
1
,d
1
,
h
2
,d
2
,
h
3
,d
3
with (
h
1
=
d
1
and
h
2
=
d
2
)or
(
h
1
=
d
1
and
h
2
=
d
2
) respectively that
h
(
c, n
+1)
h
(
e,n
)=
h
(
e,n
+1)
h
(
c, n
)
,
(18)
h
(
c, n
+1)
g
(
e,n
)=
g
(
e,n
+1)
h
(
c, n
)
.
(19)
With
c
running from 1 to
n
and
e
=0(18)yields
h
(
c, n
+1)=
h
(
c, n
)
h
(0
,n
)
h
(0
,n
+1)
(
c
∈{
1
...n
}
)
(20)
and hence by the inductive hypothesis we have
h
(
c, n
+1)=
c
+
ˇʽ
ˇʽ
h
(0
,n
+1)
(
c
∈{
1
...n
}
)
.
(21)
Considering 0
≤
e,f
≤
n
+1with
e
+
f
=
n
+1 and taking distinct pairs
h
1
,d
1
,
h
2
,d
2
with (
h
1
=
d
1
and
h
2
=
d
2
) we find that
⊛
⊝
h,d
⊞
e
+
f
+1
n
+2
e
+1
⊠
w
ʳ
[
k,k,h,d
]
ʲ
k
(
a
j
)
∧
ʳ
[
k,k,h
1
,d
1
]
(
a
1
,a
j
)
∧
ʳ
[
k,k,h
2
,d
2
]
(
a
1
,a
j
)
j
=1
j
=2
j
=
e
+2