Voortgezette logica

Op deze pagina vindt u informatie over het vak Voortgezette Logica. Het vak heb ik gevolgd als onderdeel van mijn opleiding KI aan de Rijksuniversiteit Groningen. De theorie is behandeld aan de hand van het boek 'Logica voor informatica'.

Behandelde stof

Inductieve definities en bewijzen

inductie: Herhaaldelijk toepassen van een basisstap en een opbouwstap om recursief concepten te definiëren en stellingen te bewijzen.
functionele volledigheid: Een verzameling connectieven C heet functioneel volledig als je met alleen C iedere formule kunt beschrijven; oftewel, iedere formule φ heeft een logisch equivalente formule φ' die alleen connectieven uit C bevat.

Een inductieve definitie bestaat uit
1. Eén of meerdere basisstappen waarin bepaalde dingen meteen tot objecten van de gewenste soort worden verklaard;
2. Eén of meerdere opbouwstappen die verder constructieprincipes geven om objecten te maken
3. Een afsluitende stap die bepaalt dat alles wat niet in eindig veel stappen met behulp van 1 en 2 gevormd kan worden geen toegestaan object is.

Definitie propositielogica

BASIS: Elke propositieletter p is een propositionele formule.

OPBOUW: Als φ en ψ propositionele formules zijn, dan zijn (φ AND ψ), disjunctie, implicatie, biïmplicatie en negatie ook propositielogische formules.

AFSLUITING: Niets anders is een propositielogische formule dan wat je met een eindig aantal combinaties van basis- en opbouwstap kunt maken.

Lambda-calculus

abstractie: (λx . P) is de functie die aan iedere x in P een bepaalde waarde toekent.
applicatie: ((λx . P)c) is de uitdrukking die aan iedere x in P de waarde c toekent.

Meerwaardige logica

Modale logica

Syntax

Semantiek en tableaus

axiomatische bewijzen en karakteriseringen

predikatenlogica

Tijdslogica

Parallele processen

Complexiteit

Niet-monotoon redeneren

Begrippen in de logica

predikaatsymbool: Symbool dat een kenmerk van een object of een relatie tot een of meerdere andere objecten aangeeft. (vb. Dommer(Pim, Einstein), het predikaat Dommer(x,y) geeft aan dat x dommer is dan y (mits dat zo gedefinieerd is))
functiesymbool: Symbool dat verwijst naar een instantie ervan met een bepaald kenmerk. (vb. vader(Archytas): de vader van Archytas). Functiesymbolen kunnen genest worden in tegenstelling tot predikaten.
negatie: Een negatie geeft aan dat iets waar is als hetgeen waar de negatie op van toepassing is onwaar is. Negaties worden vaak gebruikt om woorden als 'niet', 'noch' en voorvoegsels als 'on' en 'a' te vertalen naar de eerste orde taal.
conjunctie: Een conjunctie geeft aan dat iets waar is als iedere bewering waarop de conjunctie van toepassing is waar is. Een conjunctie wordt o.a. gebruikt om woorden als 'en', 'desalniettemin' en 'maar' naar LOFOL (eerste orde taal) te vertalen.
disjunctie: Een disjunctie geeft aan dat iets waar is als een of meerdere uitspraken waarop de conjuctie van toepassing is waar is. Wordt meestal gebruikt om (inclusief) 'of' te vertalen.
LOFOL: LOFOL staat voor 'Language of First Order Logic', ofwel de eerste orde taal.
ambiguïteit: Een zin is ambigu als op basis van de syntaxis hieraan meer dan 1 betekenis kan worden gegeven. In FOL wordt ambiguïteit meestal voorkomen door het gebruik van haakjes. (vb. Het is blauw of het is groot en het is rond. De waarheidswaarde is niet duidelijk als het een blauw vierkant betreft.).
implicatie: Een implicatie, aangegeven met een pijl, geeft aan dat wat rechts van de pijl staat altijd waar moet zijn als aan hetgeen voor de pijl is voldaan. In het Nederlands wordt dit meestal met '(als ...) dan' uitgedrukt.
equivalentie: Een equivalentie, aangegeven met een dubbele pijl, geeft aan dat de waarheidswaarde van de formule links van het equivalentiesymbool overeenkomt met de waarheidswaarde van wat rechts van de pijl staat.
solvability: Oplosbaarheid (afgekort tot SAT) van een probleem (in relatie tot tijd en ruimte complexiteit).
tijdcomplexiteit: De tijdcomplexiteit van een probleem is het aantal stappen dat het neemt om een instantie (node) van een probleem op te lossen als functie van de grootte van de invoer bij toepassing van het meest efficiënte algoritme.
frame: ..
tansitief: ...
irreflexitief: ...
axioma: ...