Cursus / training:

Methode Formele Logica

©


Regels voor formulebewerkingen in de Predikaten-logica.



Herschrijfregels: Regels voor transformatie onder parafrase/ Equivalentie.



Parafrase via Syntactische verandering.

Syntactische varianten.


Syntactische verandering -
• zonder (syntactische) termreductie;
• met/zonder (syntactische) verandering van hoofdconnectief;
• zonder (semantische) verandering van hoofdconnectief;
• en zonder (semantisch) verlies van logische kracht.

III.

 

Wetten voor logische Normaal Vorm conversies [I].



Syntactische standaardisatie.

5.

 

Parafrase via Syntactische verandering: binding (Associatief).



Bindingverandering c.q. Nestingverandering (Associatief).
Diverse regels voor syntactische notatie en denotatie in

PDL

.

5.1.

Kwantoren als connectieven.



5.1a.

Kwantoren als connectieven.


Kwantoren zijn een soort connectieven, of logische operatoren.
Ze vervullen in logische formules de rol van connectief.
De kwantoren binden sterker dan de andere (

PPL

) connectieven.
Bijvoorbeeld:
In 'x ¬A(x)', of 'x (¬(A(x ))', is '' het hoofdconnectief, en '¬' een subconnectief.
In '¬x A(x)', of '¬(x (A(x ))', is '¬' het hoofdconnectief, en '' een subconnectief.

5.1b.

Syntactische associatieregels in

PDL

.


{'¬', '' en '' } associëren naar rechts.
Bijv.: '(x (¬(y (¬(A(x,y ))))))'

=

(i) 'x ¬ y ¬A(x,y)'; of nog korter: ' x ¬y ¬Axy'.
Bijv.: x A(x) B(x) ≡ ( x A(x)) B(x).
Bijv.: x (A(x) B(x)) ≡ ( x (A(x) B(x))).

6.

 

Wetten voor Negatief Normaal Vorm (NNF) conversie, in PDL.



Regels voor Negatief Normaal Conversie (in

PDL

).
Omzetting naar Negatief Normaal Vorm (NNF), door Negatie-binnenplaatsing.

6.1.

 

Negatie binnenplaatsing, met nestingverandering, in PDL.


Bindingverandering c.q. Nestingverandering (Associatief).
Syntactische verandering -
• met (syntactische) termreductie;
• zonder (syntactische) verandering van hoofdconnectief;
• zonder (semantische) verandering van hoofdconnectief;
• en zonder (semantisch) verlies van logische kracht.
Bijv. t.b.v. standaardisatie, via (maximale) reductie van syntactische complexiteit door middel van Nesting vereenvoudiging.

6.1.1.

 

Negatie binnenplaatsing, met nestingverandering; met Universele kwantor .


{¬(x A(x))}  x A(x)).
{(x A(x)) B(x)}   (x (A(x) B(x))).

6.1.2.

 

Negatie binnenplaatsing, met nestingverandering; met Existentiële kwantor.


{¬(x A(x))}  x A(x)).
{(x A(x)) B(x)}   (x (A(x) B(x))).

6.2.

 

Parafrase via Negatie-binnenplaatsing; met kwantor-omslag.


Regels voor Negatie-binnenplaatsing.
Met kwantor-omslag en -vóórplaatsing (zonder connectief-transformatie):
Syntactische verandering -
• zonder (syntactische) termreductie;
• met (syntactische) verandering van hoofdconnectief;
• zonder (semantische) verandering van hoofdconnectief;
• en zonder (semantisch) verlies van logische kracht.

6.2.1.

 

Negatie binnenplaatsing, met kwantor-omslag; met Universele kwantor.


¬x [A(..)] ≡ x ¬[A(..)].

6.2.2.

 

Negatie binnenplaatsing, met kwantor-omslag; met Existentiële kwantor.


¬x [A(..)] ≡ x ¬[A(..)].

Kwantorbewerkingen.



