Methode 'Praktische Logica':

  

Criteria

in Formele Logica


(Uitgebreid overzicht)


[Eerste, voorlopige versie:]

Zie het voorafgaande:
· Inleiding Formele logica.
  Voordelen van formalisering en varianten van logica.
· Inleiding Propositielogica.
  Redeneren met elementaire beweringen.
· Inleiding Predikatenlogica.
  Redeneren over individuen en categorieën.
· Inleiding Resolutielogica.
  Sophisticated logische bewijsmethode.

Inleiding



Mogelijkheden en grenzen van de logica



Voor een optimaal gebruik van logica voor praktische doeleinden is een goed begrip nodig van wat logica kan, maar ook wat ze níet kan.

De formele logica is waarschijnlijk het enige vakgebied dat zèlf haar eigen grenzen aangeeft. Ze doet dit op een heel exacte manier, via logische consequenties - uiteraard - en op grond van de eigen (logische) principes van de logica: betrouwbaar, kristalhelder en onontkoombaar.

In het overzicht 'Criteria in de Formele Logica' worden de belangrijkste criteria in de formele logica besproken.

Inhoudelijke criteria:


Waarheid, onbeslistheid, onwaarheid (contradictie).
Regels voor evaluatie, interpretatie, valuatie.

Meta-logische criteria, eerste niveau:


(a) Semantisch: geldigheid, contingentie, onvervulbaarheid.
(b) Syntactisch: afleidbaarheid, inconsistentie; bewijsbaarheid.
(c) Semantiek en syntax: consistentiestelling, correctheid, volledigheid.

Meta-logische criteria, tweede niveau:


O.m. compactheid, beslisbaarheid.


Inhoud



Hieronder volgt een zeer beknopte inhoudsopgave van de overige onderdelen van deze cursusmodule.
De volledige weergave wordt aangeboden in de bijbehorende syllabus.
Voor bestellingen of meer informatie: Contact.

Inhoud

(hoofdpunten):



Criteria van de Formele Logica.



Mogelijkheden en grenzen van formele logische systemen.



(•) Gebruikte symbolen.
(•) (Tabel) Meta-logische concepten.

I. Semantische criteria.



Logisch inhoudsniveau.



1. Waarheid.


Definitie: van waarheid.

Waarheidswaarden


(·) Waarheidswaarde.
(·) Evaluatie (truth evaluation).
(·) Interpretatie.
(1) Valuatie, toekenning van waarheidswaarden.
(2) Structuur (domein-structuur).
(3) Bedeling.
(·) Model.

(1)

Valuatie, waarheidswaardetoekenning


(a) Valuatie van een formule.
(1) Bevestiging (Affirmatie) van een formule.
(2) Ontkenning (Negatie) van een formule.
(b) Valuatie van een verzameling formules.

Wetten/Regels m.b.t. Valuatie:


Valuatie en (Semantische) equivalentie.

(2)

Interpretatie.


Interpretatie en Model.
(a) Interpretatie van een formule.
(b) Interpretatie van een verzameling.
Interpretatie in logische systemen.
(1)

Een structuur (of 'datastructuur').


(a)

Een structuur in PPL:


(·) Propositiesymbolen.
(b)

Uitbreidingen in PDL:


(1) Variabelenamen.
(2) Objectnamen of constanten.
(3) Functienamen.
(4) Predikaatnamen.
(2)

Een bedeling (assignment functie).



Logisch meta-niveau I.


Beweringen over wetmatigheden in het domein.
Vervulbaarheid / geldigheid van redeneringen.

Geldigheid en (on)vervulbaarheid.



2. Geldigheid (validiteit).


Definitie: van 'Geldigheid'.

Geldigheid in verschillende formele systemen.


(a) Geldigheid in PPL.
(b) Geldigheid in PDL-I.
(1) onder elke (volledige) structuur 'A!' van F.
(2) met elke (volledige) bedeling 'f_asg()' van variabelen in F.
(zie verder elders).

