Logische Methoden voor KI
Aantekeningen en regels per hoofdstuk voor het eindtentamen
Hoofdstuk 1 – Logica en AI
Een inferentie is het proces van het afleiden van een conclusie of inzicht op basis van informatie,
zonder dat die expliciet wordt vermeld.
Deductieve inferentie is een manier van redeneren waar specifieke conclusies worden afgeleid uit
algemene premissen. Als de premissen waar zijn dan is de conclusie noodzakelijkerwijs ook waar.
Inductieve inferentie aan de andere kant leidt algemene conclusies af uit specifieke observaties. De
conclusie is waarschijnlijk waar, maar niet gegarandeerd. Omdat inductie gebaseerd is op het
herkennen van premissen of regelmatigheden.
Een redenering is deductief geldig (⊨) Als de conclusie noodzakelijkerwijs volgt uit de premissen.
Als de premissen waar zijn, kan de conclusie niet onwaar zijn. Een redenering is inductief geldig (∣≈)
als de conclusie waarschijnlijk volgt uit de premissen. De conclusie is gebaseerd op waarnemingen of
patronen, maar er is zeker geen garantie dat deze waar is. De logica is gebaseerd op waarschijnlijkheid
in plaats van zekerheid. Inductie is een krachtig hulpmiddel om waarschijnlijkheden te schatten en
generalisaties te maken, maar het blijft vatbaar voor fouten en vereist flexibiliteit om nieuwe
informatie te verwerken.
Dan heb je nog systeem 1 denken versus systeem 2 denken. Systeem 1 denken is snel, automatisch
intuïtief en onbewust. Voorbeelden zijn gezichten herkennen, zien of het ene object groter is dan de
ander en simpele berekeningen uitvoeren zoals 5+7. Systeem 2 denken is traag, logisch, berekenend
en weloverwogen. Voorbeelden zijn het tellen van het aantal As in een tekst, een logische puzzel
oplossen en complexere berekeningen uitvoeren zoals 432 x 441. LLMs, zoals ChatGPT zijn goed in
systeem 1 denken, wat betekent dat ze snel patronen herkennen en intuïtieve antwoorden genereren.
Echter, voor systeem 2 denken, zijn ze niet zo goed. Omdat deze taken bewuste, trage en
systematische redenering vereisen.
Hoofdstuk 2 – Geldige inferentie
Een inferentie van de vorm modus ponens ziet er zo uit: A → B, A ⊨ B. Dit wil zeggen dat als je
twee afzonderlijke stukken informatie samenvoegt, Als A dan B en de premisse A, je geldig de
conclusie B mag afleiden.
Het basisgereedschap dat we zullen gebruiken heet een semantisch model. Dit is een afbeelding van
een mogelijk redeneerscenario. Als we naar een model kijken, kunnen we ons afvragen of een
bepaalde zin A, waar of onwaar is in dit model. Elk model geeft een antwoord. Het kent een
definitieve waarheidswaarde toe aan elke zin.
Voor elke zin A in onze formele taal, schrijven we [A] om te refereren aan een set modellen waar die
zin waar is. Met deze notatie kunnen we praten over relaties tussen sets modellen. [A] en [B]voor twee
willekeurige zinnen A en B. Wanneer er elementen van een set ook in een andere set zitten, dan
zeggen we dat er een subset relatie is tussen die twee sets en schrijven we A ⊆ B. Deze relatie is een
goede eerste stap om deductieve validiteit te definiëren: als in elk mogelijk model M waarin A waar is,
ook B waar is, dan is de inferentie van A naar B geldig. Het is noodzakelijk waarheid bewarend.
Een intersectie (X∩Y) van twee sets verwijst naar de elementen die in beide verzamelingen
voorkomen. Het beschrijft het overlappende deel. Een logische conjunctie verbindt twee beweringen
A en B in een samengestelde bewering (A∧B), dit is ook alleen waar als beide beweringen A en B
waar zijn (conceptueel hetzelfde als een intersectie).
Transitiviteit is de eigenschap dat als een eerste set (A∧B) een subset is van een tweede ([A]), en die
tweede set een subset is van een derde ([C]), de eerste set ook een subset is van de derde. Monotonie
in deductie betekent dat het toevoegen van nieuwe informatie (bijv. B) aan bestaande premissen (A),
de geldigheid van een conclusie (C) niet annuleert. Als A ⊨ C, blijft A ∧B ⊨ C gelden. Nieuwe
informatie kan de conclusie niet ondermijnen, zolang de oorspronkelijke premissen behouden blijven.
Dit maakt deductieve regels onweerlegbaar: eenmaal geldig, blijven ze geldig, ongeacht extra
informatie.
,Probabilities worden gebruikt om de waarschijnlijkheid te meten dat een bepaalde uitspraak waar is.
Een waarde tussen 0 en 1 geeft aan hoe groot de kans is dat de specifieke situatie daadwerkelijk
plaatsvindt. Als een zin A waar is in de helft van alle mogelijke scenario’s dan is P(A) = 0.5. De kans
is 50% dat de uitspraak waar is. Bij conditional probabilities meten we hoe waarschijnlijk een
uitspraak B is, ervan uitgaande dat, een andere uitspraak A waar is. Dit noteren we als P(B ∣ A): de
kans op B gegeven A. Als A staat voor varkens kunnen vliegen en B voor paarden kunnen vliegen,
dan berekent:
Hoe waarschijnlijk het is dat paarden kunnen vliegen, ervan uitgaande dat varkens al kunnen vliegen.
Strong inductive inferences vinden plaats wanneer de kans op een conclusie C, gegeven de
premissen P1, P2, … aanzienlijk toeneemt. Dit wordt gemeten door het verschil tussen de kans op C
zonder enige premissen (P(C)) en de kans op C gegeven alle premissen (P (C ∣ P1 ∧ P2 ∧ …). Als (P
(C ∣ P1 ∧ P2 ∧ …) veel groter is dan (P(C)) dan spreken we ven een sterke inductieve inferentie.
Bij inductie faalt monotonie, wat betekent dat het toevoegen van extra informatie aan de premissen
kan leiden tot het ongeldig maken van een eerdere conclusie. Bij deductieve logica geldt dat als een
conclusie geldig is gebaseerd op bepaalde premissen, het toevoegen van nieuwe informatie die
conclusie niet ongeldig maakt. Non-monotonicity beschrijft het principe dat bij inductief redeneren
een conclusie herzien kan worden door nieuwe informatie. Een geldige inferentie kan door het
toevoegen van nieuwe informatie ongeldig worden. Non-monotonicity benadrukt dus dat inductieve
regels defeasible (weerlegbaar) zijn.
Zie bijlage B2 voor extra informatie.
Hoofdstuk 3 – Formele talen
De logical form van een redenering is het patroon dat de logische structuur weergeeft, los van de
specifieke inhoud van de zinnen. Hoe zinnen logisch met elkaar samenhangen. Bij “A of B, niet B, dus
A” is de logische vorm van een disjunctive syllogisme duidelijk, ongeacht de specifieke betekenis
van A en B. Logische constanten zijn speciale symbolen die logische relaties en verbindingen
aangeven zoals: ¬ voor niet, ∧ voor en, ∨ voor of en → voor als… dan…
Sentence letters (p, q, r, …) zijn placeholders voor concrete zinnen. Ze staan voor willekeurige
uitspraken. De abstractie ervan maakt het mogelijk om te focussen op de logische structuur in plaats
van de inhoud. De propositional connectives zijn de symbolen (¬, ∧,∨,→,...) die de relaties tussen
zinnen aanduiden. Bijv. p ∨ q beschrijft p of q. De propositional logic onderzoekt de geldigheid van
redeneringen op basis van de sentence letters en de connectives. Het richt zich op de logische structuur
van uitspraken bijvoorbeeld: p ∨ q, ¬p ⊨ q (als p of q, en niet p dan volgt q). Een logical tool is een
formele taal die wordt gebruikt om kennis precies en consistent vast te leggen. Formele talen lossen
een fundamenteel probleem op in AI: hoe kunnen we kennis opslaan en communiceren met
computers? Door de wiskundige en deterministische aard van formele talen kunnen computers deze
gemakkelijker begrijpen en toepassen.
De elementary set theory is de basis van de theorie over sets. Een set is een collectie van objecten,
die de elementen/members van de set worden genoemd. Als een object x tot de set X behoort,
schrijven we x ∈ X. Als x niet tot X behoort dan schrijven we x ∉ X. Een extensional definition
beschrijft een set door expliciet al haar elementen op te sommen. Bijv. de verzameling {1, a {Robbie,
0} bevat precies de elementen: het getal 1, het symbool a en de set {Robbie, 0}. Bij set abstraction
wordt een set gedefinieerd door een eigenschap Φ waaraan haar elementen voldoen. De notatie is
{x:Φ(x)}, wat betekent “ de set van alle x waarvoor Φ (x) waar is. Bijv.: {x: x is een priemgetal}. Een
formule is een element van een formele taal en worden vaak aangeduid met hoofdletters (A, B, C, …)
of Griekse letters (ϕ,ψ,θ,...). Een alfabet in de context van formele talen is een set van symbolen die
gebruikt worden om formules (uitdrukkingen) te bouwen. De grammatica bepaalt de regels voor hoe
de symbolen uit het alfabet gecombineerd mogen worden om geldige formules te vormen.
Non-logical symbols zijn symbolen die vaak afkomstig zijn van logische abstractie:
, - Propositional variables (sentence letters) zijn symbolen/zinnen die uitspraken representeren,
zoals “het regent”. Deze worden vaak aangeduid met p, q, r, enz., maar kunnen ook
geheugensteuntjes zijn zoals RAIN.
- Constants zijn symbolen die specifieke objecten representeren zoals “Alan” of “Ada”. Ze
worden vaak aangeduid met a, b, c, enz., maar kunnen ook gewone numerieke waarden of
speciale symbolen zijn zoals 0, 1, 2, of π.
- Function symbols vertegenwoordigen functionele expressies zoals “+” of “de vader van”.
Dit wordt vaak aangeduid met f, g, h, enz., maar kunnen ook geheugensteuntjes zijn, zoals
FatherOF.
- Predicates zijn symbolen die eigenschappen of relaties definiëren, zoals “is blauw” of “is
groter dan”. Ze worden vaak aangeduid met P, Q, R, enz., maar kunnen ook als BLUE of
GROTER.
Logical symbols zijn de symbolen die het resultaat zijn van idealisatie in een logisch systeem:
- Variabelen: staan voor willekeurige objecten of eigenschappen in een logische context.
Worden aangeduid met x, y, z, enz., maar soms ook met Griekse letters zoals α, β, δ, als we
het over individuen hebben.
- Sentence operators: verbinden zinnen om nieuwe zinnen te vormen. Voorbeelden zijn de
klassieke propositie symbool operatoren:
- Quantifiers stellen ons in staat om beweringen te doen over alle (∀) of sommige (∃) objecten.
Ze worden gebruikt om generalisaties te maken, bijv.: “voor elke X, geldt…” of “er bestaat
een x waarvoor…”. Je hebt ook numerieke quantificatoren zoals ∃3 wat betekent “er zijn er
precies 3”.
- Auxiliaries (hulpsymbolen) helpen bij de structuur van de taal, maar hebben zelf geen
betekenis. Het zijn bijvoorbeeld komma’s (“,”) of haakjes (“(“en “)”), en worden gebruikt
voor het verduidelijken of ontleden van formules.
- Parsing verwijst naar het proces van het analyseren van een reeks symbolen om te bepalen of
het een geldige formule is volgens de grammatica van een taal.
Inductieve definitie is een manier om een set van formules te definiëren door te beginnen met een set
van atomaire formules en vervolgens regels te geven voor het bouwen van complexere formules. Ons
doel is om de L van (well-formed) formulas te definiëren. Dit is een set die bestaat uit formules die
op een juiste manier zijn geconstrueerd volgens de grammatica van de taal. Ze voldoen aan de
constructieregels en de afsluitingsvoorwaarde, wat betekent dat er geen andere formules buiten deze
regels vallen. We beginnen hiermee met het specificeren van een set Atomic formulas, dit zijn de
basisformules die niet ver zijn opgebouwd. Vervolgens ga je met een set constructie regels bepalen
hoe nieuwe formules kunnen worden opgebouwd uit bestaande formules.
Hier is hoe het werkt voor een standaardtaal in propositielogica waar Σ bevat:
- P1, …, Pn (n propositional variables)
- ¬, ∧, ∨, →, ↔ (the propositional operators)
- (, ) (the auxiliaries)
Vervolgens zeggen we dat:
- P1, …, Pn ∈ L
- if A ∈ L, then ¬A ∈ L as well as
- if A, B ∈ L, then (A ∧ B), (A ∨ B), (A→B), (A↔B) ∈ L
De Backus-Naur Form (BNF) is een formele manier om de grammatica van een taal te definiëren.
Het gebruikt een notatie waarin productieregels worden gegeven die bepalen hoe nieuwe formules
Aantekeningen en regels per hoofdstuk voor het eindtentamen
Hoofdstuk 1 – Logica en AI
Een inferentie is het proces van het afleiden van een conclusie of inzicht op basis van informatie,
zonder dat die expliciet wordt vermeld.
Deductieve inferentie is een manier van redeneren waar specifieke conclusies worden afgeleid uit
algemene premissen. Als de premissen waar zijn dan is de conclusie noodzakelijkerwijs ook waar.
Inductieve inferentie aan de andere kant leidt algemene conclusies af uit specifieke observaties. De
conclusie is waarschijnlijk waar, maar niet gegarandeerd. Omdat inductie gebaseerd is op het
herkennen van premissen of regelmatigheden.
Een redenering is deductief geldig (⊨) Als de conclusie noodzakelijkerwijs volgt uit de premissen.
Als de premissen waar zijn, kan de conclusie niet onwaar zijn. Een redenering is inductief geldig (∣≈)
als de conclusie waarschijnlijk volgt uit de premissen. De conclusie is gebaseerd op waarnemingen of
patronen, maar er is zeker geen garantie dat deze waar is. De logica is gebaseerd op waarschijnlijkheid
in plaats van zekerheid. Inductie is een krachtig hulpmiddel om waarschijnlijkheden te schatten en
generalisaties te maken, maar het blijft vatbaar voor fouten en vereist flexibiliteit om nieuwe
informatie te verwerken.
Dan heb je nog systeem 1 denken versus systeem 2 denken. Systeem 1 denken is snel, automatisch
intuïtief en onbewust. Voorbeelden zijn gezichten herkennen, zien of het ene object groter is dan de
ander en simpele berekeningen uitvoeren zoals 5+7. Systeem 2 denken is traag, logisch, berekenend
en weloverwogen. Voorbeelden zijn het tellen van het aantal As in een tekst, een logische puzzel
oplossen en complexere berekeningen uitvoeren zoals 432 x 441. LLMs, zoals ChatGPT zijn goed in
systeem 1 denken, wat betekent dat ze snel patronen herkennen en intuïtieve antwoorden genereren.
Echter, voor systeem 2 denken, zijn ze niet zo goed. Omdat deze taken bewuste, trage en
systematische redenering vereisen.
Hoofdstuk 2 – Geldige inferentie
Een inferentie van de vorm modus ponens ziet er zo uit: A → B, A ⊨ B. Dit wil zeggen dat als je
twee afzonderlijke stukken informatie samenvoegt, Als A dan B en de premisse A, je geldig de
conclusie B mag afleiden.
Het basisgereedschap dat we zullen gebruiken heet een semantisch model. Dit is een afbeelding van
een mogelijk redeneerscenario. Als we naar een model kijken, kunnen we ons afvragen of een
bepaalde zin A, waar of onwaar is in dit model. Elk model geeft een antwoord. Het kent een
definitieve waarheidswaarde toe aan elke zin.
Voor elke zin A in onze formele taal, schrijven we [A] om te refereren aan een set modellen waar die
zin waar is. Met deze notatie kunnen we praten over relaties tussen sets modellen. [A] en [B]voor twee
willekeurige zinnen A en B. Wanneer er elementen van een set ook in een andere set zitten, dan
zeggen we dat er een subset relatie is tussen die twee sets en schrijven we A ⊆ B. Deze relatie is een
goede eerste stap om deductieve validiteit te definiëren: als in elk mogelijk model M waarin A waar is,
ook B waar is, dan is de inferentie van A naar B geldig. Het is noodzakelijk waarheid bewarend.
Een intersectie (X∩Y) van twee sets verwijst naar de elementen die in beide verzamelingen
voorkomen. Het beschrijft het overlappende deel. Een logische conjunctie verbindt twee beweringen
A en B in een samengestelde bewering (A∧B), dit is ook alleen waar als beide beweringen A en B
waar zijn (conceptueel hetzelfde als een intersectie).
Transitiviteit is de eigenschap dat als een eerste set (A∧B) een subset is van een tweede ([A]), en die
tweede set een subset is van een derde ([C]), de eerste set ook een subset is van de derde. Monotonie
in deductie betekent dat het toevoegen van nieuwe informatie (bijv. B) aan bestaande premissen (A),
de geldigheid van een conclusie (C) niet annuleert. Als A ⊨ C, blijft A ∧B ⊨ C gelden. Nieuwe
informatie kan de conclusie niet ondermijnen, zolang de oorspronkelijke premissen behouden blijven.
Dit maakt deductieve regels onweerlegbaar: eenmaal geldig, blijven ze geldig, ongeacht extra
informatie.
,Probabilities worden gebruikt om de waarschijnlijkheid te meten dat een bepaalde uitspraak waar is.
Een waarde tussen 0 en 1 geeft aan hoe groot de kans is dat de specifieke situatie daadwerkelijk
plaatsvindt. Als een zin A waar is in de helft van alle mogelijke scenario’s dan is P(A) = 0.5. De kans
is 50% dat de uitspraak waar is. Bij conditional probabilities meten we hoe waarschijnlijk een
uitspraak B is, ervan uitgaande dat, een andere uitspraak A waar is. Dit noteren we als P(B ∣ A): de
kans op B gegeven A. Als A staat voor varkens kunnen vliegen en B voor paarden kunnen vliegen,
dan berekent:
Hoe waarschijnlijk het is dat paarden kunnen vliegen, ervan uitgaande dat varkens al kunnen vliegen.
Strong inductive inferences vinden plaats wanneer de kans op een conclusie C, gegeven de
premissen P1, P2, … aanzienlijk toeneemt. Dit wordt gemeten door het verschil tussen de kans op C
zonder enige premissen (P(C)) en de kans op C gegeven alle premissen (P (C ∣ P1 ∧ P2 ∧ …). Als (P
(C ∣ P1 ∧ P2 ∧ …) veel groter is dan (P(C)) dan spreken we ven een sterke inductieve inferentie.
Bij inductie faalt monotonie, wat betekent dat het toevoegen van extra informatie aan de premissen
kan leiden tot het ongeldig maken van een eerdere conclusie. Bij deductieve logica geldt dat als een
conclusie geldig is gebaseerd op bepaalde premissen, het toevoegen van nieuwe informatie die
conclusie niet ongeldig maakt. Non-monotonicity beschrijft het principe dat bij inductief redeneren
een conclusie herzien kan worden door nieuwe informatie. Een geldige inferentie kan door het
toevoegen van nieuwe informatie ongeldig worden. Non-monotonicity benadrukt dus dat inductieve
regels defeasible (weerlegbaar) zijn.
Zie bijlage B2 voor extra informatie.
Hoofdstuk 3 – Formele talen
De logical form van een redenering is het patroon dat de logische structuur weergeeft, los van de
specifieke inhoud van de zinnen. Hoe zinnen logisch met elkaar samenhangen. Bij “A of B, niet B, dus
A” is de logische vorm van een disjunctive syllogisme duidelijk, ongeacht de specifieke betekenis
van A en B. Logische constanten zijn speciale symbolen die logische relaties en verbindingen
aangeven zoals: ¬ voor niet, ∧ voor en, ∨ voor of en → voor als… dan…
Sentence letters (p, q, r, …) zijn placeholders voor concrete zinnen. Ze staan voor willekeurige
uitspraken. De abstractie ervan maakt het mogelijk om te focussen op de logische structuur in plaats
van de inhoud. De propositional connectives zijn de symbolen (¬, ∧,∨,→,...) die de relaties tussen
zinnen aanduiden. Bijv. p ∨ q beschrijft p of q. De propositional logic onderzoekt de geldigheid van
redeneringen op basis van de sentence letters en de connectives. Het richt zich op de logische structuur
van uitspraken bijvoorbeeld: p ∨ q, ¬p ⊨ q (als p of q, en niet p dan volgt q). Een logical tool is een
formele taal die wordt gebruikt om kennis precies en consistent vast te leggen. Formele talen lossen
een fundamenteel probleem op in AI: hoe kunnen we kennis opslaan en communiceren met
computers? Door de wiskundige en deterministische aard van formele talen kunnen computers deze
gemakkelijker begrijpen en toepassen.
De elementary set theory is de basis van de theorie over sets. Een set is een collectie van objecten,
die de elementen/members van de set worden genoemd. Als een object x tot de set X behoort,
schrijven we x ∈ X. Als x niet tot X behoort dan schrijven we x ∉ X. Een extensional definition
beschrijft een set door expliciet al haar elementen op te sommen. Bijv. de verzameling {1, a {Robbie,
0} bevat precies de elementen: het getal 1, het symbool a en de set {Robbie, 0}. Bij set abstraction
wordt een set gedefinieerd door een eigenschap Φ waaraan haar elementen voldoen. De notatie is
{x:Φ(x)}, wat betekent “ de set van alle x waarvoor Φ (x) waar is. Bijv.: {x: x is een priemgetal}. Een
formule is een element van een formele taal en worden vaak aangeduid met hoofdletters (A, B, C, …)
of Griekse letters (ϕ,ψ,θ,...). Een alfabet in de context van formele talen is een set van symbolen die
gebruikt worden om formules (uitdrukkingen) te bouwen. De grammatica bepaalt de regels voor hoe
de symbolen uit het alfabet gecombineerd mogen worden om geldige formules te vormen.
Non-logical symbols zijn symbolen die vaak afkomstig zijn van logische abstractie:
, - Propositional variables (sentence letters) zijn symbolen/zinnen die uitspraken representeren,
zoals “het regent”. Deze worden vaak aangeduid met p, q, r, enz., maar kunnen ook
geheugensteuntjes zijn zoals RAIN.
- Constants zijn symbolen die specifieke objecten representeren zoals “Alan” of “Ada”. Ze
worden vaak aangeduid met a, b, c, enz., maar kunnen ook gewone numerieke waarden of
speciale symbolen zijn zoals 0, 1, 2, of π.
- Function symbols vertegenwoordigen functionele expressies zoals “+” of “de vader van”.
Dit wordt vaak aangeduid met f, g, h, enz., maar kunnen ook geheugensteuntjes zijn, zoals
FatherOF.
- Predicates zijn symbolen die eigenschappen of relaties definiëren, zoals “is blauw” of “is
groter dan”. Ze worden vaak aangeduid met P, Q, R, enz., maar kunnen ook als BLUE of
GROTER.
Logical symbols zijn de symbolen die het resultaat zijn van idealisatie in een logisch systeem:
- Variabelen: staan voor willekeurige objecten of eigenschappen in een logische context.
Worden aangeduid met x, y, z, enz., maar soms ook met Griekse letters zoals α, β, δ, als we
het over individuen hebben.
- Sentence operators: verbinden zinnen om nieuwe zinnen te vormen. Voorbeelden zijn de
klassieke propositie symbool operatoren:
- Quantifiers stellen ons in staat om beweringen te doen over alle (∀) of sommige (∃) objecten.
Ze worden gebruikt om generalisaties te maken, bijv.: “voor elke X, geldt…” of “er bestaat
een x waarvoor…”. Je hebt ook numerieke quantificatoren zoals ∃3 wat betekent “er zijn er
precies 3”.
- Auxiliaries (hulpsymbolen) helpen bij de structuur van de taal, maar hebben zelf geen
betekenis. Het zijn bijvoorbeeld komma’s (“,”) of haakjes (“(“en “)”), en worden gebruikt
voor het verduidelijken of ontleden van formules.
- Parsing verwijst naar het proces van het analyseren van een reeks symbolen om te bepalen of
het een geldige formule is volgens de grammatica van een taal.
Inductieve definitie is een manier om een set van formules te definiëren door te beginnen met een set
van atomaire formules en vervolgens regels te geven voor het bouwen van complexere formules. Ons
doel is om de L van (well-formed) formulas te definiëren. Dit is een set die bestaat uit formules die
op een juiste manier zijn geconstrueerd volgens de grammatica van de taal. Ze voldoen aan de
constructieregels en de afsluitingsvoorwaarde, wat betekent dat er geen andere formules buiten deze
regels vallen. We beginnen hiermee met het specificeren van een set Atomic formulas, dit zijn de
basisformules die niet ver zijn opgebouwd. Vervolgens ga je met een set constructie regels bepalen
hoe nieuwe formules kunnen worden opgebouwd uit bestaande formules.
Hier is hoe het werkt voor een standaardtaal in propositielogica waar Σ bevat:
- P1, …, Pn (n propositional variables)
- ¬, ∧, ∨, →, ↔ (the propositional operators)
- (, ) (the auxiliaries)
Vervolgens zeggen we dat:
- P1, …, Pn ∈ L
- if A ∈ L, then ¬A ∈ L as well as
- if A, B ∈ L, then (A ∧ B), (A ∨ B), (A→B), (A↔B) ∈ L
De Backus-Naur Form (BNF) is een formele manier om de grammatica van een taal te definiëren.
Het gebruikt een notatie waarin productieregels worden gegeven die bepalen hoe nieuwe formules
