[t/u ]P τ |
= P [t/u ]τ | |
[t/u ]τ 1 Rτ 2 |
= [t/u ]τ 1 R[t∕u ]τ 2 | |
[t/u](τ 1 is τ2 ) |
= [t/u]τ 1 is [t/u]τ2 | |
[t/u ]not Φ |
= not [t/u]Φ | |
[t/u ](Φ or Ψ) |
= [t/u ]Φ or [t/u ]Ψ | |
[t/u](φ ⇒ ψ) |
= [t/u]φ ⇒ [t/u]Ψ |
if u ∈∕ adr (Φ) |
[t/u](φ ⇒ ψ) |
= [t/u]φ ⇒ Ψ |
if u ∈ adr (Φ) |
[t∕u][~u | γ1, . . . ,γm] |
= [~u | [t∕u]γ1 , . . . , [t∕u]γm] |
if u ∈∕ {~u} |
[t∕u][~u | γ1, . . . ,γm] |
= [~u | γ1 , . . . , γm] |
if u ∈ {~u} |
[t∕u](Φ; Ψ) |
= [t∕u]Φ; [t∕u]Ψ |
if u ∈∕ adr(Φ) |
[t∕u](Φ; Ψ) |
= [t∕u]Φ; Ψ |
if u ∈ adr(Φ) |
The next definition gives our translation function ↑ from boxes and condi-
tions to first-order formulae. The variable x that is appearing in the sixth
and eighth clauses is supposed to be fresh in both cases, i.e. it is defined to
be the first variable in some fixed ordering that does not occur (at all) in
Φ or in Ψ. Note that the sequencing operation ; is associative: Φ; (Ψ; Ξ) is
equivalent with (Φ; Ψ); Ξ for all Φ, Ψ and Ξ. This means that we may assume
that all boxes are either of the form [~u | ~γ]; Φ or of the form [~u | ~γ]. We shall
use the form [~u | ~γ]; Φ to cover both cases, thus allowing the possibility that
Φ is empty. If Φ is empty, Φ ⇒ Ψ denotes Ψ.
(P τ )t = P (τ )t
(τ 1 Rτ 2 )t = R(τ 1 )t(τ 2 )t
(τ 1 is τ2)t = (τ 1 )t = (τ2)t
(not Φ)t = — (Φ)t
(φ or Ψ)t = Φt ∨ Ψt
(([u~ | ~]; Φ) ⇒ Ψ)t = ∀x([x∕u](([~ | ~]5Φ) ⇒ Ψ))t
(([ | γι,...,Ym]5Φ) ⇒ Ψ)t = (7ιt ∧ ... ∧ .) → (Φ ⇒ Ψ)t
([u~u | ~γ]; Φ)t = ∃x([x∕u]([~u | ~γ]; Φ))t
([ | γ1, . . . , γm]; Φ)t = γ1t ∧ . . . ∧γmt ∧ Φt
By way of example, the reader may verify that the function f sends (14) to
(15).
(14) [ | [u1 u2 | man u1 , woman u2, u1 bores u2] ⇒ [ | u2 ignores u1]]
(15) ∀x1 x2 ((man(x 1 ) ∧ woman(x2) ∧ bores (x 1 )(x2)) → ignores (x 2)(x 1))
It is clear that the function f is algorithmic: at each stage in the reduction of
a box or condition it is determined what step should be taken. The following
12
More intriguing information
1. An Investigation of transience upon mothers of primary-aged children and their school2. Comparative study of hatching rates of African catfish (Clarias gariepinus Burchell 1822) eggs on different substrates
3. What Lessons for Economic Development Can We Draw from the Champagne Fairs?
4. Imperfect competition and congestion in the City
5. The name is absent
6. IMPLICATIONS OF CHANGING AID PROGRAMS TO U.S. AGRICULTURE
7. Qualifying Recital: Lisa Carol Hardaway, flute
8. Education as a Moral Concept
9. Environmental Regulation, Market Power and Price Discrimination in the Agricultural Chemical Industry
10. The name is absent