Gebruiker:Otto ter Haar/logica

Typografie

Sommige webbrowsers geven de symbolen ∅, ≢, ⊤, ⊡ en ⊢ niet of verminkt weer. Soms maakt het verschil of deze symbolen in een kader staan:

∅, ≢, ⊤, ⊡, ⊢

• Internet Explorer 9.0 geeft deze symbolen correct weer.
• Chrome 18 geeft de symbolen correct weer.
• Firefox 12.0 geeft het symbool ≢ enigszins verminkt weer.
• Opera 11.64 geeft de symbolen in de gewone tekst goed weer. In een kader zijn ze wat kleiner.
• Safari 5.1 geeft de symbolen enigszins verminkt en minder goed leesbaar weer zowel in de gewone tekst als wanneer het symbool in een kader staat.

Inleiding

Taal

Mensen communiceren met behulp van taal. Taal kan verschillende verschijningsvormen hebben: lichaamstaal, gebaar, spraak, schrift.

Lichaamstaal

Lichaamstaal is de oudste taal: ouder dan de mens als soort zelf. Het is voor een deel aangeboren en veel dieren communiceren met lichaamstaal.

Gebaar en spraak

Gebaren zijn van recentere datum en komen alleen bij mensen voor al is het wel aan mensapen te leren. Gebaren berusten op conventie. Bepaalde bewegingen of houdingen hebben in een sociale gemeenschap een betekenis ontwikkeld. Spraak komt ook alleen bij mensen voor en is ook heel oud. Ik denk dat er eerst gebaren waren die vervolgens ondersteund of bekrachtigd werden met stemgeluid, dat zich vervolgens ontwikkelde tot spraak. De wetenschap die het ontstaan van taal bestudeert is de glottogonie. De oudste fossielen waarover consensus bestaat dat ze de resten zijn van individuen van de soort homo sapiens en niet van een andere mensachtige zijn ongeveer 200.000 jaar oud. De oudste cultuurschatten, zoals tekeningen of beeldjes, zijn veel jonger: dat begint ongeveer 50.000 jaar geleden. Ik denk dat er toen pas gesproken taal ontstond: taal is het werktuig wat de mens in staat stelt cultuur te ontwikkelen. De eerste mensen hadden dus geen spraak. Hoewel ze er anatomisch toe in staat waren hadden ze dat nog niet ontwikkeld. Dat duurde 150.000 jaar. Toen een menselijke stam het werktuig van de gesproken taal eenmaal had ontwikkeld ontstond de mogelijkheid cultuur op te bouwen.

Schrift

Het schrift is pas recent ontstaan. Veel talen kenden tot in de vorige eeuw geen schrift, zoals het Zoeloe. De eerste schriften ontstonden zo'n 5000 jaar geleden. Ik denk dat het een gevolg is van de domesticatie van dieren en planten. Volken die leefden als jagers en verzamelaars ontwikkelden wellicht geen schrift omdat ze het niet nodig hadden in hun cultuur. Waar veeteelt en landbouw ontstaat ontwikkelt zich bezit, eigendom, dat verder gaat dan wat een mens in zijn handen houdt. Daarmee ontstond ook de behoefte om die conventie van bezit vast te leggen. Daar is schrift in tegenstelling tot spraak geschikt voor. Niettemin kenden de Zoeloes wel landbouw, dus een voldoende voorwaarde is het niet. Ik ken geen voorbeeld van een volk dat geen landbouw, maar wel een schrift heeft. Deze volken, zoals de Inuit, kregen pas een schrift toen ze gekoloniseerd werden.

Natuurlijke en formele talen

Dit onderscheid is moeilijk uit te leggen, omdat er volgens mij geen wezenlijke verschillen zijn. Zowel natuurlijke als formele talen zijn resultaten van menselijke inventiviteit. Beide veranderen als ze veel gesproken of geschreven worden, omdat ze mee evolueren met de samenleving waarin ze functioneren. De Nederlandse taal, zoals getest bij het Groot Dictee der Nederlandse Taal, is een formele taal met een reguliere grammatica, gevormd door het Groene Boekje en het woordenboek Van Dale. Het verschil met een formele taal is dat de regels van de Nederlandse Taalunie alleen de spelling van de woorden vastlegt en niet de zinsbouw. Voor de zinsbouw zijn wel regels geformuleerd in de grammatica van de Nederlandse taal, maar deze is beschrijvend van aard en heeft niet de bedoeling om a priori vast te leggen wat een correct geformuleerde Nederlandse zin is. Bij een formele taal is die ambitie er wel: de syntaxis van een formele taal legt vast wat correct geformuleerde formules zijn. Formules die daar niet volledig aan voldoen maken geen deel uit van de formele taal. De syntaxis brengt met haar productieregels de formele taal voort.

