Formele_logica_systeem_complexiteit_semantische

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 kenmerkendeeigenschap. 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 combinatiesvan 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 relatiestussen gegevens, dat wil zeggen de combinaties en afleidingen; en niet op de afzonderlijke gegevens (zoals directe waarnemingen en gevoelens). Ze gelden ook onafhankelijkvan de inhoud en de aardvan 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 ondenkbarevorm: 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 minimaleniveau'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 explosieftoenemen met elke trap van toenemende verfijning van het logische systeem dat we toepassen.

Logisch systeem op semantischniveau.

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 syntactischniveau.

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.

Toepasbaarin

PPL

en hoger.

D

^*: (referentieel) domeinof 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 domeinook 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 domeinuit éé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 oneindigis, worden onnoemelijk veel redeneringen over het domein in de praktijk onbeslisbaar.
Voor een domeindat zinvol is en hanteerbaar (manageable), geldt:

{ (d

=

|

D

^*_(mgb
)

|

);

≤

<

₀ ) }.

1.2. Waarden.

Algemeentoepasbaar 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 oneindigis, wordt vrijwel elke redenering over het domein in de praktijk onbeslisbaar.
Voor een waardenpaletdat zinnig is en hanteerbaar (manageable), geldt:

{ (v

=

|

V

^*_(mgb
)

|

);

≤

<

₀ ) }.

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*MAX(1,(r

*

n)) }.

M.a.w., hebben we voor een

PDL

systeem voldoende informatie over de parameters p, ren n , dan kunnen we aberekenen 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 vwaarden en delementen.
Ze geven het domeinweer op een observationeelniveau.
Op semantischniveau 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, universeeltoepasbare 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(v,d) : Het totale aantal mogelijke unieke objecttoestanden.

{

d ( h(v,d)

:=

|

H

^·(v,d)

|

;

:=

(

|

V

^·v

|

D

^·d

|

;

:=

*

d )_d, _v }.

In een binairsysteem.

Onder (v

=

2 ) geldt:

H

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

D

^·d.
De waarden h(2,d) komen overeen met de natuurlijke niet-negatieve even getallen. Zie reeks A005843(eerder M0985) in de On-line Encyclopedia of Integer Sequences (OEIS).

{

d( h(2,d)

:=

*

:=

A005843(d)

|

(offset0 ) )_d }.

Bijv., bij (d

=

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

..

} );
volgt (h(2,d)

=

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

..

} ).

Bereik.

Het getal h(v,d) blijft lineair (polynomiaal) in d.

≤

h(v,d)

<

₀ ).

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 conjunctecombinaties van alle objecten met hun specifieke waarden, dus verschillende objecttoestanden.
Ze geven het domeinweer op een louter beschrijvendniveau.
Op semantischniveau 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-kwadraat (Χ²), en varianten of afgeleiden daarvan, zoals correlatiecoëfficiënt, regressiecoëfficiënt, Student'st, F, Fisherz, 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(v,d) : Het totale aantal mogelijke unieke domeintoestanden.
Het getal b(v,d) komt overeen met het aantal herhalingsvariaties, oftewel, volgordevariaties met teruglegging c.q. herhaling, met omvang (lengte) d uit velementen.

{

d ( b(v,d)

:=

|

B

^·(v,d)

|

;

:=

_{(d1:=1, ..
d)}v ;

:=

v^{^d};

:=

b(v,d-1 )

*

v )_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 binairsysteem.

Onder (v

=

2 ) geldt:

B

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

P

- van

D

^·d.
In een binairsysteem vertegenwoordigt het aantal domein toestanden de hoeveelheid signaal, de signaalinhoud, of signaalcapaciteit, die wordt gemeten als het aantal domeinelementend in bits (binary digits).
De waarden b(v,d) komen in een binairsysteem overeen met de machten van 2. Zie reeks A000079 (eerder M1129, N0432) in de OEIS.

{

d( b(2,d)

:=

|

P

^·d

|

;

:=

b(2,d -1 )

*

:=

lg₂dbits;

:=

A000079(d)

|

(offset0 ) )_d }.

Bijv., bij (d

=

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

..

} );
volgt (b(2,d)

=

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

..

} ).

