Introductie-Predikatenlogica-PDL-Deel-IVb-H-11

Cursus / training:

Methode Formele Logica

^©

11. Substitutie in de Predikaten-logica.

11.1. **Algemene substitutie, c.q. interpretatie.**

Substitutie: Vervanging van een expressie (formule, predicatie of term).
Bijv.: vervang x door y; oftewel, vul y in op de plaats van x.
Ter ontwarring van de terminologie, let op het verschil in gebruik van de term:
'Substitueren (vervangen) van x door y'; oftewel:
'Substitueren (invullen) van y voor x' (Van Dale, 2018).

Substitutie wordt toegepast op minstens één expressie,
bijv. propositie, (complexe) Disjunctie, clause, predicatie, term, en/of verzameling expressies.

(1)

Notaties.

E_k : expressie (term/ formule).
F_h : formule.
v_i : variabele.

t

_j : term.

E₁,

T

: target element, 'slot' (voorwaarde, of voorwaardelijke conclusie).
Datgene wat vervangen wordt.
E₂,

r

: referent, 'filler' (feit, bijv. constante).
Datgene wat geïntroduceerd ('ingevoerd') en geabsorbeerd wordt.

(2)

Substitutie-operatie.

'E₀ ·[E₁

:=

E₂]'

Binnen een expressie E₀ wordt elk voorkomen van E₁ als target vervangen door E₂ als referent.

E₁ ·[v1

:=

t

1] :

Binnen een expressie E₁ wordt elke aanwezige variabele v₁ als target vervangen door term

t

₁ als referent.

(3)

Relevante Wetten/Regels m.b.t. substitutie:

Substitutie is in wezen gebaseerd op ketenredenering op basis van transitiviteit.

Bijv.: {(E₀

=

'(A1

B1)')

((E₁

=

'A1')

((E₂

=

{ A2 })

((E₂

E₁)

(A2

_(s) B1) ) ) ) }.
Bijv.: {(E₀

=

'(A1

B1)')

((E₁

=

'B1')

((E₂

=

{ B2 })

((E₁

E₂)

(A1

_(s) B2) ) ) ) }.

Substitutiestelling.

(2.1)

Substitutie onder parafrase.

D.i. Equivalentie, synonymie.

Equivalentie:
(E₁ ≡ E₂)

(F ·[E₃

:=

E₁] ≡ F ·[E₃

:=

E₂]).
Synonymie.
(

t

₁

=

_(r)

t

₂)

(F ·[

t

₃

:=

t

₁] ≡ F ·[

t

₃

:=

t

₂]).

Bijv. (PPL): (A1

C1);

(A1

A2);

·[A1

:=

A2];

_(s) (A2

C1) : is geldig.
Bijv. (PPL,Skl): {A₁(

t

₁)

C₁(

t

₁))}

(

t

₁

=

_(r)

t

₂);

·[

t

₁

:=

t

₂];

_(s) (A₁(

t

₂)

C₁(

t

₂)) : is geldig.

(2.2)

Substitutie onder degressie.

(E₁

E₂)

(F ·[E₃

:=

E₁]

F ·[E₃

:=

E₂]).
(

R

^*(

t

₂)

R

^*(

t

₁) );

(F ·[

t

₃

:=

t

₁]

F ·[

t

₃

:=

t

₂]).

Bijv. (PPL): (A1

(C1

C2));

((C1

C2)

C3);

·[(C1

C2)

:=

C3];

_(s) (A1

C3) : is geldig.
Bijv. (PDL,Skl): {A₁(v₁)

C₁(v ₁))}

(

R

^*(

c

₁)

R

^*(v₁) );

·[v₁

:=

c

₁];

_(s) (A₁(

c

₁)

C₁(

c

₁)) : is geldig.

11.2. Substitutie van argumenten.

Toekenning van termen aan variabelen (argumenten van functies en predicaten).

(1)
(2)

Substitueerbaarheid.

Uitdrukking E₁ is substitueerbaar
binnen een andere uitdrukking E₀ (bijv. een bewering of redenering (formule) F):
desda er geldt: E₁ kan een uitdrukking E₂ binnen E₀ vervangen.