Terminologie en formele taal

We beschrijven een formele taal met behulp van begrippen en termen uit de taalkunde. Omdat formele en natuurlijke talen veel van elkaar verschillen krijgen deze uit de taalkunde van natuurlijke talen geleende begrippen en termen vaak een iets andere betekenis. Bij een formele taal is het begrip grammatica gedefinieerd en het begrip syntaxis niet. In de praktijk is de betekenis nagenoeg gelijk al is het begrip grammatica iets meer omvattend. Met syntaxis worden de productieregels van de formules aangeduid wat mooi aansluit met het begrip zinsbouw, dat in een natuurlijke taal synoniem is met syntaxis. Zinsbouw kan zo in een formele taal uitgelegd worden als de constructie van formules. Formules zijn de zinnen van de formele taal. Termen zijn de woorden van de formele taal.

We maken in een formele grammatica onderscheid tussen eindsymbolen en metasymbolen. Eindsymbolen zijn symbolen die deel uit maken van de formele taal. Metasymbolen zijn hulpsymbolen om grammaticaal correcte termen en formules te maken. Grammaticaal correcte termen en formules worden afgeleid met behulp van syntactische axioma's en afleidingsregels. Deze regels vormen de syntaxis. Metavariabelen zijn metasymbolen: het zijn plaatshouders voor eindsymbolen in schema's van afleidingsregels of axioma's.

Atomen zijn de kleinste, ondeelbare, formules uit de taal. Proposities zijn eenvoudige formules, opgebouwd uit atomen en propositionele connectieven.

We maken onderscheid tussen formele syntaxis en contingente syntaxis. De formele syntaxis bestaat uit axioma's en afleidingsregels die uitsluitend een syntactische rol spelen en geen andere informatie bevatten dan gegevens over de syntactische eigenschappen van de formele taal. De formele syntaxis brengt de syntactische logica voort. De syntactische logica is een formele hulptaal voor de contingente logica. De contingente syntaxis bestaat uit axioma's en afleidingsregels die de begrippen beschrijven waarover we stellingen willen kunnen afleiden. Hierin bevindt zich de informatie welke we met een formele taal en een geaxiomatiseerd systeem trachten bloot te leggen.

We moeten een formele taal scheppen, te beginnen met de syntaxis voor de cijfers die gebruikt worden in de indices van de variabelen. Het scheppen van een formele taal verschaft ons de mogelijkheid een redenering in die taal weer te geven. Een natuurlijke taal, zoals de Nederlandse taal, is daar minder geschikt voor dan een formele taal, die daar specifiek voor is toegerust. Omdat we deze formele taal ook gebruiken om syntactische objecten, zoals indices, variabelen en formules, op te bouwen, gebruiken we formules waarvan we de precieze definitie pas later formuleren.

Het doel van dit systeem, eerste orde predikatenlogica, is om als middel te dienen om stellingen te bewijzen. Een bewijs is een boom van stellingen, die via afleidingsregels met elkaar verbonden zijn. De bladeren van de boom zijn de hypothesen en de stam van de boom is de stelling die het resultaat is van het bewijs.

Afleidingsregels bestaan uit één of meer stellingen boven een streep, dit zijn de premissen of voorwaarden van de regel, en één stelling onder die streep. Die laatste is de conclusie of het gevolg van de regel. Een axioma is een bijzonder geval van een afleidingsregel, zonder premisse, maar met alleen een conclusie.

Ariteit van symbolen

Sommige eindsymbolen worden altijd gevolgd door één of meer andere symbolen. Deze eindsymbolen noem ik syntactische operatoren en de syntactische objecten die er op volgen zijn de argumenten van de operator. Het minimale aantal symbolen dat moet volgen op een symbool is de ariteit van het symbool. Een eindsymbool met ariteit nul noem ik een gesloten eindsymbool. In de praktijk zijn er alleen symbolen met ariteit nul, één, twee of drie. Dit maakt dat elk symbool van de formele taal één van de vier volgende vormen heeft:

• S₀
• S₁.
• S₂..
• S₃...

