Cursus / training:

Methode voor Logische Analyse


Principes van Formele logica .



Combinatorische explosie in Logische systemen



Inhoudsopgave



Combinatorische explosie in Logische systemen



Inleiding: Informatie, logica en complexiteit.



Oordeelsvorming maakt gebruik van informatie


Onze oordelen en inschattingen lijken in veel opzichten op onze overige reacties en beslissingen. We baseren ze op informatie die we beschikbaar hebben, op bewust maar ook op onbewust niveau.

Informatie en verschil.


Over het begrip 'informatie' zijn veel verschillende opvattingen. Om misverstanden te vermijden, en de wezenlijke betekenis van het begrip te begrijpen, is het handig om eerst te kijken naar haar meest kenmerkende eigenschap. Die wordt duidelijk wanneer we ons de situatie voorstellen waarin ze er totaal níet is. Zonder enige informatie is er alleen zinloze chaos, nietszeggende ruis (noise), totale vaagheid, een volstrekt niet-weten.
Informatie begint pas bij onderscheiding van enig verschil. Zodra een onderscheid valt te maken - bijv. een verschil tussen wel/niet, aan/uit, ja/nee, waar/onwaar, enz. - ontstaat enige ordening. Alleen dan wordt redeneren mogelijk, en is de logica van toepassing. Elke hoeveelheid informatie impliceert dus minstens één verschil.

Informatie en ordening.


Elk verschil impliceert op zijn beurt minstens twee 'dingen', verschijnselen of toestanden in een gebied in de werkelijkheid. Op basis van onderscheidingen kunnen dus combinaties van dingen worden beschouwd.
Tussen die dingen bestaat tegelijk minstens één ordeningsrelatie, namelijk die welke noodzakelijk volgt uit datzelfde bespeurde verschil.
Bovendien, om enige betekenis voor ons te hebben, kan informatie sowieso niet bestaan uit louter losse gegevens. We bekijken informatie altijd in een bepaalde samenhang. Dit impliceert dat ze de mogelijkheid biedt ordening te onderscheiden.
Omgekeerd bezien vertegenwoordigt elke ordeningstoestand, of structuur, op zichzelf genomen een bepaald gehalte aan informatie.

Logische relaties.


Gegeven een willekeurige verzameling elementen kunnen we kijken welke logische relaties tussen die elementen mogelijk zijn.
De logische relaties hebben betrekking op de verschillende toestanden of waarden die de elementen afzonderlijk kunnen aannemen, alsook door hun onderlinge afleidingsrelaties.

Informatie en redenering.


Door het combineren van gegevens kunnen we meer complexe vormen van informatie verkrijgen.
Dit doen we uiteraard door middel van onze gedachten.
Elke gedachtegang, en in feite elk proces van informatieverwerking, heeft de algemene vorm van een redenering, dat wil zeggen:
Redeneren:
Een aantal uitgangsgegevens worden gecombineerd, en uit de combinatie worden volgende gegevens afgeleid.
De manieren waarop die combinaties kunnen worden gemaakt, en de waarden die deze combinaties kunnen aannemen, worden bepaald door de wetten van de logica.
Uiteraard gelden deze eigenschappen ook en bij uitstek voor elke oordeelsvorming. Die kan beschouwd worden als redeneervorm, omdat ze aangrijpt op informatie, en vervolgens resulteert in bepaalde informatie.

Logische wetten.


De logische wetten hebben louter betrekking op de relaties tussen gegevens, dat wil zeggen de combinaties en afleidingen; en niet op de afzonderlijke gegevens (zoals directe waarnemingen en gevoelens). Ze gelden ook onafhankelijk van de inhoud en de aard van de gegevens, m.n. mogelijke variaties in onderwerp, domein, probleem, doel, toepassing, toepassingsgebied, enz..

Trappen van logische complexiteit.


Elke redeneervorm bestaat uit een combinatie van één of meer onderscheiden logische relaties.
Redeneringen zijn - letterlijk - in elke denkbare vorm mogelijk, maar ook in elke ondenkbare vorm: ze zijn vrijwel onbeperkt in mogelijke variatie, complexiteit en omvang. Zoals we hieronder zullen zien, reikt dit al in een klein aantal stappen onafzienbaar ver buiten het voorstellings- en bevattingsvermogen van mensen, en evengoed buiten de reken- en opslagcapaciteit van fysieke of zelfs theoretische computers van elke voorstelbare omvang.
Gelukkig kunnen al die mogelijke vormen worden geordend en beoordeeld met behulp van de wetten van de logica. Inzicht in de wetten van de logica is daarom onontbeerlijk voor elke zinvolle en betrouwbare oordeelsvorming. Voor het optimaal benutten van de logica is een helder inzicht in de minimale niveau's van logische complexiteit en hun proporties onmisbaar.

1.

 

Grondslagen van een Logisch systeem.



In dit overzicht kijken we naar de logische mogelijkheden die volgen uit een willekeurige verzameling eenheden (items of objecten). We zullen daarbij zien op welke manieren hierbij combinatorische explosie optreedt, in welke mate dit gebeurt en welke consequenties dit heeft voor de complexiteit van informatieverwerking en oordeelsvorming met betrekking tot de uitgangsgegevens.
Om ons te beperken tot de meest algemeen geldige principes gaan we uit van een logische systeem dat zelf van minimale complexiteit is. Uit dit systeem kan de propositielogica worden afgeleid, maar ook, met de nodige aanvullingen, iets complexere systemen zoals de predicatenlogica en de modale logica.
In het algemeen geldt dat de consequenties van combinatorische explosie en complexiteit zelf explosief toenemen met elke trap van toenemende verfijning van het logische systeem dat we toepassen.

Logisch systeem op semantisch niveau.


S!