7.

 

Enkelvoudige transformaties onder parafrase/ Equivalentie.



7.1.

 

Kwantorverplaatsing, c.q. kwantor bereik-verandering, onder Equivalentie/ parafrase: volgordebehoudend.



Evt. met kwantor bereik-verandering.
Altijd geldig - mits zonder Kwantor-volgordeverandering in combinaties van U en E kwantoren die in hun semantisch bereik een overlapping hebben (van hun grondinstantiaties) waarbinnen hun variabelen semantisch 'actief' zijn (dus in hun syntactische nesting een overlapping hebben (van termen) waarbinnen hun variabelen vermeld worden in argument-lijsten.

7.1.1.

 

(U/E) Kwantorverplaatsing: 'vóórplaatsing/ buitenplaatsing', c.q. kwantor bereik-vergroting, (volgordebehoudend).



D.i. plaatsing buíten de predicatie-nesting; dus kwantum bereik-vergroting.

Regels voor Prenex Normaal Conversie (in

PDL

).
Omzetting naar Prenex Normaal Vorm (PNF):
D.i. plaatsing buíten de predicatie-nesting; via kwantor bereik-vergroting.!
(Kwantor-bereik extensie); door Kwantor-voorplaatsing/ buitenplaatsing.

Toepasbaar in Conjunctie, Disjunctie.
Altijd geldig.
Equivalentie/ Parafrase: soms valide.
Degressie: soms valide.

Let op bij verandering van kwantor-nesting: indien een existentiële variabele y daarbij binnen het bereik komt van een universele variabele x;
wordt ze daarvan afhankelijk.
Dit betekent disjuncte (samples) expansie, dus degressie.
Prenex normalisatie Kan dus niet standaard in een positieve bewijsmethode worden toegepast.

7.1.1.1.

 

'U-Kwantor-vóórplaatsing/ buitenplaatsing' (volgordebehoudend).



Equivalentie/ Parafrase: soms valide.
Via operatie: conjuncte literalen/ samples reïteratie (o.a. via condensatie).
Degressie: soms valide.
Via operatie: disjuncte samples expansie.

(1)

In Literaal (atoom/predicatie).


(N.v.t.)
(2)

In Conjunctie.


Eerste term.
N.b.: y blijft hier onafhankelijk van x:
{x[A] B}   (cj.lt.rei.) (x[A B]) : geldig.
{(x A(x))  ( y B(y))}  (cj.lt.rei.) (x (A(x)  ( y B(y))) : geldig.
{y ((x A(x))   B(y))}  (cj.lt.rei.) ( x y (A(x)   B(y))) : geldig.
{y ((x A(x))   B(y))}   (cj.lt.rei.) ( y x (A(x)   B(y))) : geldig.

Maar: y wordt nu (ook) afhankelijk van x:
{w ((x A(x))   B(w))}  (

degres

)
(dj.samp.xpn.) (x w (A(x)  B(w))) : geldig.
{(x A(x))  ( y w C_(w,y)))}   (

degres

)
(dj.samp.xpn.) ( x (A(x)  ( y w C_(w,y)))) : geldig.
{(x A(x))  ( w y C_(w,y))}   (

degres

)
(dj.samp.xpn.) ( x (A(x)  ( w y C_(w,y)))) : geldig.
Tweede term.
N.b.: y blijft hier onafhankelijk van x:
{A x[B]}   (cj.lt.rei.) (x[A B]) : geldig.
{(x A(x))  ( y B(y))}   (cj.lt.rei.) (y ((x A(x))   B(y))) : geldig.
{y z (A(y)   (x C_(x,z)))}   (dj.samp.rei.) (y z x (A(y)   C_(x,z))) : geldig.

N.b.: y blijft hier (ook) afhankelijk van x:
{x (A(x)  ( w y C_(w,y)))}   (dj.samp.rei.) (x w (A(x)  ( y C_(w,y)))) : geldig.
{y (A(y)  ( x z C_(x,z)))}   (dj.samp.rei.) (y x (A(y)  ( z C_(x,z)))) : geldig.
(3)

In Disjunctie.


Eerste term.
N.b.: y blijft hier onafhankelijk van x:
{x[A] B}   (dj.samp.rei.) (x[A B]).
{(x A(x))  ( w B(w))}   (dj.samp.rei.) (x (A(x)  ( w B(w)))) : geldig.
{w ((x A(x))   B(w))}   (dj.samp.rei.) ( x w (A(x)   B(w))) : geldig.
{y ((x A(x))   B(y))}   (dj.samp.rei.) {( y x (A(x)   B(y)))} : geldig.

Maar: y wordt nu (ook) afhankelijk van x:
{w ((x A(x))   B(w))}  (

degres

)
(dj.samp.xpn.) (x w (A(x)  B(w))) : geldig.
{(x A(x))  ( y w C_(w,y)))}   (

degres

)
(dj.samp.xpn.) ( x (A(x)  ( y w C_(w,y)))) : geldig.
{(x A(x))  ( w y C_(w,y))}   (

degres

)
(dj.samp.xpn.) ( x (A(x)  ( w y C_(w,y)))) : geldig.
Tweede term.
{A x[B]}   (dj.samp.rei.) (x[A B]).
{(x A(x))  ( w B(w))}   (dj.samp.rei.) (w ((x A(x))   B(w))) : geldig.