Wetten/Regels m.b.t. Algemene geldigheid:


(1) Geldigheid en negatie.
Dubbele negatie onder geldigheid.
Voorplaatsing en tussenplaatsing.
Onderschikking van andere criteria.
(2) Geldigheid en waarheid.
(a) Algemeen geldig impliceert waar.
(b) Waar (zijn) impliceert niet algemeen geldig.
(3) Geldigheid en conjunctie.
(4) Geldigheid en disjunctie.
(5) Geldigheid en implicatie.
(6) Geldigheid en equivalentie.

3. Ongeldigheid.


Definitie: van 'Ongeldigheid' (non sequitur [nonseq]).

4. Logisch gevolg.


Definitie: van 'Logisch gevolg'

Wetten/Regels m.b.t. Logisch gevolg.


(1) Logisch gevolg en implicatie.
(2) Logisch gevolg en geldigheid.
(3) Logisch gevolg en equivalentie.

5. Vervulbaarheid.


Definitie: van 'Vervulbaarheid'
(a) Vervulbaarheid van een formule.
(b) Vervulbaarheid van een verzameling.

Vervulbaarheid in diverse formele systemen.


(a) Vervulbaarheid in PPL.
(b) Vervulbaarheid in PDL-I.

Wetten/Regels m.b.t. Vervulbaarheid.


(a) Vervulbaarheid en equivalentie.

6. Onvervulbaarheid.

:
Definitie: van 'Onvervulbaarheid'

Onvervulbaarheid in diverse formele systemen:


(1) Onvervulbaarheid in PPL.
(2) Onvervulbaarheid in PDL-I.
(3) Onvervulbaarheid in PDL-ISkNF.

Wetten/Regels m.b.t. Onvervulbaarheid.


(1) Onvervulbaarheid en conjunctie.
(2) Onvervulbaarheid en disjunctie.
(3) Onvervulbaarheid en vereniging.

7. Contingentie.


Definitie: van 'Contingentie'.
(a) Contingentie van een formule.
(b) Contingentie van een verzameling.

II. Syntactische criteria.


(·) Syntax.
(·) Afleiding.
(·) Bewijs.

1. Afleidbaarheid.


Definitie: van 'Afleidbaarheid'.
(a) Afleidbaarheid van een formule.
(b) Afleidbaarheid van een formule uit een verzameling.

Deductieve afsluiting.


(a) Deductieve afsluiting van een theorie.
(b) Deductieve afsluiting van een verzameling formules.

Afleidbaarheid in diverse formele systemen


(a) Afleidbaarheid in PPL.
Deductiestelling (Deduction theorem).
(b) Afleidbaarheid in PDL-I.
Principe van universele generalisatie.

Wetten/Regels m.b.t. Afleidbaarheid.


(1) Afleidbaarheid en relevantie.
(2) Afleidbaarheid en geldigheid.
(3) Afleidbaarheid en equivalentie.

2. Bewijsbaarheid.


D.w.z. 'Eindig-afleidbaarheid.
Definitie: van 'Bewijsbaarheid'.
(·) Bewijs.
(·) Theorema bewijs.
(a) Bewijsbaarheid van een formule.
(b) Bewijsbaarheid van een formule uit een verzameling.

3. Consistentie.


Definitie: van 'Consistentie'.
(a) Consistentie van een systeem.
(b) Consistentie van een verzameling.
(c) Consistentie van een formule.

Wetten/ Regels m.b.t. consistentie.



4. Inconsistentie.


(a) Inconsistentie van een formule.
(b) Inconsistentie van een verzameling.
(c) Inconsistentie van een systeem.

III. Relaties tussen semantische en syntactische criteria.



1. De relatie tussen Consistentie en Vervulbaarheid.


(1)

Consistentie garandeert Vervulbaarheid.


Consistentiestelling.
(a) Consistentie in PPL.
(b) Consistentie in PDL-I.
Bewijs van Consistentiestelling.
(2)