: een logisch systeem ('apparaat', calculus).

S!

PPL :

S!

is een systeem in de propositielogica (

PPL

) (of hoger).

S!

PDL-I :

S!

is een systeem in de predicatenlogica (

PDL-I

), first-order logic (

FOL

) (of hoger).
SEM!(

S!

) : de semantiek, een verzameling ordeningsregels, van

S!

.

Logisch systeem op syntactisch niveau.


L!

: een formeel systeem (taalsysteem).

L!

PPL :

L!

is een taal in de propositielogica (

PPL

) (of hoger).

L!

PDL-I :

L!

is een taal in de predicatenlogica (

PDL-I

), first-order logic (

FOL

) (of hoger).
SYN!(

L!

) : de syntax, of grammatica, een verzameling ordeningsregels, van

L!

.
WFF*(

L!

) : de verzameling welgevormde uitspraken (well-formed formulas) van

L!

.

Basisparameters.



1.1.

 

Objecten.


Toepasbaar in

PPL

en hoger.

D

* : (referentieel) domein of populatie, verzameling elementen d[d1 ];   waarbij (d1

=

1, .. d).
d : domein- of populatie-omvang; totaal aantal unieke objecten, domein-elementen ('dingen', fenomenen, items, variabelen) d[d1] in

D

*.

D

*

=

{d[1], .. d[d1], .. d[d] }.
d

=

|

D

*

|

.

Voorbeeld.


Bij twee items (d

=

2 ) kan de verzameling

D

·d bestaan uit de volgende elementen (objecten), hier weergegeven met propositiesymbolen en in arbitraire volgorde:
{ (d

=

2 ) (

D

·d

=

  {' A' ,' B'} ) }.
In principe kan het domein ook leeg zijn. Dat maakt het oordeelssysteem

S!

[s1] dan wel uiterst minimaal, zo niet futiel.
Enkele voorbeelden van beweringen in zo'n 'minimaal' systeem, in een formele taal:
{ (d

=

0 ) (

D

·d

=

{} ) : ({}

=

(v) {} ); (({})

$

=

(v)

$

0 ); ({}

=

(r)

$

0 ); etc.}.
Ook kan het domein uit één element bestaan. Maar dan blijft het oordeelssysteem

S!

[s1 ] ook buitengewoon simpel.
Enkele voorbeelden van beweringen in zo'n 'primitief' systeem, in een formele taal:
{ (d

=

1 ) (

D

*

=

{d[1]} ) : ((d[1] )

$

=

(v)

$

1 ); ((d[1] )

$

=

(v)

$

0 ); etc.}.

Bereik.


Wanneer het aantal objecten minder dan één is, wordt elke redenering zinloos.
Wanneer het echter oneindig is, worden onnoemelijk veel redeneringen over het domein in de praktijk onbeslisbaar.
Voor een domein dat zinvol is en hanteerbaar (manageable), geldt:
{ (d  

=

|

D

*(

mgb

)

|

); (1

d

<

0 ) }.

1.2.

 

Waarden.


Algemeen toepasbaar op objecten.

V

* : waarderingsstelsel of 'waardenpalet', verzameling waarden v[v1];   waarbij (v1

=

1, ..v).
v : totaal aantal unieke waarden, toestandswaarden, objectwaarden of signaalwaarden ( valenties, schaal); bijv. waarheidswaarden, v[v1] in

V

*.

V

*

=

{v[1], .. v[v1], .. v[v] }.
v

=

|

V

*

|

.

Voorbeeld.


Bij twee waarden (v

=

2 ) kan de verzameling

V

·v bestaan uit de volgende elementen (waarden), hier weergegeven met waarde constanten en in arbitraire volgorde:
{ (v

=

2 ) (

V

·v

=

  {0 ,1 } ) }.

Bereik.


Wanneer het aantal waarden minder dan twee is, wordt elke toekenning van waarde betekenisloos, en daardoor wordt elk begin van een zinnige redenering onmogelijk.
Wanneer dit aantal echter oneindig is, wordt vrijwel elke redenering over het domein in de praktijk onbeslisbaar.
Voor een waardenpalet dat zinnig is en hanteerbaar (manageable), geldt:
{ (v  

=

|

V

*(

mgb

)

|

); (2

v

<

0 ) }.

1.3.

 

Parameters voor PDL

.
In de

PDL

komen daarbij nog aanvullende parameters.
(2a) p : totaal aantal unieke predikaat-variabelen (attributen, predikaatnamen); waaronder evt. identiteit, '='.
(2b) r : (maximaal) totaal aantal unieke argument-plaatsen, of ariteit, per predikaatnaam.
(neem hiervoor omwille van eenvoud en zekerheid eventueel het maximum over alle predikaatnamen).
(2c) n : totaal aantal unieke elementen (individuen, objecten) in het referentieel domein (de populatie).
Het (maximaal) aantal unieke items a is in

PDL