{y (A(y)  ( x C_(x,y))}   (dj.samp.rei.) (y x (A(y )   C_(x,y))) : geldig.
{y (A(y)  ( x z C_(z,y)))}   (dj.samp.rei.) (y x (A(y)  ( z C_(x,z)))) : geldig.
N.b.: y blijft hier (ook) afhankelijk van x:
{x (A(x)  ( w y C_(w,y)))}   (dj.samp.rei.) (x w (A(x)  ( y C_(w,y)))) : geldig.
{x y (A(x)   (w C_(w,y)))}   (dj.samp.rei.) (x y w (A(x)   C_(w,y))) : geldig.
(4)

In Implicatie.


Eerste term. Vanaf premisse(n).
{x[A] B}  ( x[A B]). (!)
Tweede term. Vanaf conclusie(s).
{A x[B]}  ( x[A B]).

7.1.1.2.

 

'E-Kwantor-vóórplaatsing / buitenplaatsing' (volgordebehoudend).


(1)

In Literaal (atoom/predicatie).


(N.v.t.)
(2)

In Conjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: [evt. disjuncte samples expansie, condensatie; netto: ] disjuncte samples reiteratie.
Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: [evt. disjuncte samples expansie, resp. condensatie;
netto :] disjuncte samples reiteratie.
Eerste term.
{x[A] B}   (dj.samp.rei.) (x[A B]) : geldig.
{(x A(x))  ( w B(w))}   (dj.samp.rei.) (x (A(x)  ( w B(w)))) : geldig.
{w ((x A(x))   B(w))}   (dj.samp.rei.) ( x w (A(x)   B(w))) : geldig.

{(y A(y))  ( z x C_(x,z))}   (dj.samp.rei.) (y (A(y)  (z x C_(x,z)))) : geldig.
{(y A(y))  ( x z C_(x,z))}   (dj.samp.rei.) (y (A(y)  (x z C_(x,z)))) : geldig.
Tweede term.
{A x[B]}   (dj.samp.rei.) (x[A B]) : geldig.
{(x A(x))  ( w B(w))}   (dj.samp.rei.) (w ((x A(x))   B(w))) : geldig.

(N.b.: y blijft hier (ook) onafhankelijk van x:)
{(x A(x))  ( y B(y))}   (dj.samp.rei.) (y ((x A(x))   B(y))) : geldig.
{x w (A(x)   (y C_(w,y)))}   (dj.samp.rei.) (x w y (A(x)   C_(w,y))) : geldig.
{(x A(x))  ( y C_(x,y))}   (dj.samp.rei.) (x y (A(x)  C_(x,y))) : geldig.
{y (A(y)  ( z x C_(x,z)))}   (dj.samp.rei.) (y z (A(y)  ( x C_(x,z)))) : geldig.
{y x (A(y)   (z C_(x,z)))}   (dj.samp.rei.) (y x z (A(y)   C_(x,z))) : geldig.
(3)

In Disjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Eerste term.
{x[A] B}  ( x[A B]).
{(x A(x))  ( x B(w))}   (dj.samp.rei.) (x (A(x)  ( w B(w)))) : geldig.
{w ((x A(x))   B(w))}   (dj.samp.rei.) ( x w (A(x)   B(w))) : geldig.

{(y A(y))  ( x z C_(x,z))}   (dj.samp.rei.) (y (A(y)  (x z C_(x,z)))) : geldig.
Tweede term.
{A x[B]}  ( x[A B]).
{(x A(x))  ( w B(w))}   (dj.samp.rei.) (w ((x A(x))   B(w))) : geldig.

(N.b.: y blijft hier (ook) onafhankelijk van x:)
((x A(x))  ( y B(y)))}   (dj.samp.rei.) (y ((x A(x))   B(y))) : geldig.
(N.b.: y blijft hier (ook) afhankelijk van x:)
{x (A(x)  ( y w C_(w,y)))}   (dj.samp.rei.) (x y (A(x)  ( w C_(w,y)))) : geldig.
{x w (A(x)   (y C_(w,y)))}   (dj.samp.rei.) (x w y (A(x)   C_(w,y))) : geldig.
(N.b.: z blijft hier (ook) afhankelijk van x:)
{y x (A(y)   (z C_(x,z)))};   (dj.samp.rei.) (y x z (A(y)   C_(x,z))) : geldig.
(4)