Bereik.

Het getal b(v,d) blijft exponentieel in d.

≤

b(v,d)

<

₀ ^{^₀} );

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 domeinweer op een analytischniveau.
Op semantischniveau 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(v,d): Het totale aantal mogelijke unieke logische relaties.
Het getal t(v,d) is het aantal volgordevariaties met teruglegging c.q. herhaling (herhalingsvariaties ) met omvang (lengte) b(v,d) uit velementen.

{

d ( t(v,d)

:=

|

T

^·(v,d)

|

);

:=

_{(b1:=1, ..
b(v,d
) )}v;

:=

|

B

^{·(v,b(v,
d))}

|

;

:=

v^{^|
B
^{·(v
,d)}|};

:=

v^{^b(v,d)};

:=

v^{^(v^{^d})}

:=

t(v,d -1 )

*

v ) _d, _v }.

In een binairsysteem.

Onder (v

=

2 ) geldt:

T

^·(v,d) is even groot als de power setvan de power setvan

D

^·d.
De waarden t(v,d) komen in een binairsysteem, overeen met de machten van 2 van de machten van 2. Zie reeks A001146 (eerder M1297, N0497) in de OEIS.

{

d( t(2,d)

:=

|

P

^·b(2,d)

|

;

:=

|

P

^{·|P
^·d|}

|

);

:=

t(2,d-1 )

*

:=

A001146(d)

|

(offset0 ) )_d }.

Bijv., bij (d

=

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

..

} );
volgt (t(2,d)

=

{ 4, 16, 256, 65536, 4294967296, 1.844674407370955 ·(10^{^19}), 3.402823669209385 ·(10^{^38}), 1.157920892373162 ·(10^{^77}), 1.340780792994260 ·(10 ^{^154}), 1.797693134862316 ·(10^{^308}),

..

} ).

Bereik.

Het getal t(v,d) blijft hyperexponentieel in d.

≤

t(v,d)

<

₀ ^{^(₀ ^{^
₀} )} );

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, samenhangendgeheel van alle mogelijke volgordes van (waarheids)waarden, oftewel (waarheids)waardepatronen t(v,d ), 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(v,d ) waardeconstanten. De laatste zijn te vergelijken met lettertekensof symbolen in geschreven taal.
De lengte b(v,d) 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 onderlingelogische relaties.

W

