»  

Alento

Training & Advies

 

-

 

Arc of Essentials ©

 

-

  drs. C.P. van der Velde  

-

  12-11-2015

Dimensie/ vakgebied:

Logica



Methode:

'Formele Logica'

(LGP)

©



Introductie Propositielogica (PPL)

.

Redeneren met elementaire beweringen.



(I. Inleiding, inhoudsopgave).



Het kader van de propositielogica



De propositielogica is het meest simpele systeem van formele logica. Het bevat de basisregels van de logica, die ten grondslag liggen aan vrijwel alle logische systemen van 'hogere' orde.
Deze regels zijn allereerst van toepassing op het redeneren over elementaire beweringen.

Elementaire beweringen zijn de 'bouwstenen' van alle beweringen in de natuurlijke taal: dat zijn taaluitingen die iets zeggen over een bepaald thema, direct of indirect, impliciet of expliciet. In de natuurlijke taal zijn elementaire beweringen de betekenisrepresentaties van zinnen en bijzinnen, oftewel alle taaleenheden die een zgn. gezegde bevatten. Elk gezegde bevat met name een hoofdwerkwoord of proceswoord: in dynamische vorm (lopen, praten, ..) of statische vorm (de loop, het gesprek, ..). Bij elk proceswoord hoort tenminste één ding dat het proces 'doet': de uitvoerder of agens (grammaticaal is dit het onderwerp van het gezegde in bedrijvende vorm).

In de logica worden elementaire beweringen aangeduid als proposities. Het logische systeem voor het redeneren over proposities heet dan ook de propositielogica (PPL).

De grondslag voor dit systeem werd gelegd door de beroemde Griekse filosoof Aristotelis.

{Nb. Aristotelis (384-322 A.D.) was geboren in Stagira als zoon van Nicomachus, een bekende geneesheer. Hij werd leerling van Plato aan de Academie van Athene, werd leraar van Alexander de Grote aan het Macedonische hof en begon een eigen Lyceum. Onder zijn belangrijkste werken zijn het Organum, bestaande uit zes verhandelingen over logica, Physica, Metaphysica, De Anima, De Ethica, De Poetica, Rhetorica, en een aantal werken over biologie en fysica. Hij stierf in Chalcis. }



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
.

Inhoudsopgave


Formeel logisch systeem L!.


De Propositielogica (PPL): Formeel logisch systeem.



1.

 

Basisgedachten voor Propositielogica.


(•) Gebruikte notaties.
(•) Proposities en connectieven.
(•) Logische connectieven / operatoren - in PPL.

2.

 

Syntax voor Propositielogica.


2.1

 

Het alfabet van PPL


(1) De logische symbolen van PPL.


(1a) Waarheidswaardeconstanten.
  bereik (range) van waarheidswaarden.
(1b) Waarheidswaarde-aanduiding.
(1c) Logische connectieven of operatoren.
(1d) Referentiële identiteit, numerieke identiteit, synonymie van expressies.
(1e) Syntactische hulpsymbolen.
(1f) Logische kwantoren (kwantifiers).
(1g) Variabelenamen, voor willekeurige eenheden (objecten) uit het domein.

(2) De niet-logische symbolen van PPL.


(2a) Propositionele variabelen:
  voor enkelvoudige formules (atomen).

2.2

 

Formatieregels voor PPL


2.3

 

Notatieregels voor het hoofdconnectief.


I.3a. Bindingskracht van connectieven

3.

 

Semantiek voor Propositielogica.


3.1

 

Interpretatie.


(3.1.1) Interpretatiedomein
(3.1.2) Schrijfwijzen voor waarheidswaarden

Logische wetten in de propositielogica (PPL):


3.2

 

Axioma's voor twee variabelen:


(3.2.1) Waarheidswaarden-tabel in PPL - voor connectieven.
(3.2.2) Omzettings-tabel voor conjunctie, disjunctie en implicatie.
(3.2.3) Wat is implicatie - en wat niet?
(3.2.4) Basiswetten van implicatie.
(3.2.5) Waarheidswaarden, logische identiteit en valuatie.
(3.2.6) Logische identiteit en valuatie.
(3.2.7) Logische kracht (in propositielogica).
(3.2.8) Reductie van logische kracht