In Implicatie.


Eerste term. Vanaf premisse(n).
{x[A] B}  ( x[A B]). (!)
Tweede term. Vanaf conclusie(s).
{A x[B]}  ( x[A B]).

7.1.2.

 

(U/E) Kwantorverplaatsing: ' binnenplaatsing', c.q. kwantor bereik-verkleining, volgordebehoudend.


D.i. plaatsing bínnen de predicatie-nesting; dus kwantum bereik-verkleining.
Altijd geldig.

7.1.2.1.

 

U-Kwantor-verplaatsing

:

'binnenplaatsing',

volgordebehoudend.


D.i. plaatsing bínnen de predicatie-nesting; dus kwantum bereik-verkleining.
(1)

In Literaal (atoom/predicatie).


(N.v.t.)
(2)

In Conjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Eerste term.
(Maar: y wordt nu NIET MEER afhankelijk van x:)
{x (A(x)  ( y C_(x,y)))}  (( x A(x))  ( y C_(x,y))) :

ongeldig

.
Tweede term.
{x y (A(x)   B(y))}   (dj.samp.rei.) ( x (A(x)  ( y B(y))) : geldig.
{y x (A(y)   C_(x,y))}   (dj.samp.rei.) (y (A(y)  ( x C_(x,y)))) : geldig.
(3)

In Disjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Eerste term.
(Maar: y wordt nu NIET MEER afhankelijk van x:)
{x (A(x)  ( y C_(x,y)))}  (( x A(x))  ( y C_(x,y))) :

ongeldig

.
Tweede term.
{x y (A(x)   B(y))}   (dj.samp.rei.) ( x (A(x)  ( y B(y))) : geldig.
{y x (A(y)   C_(x,y))}   (dj.samp.rei.) (y (A(y)  ( x C_(x,y)))) : geldig.

7.1.2.2.

 

E-Kwantor-verplaatsing: ' binnenplaatsing' (volgordebehoudend).


D.i. plaatsing bínnen de predicatie-nesting; dus kwantum bereik-verkleining.
Toepasbaar in Conjunctie, Disjunctie.

(1)

In Literaal (atoom/predicatie).


(N.v.t.)
(2)

In Conjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
{x (A(x)  ( y C_(x,y)))}   (dj.samp.rei.) ((x A(x))  ( y C_(x,y))) : geldig.
Tweede term.
{x y (A(x)   B(y))}  (dj.samp.rei.) ( x (A(x)  ( y B(y)))) : geldig.
{x y (A(x)   C_(x,y))}   (dj.samp.rei.) (x (A(x)  ( y C_(x,y)))) : geldig.
(3)

In Disjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Eerste term.
{x (A(x)  ( y C_(x,y)))}   (dj.samp.rei.) ((x A(x))  ( y C_(x,y))) : geldig.
Tweede term.
{x y (A(x)   B(y))}  (dj.samp.rei.) ( x (A(x)  ( y B(y)))) : geldig.
{x y (A(x)   C_(x,y))}   (dj.samp.rei.) (x (A(x)  ( y C_(x,y)))) : geldig.

Parafrase via Syntactische verandering: volgorde (Commutatief) - I.



7.2.

 

Kwantorverplaatsing: met volgordeverandering, (gelijkwaardig).




Kwantor-volgorde verandering.

7.2.1.

 

(U/E) Kwantorverplaatsing:
Kwantor-volgorde verandering (gelijkwaardig).


(U-U/E-E)
D.i. plaatsverwisseling van gelijkwaardige kwantoren: existentiële kwantoren of universele kwantoren.
Toepasbaar in Literaal, Conjunctie, Disjunctie.
Altijd geldig.
Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).

7.2.1.1.

 

(2 x U) Kwantor-volgorde verandering.


Plaatsverwisseling van (alleen) universele kwantoren.
(1)

In Literaal (atoom/predicatie).


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte literalen reiteratie.
{x y A(x,y)}   (dj.lt.rei.) (y x A(x,y)) : geldig.
(2)

In Conjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: conjuncte literalen reiteratie.
Beide termen.
{x w (A(x)   B(w))}   (cj.lt.rei.) ( w x (A(x)   B(w))) : geldig.
{x y (A(x)   C_(x,y))}   (cj.lt.rei.) (y x (A(x)   C_(x,y))) : geldig.
{x y (A(y)   C_(x,y))}   (cj.lt.rei.) (y x (A(y)   C_(x,y))) : geldig.
(3)

In Disjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Beide termen.
{x w (A(x)   B(w))}   (dj.samp.rei.) ( w x (A(x)   B(w))) : geldig.
{x w (A(x)   (y C_(w,y)))}   (dj.samp.rei.) (w x (A(x)  ( y C_(w,y)))) : geldig.
{x y (A(x)   C_(x,y))}   (dj.samp.rei.) (y x (A(x)   C_(x,y))) : geldig.

7.2.1.2.

 

(2 x E) Kwantor-volgorde verandering.


Plaatsverwisseling van (alleen) existentiële kwantoren.

(1)

In Literaal (atoom/predicatie).


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
{x y A(x,y)}   (dj.lt.rei.) (y x A(x,y)) : geldig.
(2)

In Conjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Beide termen.
{x y (A(x)   B(y))}   (dj.lt.rei.) ( y x (A(x)   B(y))) : geldig.
{x y (A(x)   C_(x,y))}   (dj.lt.rei.) (y x (A(x)   C_(x,y))) : geldig.
(3)

In Disjunctie.


Equivalentie/ Parafrase: wel valide (dus ook Implicatie, géén degressie).
Via operatie: disjuncte samples reiteratie.
Beide termen.
{x y (A(x)   B(y))}   (dj.lt.rei.) ( y x (A(x)   B(y))) : geldig.
{x y (A(x)   C_(x,y))}   (dj.lt.rei.) (y x (A(x)   C_(x,y))) : geldig.

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