^·(v,d)_[T
]: 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 relatiein PPL			Logische relatiein PDL		Logische relatiein 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 ₁	¬¬ A ₁					0.50
4	1	0	1	0	A ₂	¬¬ A ₂					0.50
5	0	0	1	1	¬ A ₁	¬ A ₁					0.50
6	0	1	0	1	¬ A ₂	¬ A ₂					0.50
7	1	0	0	0	A ₁ A ₂	¬(¬ A ₁¬ A ₂)		x A [x]	¬x ¬ A [x]	A [x]	0.75
8	0	1	0	0	A ₁¬ A ₂	¬(¬ A ₁ A ₂)					0.75
9	0	0	1	0	¬ A ₁ A ₂	¬( A ₁¬ A ₂)					0.75
10	0	0	0	1	¬ A ₁¬ A ₂	¬( A ₁ A ₂)	A ₁\ A ₂	¬x A [x]	x ¬ A [x]	¬ A [x]	0.75
11	1	1	1	0	A ₁ A ₂	¬(¬ A ₁¬ A ₂)		x A [x]	¬x ¬ A [x]	A [ c _s]	0.25
12	1	1	0	1	A ₁¬ A ₂	¬(¬ A ₁ A ₂)	A ₁ A ₂				0.25
13	1	0	1	1	¬ A ₁ A ₂	¬( A ₁¬ A ₂)	A ₁ A ₂				0.25
14	0	1	1	1	¬ A ₁¬ A ₂	¬( A ₁ A ₂)	A ₁\| A ₂	¬x A [x]	x ¬ A [x]	¬ A [ c _s]	0.25
15	1	0	0	1	A ₁ A ₂	¬( A ₁# A ₂)					0.50
16	0	1	1	0	A ₁# A ₂	¬( A ₁ A ₂)					0.50

Omvang.

w(v,d)_t: Het totale aantal cellen in de bijbehorende waarheidswaardetabel.
Het getal w(v,d)_t wordt het product van het aantal rijen (domeintoestanden b(v,d)) en het aantal kolommen (toestandsrelaties t(v,d)).

{

d ( w(v,d)_t

:=

|

W

^{·(
2,d)}_t

|

;

:=

|

(

T

^*(v,d),

B

^*(v,d))

|

;

:=

(

|

T

^*(v,d)

|

*

|

B

^*(v,d)

|

);

:=

(

|

B

^*(v,b(v,d))

|

*

|

B

^*(v,d)

|

);

:=

b(v,d)

*

t(v,d);

:=

v^{^(v^{^d})}

*

v^{^d};

:=

v ^{^((v^{^d}) +d)} ) _d, _v }.

In een binairsysteem.

Onder (v

=

2 ) geldt:

{

d( w(2,d)_t

:=

|

W

^·(2,d)_t

|

;

:=

2 ^{^((2 ^{^d}) +d)} )_d }.

Bijv., bij (d

=

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

..

} );
volgt (w(2,d)_t

=

{ 8, 64, 2018, 1048576, 137438953472, 1.180591620717 ·(10 ^{^21}), 4.355614296588 ·(10^{^40}), 2.964277484475 ·(10^{^79}), 6.864797660131 ·(10 ^{^156}), 1.840837770099 ·(10^{^311}),

..

};
resp. in bytes(8-bits): { 1, 8, 256 ,131072 ,17179869184, 1.475739525897 ·(10^{^20}, 5.444517870735 ·(10 ^{^39}, 3.705346855594 ·(10^{^78}, 8.580997075163 ·(10^{^155}, 2.301047212624 ·(10 ^{^310},

..

} ).

NB. De waarden w(v,d)_t^·(2,d) komen niet voor als reeks in de OEIS.

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 semantischniveau 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(v,d): Het totale aantal mogelijke unieke combinaties van redeneerelementen.
Het getal u(v,d) is gelijk aan de som van alle mogelijke uniekeongeordende selecties (zonder interne herhaling) uit

T

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

U

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

{

d ( u(v,d)

:=

|

U

^·(v,d)

|

;

(

u1( (

U

^*_{[
u1]}

U

^·(v,d))

( (u(v,d)_[u1]

:=

|

U

^*_[u1]

|

)

(

t1( (t1

=

u( v,d)_[u1])

( (

U

^*_{[u1
]}

U

^·t1)

(

U

^·t1

U

^{·(v
,d)}) ) )_t1 ) ) )_u1 );

( u(v,d)

:=

_{(u1:=1, ..
u(v,
d) )} u(v,d)_[u1];

:=

_{(t1:=1, ..
t(v,
d) )} (

|

U^·t1

|

);

:=

_{(t1:=1, ..
t(v,
d) )}

binomial

(t(v,d), t1);

:=

|

T

^·(v,t(v,d))

|

;

:=

2^{^|
T
^·(v,d)
|};

:=

2^{^(v^{^(v^{^d})})} ) )_d, _v }.

In een binairsysteem.

Onder (v

=

2 ) geldt:

U

^·(v,d) is even groot als de power setvan de power setvan de power setvan

D

^·d.
Enkele waarden u(2,d) komen overeen met getallen in de reeks A051285.

{

d( u(2,d)

:=

|

P

^·t(v,d)

|

;

:=

|

P

^{·P
^{·b(
v,d)}|}

|

;

:=

|

P

^{·|P
^{·|
P
^{^d} |}|}

|

);

:=

2 ^{^A001146(d)};

:=

A001146(d+1 )

( (1

≤

3 )

( u(2,d)

:=

A051285(d+4 )

|

(offset1 ) ) )_d }.

Bijv., bij (d

=

{1, 2, 3, 4,

..

} );
volgt (u(2,d)

=

{ 16, 65536,
1.1579208923731619542357098500868790785327 ·(10^{^ 77}),
2.0035299304068464649790723515602557504478 ·(10^{^ 19728}),
3.1032805438632861402998911558636402031970 ·(10^{^ 1292913986}),
1.9069740116044733845522417467451879838889 ·(10^{^ 5.553023288523357132 ·(10^ 18)}),
5.4045967703464487690453355840188902868344 ·(10^{^ 1.0243519943873936375001210925010323270013 ·(10^
58)}),
3.7925849315209683683886667618408605094478 ·(10^{^ 3.4856892121032617929865715700930417996503 ·(10^
76)}),
1.5365619647315663399281284825759039148145 ·(10^{^ 4.0361523630141126896913151985426995150356 ·(10^
153)}),
2.3710362762239815690861934492953363891223 ·(10^{^ 5.4115955659277171970558682351758834358915 ·(10^
307)}),

..

} ).

Bereik.

Het getal u(v,d) blijft ultra-exponentieel in d.

≤

u(v,d)

<

2 ^{^(
₀ ^{^(₀ ^{^
₀} )} )} ).

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)

Redeneringenals 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 'premisseimpliceert 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 vwaarden over een domein met dobjecten 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)}_[k2] met lengte (omvang) l_[k2]elementen.

R

^·(v,d)_[k1,k2]: Een redenering van (een element van)

U

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

U

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

{

k2(

R

^{·(
v,d)}_[k1,k2]

(

U

^{·(
v,d)}_[k1]

U

^{·(v,
d)}_[k2]) )_k2, _k1, _d, _v }.

Bijv. (PPL):

{

d1( v1

=

2; d1

=

D

^·d1

=

{A, B, C, D};

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,k2]

:=

((A, (B

¬C) )

( ¬A

B), (C

¬D) ) )_k2, _k1 )_d1, _v1 }.

(2)

De verzamelingvan afleidingen.

R

^·(v,d)_[U
]: De verzameling van alle mogelijke unieke redeneringen c.q. gevolgtrekkingen op semantischniveau.

{

d (

R

^·(v,d)_[U
]

:=

_{(k1:=1, ..
u(v,d) )}

_{(k2
:=1, ..
u(v,d) )}

R

^·(v,d)_[U
]_[k1,k2] _k2, _k1 )_d , _v }.

Dit betekent dat de verzameling van alle mogelijke uniekeredeneervormen onder de parameters {v,d} wordt gevormd door een matrix:

{

d (

R

^·(v,d)_[U
]

:=

(

U

^·(v,d)

X

U

^·(v,d) ) )_d, _v }.

Omvang.

r(v,d)_U: Het totale aantal van alle mogelijke unieke redeneringen c.q. gevolgtrekkingen op semantischniveau.

De omvang van de verzameling wordt uiteraard gevormd door het Cartesisch product (u(v,d) ·u(v,d)).

{

d ( r(v,d)_U

:=

|

R

^{·(v
,d)}_[U
]

|

;

:=

u(v,d)^{^2};

:=

v^{^(2 *
t(v,d) )} )_d , _v }.

In een binairsysteem.

{

d( r(2,d)_U

:=

|

R

^·(2,d)_[U
]

|

;

:=

u(2,d)^{^2};

:=

2^{^(2 *
t(
2,d) )}

:=

)_d, _v }.

Bijv., bij (d

=

{1, 2, 3,

..

} );
volgt (r(2,d)_U

=

{ 256, 4294967296, 1.340780792994 ·(10^{^154}),

..

} ).

Complexiteitsklasse.

De verzameling

R

^·(v,d)_[U
]: blijft van hetzelfde complexiteitsniveau als

U

^·(v,d).

(2)

Afleidingen zijn op semantischniveau 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 semantischniveau 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 verzamelingredeneringen in hun minimaleparafrasevorm .

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 dobjecten.
Daarbij beschouwen we de componenten zoals gezegd in conjunctie.
We gaan voor het gemak uit van een binairsysteem. Dit heeft altijd 2 waarden: valentie

=

2 ).