4.

 

Axioma's voor de propositielogica.


5.

 

Regels voor formulebewerkingen in Propositielogica.


Wetten/ regels voor redeneren in de Propositielogica (PPL).

5.1

 

Basiswaarden (valenties)


(5.1a) Waarheid, geldigheid
Altijd ware bewering (tautologie; validiteit).
(5.1b) Onwaarheid, contradictie
Nimmer ware bewering (falsum, contradictio)

5.2

 

Enkelvoudige formules (Atomen)


5.3

 

Conjuncties.


5.4

 

Inclusieve Disjuncties, c.q. implicaties.


5.5

 

Equivalentie en Exclusief-disjunctie.



Wetten voor logische Normaal Vorm conversies.



6.

 

Wetten voor Negatief Normaal Vorm (NNF) conversie


6.1

 

Dubbele negatie-eliminatie


(6.1a) Wet van de Dubbele Ontkenning (Negatio duplex).
Negatie eliminatie regel ('¬ el').

6.2

 

Negatie-binnenplaatsing


(6.2a) Negatieve implicatie omzetting

6.3

 

Negatie-binnenplaatsing met -distributie


(6.3a) Negatieve conjunctie omzetting (T3)
M.b.v. Wet van De Morgan (DeMorgan's Law), 'negatie spreiding'.
(6.3b) Negatief-disjunct-normaal conversie (T4)
Negatieve disjunctie omzetting.
M.b.v. Wet van De Morgan (DeMorgan's Laws), 'negatie spreiding'.

6.4

 

Negatie-eliminatie via connectief-conversie


(6.4a) Negatieve equivalentie omzetting
(6.4b) Negatieve exclusief-disjunctie omzetting

[INHOUD VAN DIT GEDEELTE:]

Wetten voor Connectief Normaal Vorm conversies.


6. Wetten voor Conjunctief Normaal Vorm (CNF) Conversie

.

7. Wetten voor Disjunctief Normaal Vorm (DNF) Conversie



6. Wetten voor Conjunct Normaal Vorm (CNF) Conversie


(5.1) Equivalentie normaal omzetting
(5.2) Exclusief-disjunctie normaal omzetting
(5.3) Implicatie normaal omzetting
(5.4) Disjunctie normaal omzetting
(5.5) Disjunctie normaal comprimatie
Via destillatie van conjuncten
(5.6) Conjunct-normaal distributie (verdeling)
Via spreiding van conjuncten over disjuncties
(5.6a) Vanuit DNF, met atoom-diepte = 2
(5.6b) Vanuit DNF, met atoom-diepte = 3
(5.6c) Vanuit DNF, met atoom-diepte = 4

VI. Wetten voor Disjunct Normaal Vorm (DNF) Conversie


(6.1) Equivalentie disjunctief omzetting
(6.2) Exclusief disjunctie disjunctief omzetting
(6.3) Implicatie disjunctief omzetting
(6.4) Conjunctie disjunctief omzetting
(6.5) Conjunctie disjunctief comprimatie
Via destillatie van disjuncten
(6.6) Conjunct-disjunctie distributie (verdeling)
Via spreiding van disjuncten over conjuncties

[INHOUD VAN DIT GEDEELTE:]

VII. Wetten tbv. 'Reductie' van formules


Via comprimatie (met behoud van logische kracht) of detractie (met verlies van logische kracht).

(7.1) Reductie van (complexe) proposities, wegens redundantie van literalen; in CNV/DNV
Elimineren van atomaire clause(s) (negatieve of positieve atomaire proposities / predikaties).
(7.1a) Reductie van (complexe) conjuncties; in CNV
Eliminatie van literalen op grond van 'Basale redundantie'.
Betreft relaties tussen unit clauses (literalen op de hoofdlijn).
(7.1a1) Elimineren van conjuncte literalen; op grond van 'Basale equivalentie' (onder unificatie); in CNV.
(7.1a2) Elimineren van conjuncte literalen; op grond van 'Basale implicatie' (onder unificatie); in CNV.
(7.1b) Reductie van (complexe) disjuncties; in CNV/DNV.
Factoriseren (factoring) (in PPL):
Eliminatie van literalen op grond van 'Lokale redundantie'.
Betreft relaties tussen alternatieven/ disjuncten (literalen binnen disjuncties).
(7.1b1) Elimineren van disjuncte literalen; op grond van 'Lokale equivalentie' (onder unificatie).
Eliminatie van doublure(s).
Principe: 'Propositional reduction rule', 'P-reduction'.
N(r) : operator van gereduceerde clauses verkregen door p-reductie.
Reduct: 'P-reduct'.
(7.1b2) Elimineren van disjuncte literalen; op grond van 'Lokale implicatie' (onder unificatie).
Condensatie (van disjuncties).
Elimineren van 'lokaal-dominante' disjuncte elementen.
Volgens 'Lokaal-disjunct implicatieregel'
(7.1b2-sub) Op grond van 'Complexe implicatie van conjunctie' in CNV/DNV
DNV Conjunctie eliminatie regel.
(7.1c) Op grond van 'Complexe equivalentie'; in CNV
Betreft relatie tussen meerdere (complexe) disjuncties.
Zie (7.2a).

(7.2) Reductie wegens redundantie van (complexe) disjuncties; in CNV
Elimineren van (complexe) disjuncties
Op grond van 'Globale redundantie', d.i. overtolligheid op de hoofdlijn.
(Alle onder parafrase/ equivalentie).
(7.2a) Op grond van 'Complexe equivalentie'; in CNV
Betreft relatie tussen meerdere (complexe) disjuncties.
(7.2b) Op grond van 'Transferente equivalentie'; in CNV
Betreft relatie tussen een unit clause en een literaal binnen een complexe disjunctie.
De unit clause impliceert de complexe disjunctie.
Impliceert Clause implication.
Disjunctief Syllogisme.
Principe: 'One-Literal Rule' (a) (Davis Putnam, 1960):
(7.2c) Op grond van 'Complexe implicatie van disjunctie'; in CNV
Betreft relatie tussen (complexe) equivalenties.
De éne disjunctie is bevat in de andere.
CNV Conjunctie eliminatie regel.

(7.3) Reductie wegens 'Niet-fatale' Contradictie; in CNV/DNV.
Elimineren van Redundanties, wegens Contradictie
(Alle onder parafrase/ equivalentie).
(7.3a) Reductie op grond van Lokale onwaarheid; in CNV/DNV.
Speciaal geval van (7.1b2): 'Lokale implicatie' (onder unificatie).
Elimineren van 'zwakkere' elementen.
Volgens 'Lokaal-disjunct implicatieregel'.
(7.3b) Reductie wegens basale contradictie in conclusie; in afleiding
De hoofdwetten tbv. 'Resolutie' c.q. 'Fatale reductie' (in PPL).
Tbv. Resolutie bewijsmethode.
Analoog aan (7.3a).
(7.3b1) Wegens onware conclusie uit ware bewering
(7.3b2) Wegens onware conclusie uit onware bewering
(7.3b3) Wegens strijdige conclusie uit (ware) bewering
(7.3c) Reductie op grond van 'Lokale contradictie'; in CNV/DNV
Betreft relaties binnen één disjunctie, m.n. (lokale) 'taulologie'.
'Tautologische (pseudo-)contingenties'.
Principe: 'Tautology Rule' (Davis Putnam, 1960).
(7.3d) Reductie op grond van 'Transferente contradictie'; in CNF
Betreft relatie tussen een unit clause en een literaal binnen een complexe disjunctie.
Principe: 'One-Literal Rule' (b) (Davis and Putnam, 1960);
(a) Algemeen:
'Unit Resolution', 'U-resolutie'.
Principe: 'Unit resolution rule'.
Reduct: 'U-resolvent'.
(b) De resolvent is een unit clause.
'Unit Resulting resolution', 'UR-resolutie'.
Principe: 'Unit resulting resolution rule'.
Reduct: 'UR-resolvent'.
(7.3d1) Met een tweeplaatsige disjunctie
(7.3d2) Met een méérplaatsige disjunctie
(7.3d3) De resterende disjunctie bevat enkel positieve literalen
Positive hyper-resolution
Principe: 'Positive hyper-resolution rule'.
(7.3d4) De resterende disjunctie bevat enkel negatieve literalen
Negative hyper-resolution
Principe: 'Negative hyper-resolution rule'.
(7.3e) Reductie op grond van 'Transferente contradictie'; in DNV
DNV conjunct eliminatie regel

(7.4) Reductie via Samentrekken (Contractie) van (complexe) disjuncties; in CNV
Samentrekking (contractie) van verschillende clauses.
Met eventueel eliminatie van equivalente literalen.
Op grond van 'Parallelle/ Symmetrische equivalentie' (onder unificatie).
D.i. (gedeeltelijke) equivalentie van complexe disjuncties.
(7.4a) 'Parallelle/ Symmetrische equivalentie', zonder tegelijk 'Parallelle/ Symmetrische contradictie'; in CNV
Opties:
(7.4a1) Met toepassing van Conjunctie-splitsing
D.w.z. Complexe conjunctie reductie.
(Met degressie). (7.4a2) Contractie, daarna comprimatie wegens 'Lokale equivalentie'
Met als gevolg 'Lokale redundantie' (zie ook elders).
Principe: 'Pure Literal Rule' (Davis and Putnam, 1960, p.43-52).
(Met degressie). (7.4a3) Met 'Parallelle/ Symmetrische implicatie' in CNF
(onder unificatie).
D.i. Disjunctief normaal Comprimatie van conjuncte disjuncties.
(Onder parafrase/ equivalentie).
(Comprimatie, géén reductie!).
Zie ook (6.5) Conjunctie disjunctief comprimatie
(7.4b) 'Parallelle/ Symmetrische equivalentie', met tegelijk 'Parallelle/ Symmetrische contradictie'; in CNV.
Zie hiervoor onder (7.5) Reductie via Absorptie.

(7.5) Reductie via Absorptie
Samentrekken (contractie) van disjuncties. Met eliminatie van complementaire literalen.
Absorptie: De éne clause (disjunctie) wordt opgenomen door een andere clause (disjunctie).
Op grond van 'Parallelle/ Symmetrische contradictie'
D.i. contradictie tussen literalen van verschillende clauses (onder unificatie).
Binaire resolutie;
'Propositional resolution', 'P-resolution'.
Principe: 'Resolution rule' (J.A. Robinson, 1965):
Operator: 'Propositional resolution rule', 'Binary resolution rule'.
Reduct: 'P-resolvent' (Géén equivalentie).
Varianten: (Sommige onder parafrase/ equivalentie, andere met degressie).
(7.5a) Met daarnaast uitsluitend uniforme literalen, in PPL (c.q. unificeerbare literalen, in PDL)
Reductie via Disjunctief normaal Comprimatie van conjuncte disjuncties;
Daarna eliminatie van lokale complementaire conjuncte literalen.
(Onder parafrase/ equivalentie).
(7.5b) Met daarnaast uitsluitend niet-unificeerbare literalen
Alleen symmetrische eliminatie van complementaire literalen
(Met degressie).
(7.5c) Met wel en niet-unificeerbare literalen
Opties: (Alle met degressie).
(7.5c1) Alleen eliminatie van symmetrisch-complementaire literalen (vgl. 7.5b)
Eérst eliminatie van symmetrisch-complementaire disjuncte literalen.
Principe: 'Splitting Rule' (Davis and Putnam, 1960):
(7.5c2) Absorptie
Extra verlaging van logische kracht.
Eérst eliminatie van symmetrisch-complementaire disjuncte literalen;
daarna samentrekking (contractie) van disjuncties;
daarna eliminatie van lokaal-equivalente disjuncten.
(7.5c3) Absorptie, en vervolgens disjunctie-expansie
(7.5c4) Clause-eliminatie
Eérst samentrekking (contractie) van disjuncties;
daarna 'lokale contradictie', d.w.z. (lokale) taulologie;
daarna eliminatie van gehele disjunctie.
(7.5d) Wegens 'Dubbele Parallelle/ Symmetrische contradictie'
(onder unificatie).
Geen reductie van formule, maar vorm van comprimatie (met transformatie van hoofdconnectief).
Handig voor reductie van de verzameling literalen (Standaardisatie)
(Alle onder parafrase/ equivalentie).
(7.5d1) Reductie tot Equivalentie
(7.5d2) Reductie tot Exclusief-disjunctie

VIII. Reductie wegens 'Fatale' Contradictie.


(8.1) Reductie op grond van 'Basale contradictie' (unit conflict)
Betreft relatie tussen meerdere unit clauses op de hoofdlijn.
'Fatale' reductie: levert geslaagde Resolutie.
T.b.v. bewijs door weerlegging van het tegendeel ('Reductio ad absurdum').
(Alle onder parafrase/ equivalentie).
(8.1a) Op grond van 'Complete contradictie'
Wegens Exclusief disjunctie.
(8.1b) Op grond van 'Basale falsificatie'
Wegens Implicatie door basale onwaarheid.

IX. Wetten voor bewijs-via-substitutie (in PPL)


(9.1) Substitutie via Equivalentie
(9.1a) Transferente eliminatie van equivalentie
(9.1b) Equivalentie eliminatie regel ('≡ el')
(Is in feite een vorm van 'symmetrisch' modus ponens).
(9.2) Introductie of uitbreiding van Implicatie
(9.2a) Implicatie introductie regel ('> in')
(9.2b) Voorwaardelijke negatieve premisse.
(9.2c) Implicatie toevoeging
(9.3) Wet van de Contrapositie
(9.4) Substitutie via Implicatie
Bewijs via 'bevestigende wijs'
Modus ponens (MP), 'Material detachment'.
Implicatie eliminatie regel ('> el')
(9.5) Weerlegging via 'ontkennende wijs'
Contrapositie, Modus tollens (MT).
(9.5-sub) Weerlegging via evidente negatie
(9.6) Bewijs via 'ketenredenering', c.q. 'sluitredenering' (syllogisme)
(versie PPL).
(9.6a) Regel van Algemeen syllogisme
(9.6b) Regel van keten redenering
[geen equivalentie!]
(9.7) 'Disjunct-implicatieregel'
(via transitiviteit). [geen equivalentie!]
(9.8) Disjunctie Eliminatie regel 'v el' ('officieel')
(9.9) Voorwaardelijke premisse-regel

X. Wetten tbv. Convergente reductie bewijsvoering (in PPL).


(10.1) DNV Conjunctie eliminatie regel
[zie ook (7.2c-sub)]
(10.2) DNV Conjunct eliminatie regel
(10.3) Afleiden van 'zwakkere' beweringen [I]
(10.3a) Conjunctie eliminatie regel ('& el')
(10.3b) Disjunctie introductie regel ('v in')
Onbeperkte disjunctieve uitbreiding.



VII. Wetten tbv. 'Reductie' van (complexe) formules.



Principes van
syntactische doublure-reductie;
semantische equivalent-reductie (d.i. parafrase-reductie) (in CNF):



Te gebruiken bij diverse bewijsmethodes in formele logica, bijvoorbeeld:

[INHOUD VAN DIT GEDEELTE:]

XI. Afleiden van 'zwakkere' beweringen [II]


(11.1) Uitbreiding of reductie van premisse(n)
(11.2) Uitbreiding of reductie van conclusie(s)

XII. Distributiewetten mbt. implicaties


(12.1) Distributie van premisse(n)
(12.1) Distributie van conclusie(s)

XIII. Wetten van Import en export



XIV. Overige nuttige wetten en regels in PPL