Hierbij is S₀ een metasymbool voor een eindsymbool met ariteit nul; S₁ het metasymbool voor een syntactische operator met ariteit één; S₂ het metasymbool voor een syntactische operator met ariteit twee en S₃ het metasymbool voor een syntactische operator met ariteit drie. Een syntactische operator die geen eindsymbool met ariteit nul is noem ik een operator met positieve ariteit. Het metasymbool . is een argument van de voorafgaande syntactische operator en bestaat op zijn beurt weer uit gesloten eindsymbolen of syntactische operatoren met argumenten. Punten hoeven onderling niet identiek te zijn en kunnen zelfs tot verschillende categorieën behoren. De punten zijn wel gesloten, in die zin dat de resterende ariteit nul is.
Syntactische operatoren met een positieve ariteit kunnen onderscheiden worden naar de syntactische categorieën waar ze op werken.

Strings en snaren

Een rij symbolen heet in de informatica een string. Onder een snaar versta ik een string waarvan het eerste symbool van de propositionele categorie is en de daaropvolgende symbolen van de syntactische categorie zijn die is voorgeschreven door de voorafgaande symbolen met positieve ariteit.

De ariteit van een snaar kun je definiëren als het aantal symbolen wat nog op de snaar moet volgen om de symbolen in de snaar voldoende argumenten te geven. Er geldt:

lengte van een snaar = het aantal symbolen waar de snaar uit bestaat

ariteit van een snaar = 1 + de som van de ariteiten van de symbolen in de snaar - de lengte van de snaar

Een snaar met ariteit nul noem ik een gesloten snaar.
Een snaar met positieve ariteit noem ik een open snaar.

De lege snaar

Een snaar bestaande uit nul symbolen is de lege snaar en wordt aangeduid met ε. Er geldt:

lengte(ε) = 0

ariteit(ε) = 1

De lege snaar is dus open.

Syntactische categorieën

Symbolen kunnen tot verschillende syntactische categorieën behoren. Voorbeelden van syntactische categorieën zijn:

nummer	naam	type
1	categorieën	propositioneel
2	cijfers	preliminair
3	indices	preliminair
4	constanten	parametrisch
5	variabelen	parametrisch
6	termen	parametrisch
7	functies	parametrisch
8	atomen	propositioneel
9	predicaten	propositioneel
10	relaties	propositioneel
11	connectieven	propositioneel
12	operaties	propositioneel
13	proposities	propositioneel
14	parameters	intermediair
15	halftermen	intermediair
16	halfformules	intermediair
17	kwantoren	propositioneel
18	formules	propositioneel
19	contexten	intermediair
20	stellingen	propositioneel

Er zijn verschillende typen categorieën: een syntactisch object van een propositionele categorie kan waar of onwaar zijn; een object van een parametrische categorie kan gebonden worden door een kwantor; een object van een preliminaire categorie is zelf nooit een eindsymbool, maar een onderdeel van een eindsymbool; een object van een intermediaire categorie is een onderdeel van een propositionele categorie die zelf niet waar of onwaar kan zijn (en dus niet propositioneel is).

Symbolen

• Categorieën: categorieën, cijfers, indices, constanten, variabelen, termen, functies, atomen, predicaten, relaties, connectieven, operaties, proposities, parameters, halftermen, halfformules, kwantoren, formules, contexten, stellingen
• Relaties tussen twee objecten: ≡, ≢
• Operatie op drie objecten: [/]
• Metavariabelen voor categorieën: α, β

symbool	naam	categorie	ariteit	argument1	argument2	argument3	waarde	notatie
categorieën	categorieën	categorieën	0					categorieën
cijfers	cijfers	categorieën	0					cijfers
indices	indices	categorieën	0					indices
constanten	constanten	categorieën	0					constanten
variabelen	variabelen	categorieën	0					variabelen
termen	termen	categorieën	0					termen
functies	functies	categorieën	0					functies
atomen	atomen	categorieën	0					atomen
predicaten	predicaten	categorieën	0					predicaten
relaties	relaties	categorieën	0					relaties
connectieven	connectieven	categorieën	0					connectieven
operaties	operaties	categorieën	0					operaties
proposities	proposities	categorieën	0					proposities
parameters	parameters	categorieën	0					parameters
halftermen	halftermen	categorieën	0					halftermen
halfformules	halfformules	categorieën	0					halfformules
kwantoren	kwantoren	categorieën	0					kwantoren
formules	formules	categorieën	0					formules
contexten	contexten	categorieën	0					contexten
stellingen	stellingen	categorieën	0					stellingen
≡	identiek	relaties	2	α	α		proposities	.≡.
≢	niet identiek	relaties	2	α	α		proposities	.≢.
[/]	substitutie	operaties of functies	3	α	β	β	α	.[./.]