Dit systeem kent een aantal logische relaties zoals we eerder zagen:

(t(v,d)

=

v^{^(v^{^d})}).

De verzameling mogelijke redeneringen kan dus gereduceerd worden tot haar parafrase reductversie op semantischniveau.

R

^·(v,d)_[T
] De verzameling van alle mogelijke unieke minimale redeneringen c.q. gevolgtrekkingen op semantischniveau.

(v d

|

(

k2(

R

^·(v,d)_[U
]_{[k1,k2
]}

(

U

^·(v,d)_[k1] in conjunctie

U

^·(v,d)_[k2] in conjunctie );

(

Cj

(

U

^·(v,d)_{[k1
]}

Cj

(

U

^·(v,d)_[k2]);

(

U

^·(v,d)_[k1]_syn
par-rdc

U

^{·(v,d
)}_[k2]_syn
par-rdc);

_par-rdc (

q1( (

T

^·(v,d)_[p1]

T

^·(v,d)_[q1]);

R

^·(v,d)_[T
]_[p1,q1] ;

R

^·(v,d)_[T
]

:=

_{(p1:=1, ..
u(v,d) )}

_{(q1:=1, ..
u(v,d) )}

R

^·(v,d)_[T
]_[p1,q1] ) ) );

De parafrase reductversies van premisseen conclusie zullen elk dus bestaan uit precies één element uit elk van de oorspronkelijke deelverzamelingen k1, k2, uit

U

^{·(v,d
)}.

Dit betekent dat de verzameling van alle mogelijke uniekeminimaleredeneervormen 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(v,d)_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(v,d) ·t(v,d)).

{

d ( r(v,d)_T

:=

|

R

^{·(v
,d)}_[T
]

|

;

:=

t(v,d)^{^2};

:=

v^{^(2 *
b(v,d) )} )_d , _v }.

In een binairsysteem.

{

d( r(2,d)_T

:=

|

R

^·(2,d)_[T
]

|

;

:=

t(2,d)^{^2};

:=

t(2,d+1);

:=

2^{^(2 *
b(2,d) )};

:=

A001146(d)^{^2};

:=

A001146(d+1 )

|

(offset 0 ) )_d }.

Bijv., bij (d

=

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

..

} );
volgen aantallen tupelsvoor afleidingsrelaties (r(2,d)_T

=

{ 16, 256, 65536, 4294967296, 1.844674407370954 ·(10^{^19}), 3.402823669209384 ·(10^{^38}), 1.157920892373162 ·(10 ^{^77}), 1.340780792994260 ·(10^{^154}), 1.797693134862316 ·(10^{^308} ), 3.231700607131101 ·(10^{^616}),

..

} ).

Complexiteitsklasse.

De verzameling

R

^·(v,d)_[T
]: blijft van hetzelfde complexiteitsniveau als

T

^·(v,d).

(2)

Evaluatievan 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 implicatiesimpel op te lossen volgens de regels van de algemene waarheidswaardetabel.

Zie boven, 2.4. Waarheidswaardetabel.
Zie ook: Principes van Logische bewijsvoering; (4.1a) Methode van Waarheidswaardentabellen.
En: Bewijsmethode voor Propositielogica: de Waarheidswaardentabel-methode .

(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)

=

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.

$

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)

Geldigeredeneringen.

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

Omvang.

x_T: Het totale aantal van alle mogelijke unieke valideredeneringen c.q. gevolgtrekkingen.
De formule voor het aantal valide afleidingsrelaties x_T bij valentie v=2 en aantal objecten dis:

x_T^·(v,d)

:=

(v+1)^{·^b
(v,d)};

:=

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

In een binairsysteem.

De waarden x_T^·(2,d) komen goeddeels overeen met de machten van 2 van de machten van 3. Zie A011764 in de OEIS .

bij (d

=

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

..

} );
volgen als aantallen geldige implicaties:
{ 9, 81, 6561, 43046721, 1.853020188851841 ·(10 ^{^015}), 3.433683820292512 ·(10 ^{^030}), 1.179018457773858 ·(10 ^{^061}), 1.390084523771447 ·(10 ^{^122}), 1.932334983228892 ·(10 ^{^244}), 3.733918487410200 ·(10 ^{^488}), .. } );