Gegeven: E₁ ·[

t

₁

:=

t

₂];

(a)

Randvoorwaarden voor relevantie van een substitutie:

Syntactische welgevormdheid.
(a1)

¬(E₁

PPL

^* ) : anders is de substitutie loos.
(a2)

(

t

₁

E₁ ) : anders is de substitutie loos.
(a3)

¬(

Code

(

t

₁)

=

Code

(

t

₂) ); c.q. ¬(

t

₁

=

_(c)

t

₂ ) : anders is de substitutie loos.
(a4)

(

t

₂

TERM^*).

(b)

Randvoorwaarden voor validiteit van een substitutie:

Semantische validiteit.
(b1)

(

t

₁

(VAR^*

CNS^* _d

FNC^*_d

FNC^*_s) )

¬(

t

₁

CNS ^*_s) ) : anders volgt bijv. prefix conflict.
(b2)

(

R

^*(

t

₂)

R

^*(

t

₁) ) : Het referentiegebied van

t

₁ is gelijk aan of subsumeert dat van

t

₂.
(b3)

¬(

t

₁

t

₂) : anders volgt circulariteit.
(b4) Geen kwantor conflict in de interne context (binnen de omvattende expressie).

(¬(FREE(E₁,

t

₁ )

((

t

₂

VAR^* )

FREE(E₁,

t

₂ ) ) ) ).

Bijv.: (

y (({F[x ]}

¬(y

VAR^*(F ) ) ) ≡ (F ·[x

:=

y])) ).
Bijv.: (

y (({F[x ]}

¬(y

VAR^*(F ) ) ) ≡ (F ·[x

:=

y])) ).

(b5) Geen kwantor conflict in de externe context (buiten de omvattende expressie).
Generalisatie van vorige:

(

i (¬(FREE(E[i],

t

₁ )

((

t

₂

VAR^* )

(

j (E[i]

E[j] )

FREE(E[j],

t

₂ ) )_j ) ) )_i ).

(4)

Soorten arbitraire ('ad hoc') interpretaties:

Van variabelen (als termen in argumentenlijsten).

(4.1)

Variabele-hernoeming (renaming).

C.q. herbenoeming/ hercodering; hernummering/ her-indexering (permutatie, c.q. representatie) van een objectvariabele.
Transformaties onder parafrase en/of degressie.
Met logische object-variabelen: {x,y,z, w,v,u, ..}.

'·[v₁

:=

v₂]' : Herbenoeming van een variabele.

Vervanging in de voorgaande expressie van elk voorkomen van v₁ door v₂.

(4.2)

Argument-instantiatie.

Via Domeininterpretatie. Verlaging van de generaliteit, d.i. kwantiteit van een term.
Is dus een vorm van conjuncte reductie. Dus met degressie.
Met logische functies: éénplaatsig, constanten, bijv.: {

a

b

c

d

e

, ..}; meerplaatsig, functies, bijv.: {

f

g

h

, ..}.

(4.3)

Argumenten-unificatie.

Bewerkstelligen van uniformiteit van (minstens) twee termen.
Wordt bereikt via minstens één substitutie, m.n. variabele-hernoeming (4.1) of conjuncte reductie c.q. instantiatie (4.2).

(4.4)

Argumenten-differentiatie.

Bewerkstelligen van pluriformiteit van (minstens) twee termen.
Wordt bereikt via minstens één substitutie, m.n. variabele-hernoeming (4.1) of disjuncte expansie (geldig) of conjuncte expansie (ongeldig).

11.3. **Voorwaarden voor variabele-hernoeming (renaming).**

Voorwaarde is synonymie: het referentieel gebied van beide variabelen in het domein is identiek.

(E·[v₁

:=

v₂] )

(

R

^*(v₁)

=

R

^*(v₂) ).

Als v₂ nog niet in de desbetreffende expressie E voorkwam, dan blijft het referentieel bereik van E gelijk, en is het resultaat een variant, d.i. een alfabetische variant , van de oorspronkelijke expressie.