van deze laatste drie een afgeleide.
{p

a

(p *MAX(1,(r *n)) }.
M.a.w., hebben we voor een

PDL

systeem voldoende informatie over de parameters p, r en n, dan kunnen we a berekenen en verder redeneren conform de regels voor een

PPL

systeem.

Hieronder onderzoeken we welke combinatorische mogelijkheden deze parameters opleveren op semantisch respectievelijk syntactisch vlak.

2.

 

Semantische expansie.



2.1.

 

Elementaire objecttoestanden.


Objecttoestanden worden gevormd door paren, of tupels (het Cartesisch product) uit de v waarden en d elementen.
Ze geven het domein weer op een observationeel niveau.
Op semantisch niveau zijn dit waarheidsbeweringen met betrekking tot de toestand van afzonderlijke objecten.
In logische talen zijn dit bijv. literalen, grondinstanties, of 'witnesses'.
Deze zijn te vergelijken met steekproeven (samples) uit een populatie.

H

·(v,d) : De verzameling van alle mogelijke unieke objecttoestanden .

Voorbeeld.


In het simpelste, universeel toepasbare logisch systeem, met twee waarheidswaarden (v

=

2, binair systeem) en twee items (d

=

2), bestaat de verzameling

H

·(v,d) uit de volgende elementen (objecttoestanden), hier weergegeven met propositiesymbolen en in arbitraire volgorde:
(

H

·(v

=

2,d

=

2)

=

  { ' A' ,'¬A' ,' B' ,'¬B' } ).

Omvang.


h : Het totale aantal mogelijke unieke objecttoestanden.
{ v, d

|

(h (( h

=

|

H

·(v,d)

|

);
(h  

=

(

|

V

·v

|

,

|

D

·d

|

);

=

v *d   ) )h ) d, v }.

In een binair systeem.


Onder (v

=

2 ) geldt:

H

·(v,d) is even groot als de verdubbeling van verzameling

D

·d.
Bijv., onder (v

=

2 );
bij (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt (h

=

{ 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,

..

} ).
De waarden h komen goeddeels overeen met de natuurlijke niet-negatieve even getallen. Zie reeks A001003 (eerder M0985) in de On-line Encyclopedia of Integer Sequences (OEIS).

Bereik.


Het getal h blijft lineair (polynomiaal) in d.
(2

h

<

0 ).

Complexiteitsklasse.


De verzameling

H

·(v,d) blijft binnen de klasse van aftelbaar oneindige verzamelingen (countable infinite sets, denumerable sets).
Is dus algoritmisch doorzoekbaar (tracktable) - met een singletape Turing machine - binnen lineair polynomiale rekentijd (

P-TIME

).
(

H

·(v,d)

POLY

(d^1 );

TIME

(d );

P-TIME

).

2.2.

 

Domeintoestanden.


Domein toestanden bestaan uit conjuncte combinaties van alle objecten met hun specifieke waarden, dus verschillende objecttoestanden.
Ze geven het domein weer op een louter beschrijvend niveau.
Op semantisch niveau zijn dit waarheidsbeweringen met betrekking tot de toestand van het gehele domein dat we in ogenschouw nemen.
Ze zijn te vergelijken met de cellen (categorieën van variantie) van een zgn. contingentie tabel ( cross tabulation, of 'crosstab'), die de grondslag vormt voor talrijke statistische maten voor de vergelijking van varianties, met name Chi-kwadraat2), en varianten of afgeleiden daarvan, zoals correlatie coëfficiënt, regressie coëfficiënt, Student's t , F, Fisher z, enz..

B

·(v,d) : De verzameling van alle mogelijke unieke domeintoestanden .

Voorbeeld.


Bij twee waarheidswaarden (v

=

2, binair systeem) en twee items (d

=

2) bestaat de verzameling

B

·(v,d) uit de volgende elementen ( domeintoestanden), hier weergegeven met propositiesymbolen en in arbitraire volgorde:
(

B

·(v

=

2,d

=

2)

=

  {'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)' } ).

Omvang.


b : Het totale aantal mogelijke unieke domeintoestanden.
Het getal b komt overeen met het aantal herhalingsvariaties, oftewel, volgordevariaties met teruglegging c.q. herhaling, met omvang (lengte) d uit v elementen.
{ v, d

|

(b ( b

=

|

B

·(v,d)

|

;
(b  

=

(d1 := 1,

..

d )
v;  

=

v ^d ) b )d, v }.
Dit aantal bepaalt de lengte van digitale waarheidswaardepatronen van de logische relaties.
Het is gelijk aan het aantal rijen in de waarheidswaardetabel.

In een binair systeem.


Onder (v

=

2 ) geldt:

B

·(v,d) is even groot als de verzameling van alle mogelijke deelverzamelingen - de machtsverzameling of power set - van

D

·d.
(v

=

2) (b

=

|

B

·(2,d)

|

;

=

|

P

^d

|

).
Bijv., onder (v

=

2 );
bij (d

=

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt (b

=

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,

..

} ).
De waarden b komen goeddeels overeen met de machten van 2. Zie reeks A000079 (eerder M1129, N0432) in de OEIS.
In een binair systeem vertegenwoordigt het aantal domein toestanden de hoeveelheid signaal, de signaalinhoud, of signaalcapaciteit, die wordt gemeten als het aantal domeinelementen d in bits (binary digits):
b

=

lg2 d bits.

Bereik.


Het getal b blijft exponentieel in d.
(2

b

<

0 ^0 );

Complexiteitsklasse.


De verzameling

B

·(v,d) blijft binnen de klasse van de niet-aftelbaar oneindige verzamelingen (uncountable infinite sets), die de omvang hebben van het continuum ( cardinality of the continuum).
Is dus alleen algoritmisch doorzoekbaar binnen exponentiële rekentijd (

EXP-TIME

).
(

B

·(v,d)

EXP-TIME

(d ) ).

2.3.

 

Logische relaties.


Logische relaties geven het domein weer op een analytisch niveau.
Op semantisch niveau zijn dit de voorwaardelijke waarheidsbeweringen die mogelijk zijn met betrekking tot de toestand van het gehele domein of delen ervan.
In logische talen zijn dit bijv. waarheidswaardepatronen, formules, proposities, theorema's, e.d..
Deze komen overeen met de kolommen in de waarheidswaardetabel.

T

·(v,d) : De verzameling van alle mogelijke unieke logische relaties.

Voorbeeld.


Bij twee waarheidswaarden (v

=

2, binair systeem) en twee items (d

=

2), bestaat de verzameling logische relaties (

T

·(v,d)) uit de volgende elementen (logische relaties), hier weergegeven met propositiesymbolen en in arbitraire volgorde:
(

T

·(v

=

2,d

=

2)

=


{' T' ,' F' ,' A' ,' B' ,'¬A' ,'¬B'
,'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)'
,'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)'
,'( A B)' ,'( A

#

B)' } ).

Omvang.


t : Het totale aantal mogelijke unieke logische relaties.
Het getal t is het aantal volgordevariaties met teruglegging c.q. herhaling (herhalingsvariaties) met omvang (lengte) b uit v elementen.
{ v, d, b

|

( t ((t

=

|

T

·(v,d)

|

);
(t  

=

(b1 := 1,

..

b )
v;  

=

|

B

·(v,b)

|

;

=

v ^

|

B

·(v,d)

|

;

=

v ^(v ^d) ) )t )b, d, v }.

In een binair systeem.


Onder (v

=

2 ) geldt:

T

·(v,d) is even groot als de power set van de power set van

D

·d.
(v

=

2) (t

=

|

T

·(2,d)

|

;

=

|

P

^b

|

;

=

|

P

^|

P

^d

|

|

).
Bijv., onder (v

=

2 );
bij (d

=

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt (t

=

{ 4, 16, 256, 65 536, 4 294 967 296, 1.844674407371 ·(10^19), 3.402823669209 ·(10^38), 1.157920892373 ·(10^77), 1.340780792994 ·(10^154), 1.797693134862 ·(10^308),

..

} ).
De waarden t komen goeddeels overeen met de machten van 2 van de machten van 2. Zie reeks A001146 (eerder M1297, N0497) in de OEIS.

Bereik.


Het getal t blijft hyperexponentieel in d.
(2

t

<

0 ^(0 ^0 ) );

Complexiteitsklasse.


De verzameling

T

·(v,d) is algoritmisch doorzoekbaar binnen hyper-exponentiële rekentijd (

2-EXP-TIME

).
(

T

·(v,d)

2-EXP-TIME

(d ) ).

2.4.

 

De waarheidswaardetabel.


Gegeven een gekozen domein

D

·d en waardepallet

V

· v worden de mogelijke directe logische relaties-tussen-relaties volledig gedefinieerd door middel van de zgn. waarheidswaardetabel.
Deze wordt opgebouwd volgens een systematische waardetoekenning (validatie) van de objecten op basis van een simpel gestandaardiseerd rekenkundig schema (algoritme). De objecten doorlopen achtereenvolgens elk het gehele scala waarden via zgn. 'geneste' cycli (loops), waardoor ze hun unieke, geordende waarheidswaardepatronen verkrijgen. Vervolgens worden alle overige geordende waardencombinaties ingevuld. Op deze manier ontstaat de tabel als een sluitend, samenhangend geheel van alle mogelijke volgordes van (waarheids)waarden, oftewel (waarheids)waardepatronen t, bij parameters (d,v).
De waardepatronen zijn te vergelijken met uitspraken met minstens één gezegde c.q. hoofdzin of bijzin, oftewel 'zinnen'.
Ze hebben in een binair systeem de vorm van binaire getallen. Elk hiervan heeft een lengte van b waardeconstanten . De laatste zijn te vergelijken met lettertekens of symbolen in geschreven taal.
De lengte b komt overeen met de hoeveelheid informatie in standaard eenheden: bits.
Bovendien geeft de tabel volkomen gegarandeerd alle mogelijke elementaire logische relaties weer in hun vaste , directe onderlinge logische relaties.

T

·(v,d)w : De geordende verzameling van alle cellen in de waarheidswaardetabel.

Voorbeeld.


De waarheidswaardetabel voor een logisch systeem met (v =2) waarden en (d=2) variabelen, geïnterpreteerd voor propositielogica (

PPL

), predikatenlogica (

PDL

), resp. verkorte, Skolem vorm (

Sk

).

Tabel   tweewaardige waardencombinaties
- met twee variabelen, geïnterpreteerd voor PPL, resp. PDL, resp. Sk


Nr. Waarde- patroon Logische relatie in

PPL

Logische relatie in

PDL

Logische relatie in

Sk

Logische kracht
1 1 1 1 1

T

¬

F

X

¬

X

      0
2 0 0 0 0

F

¬

T

X

¬

X

      1
3 1 1 0 0

A

1
¬¬

A

1
        0.50
4 1 0 1 0

A

2
¬¬

A

2
        0.50
5 0 0 1 1 ¬

A

1
¬

A

1
        0.50
6 0 1 0 1 ¬

A

2
¬

A

2
        0.50
7 1 0 0 0

A

1

A

2
¬(¬

A

1 ¬

A

2)
  x

A

[x]
¬x ¬

A

[x]

A

[x]
0.75
8 0 1 0 0

A

1 ¬

A

2
¬(¬

A

1

A

2)
        0.75
9 0 0 1 0 ¬

A

1

A

2
¬(

A

1 ¬

A

2)
        0.75
10 0 0 0 1 ¬

A

1 ¬

A

2
¬(

A

1

A

2)

A

1 \

A

2
¬x

A

[x]
x ¬

A

[x]
¬

A

[x]
0.75
11 1 1 1 0

A

1

A

2
¬(¬

A

1 ¬

A

2)
  x

A

[x]
¬x ¬

A

[x]

A

[

c

s

]
0.25
12 1 1 0 1

A

1 ¬

A

2
¬(¬

A

1

A

2)

A

1

A

2
      0.25
13 1 0 1 1 ¬

A

1

A

2
¬(

A

1 ¬

A

2)

A

1

A

2
      0.25
14 0 1 1 1 ¬

A

1 ¬

A

2
¬(

A

1

A

2)

A

1 |

A

2
¬x

A

[x]
x ¬

A

[x]
¬

A

[

c

s

]
0.25
15 1 0 0 1

A

1

A

2
¬(

A

1 #

A

2 )
        0.50
16 0 1 1 0

A

1 #

A

2
¬(

A

1

A

2)
        0.50

Omvang.


tw : Het totale aantal cellen in de bijbehorende waarheidswaardetabel.
Het getal tw wordt uiteraard nog groter dan t, nl. het product van het aantal domeintoestanden ( rijen) b, en het aantal toestandsrelaties (kolommen) t.
{ v, d, b, t

|

( tw ((tw

=

|

T

·(v,d)w

|

);
(tw
 

=

|

(

T

*(v,d ),

B

*(v,d) )

|

;  

=

(

|

T

*(v,d)

|

*

|

B

*(v,d)

|

);  

=

(

|

B

*( v,b)

|

*

|

B

*(v,d)

|

);
 

=

v ^(v ^d ) *v ^d ;  

=

v ^((v ^d) +d ) ) ) tw )t, b, d, v }.

In een binair systeem.


Onder (v

=

2 ) geldt:
{ (v

=

2 ) ( tw  

=

|

T

·(2,d)w

|

;  

=

2 ^((2 ^d) +d ) ) }.
Bijv., onder (v

=

2 );
bij (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt (tw

=

{8, 64, 2018, 104 8576, 137 438 953 472, 1.18059162071744 ·(10^21 ), 4.35561429658752 ·(10^40), 2.96427748447488 ·(10^79), 6.86479766012928 ·(10^156), 1.840837770098688 ·(10^311),

..

};
resp. in bytes (64-bits): {0.125, 1, 32, 16 384, 2 147 483 648, 1.844674407371 ·(10^19), 6.805647338418 ·(10^38), 4.631683569492 ·(10^77), 1.072624634395 ·(10^155), 2.876309015779 ·(10^309),

..

} );

2.5.

 

Redeneerelementen, argumenten (semantisch).



Wanneer we een redenering opzetten maken we gebruik van bepaalde mogelijke logische relaties over het onderwerp in kwestie. Een redenering bestaat dus uit een combinatie van logische relaties. Dat wil zeggen, een bepaalde selectie, of deelverzameling, uit

T

·(v,d). Zo'n combinatie kunnen we beschouwen als een 'pakket' van bouwstenen waarmee we een specifieke redenering kunnen maken. Elke bouwsteen kan fungeren als bewering, argument/premisse of conclusie.
Op semantisch niveau zijn deze in elk geval gezuiverd van doublures.
Voor een solide oordeelsvorming moeten we rekening houden met alle mogelijke selecties.

U

·(v,d) : De verzameling van alle mogelijke unieke combinaties van redeneerelementen.

Voorbeeld.


Bij twee waarheidswaarden (v

=

2, binair systeem) en één item (d

=

1) bestaat de verzameling

U

·(v,d) uit de volgende deelverzamelingen ( redeneervormen) hier weergegeven als combinaties van logische relaties gesteld in termen van propositiesymbolen, en in arbitraire volgorde:

U

·(v

=

2,d

=

1)

=


{ {}
,{' T'}
,{' T' ,' F'} {' T' ,' A'} {' T' ,'¬A'}
,{' T' ,' F' ,' A'} ,{' T' ,'F' ,'¬A'} ,{' T' ,' A' ,'¬A'}
,{' T' ,' F' ,' A' ,'¬A'}
,{' F'}
,{' F' ,' A'} ,{' F' ,'¬A'}
,{' F' ,' A' ,'¬A'}
,{' A'}
,{' A' ,'¬A'}
,{¬A'} }.

Omvang.


u : Het totale aantal mogelijke unieke combinaties van redeneerelementen.
Het getal u is gelijk aan de som van alle mogelijke unieke ongeordende selecties (zonder interne herhaling ) uit

T

·(v,d) - dus van de binomiaal coëfficiënten per deelverzameling van

T

·v,d van het aantal logische relaties t boven de mogelijke lengte t1 van die deelverzameling.
{ v, d, t

|

( u ((u

=

|

U

·(v,d)

|

);
(u1 ((U*[u1]

U

·(v,d) ); ((u[u1]

=

|

U* [u1]

|

)   (1

u [u1]

t )
(t1 ((u[u1]

=

t1 ) ((U*[u1] U·t1 ) (U· t1

U

·(v,d) ) ) ) t1 ) ) )u1 );
(u
 

=

(u1 := 1,

..

u )
u[u1];
 

=

(t1 := 1,

..

t )
(

|

U·t1

|

);
 

=

(t1 := 1,

..

t )

binomial

(t, t1 );
 

=

|

T

·(v,t)

|

;

=

2 ^

|

T

·(v,d)

|

;

=

2 ^(v ^(v ^d)) ) )u )t, d, v }.

In een binair systeem.


Onder (v

=

2 ) geldt:

U

·(v,d) is even groot als de power set van de power set van de power set van

D

·d.
(v

=

2 ) (u

=

|

U

·(2,d)

|

;

=

|

P

^t

|

;

=

|

P

^|

P

^b

|

|

;

=

|

P

^|

P

^|

P

^d

|

|

|

).
Bijv., onder (v

=

2 );
bij (d

=

{1, 2, 3,

..

} );
volgt (u

=

{16, 65 536, 1.157 920 892 373 ·(10^77),

..

} ).
De waarden u komen goeddeels overeen met de reeks 2 ^ A001146(d );

=

A001146(d +1 ).

Bereik.


Het getal u blijft ultra-exponentieel in d.
(2

u

<

2 ^( 0 ^(0 ^0 ) ) ).

Complexiteitsklasse.


De verzameling

U

·(v,d) blijft algoritmisch doorzoekbaar binnen ultra-exponentiële rekentijd (

3-EXP-TIME

).
(

U

·(v,d)

3-EXP-TIME

(d ) ).

2.6.

 

Redeneringen, afleidingen (semantisch).



(1)

Redeneringen als afleiding.


Een zeer algemeen 'in de natuur' voorkomende redenering is die waarbij op zijn minst één denkstap wordt gezet. Dat wil zeggen dat uit een bepaalde verzameling gegevens (feiten, verbanden) een andere verzameling gegevens wordt afgeleid.
Zo'n afleiding heeft als hoofdconnectief de implicatie.
Kort gezegd, elke redenering heeft de vorm 'premisse impliceert conclusie'.
Bijv.: (X Y ).
NB. Aristotelis formuleerde een principe voor de reneervorm van het syllogisme dat in feite geldt voor elke redeneervorm: "The syllogism is a discourse in which, certain things being laid down, another thing follows necessarily, simply because those things are laid down." (Aristotle, Prior Anal., 1, 1).
Een redenering in een systeem met een schaal van v waarden over een domein met d objecten zal dus de vorm hebben van een afleiding met de vorm:
Bijv.: (X·(v,d) Y·(v, d) ).
In het algemeen redeneren we vanuit een verzameling uitgangspunten (premissen) naar een verzameling conclusies.
Dit betekent dat zowel de premisse-groep als de conclusie-groep bestaat uit een bepaalde deelverzameling van

U

·(v,d).
(a) De premisse wordt gevormd door een bepaalde deelverzameling uit

U

·(v,d) , zeg

U

·(v,d)[k1] met lengte (omvang) l [k1] elementen.
(b) De conclusie wordt gevormd door een (andere of dezelfde) deelverzameling zeg

U

·(v ,d)[m1] met lengte (omvang) l[m1] elementen.

R

·(v,d)[k1,m1]: Een redenering van (een element van)

U

·(v,d) naar (een element van)

U

·(v,d).
Deze krijgt globaal genomen de vorm:
(v d

|

k1 m1 (

R

·(v,d)[k1, m1]
(

U

·(v,d)[k1]

U

·(v,d)[m1] ) ) ).

Bijv. (PPL): v1 d1 ( v1

=

2; d1

=

4;

D

·d1

=

{A, B, C, D };
k1 k2 ( (

U

·(v1,d1)[k1]

U

·(v1,d1) ); (

U

·(v1,d1)[k2]

U

·(v1,d1) );
(

U

·(v1,d1)[k1]

U

·(v1,d1)[k2] );
(

U

·(v1,d1)[k1]

=

{A, (B ¬C ) };
(

U

·(v1,d1)[k2]

=

{¬A B ), (C ¬ D ) } );

R

·(v,d)[k1,m1]

:=

((A, (B ¬C ) ) (¬A B ), (C ¬D ) ) );

(2)

De verzameling van afleidingen.


R

·(v,d)[

U

]
: De verzameling van alle mogelijke unieke redeneringen c.q. gevolgtrekkingen op semantisch niveau.
(v d

|

R

·(v,d )[

U

]

:=

(k1 := 1,

..

u )
(m1 := 1,

..

u )

R

·(v,d)[

U

]
[k1,m1] ) );
Dit betekent dat de verzameling van alle mogelijke unieke redeneervormen onder de parameters {v,d} wordt gevormd door een matrix:
(v d

|

R

·(v,d )[

U

]

:=

(

U

·(v,d)

X

U

·(v,d)) );

Omvang.


ru: Het totale aantal van alle mogelijke unieke redeneringen c.q. gevolgtrekkingen op semantisch niveau.
De omvang van de verzameling wordt uiteraard gevormd door het Cartesisch product (u·u).
r·(v,d)u

=

|

R

·(v,d)[

U

]

|

;

=

u ·(v,d)^2.
De waarden r·(v,d)u komen goeddeels overeen met de reeks (2 ^A001146(d ) )^2.

(2)

Afleidingen zijn op semantisch niveau tweeplaatsig.


Zoals gezegd bevat een verzameling

U

·(v,d) deelverzamelingen

U

·(v,d)[k1] die elk bestaan uit unieke combinaties van logische relaties uit de verzameling

T

·(v,d). Al die elementen hebben hun eigen logische geldigheidswaarde die uniek is binnen

T

·(v ,d). Wanneer we deze waarden combineren, bijvoorbeeld in een premisse of conclusie binnen een afleiding, volgt volgens de logische wetten op semantisch niveau onmiddelijk parafrase reductie van de combinatie naar één logische geldigheidswaarde die weer overeenkomt met één logische relatie in

T

·(v ,d). Dit betekent dat premisse en conclusie elk per saldo (nogmaals: op semantisch niveau) maar één element bevatten. Daarom kunnen we logische afleidingen op semantisch niveau rekenen als proposities met twee enkelvoudige elementen.

2.7.

 

Minimale redeneringen, afleidingen (semantisch).



(1)

De verzameling redeneringen in hun minimale parafrase vorm.


Elk van de deelverzamelingen in de twee componenten van de afleiding kan dus altijd volgens logische wetten worden gereduceerd tot de kleinst mogelijke logisch-semantische inhoud: in dit geval logische relaties in een domein met d objecten.
Daarbij beschouwen we de componenten zoals gezegd in conjunctie.
We gaan voor het gemak uit van een binair systeem. Dit heeft altijd 2 waarden: valentie
(v

=

2 ).
Dit systeem kent een aantal logische relaties zoals we eerder zagen:
(t  

=

v ^(v ^d ) ).
De verzameling mogelijke redeneringen kan dus gereduceerd worden tot haar parafrase reduct versie op semantisch niveau.

R

·(v,d)[

T

]
De verzameling van alle mogelijke unieke minimale redeneringen c.q. gevolgtrekkingen op semantisch niveau.
(v d

|

(k1 m1 (

R

·(v,d)[

U

]
[k1,m1]
(

U

·(v,d)[k1] in conjunctie

U

·(v,d)[m1] in conjunctie );
(

Cj

(

U

·(v,d)[k1 ]

Cj

(

U

·(v,d) [m1] );
(

U

·(v,d)[k1]

syn

par-rdc

U

·(v ,d)[m1]

syn

par-rdc

);

par-rdc

(p1 q1 ( (

T

·(v,d)[p1]

T

·(v,d)[q1] );

R

·(v,d)[

T

]
[p1,q1] ;

R

·(v,d)[

T

]

:=

(p1 := 1,

..

u )
(q1 := 1,

..

u )

R

·(v,d)[

T

]
[p1,q1] ) ) );
De parafrase reduct versies van premisse en conclusie zullen elk dus bestaan uit precies één element uit elk van de oorspronkelijke deelverzamelingen k1, m1, uit

U

·(v,d).
Dit betekent dat de verzameling van alle mogelijke unieke minimale redeneervormen onder de parameters {v,d} wordt gevormd door een matrix
(v d

|

R

·(v,d )[

T

]

:=

(

T

·(v,d)

X

T

·(v,d) );

Omvang.


r t: Het totale aantal van alle mogelijke unieke minimale redeneringen c.q. gevolgtrekkingen.
De omvang van deze verzameling wordt uiteraard gevormd door het Cartesisch product (t·t).
r·(v,d)t

=

|

R

·(v,d)[

T

]

|

;

=

t ·(v,d)·2.

In een binair systeem.


Bijv., onder (v

=

2 );
uit (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt als aantallen afleidingsrelaties (t2

=

{ 16, 256, 65 536, 4 294 967 296, 1.844674407371 ·(10^19), 3.402823669209 ·(10^38), 1.157920892373 ·(10^77), 1.340780792994 ·(10^154), 1.797693134862 ·(10^308), 3.231700607131 ·(10^616),

..

} ).
De waarden r·(v,d)t komen goeddeels overeen met de reeksen A001146(d )^2;

=

A001146(d +1 ).

(2)

Evaluatie van redeneringen.


Uiteindelijk willen we weten of een redenering steekhoudend is, oftewel geldig.
Welke van de afleidingsrelaties uit de matrix

R

·(v,d)[

T

]
zijn nu geldig?
Elk element van de matrix

R

·(v,d)[

T

]
is als implicatie simpel op te lossen volgens de regels van de algemene waarheidswaardetabel.
(2.1)

Codering als binaire getallen.


Elk van de logische relaties in de componenten van

R

·(v,d)[

T

]
kan in het meest simpele logische systeem, propopositielogica (PPL), worden gecodeerd als binaire waarheidswaardepatroon.
Elk van deze waardepatronen is element van de verzameling (waardepatronen van) logische relaties

T

·(v,d)[k1].
Dit betekent, zoals we zagen, dat elk van deze binaire patronen een lengte heeft van:
b·(v,d)

=

v·^d.
(2.2)

Parafrase-reductie tot één binair getal.


De uitkomsten bestaan weer uit binaire waarheidswaardepatronen.
(2.3)

Interpretatie van de binaire uitkomst.


Regels voor interpretatie van een binair waarheidswaardepatroon:
(a) Niet alle bits staan op 0 of 1 : onbeslistheid, indefinitiet contingentie.
(b) Alle bits staan op 0 of 1 : beslistheid.
(b1) Alle bits staan op 0 : contradictie (onvervulbaarheid).
Alleen het geval indien 'waar impliceert onwaar' (d.w.z.

$

1

$

0 ).
(b2) Niet alle bits staan op 0, en evenmin op 1 : (definitiet) contingentie.
(b2.1) Niet alle bits staan op 1 : ongeldigheid (vooronderstelling, c.q. drogreden).
(b2.2) Niet alle bits staan op 0 : consistentie (vervulbaarheid).
(b3) Alle bits staan op 1 : validiteit.

(3)

Geldige redeneringen.


Het totale aantal van alle mogelijke unieke contradictoire redeneringen c.q. gevolgtrekkingen is simpelweg hetzelfde als dat van elke verzameling disjuncties: precies één.
Het totale aantal van alle mogelijke unieke consistente redeneringen c.q. gevolgtrekkingen is dus simpelweg r ·(v,d)t -1.

Omvang.


xt: Het totale aantal van alle mogelijke unieke valide redeneringen c.q. gevolgtrekkingen.
De formule voor het aantal valide afleidingsrelaties xt bij valentie v =2 en aantal objecten d is:
xt·(v,d)

=

(v +1)·^b ;

=

(v +1)·^(v·^d);

In een binair systeem.


Bijv., onder (v

=

2 );
uit (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
volgt als aantallen geldige implicaties:
{ 9, 81, 6561, 43046721, 1.853 ·(10 ^015), 3.4337 ·(10 ^030), 1.179 ·(10 ^061), 1.39 ·(10 ^122), 1.93 ·(10 ^244 ), 3.7339 ·(10 ^488), // .. } );
De waarden xt·(v,d) komen goeddeels overeen met de machten van 3 van de machten van 2. Zie A011764 in de OEIS.
Dezelfde reeks als percentages geldige implicaties:
{ 56.25, 31.64, 10.01, 1.00229, 0.01, 0.00001, 1.01822 ·(10 ^-012), 1.03677 ·(10 ^-030), 1.074897 ·(10 ^-062), 1.1554 ·(10 ^-124), .. } );

(4)

Tabel.


Hieronder volgt een tabel met de belangrijkste afmetingen van de hierboven genoemde verzamelingen.

Combinatorische explosie in logisch systeem (PPL)
Waarheidswaarden (valentie) v =2  (Binair systeem)
Unieke items
(objecten)
Digitaal Patroonlengte
(tekens)
Logische relaties
(formules)
Combinaties
van 2 formules
Valide implicaties
(aantal)
Valide implicaties
(pct.)
1
2
4
16
9 56.25%
2
4
16 256
81 31.65%
3
8
256
65536
6561
10.01%
4
16
65536
4294967296
43046721
1.002290163230%
5
32
4294967296
1.844674407371
·(10 019 [ 2])
1.853020188852
·(10 015 [ 2])
0.010045242576 74%
6
64
1.844674407371
·(10 019 [ 2])
3.402823669209
·(10 038 [ 2])
3.433683820293
·(10 030 [ 2])
0.000010090689 83316%
7
128
3.402823669209
·(10 038 [ 2])
1.157920892373
·(10 077 [ 2])
1.179018457774
·(10 061 [ 2])
1.018220213090
·(10 -012 [ 2])%
8
256
1.157920892373
·(10 077 [ 2])
1.340780792994
·(10 154 [ 3])
1.390084523771
·(10 122 [ 3])
1.036772402346
·(10 -030 [ 2])%
9
512
1.340780792994
·(10 154 [ 3])
1.797693134862
·(10 308 [ 3])
1.932334983229
·(10 244 [ 3])
1.074897014265
·(10 -062 [ 2])%
10
1024
1.797693134862
·(10 308 [ 3])
3.231700607131
·(10 616 [ 3])
3.733918487411
·(10 488 [ 3])
1.155403591277
·(10 -124 [ 3])%
100
1.267650600228 ·(10 30 [ 2])
10 381600854690 078004800107 713800
[ 30]
)
10 763201709380 156009600215 427600
[ 30]
)
10 604823044926 916660000603 060000
[ 30]
)
10 -158378664453 239349599612 367600
[ 28]
)%
1000
1.071508607186 279
·( 10 301 [ 3])
3.225562313751 201148898 088040
·( 10 300 [ 3])
6.451124627502 402297796176 080
·( 10 300 [ 3])
5.112395311035 022942430048 300
· 10 300 [ 3])
1.338729316467 379355366127 780
·(10 -298 [ 3])%
10000
1.995063116881
·(10 3010 [ 4])
10 (6.005738414240 562400144864 482
·10 ^3010 )

10 (1.201147682848 112480028972 896400
·10 ^3011 )

10 (9.518870175711 834000304730 005
·10 ^3010 )

10 (2.492606652769 290799984998 959
·10 ^-3008 )
%

Deze tabel laat zien hoe de combinatorische mogelijkheden in een simpel logisch systeem al gauw leiden tot een zoekruimte van astronomische proporties. Met 10000 items kun je bijvoorbeeld een aantal 'minimale redeneringen' maken (op semantisch niveau) waarvan het getal bestaat uit een aantal cijfers waarbij alleen al de lengte van het getal kan worden weergegeven met een exponent (decimaal logaritme) die op zijn beurt een lengte heeft van 3011 cijfers. Anders gezegd, niet het getal zelf is 3011 cijfers lang, maar de exponent waarmee je haar lengte weergeeft.

(5)

Ter vergelijking.


Om de bovenstaande getallen enigszins in perspectief te plaatsen volgen hieronder enkele voorbeelden van grote aantallen in de natuur (alle volgens tamelijk ruwe schattingen).

In het heelal.


• Het aantal clusters van sterrenstelsels: ca. 4 ·10 ^8.
• Het aantal sterrenstelsels in het heelal: ca. 10 ^11.
• Het aantal sterren per sterrenstelsel: ca. 10^8 tot 10^14.
• Het aantal sterren in 'ons' sterrenstelsel, de Melkweg: ca. 10^11.
• Het aantal sterren in het waarneembare heelal: ca. 10 ^22.
• Het aantal moleculen in het waarneembare heelal: ca. 10 ^80.

Op aarde.


• Het totale aantal vissen in de oceanen: ca. 3,5 ·10 ^9.
• Het aantal mieren op aarde: ca. 3,5 ·10 ^12.
• Het totale aantal zandkorrels op alle stranden op aarde: ca. 10 ^21.

In het menselijk lichaam.


• Het aantal cellen in het menselijk lichaam: ca. 10 ^14.
• Het aantal verschillende eiwitten die zijn op te bouwen uit 100 aminozuren: ca. 10 ^130.
Om er twee voorbeelden uit te lichten:
Met 5 items kun je al bijna zoveel -unieke, minimale- redeneringen maken als het totale aantal zandkorrels op alle stranden op aarde.
Met 7 items, de gemiddelde geheugencapaciteit van ons bewuste aandachtsvenster, kun je al bijna zoveel -unieke, minimale- redeneringen maken als er moleculen zijn in het waarneembare heelal.

Deze -letterlijk- astronomische getallen geven het niveau van complexiteit weer en daarmee beslisproblemen.
Daarbij helpt het niet om te denken aan een meer geavanceerd logisch systeem. Als algemene regel geldt: hoe geavanceerder het logische systeem, hoe meer expressief vermogen het heeft, maar hoe minder beslisvermogen. Met elke stap naar een meer geavanceerd logisch systeem, zoals modale logica, meerwaardige logica, predikatenlogica, enz., en ook zgn. 'fuzzy logica', nemen de aantallen, zoek-, complexiteits- en beslisbaarheidsproblemen enkel maar opnieuw explosief toe!
Zonder voldoende kennis en kunde van logische bewijsvoering en toetsing is het al nagenoeg onmogelijk om mogelijke redeneringen te beoordelen over meer dat twee items.


C.P. van der Velde © 2014, 2018.