Vervulbaarheid garandeert Consistentie.


(Omgekeerde van Consistentiestelling)
Bewijs van: Vervulbaarheid garandeert Consistentie.
Principe van bewijs door 'weerlegging van het tegendeel'
(Reductio ad absurdum).

2. Correctheid.


Definitie: van 'Correctheid'.
(a) Correctheid van een systeem.
(b) Correctheid van een verzameling.

Soundness Theorem.


Definitie: van 'Soundness'.

3. Volledigheid.


D.w.z. Volledige waarheid-bewijscapaciteit.
Definitie: van 'Volledigheid' (completeness).
(a) Volledigheid van een systeem.
(b) Volledigheid van een verzameling.

Volledigheid in verschillende formele systemen.


(a) Volledigheid in PPL.
(b) Volledigheid in PDL-I.
Volledigheid van PDL-I.
Bewijs.

Eindige bewijzen



4. Onvolledigheid.


(a) Onvolledigheid van een systeem.
(b) Onvolledigheid van een verzameling.

De Onvolledigheid van de elementaire rekenkunde.


Het onvolledigheidsbewijs van Gödel.
Onvolledigheid van de elementaire rekenkunde.
Bewijs (naar Kurt Gödel, 1931).
Conclusie.

5. De relatie tussen Consistentie en Volledigheid.



6. Eindig-vervulbaarheid van vervulbare verzamelingen.


Gebruikte symbolen.
Niveau's van kardinaliteit.
(De eerste drie)

Eindig-vervulbaarheid.


Gebruikte symbolen.

Lemma's m.b.t. Eindig-vervulbaarheid:


(1) Vervulbaar naar Eindig-vervulbaar.
Bewijs.
(2) Eindig-vervulbaarheid en uitbreidingen.
(3) Consequenties uit eindige deelverzameling.
(4) Consequentie (corrolary).
Bewijs.

7. Maximaal consistentie (MCS).


Definitie:

van 'Maximaal consistentie'.

Wetten/ Regels m.b.t. maximaal-consistentie:


(1) Maximaal-consistentie en een verzameling van zinnen.
(2) Eigenschappen van een maximaal-consistente verzameling van zinnen.
(3) Het Lemma van Lindenbaum.
(a) Voor een verzameling formules.
(b) Voor een formule ten opzichte van een verzameling.
Lemma van Lindenbaum.
Bewijs.

8. Compactheid.


Compactheid theorema.
Compactheidstheorema
Bewijs.

9. Definieerbaarheid van verzamelingenleer via predikatenlogica.


De verzamelingleer van Cantor.


Het Theorema van Cantor.
Bewijs.

Een eerste barst in de verzamelingenleer: de Paradox van Russell


Paradox van Russell.
Bewijs.

De Löwenheim-Skolem theorema's.


(1) Upward Löwenheim-Skolem theorema.
(2) Downward Löwenheim-Skolem theorema.
Upward Löwenheim-Skolem theorema.
Bewijs.

Logisch meta-niveau II.



10. Beslisbaarheid.


D.w.z. Validiteitsbeslisbaarheid.
Definitie van: 'Beslisbaarheid'.
Beslisbaarheid van een systeem.

De onbeslisbaarheid van de predikatenlogica.


Hilbert's Entscheidungsproblem.


N.b.
Voorbeeld van onbelisbare stelling in PDL.
Bewijs via resolutie.

De onbeslisbaarheid van de elementaire rekenkunde.


Niveau's van complexiteit van informatie.

Stelling van Church-Turing.


Algoritme.
Kenmerken van een algoritme.
De Church-Turing these.
Kenmerken van een beslisbaar algoritme.
De verzameling deterministische algoritmen.

Turing's aanpak van het Entscheidungsproblem.


Het bewijs van Turing.
(I) Bewijs via transponatie van de diagonaal-rij.
(II) Bewijs via het complement van het berekenbare deel van de diagonaal.

Conclusie van Turing's bewijs