Samenvatting Alle Definities - Logica en formele systemen

DEFINITIES LOGICA
Propositielogica: syntaxis en semantiek [p46-91]

i. Alfabet [p56]
Het alfabet van de propositielogica bestaat uit :
▪ Een verzameling propositieletters
▪ De logische symbolen ^ v -> …
▪ De hulpsymbolen ( )

ii. Formules [p57]
De formules in de propositielogica zijn als volgt gedefiniëerd :
▪ Elke propositieletter is een formule
▪ Als ϕ en ψ formules zijn, dan zijn !ϕ, (ϕ ^ ψ), (ϕ v ψ), (ϕ -> ψ) en (ϕ <-> ψ)
ook formules
▪ Niets anders is een formule

iii. Substitutie [p63]
Door elk voorkomen van p in ϕ te vervangen door een formule ψ, ontstaat een
nieuwe formule : [ψ/p]ϕ

iv. Waardering [p78]
Een waardering is een functie van alle propositie letters naar de waarheidswaarden
‘waar’ of ‘onwaar’ (0 of 1)

v. Model [p79]
Een waardering V heet een model van een formule ϕ als geldt dat V(ϕ) = 1

vi. Model van een formuleverzameling [p 80]
Een waardering V heet een model van een formuleverzameling Σ als V een model is
van elke formule ϕ ϵ Σ
De verzameling van modellen van Σ wordt genoteerd als Mod(Σ)

vii. Tautologie [p85]
Een formule ϕ heet een tautologie als elke waardering een model is van ϕ

viii. Logisch equivalent [p86]
Twee formules ϕ en ψ heten logisch equivalent als de formule (ϕ <-> ψ) een
tautologie is

ix. Functioneel volledig [p88]
Een verzameling van connectieven C heet functioneel volledig als elke formule ϕ
logisch equivalent is met een formule ψ die enkel connectieven uit C bevat

x. Disjunctieve normaalvorm [p90]
Een formule is in disjunctieve normaalvorm wanneer deze de syntactische vorm
heeft van een disjunctie van conjucties, bestaande uit atomen of negaties van
atomen