Dezelfde reeks als percentages geldige implicaties:

56.25 31.640625 10.011291503906250 1.0022595757618542 1.0045242572063333 ·(10 ^{^-002}) 1.0090689833159348 ·(10 ^{^-006}) 1.0182202130902540 ·(10 ^{^-014}) 1.0367724023455629 ·(10 ^{^-030}) 1.0748970142653895 ·(10 ^{^-062}) 1.1554035912766489 ·(10 ^{^-126}) .. } );

Complexiteitsklasse.

De verzameling

X

^·(v,d)_[T
]: blijft van hetzelfde complexiteitsniveau als

T

^·(v,d).

(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)
Uniekeitems (objecten)	Digitaal Patroonlengte (tekens)	Logische relaties (formules)	Combinaties van 2 formules	Valide implicaties (aantal)	Valide implicaties (pct.)
d	b(v,d)	t(v,d)	r(v,d)_T	x(v,d)_T	%(x/t)(v,d)_T
1	2	4	16	9	56.25%
2	4	16	256	81	31.640625%
3	8	256	65536	6561	10.01129150391%
4	16	65536	4294967296	43046721	1.002259575762%
5	32	4294967296	1.844674407371 ·(10 ^{^019[ 2]})	1.853020188852 ·(10 ^{^015[ 2]})	1.004524257206 ·(10 ^{^-002})%
6	64	1.844674407371 ·(10 ^{^019[ 2]})	3.402823669209 ·(10 ^{^038[ 2]})	3.433683820293 ·(10 ^{^030[ 2]})	1.009068983316 ·(10 ^{^-006})%
7	128	3.402823669209 ·(10 ^{^038[ 2]})	1.157920892373 ·(10 ^{^077[ 2]})	1.179018457774 ·(10 ^{^061[ 2]})	1.018220213090 ·(10 ^{^-014[ 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.733918487410 ·(10 ^{^488[ 3]})	1.155403591277 ·(10 ^{^-124[ 3]})%
100	1.267650600228 229401496703 205376 ·(10 ^{^030[ 2]})	2.285367694229 514·(10 ^{^381600854690 147056244358 827360[ 30]})	5.222905497827 925397894108 676196 ·(10 ^{^763201709380 294112488717 654720[ 30]})	2.561263804102 8273 ·(10 ^{^604823044927 026018840529 136136[ 30]})	4.903906082865 164390530139 22·(10 ^{^-158378664453 268093648188 518583 [ 30]}) %
1000	1.071508607186279 ·( 10 ^{^301[ 3]})	3.225562313751 201148898088 040 ·( 10 ^{^300[ 3]})	6.451124627502 402297796176 080 ·( 10 ^{^300[ 3]})	5.112395311035 022942430048300 ·( 10 ^{^300[ 3]})	1.338729316467 379355366127780 ·( 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.492606652769290799984998 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 itemskun je bijvoorbeeld een aantal 'minimale redeneringen' maken (op semantisch niveau ) waarvan het getal bestaat uit een aantal cijfers waarbij alleen al de lengtevan 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.

• De lichtsnelheid (in vacuüm) in kilometers per seconde: 2,99792458 *10^{^5}.
• Een astronomische eenheid (AE, internationaal au of ua) in kilometers: 1,495978707 *10^{^8}.
• Een lichtjaar in kilometers: ca. 9,46 *10^{^12}.