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.


Ek : expressie (term/ formule).
Fh : formule.
vi : variabele.

t

j : term.
E1,

T

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

r

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

(2)

Substitutie-operatie.


'E0 ·[E1

:=

E2]'
Binnen een expressie E0 wordt elk voorkomen van E1 als target vervangen door E2 als referent.
E1 ·[v1

:=

t

1] :
Binnen een expressie E1 wordt elke aanwezige variabele v1 als target vervangen door term

t

1 als referent.

(3)

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


Substitutie is in wezen gebaseerd op ketenredenering op basis van transitiviteit.
Bijv.: {(E0

=

'(A1 B1)') ((E1

=

'A1') ((E2

=

{ A2 }) ((E2 E 1) (A2 (s) B 1) ) ) ) }.
Bijv.: {(E0

=

'(A1 B1)') ((E1

=

'B1') ((E2

=

{ B2 }) ((E1 E 2) (A1 (s) B 2) ) ) ) }.

Substitutiestelling.


(2.1)

Substitutie onder parafrase.


D.i. Equivalentie, synonymie.
Equivalentie:
(E1 ≡ E2) (F ·[E3

:=

E 1] ≡ F ·[E3

:=

E2]).
Synonymie.
(

t

1

=

(r)

t

2) (F ·[

t

3

:=

t

1 ] ≡ F ·[

t

3

:=

t

2]).
Bijv. (PPL): (A1 C1); (A1 A2); ·[A1

:=

A2];
 (s) (A2 C1) : is geldig.
Bijv. (PPL,Skl): {A1(

t

1) C1(

t

1))} (

t

1

=

(r)

t

2); ·[

t

1

:=

t

2];
  (s) (A1(

t

2) C1(

t

2)) : is geldig.

(2.2)

Substitutie onder degressie.


(E1 E2) (F ·[E3

:=

E1] F ·[E3

:=

E 2]).
(

R

*(

t

2)

R

*(

t

1) ); (F ·[

t

3

:=

t

1] F ·[

t

3

:=

t

2]).
Bijv. (PPL): (A1 (C1 C2)); ((C1 C2) C3); ·[(C1 C2)

:=

C3];
 (s) (A1 C3) : is geldig.
Bijv. (PDL,Skl): {A1(v1) C1(v1 ))} (

R

*(

c

1)

R

*(v1) ); ·[v1

:=

c

1];
 (s) (A1(

c

1 ) C1(

c

1)) : is geldig.

11.2.

 

Substitutie van argumenten.


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

(1)
(2)

Substitueerbaarheid.


Uitdrukking E1 is substitueerbaar
binnen een andere uitdrukking E0 (bijv. een bewering of redenering (formule) F):
desda er geldt: E1 kan een uitdrukking E2 binnen E0 vervangen.
Gegeven: E1 ·[

t

1

:=

t

2];

(a)

Randvoorwaarden voor relevantie van een substitutie:


Syntactische welgevormdheid.
(a1) ¬(E1

PPL

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

t

1 E1 )
: anders is de substitutie loos.
(a3) ¬(

Code

(

t

1)

=

Code

(

t

2) ); c.q. ¬(

t

1

=

(c)

t

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

t

2 TERM*)
.

(b)

Randvoorwaarden voor validiteit van een substitutie:


Semantische validiteit.
(b1) (

t

1 (VAR* CNS*d FNC*d FNC*

s

) ) ¬(

t

1 CNS*

s

) )
: anders volgt bijv. prefix conflict.
(b2) (

R

*(

t

2 )

R

*(

t

1) )
: Het referentiegebied van

t

1 is gelijk aan of subsumeert dat van

t

2.
(b3) ¬(

t

1

t

2)
: anders volgt circulariteit.
(b4) Geen kwantor conflict in de interne context (binnen de omvattende expressie).
(¬(FREE(E1,

t

1 ) ((

t

2 VAR* ) FREE(E1,

t

2 ) ) ) ).
Bijv.: ({x F[x]} ¬(y VAR*(F) ) ) ≡ (y (F ·[x

:=

y])).
Bijv.: ({x F[x]} ¬(y VAR*(F) ) ) ≡ (y (F ·[x

:=

y])).
(b5) Geen kwantor conflict in de externe context (buiten de omvattende expressie).
Generalisatie van vorige:
(i (¬(FREE(E[i],

t

1 ) ((

t

2 VAR * ) (j (E[i] E[j] ) FREE(E[j],

t

2 ) )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, ..}.
'·[v1

:=

v2]' : Herbenoeming van een variabele.
Vervanging in de voorgaande expressie van elk voorkomen van v1 door v2.

(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·[v1

:=

v2] ) (

R

*(v1)

=

R

*(v2 ) ).
Als v2 nog niet in de desbetreffende expressie E voorkwam, dan blijft het referent ieel 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.
{x y ((x

=

(r) y)  (h (¬(y

t

[h] )  (

t

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

:=

y]

=

(v)

t

[h][(..,y,..)] ) )h) )y ,x }.
(1b) Regel t.b.v. substitutie van predicaties/ literalen, via renaming.
{x 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))}   [x

:=

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

:=

x]  (

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.: {A1(v1) C1(v1))} ·[v1

:=

v2];
 (v) (A1(v2) C1(v2)) : is geldig.

C.P. van der Velde © 2004, 2016, 2019.