De argumenten van ≡ en ≢ moeten van dezelfde categorie (in dit geval aangeduid met α) zijn.

Substitutie

Het tweede en derde argument van een substitutie moeten van dezelfde categorie zijn (in bovenstaande tabel β). Het eerste argument is de substitutie-basis, het tweede argument is de substituens en het derde argument het substituendum. In de substitutie-basis vervangt de substituens elke instantie van het substituendum.

Prefix- en infixnotatie

Het is gebruikelijk om de relaties ≡.. en ≢.. in de infixnotatie te schrijven. Dat wil zeggen dat het symbool van de relatie met ariteit twee tussen het eerste en tweede argument in staat. Dus .≡. in plaats van ≡.. en .≢. in plaats van ≢..

De gebruikelijke notatie .[./.] van de substitutieoperatie [/]... is een combinatie van prefix (er vóór) en infix (er tússen). De volgorde van de argumenten blijft bij de traditionele notaties ongewijzigd.

Metasymbolen

• Metavariabelen voor eindsymbolen met ariteit nul: R₀, S₀, T₀
• Metavariabele voor syntactische operator met ariteit één: S₁
• Metavariabele voor syntactische operator met ariteit twee: S₂
• Metavariabele voor syntactische operator met ariteit drie: S₃
• Metavariabelen voor categorieën: α, β, γ
• Metavariabele voor een syntactisch object: .
• Metavariabelen voor een gesloten syntactisch object (proposities en formules of bestanddelen daarvan): U, V, W, X, Y, Z
• Metavariabelen voor een gesloten propositioneel syntactisch object (proposities en formules): P, Q

metasymbool	naam	categorie	ariteit	argument1	argument2	argument3
R0		atomen of constanten of variabelen	0
S0		atomen of constanten of variabelen	0
T0		atomen of constanten of variabelen	0
S1		predicaten of functies	1	α
S2		relaties (connectieven) of functies	2	α	β
S3		operaties of functies	3	α	β	γ
α		categorieën	0
β		categorieën	0
γ		categorieën	0
δ		categorieën	0
ζ		categorieën	0
.	punt		0
U		α	0
V		β	0
W		γ	0
X		α	0
Y		β	0
Z		γ	0
P		proposities of formules	0
Q		proposities of formules	0

De . is het enige metasymbool dat niet identiek aan zichzelf is. Het is een plaatshouder voor enig syntactisch object van de juiste categorie met ariteit nul. Wat de categorie is hangt af van de operator die aan de punt voorafgaat.

Voorbeelden en toelichting

• voorbeeld 1
• voorbeeld 2

Identiteits- en substitutieaxioma's

Een syntactische relatie die elke formele taal heeft is de identiteitsrelatie. Het symbool voor deze relatie is ≡ en de ariteit is twee.

Een operatie die noodzakelijk is bij een formele taal die kwantoren bevat is de substitutieoperatie. Dit is een ternaire operatie en noteren we als .[./.]

Voor het formuleren van sommige substitutieaxioma's hebben we de niet-identiekrelatie nodig. Deze relatie heeft ariteit twee en noteren we met ≢

Reflexiviteit van de identiteitsrelatie

Voor elk eindsymbool S₀ geldt dat het identiek is aan zichzelf:

______ _≡RS0

S₀ ≡ S₀

Congruentie van relaties en functies met betrekking tot de identiteitsrelatie

Voor elke operator met positieve ariteit geldt dat deze congruent is met betrekking tot de identiteitsrelatie.

Als S₁ een predicaat of unaire functie is en U en X objecten van de syntactische categorie waar S₁ op werkt (in de tabel hierboven noemen we die categorie α) dan geldt:

      U ≡ X       _≡S1

S₁(U) ≡ S₁(X)

als S₂ een binaire relatie of binaire functie is:

          U ≡ X          _≡S2L

S₂(U,V) ≡ S₂(X,V)

          V ≡ Y          _≡S2R

S₂(U,V) ≡ S₂(U,Y)

als S₃ een ternaire relatie of ternaire functie is:

              U ≡ X              _≡S3L

S₃(U,V,W) ≡ S₃(X,V,W)

              V ≡ Y              _≡S3M

S₃(U,V,W) ≡ S₃(U,Y,W)

              W ≡ Z              _≡S3R

S₃(U,V,W) ≡ S₃(U,V,Z)

Identiteitseliminatie