=

_(v)' : identiteit (synonymie) van termen onder variabelen-hernoeming.
'≡_(v)' : Equivalentie (parafrase) van proposities onder variabelen-hernoeming.

Regels t.b.v. substitutie via renaming.

(1a) Regel t.b.v. substitutie van termen/ predicaat-argumenten, via renaming.

{

y ((x

=

_(r) y)

(

h (¬(y

t

_[h] )

(

t

_[h] [(..,x,..)]·[x

:=

=

_(v)

t

_[h][(..,y,..)] ) )_h) )_y,_x }.

(1b) Regel t.b.v. substitutie van predicaties/ literalen, via renaming.

{

y ((x

=

_(r) y)

(

h (¬(y

F_{[
h]} )

(F_[h][(..,x ,..)]·[x

:=

y] ≡_(v) F_[h] [(..,y,..)] ) )_h) )_y,_x }.

11.4. Herbenoeming van variabelen in predikaties.

Eenvoudige vorm: afleiding met parafrase, met behoud van structuur (isomorfie, bijectie).
D.i. behoud van argument-volgorde èn argumenten-diversiteit.
Dus zonder variabelen unificatie of differentiatie.
Her-indexering, permutatie. Levert een variant.
In kwantorvrije, universele predicaties.

(1)

Renaming; Binnen één Literaal.

(1a)

Renaming; Binnen één Literaal; Met éénplaatsig predicaat.

In Literaal.

Bijv.: {A(x)}

·[x

:=

y];

_(v) A(y).

(1b)

Renaming; Binnen één Literaal; Met meerplaatsig predicaat.

Bijv.: {A(x,x)}

·[x

:=

y];

_(v) A(y,y).
Bijv.: {A(x,x,y)}

·[x

:=

z;y:=w];

_(v) A(z,z ,w).

Bijv.: {A(x,

f

(x))}

·[x

:=

y];

_(v) A(y,

f

(y)).
Bijv.: {A(x,y,

f

(z))}

:=

w;y:=v;z:=u];

_(v) {A(w, v,

f

(u))}.

Renaming; met plaatsverwisseling.

Bijv.: {A(x,y)}

·[x

:=

z;y:=x;z:=y];

_(v) A(y,x).
Bijv.: {A(x,y)}

·[x

:=

z;y:=x;z:=y];

_(v) A(y,x).
Bijv.: {A(x,x,y)}

·[x

:=

z;y:=x;z:=y];

_(v) A(y, y,x).
Bijv.: {A(x,

f

(y))}

·[x

:=

z;y:=x;z:=y];

_(v) A(y,

f

(x)).

Renaming; met unificatie - zonder instantiatie.

Bijv.: {A(x,y)} : A(z,x); L1·[y

:=

x]; L2·[z

:=

_{(
parafrase
)}_(v) A(x,x).

(2)

Renaming; In Conjunctie.

(2a)

Renaming; In Conjunctie; Met éénplaatsig predicaat.

Bijv.: {A(x)

B(x)}

·[x

:=

y];

_(v) (A(y)

B(y)) : geldig.

Indirecte herbenoeming, In Conjunctie (zonder (impliciet) argument-differentiatie):

Bijv.: {A(x)

B(y)}

·[x

:=

z;y:=x;z:=y];

_{(
v)} (A(y)

B(x)).

(3)

Renaming; In Disjunctie.

(3a)

Renaming; In Disjunctie; Met éénplaatsig predicaat.

Bijv.: {A(x)

B(x)}

·[x

:=

y];

_(v) (A(y)

B(y)) : geldig.

Indirecte herbenoeming, In Disjunctie (zonder (impliciet) argument-differentiatie):

Bijv.: {A(x)

B(y)}

·[x

:=

z;y:=x;z:=y];

_{(
v)} (A(y)

B(x)).

(4)

Renaming; In Implicatie.

Bijv.: {A₁(v₁)

C₁(v₁))} ·[v₁

:=

v₂];

_(v) (A₁( v₂)

C₁(v₂)) : is geldig.