Information Technology Reference
In-Depth Information
The Binary Case
When
q
= 0, a state description (1) cannot be expressed as a conjunction of
sentences each involving only one constant as it is in the unary case with atoms,
but it is possible to define
binary atoms
and proceed similarly
3
.
For this purpose, we define
ʲ
1
(
x
)
,...,ʲ
2
p
+
q
(
x
) to be the formulae
p
q
i
=1
±
i
=1
±
R
i
(
x
)
∧
Q
i
(
x, x
)
and
ʴ
1
(
x, y
)
,...,ʴ
2
q
(
x, y
) to be the formulae
i
=1
±
Q
i
(
x, y
)
.
We define the
binary atoms to be the formulae
ʳ
[
k,c,h,d
]
(
x, y
)=
ʲ
k
(
x
)
∧ ʲ
c
(
y
)
∧ ʴ
h
(
x, y
)
∧ ʴ
d
(
y,x
)
1
,...,
2
p
+
q
1
,...,
2
q
where
k,c
.
The state description (1) can then be also expressed as
∈{
}
and
h, d
∈{
}
m
ʲ
v
j
(
a
j
)
∧
ʳ
h
j,l
(
a
j
,a
l
)
j
=1
1
≤
j<l
≤
m
where
v
j
∈{
.
There
is some redundancy in this expression but it is convenient for what follows.
We also need the concept of a partial state description which is a sentence
ʔ
(
a
1
,...,a
m
)oftheform
1
,...,
2
p
+
q
}
and
h
j,l
∈{
[
v
j
,v
l
,h,d
]:
h, d
∈{
1
,...,
2
q
}}
m
ʲ
v
j
(
a
j
)
∧
ʳ
h
j,l
(
a
j
,a
l
)
(2)
j
=1
j,l∈A
where
v
j
and
h
j,l
are as above and
A
.
Clearly every state description is a partial state description. We define the
signature of the (partial) state description (2) to be
mn
such that
ↆ{
j, l
:1
≤
j<l
≤
m
}
m
=
m
1
,...,m
2
p
+
q
,
where
m
k
is the number of
j ∈{
1
,...,m}
such that
v
j
=
k
and
1
,...,
2
p
+
q
1
,...,
2
q
n
=
n
[
k,c,h,d
]
:
k,c
∈{
}
and
h, d
∈{
}
,
where
n
[
k,c,h,d
]
is the number of
j, l
∈
A
such that
h
j,l
=[
k,c,h,d
]or
h
j,l
=[
c, k, d, h
]
.
(3)
The atoms
ʳ
[
k,c,h,d
]
and
ʳ
[
c,k,d,h
]
are counted together because
ʳ
[
k,c,h,d
]
(
x, y
)=
ʳ
[
c,k,d,h
]
(
y,x
)
(4)
3
The concepts and results in this section come from [9].