We kunnen de identiteitsrelatie elimineren met behulp van:

P   P ≡ Q _≡E

Q

Inductie naar de opbouw

Een propositie of formule P kan bewezen worden door hem af te leiden voor elke toegestane constructie.

P[S₀/U]     P[X/U] ⊢ P[S₁(X)/U]     P[Y/U]+P[X/U] ⊢ P[S₂(X,Y)/U]     P[Z/U]+P[Y/U]+P[X/U] ⊢ P[S₃(X,Y,Z)/U] _Inductie

P

Met inductie naar de opbouw van een formule kan bewezen worden dat de identiteitsrelaties ook gelden voor operatoren met postieve ariteit.

Symmetrie van de identiteitsrelatie

We kunnen nu afleiden dat de identiteitsrelatie symmetrisch is. In de eerste stap (≡≡L) wordt de congruentieregel op de identiteitsrelatie zelf toegepast (met ≡ als instantie van S₂).

______ _≡RS0              S₀ ≡ T_{0          ≡≡L}

S₀ ≡ S₀           (S₀ ≡ S₀) ≡ (T₀ ≡ S₀) _≡E

T₀ ≡ S₀

De afgeleide symmetrieregel luidt:

S₀ ≡ T_{0 ≡S}

T₀ ≡ S₀

Transitiviteit van de identiteitsrelatie

Hier leiden we af dat de identiteitsrelatie transitief is:

          S₀ ≡ T_{0          ≡≡R}

R₀ ≡ S₀       (R₀ ≡ S₀) ≡ (R₀ ≡ T₀) _≡E

R₀ ≡ T₀

De afgeleide transitiviteitsregel luidt:

R₀ ≡ S₀      S₀ ≡ T_{0 ≡T}

   R₀ ≡ T₀

Een relatie die reflexief, symmetrisch en transitief is heet een equivalentierelatie.

Symmetrie van de niet-identiekrelatie

Voor elk paar eindsymbolen S₀,T₀ geldt dat de niet-identiekrelatie symmetrisch is:

S₀ ≢ T_{0 ≢S}

T₀ ≢ S₀

Substitutie

Lees U[V/W] als "substitueer in substitutie-basis U de substituens V voor het substituendum W". Voor de substitutieoperator [/] gelden de volgende syntactische wetten:

    V ≡ W     _/0

U[V/W] ≡ U

    U ≡ W     _/1

U[V/W] ≡ V

    S₀ ≢ W     _/S0

S₀[V/W] ≡ S₀

          S₁(X) ≢ W           _/S1

S₁(X)[V/W] ≡ S₁(X[V/W])

                S₂(X,Y) ≢ W                 _/S2

S₂(X,Y)[V/W] ≡ S₂(X[V/W],Y[V/W])

                      S₃(X,Y,Z) ≢ W                       _/S3

S₃(X,Y,Z)[V/W] ≡ S₃(X[V/W],Y[V/W],Z[V/W])

Overloading

Voor de identiteitsrelaties van cijfers, indices, termen, formules en contexten gebruiken we hetzelfde symbool. Uit de formule waarin het symbool staat blijkt welk relatie bedoeld wordt. Deze werkwijze om aan een symbool meerdere functies toe te kennen heet overloading. Er is ook overloading bij het symbool voor niet-identiek zijn en bij het substitutiesymbool. In beide gevallen wordt hetzelfde symbool bij termen en bij formules gebruikt. Bovendien wordt het niet-identiek symbool bij cijfers en indices gebruikt. Het verschil blijkt steeds uit de gehele formule. Verder hebben we bij formules twee vormen van substitutie: substitutie van termen en substitutie van subformules. Ook bij metavariabelen komt overloading voor: het symbool c is zowel metavariabele voor een cijfer als voor een constante.

Ter illustratie een tabel met de benutting van het Latijnse alfabet voor metavariabelen.

metasymbool	categorie	ariteit
a	atomen	0
b
c	cijfers	0
d	cijfers	0
e	cijfers	0
f	functies	1, 2
g	functies	1, 2
h
i	indices	0
j	indices	0
k	indices	0
l
m
n
o
p	proposities	0
q	proposities	0
r	proposities	0
s	termen	0
t	termen	0
u	termen	0
v	termen	0
w	variabelen	0
x	variabelen	0
y	variabelen	0
z	variabelen	0

• Terug naar de inhoudsopgave
• Verder naar cijfers
• Verder naar termen
• Verder naar formules met kwantoren
• Verder naar logische wetten