[informatica] Propositielogica: afleidingsregels

Moderators: ArcherBarry, Fuzzwood

Berichten: 206

[informatica] Propositielogica: afleidingsregels

afleidingenprobleem1.PNG
Bovenaan wordt een afleidingsregel geïntroduceerd, namelijk de ¬I-regel.

Onderaan wordt een voorbeeld uitgewerkt die gebruikmaakt van deze regel. Echter, bovenaan is te zien dat zowel φ als ¬φ moeten afgeleid worden uit eenzelfde ψ.

Maar dat is in het voorbeeld toch niet het geval?

Want q wordt afgeleid uit p, p->q terwijl ¬q een hulpaanname is, dus die wordt eigenlijk afgeleid uit zichzelf (¬q). Hier mag je dus de ¬I-regel toch niet toepassen?




Hetzelfde probleem treedt hier op:
afleidingenprobleem2.PNG
afleidingenprobleem2.PNG (13.24 KiB) 1269 keer bekeken
Bovenaan wordt een afleidingsregel geïntroduceerd, namelijk de ¬I*-regel.
Onderaan wordt een voorbeeld uitgewerkt die gebruikmaakt van deze regel. Echter, bovenaan is te zien dat zowel φ als ¬φ moeten afgeleid worden uit eenzelfde ¬ψ.

Maar dat is in het voorbeeld toch niet het geval?

Want ¬p en ¬¬p worden beiden respectievelijk afgeleid uit ¬p en ¬¬p?

Wilt iemand me hiermee helpen? Alvast hartelijk bedankt.

Zie hier voor de voorbeelden (eerste voorbeeld pagina 56 en tweede voorbeeld pagina 58): http://resources.illc.uva.nl/lvi/978904 ... _BW_02.pdf

Gebruikersavatar
Berichten: 2.708

Re: [informatica] Propositielogica: afleidingsregels

SlimmeRick schreef: vr 16 okt 2020, 18:29 Onderaan wordt een voorbeeld uitgewerkt die gebruikmaakt van deze regel. Echter, bovenaan is te zien dat zowel φ als ¬φ moeten afgeleid worden uit eenzelfde ψ.

Maar dat is in het voorbeeld toch niet het geval?
Jawel, om dat in te zien neem:
\(\Sigma = \{ p \rightarrow q \}\)
\(\psi = p \)
\(\Phi = \{\lnot q \}\)
\(\phi = q\)
Laatst gewijzigd door Math-E-Mad-X op za 17 okt 2020, 13:16, 1 keer totaal gewijzigd.

Gebruikersavatar
Berichten: 2.708

Re: [informatica] Propositielogica: afleidingsregels

Om precies te zijn: men legt uit dat \(\lnot \phi\) moet worden afgeleid uit \(\Phi\) en \(\psi\), maar dat wil niet zeggen dat \(\psi\) ook daadwerkelijk gebruikt moet worden in die afleiding. Als \(\lnot \phi\) afgeleid kan worden uit alleen \(\Phi\) dan is dat ook prima.


Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

Math-E-Mad-X schreef: za 17 okt 2020, 13:15 Als \(\lnot \phi\) afgeleid kan worden uit alleen \(\Phi\) dan is dat ook prima.
Bedankt!
Maar ik snap het nog steeds niet. Wat u zegt maakt het voorbeeld waar, maar wat u zegt is toch niet wat de definitie zegt?

¬ϕ moet worden afgeleid uit Φ en ψ, maar hier kan ¬ϕ toch niet afgeleid worden uit ψ=p?

Berichten: 217

Re: [informatica] Propositielogica: afleidingsregels

Math-E-Mad-X schreef: za 17 okt 2020, 13:11 Jawel, om dat in te zien neem:
\(\Sigma = \{ p \rightarrow q \}\)
\(\psi = p \)
\(\Phi = \{\lnot q \}\)
\(\phi = q\)
Dit klopt niet: in voorbeeld 4.6 is Phi de lege verzameling: Φ = ∅
De ¬q (die "uit de lucht komt vallen") wordt geintroduceerd door
de →I regel: na →I,[-2] wordt ¬q weer ingetrokken:
dat geeft als resultaat de conclusie: "ALS ¬q geldt, DAN geldt ¬p"

Dus uit p en Σ={ p→q } leiden ze q af.
Samen met ¬q levert dit een contradictie.
Hierop werkt de ¬I regel met als conclusie: ¬p (onder ¬I,[-1])
Vervolgens wordt met →I de bewering ¬q ingetrokken, en houden we over:
¬q → ¬p


Soortgelijk bij voorbeeld 4.8:
de ¬p onder (1) komt van de ¬E* regel
de ¬¬p onder (2) komt van de →I regel, en wordt bij →I,[-2] weer ingetrokken.

Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

RedCat schreef: za 17 okt 2020, 19:49
Math-E-Mad-X schreef: za 17 okt 2020, 13:11 Jawel, om dat in te zien neem:
\(\Sigma = \{ p \rightarrow q \}\)
\(\psi = p \)
\(\Phi = \{\lnot q \}\)
\(\phi = q\)
Dit klopt niet: in voorbeeld 4.6 is Phi de lege verzameling: Φ = ∅
De ¬q (die "uit de lucht komt vallen") wordt geintroduceerd door
de →I regel: na →I,[-2] wordt ¬q weer ingetrokken:
dat geeft als resultaat de conclusie: "ALS ¬q geldt, DAN geldt ¬p"

Dus uit p en Σ={ p→q } leiden ze q af.
Samen met ¬q levert dit een contradictie.
Hierop werkt de ¬I regel met als conclusie: ¬p (onder ¬I,[-1])
Vervolgens wordt met →I de bewering ¬q ingetrokken, en houden we over:
¬q → ¬p


Soortgelijk bij voorbeeld 4.8:
de ¬p onder (1) komt van de ¬E* regel
de ¬¬p onder (2) komt van de →I regel, en wordt bij →I,[-2] weer ingetrokken.
Hartelijk bedankt, maar ik heb uw uitleg totaal niet begrepen... Phi kan hier toch onmogelijk de lege verzameling zijn? Want dan heb je de negatie van de lege verzameling en klopt eigenlijk niks meer van de definitie.

Berichten: 217

Re: [informatica] Propositielogica: afleidingsregels

Kijk eerst terug naar de →I regel op pagina 52:
Aan een verzameling formules Σ wordt formule φ toegevoegd, en met dit geheel wordt formule ψ afgeleid.
De →I regel trekt vervolgens formule φ weer in (bij de streep: →I,[-φ])
en concludeert: uit formuleverzameling Σ kunnen we afleiden: φ → ψ
Dit betekent dat uit formuleverzameling Σ volgt: "ALS φ geldt DAN geldt ψ".

Op zich (uiteraard) logisch: als φ bij aanvang zou gelden (= WAAR zou zijn),
dan zouden we uit Σ' = (Σ ∪ {φ}) ook ψ af kunnen leiden (net zoals we gedaan hebben boven de streep van de →I regel)

Nu voorbeeld 4.6 op pagina 56:
Φ = ∅ (we gebruiken geen (andere) formules)
ψ = p (maar die gebruiken we niet om ¬q af te leiden)
¬φ = ¬q (deze wordt geintroduceerd als tijdelijke 'hulpaanname' door de →I regel)
Voor de ¬q hebben we dus geen extra formules nodig, maar deze formule mogen we direct gebruiken wegens de →I regel.
Bij →I,[-2] trekken we deze formule weer in.

Vervolgens naar de ¬I regel:
Σ = { p → q}
ψ = p
Φ = ∅
φ = q
¬φ = ¬q
Uit de hulpaanname volgt ¬q,
uit Σ ∪ {ψ} = (p → q met toevoeging van p) volgt q.
Als we p toevoegen levert dit de tegenstrijdigheid q EN ¬q,
dus trekken we bij ¬I,[-1] formule p weer in en concluderen: ¬p
("p kan niet WAAR zijn, anders volgt q en we hadden al ¬q")

Tenslotte trekken we bij →I,[-2] formule ¬q weer in (zoals hierboven beschreven) en is de afleiding voltooid:
uit Σ ∪ Φ = { p → q } hebben we afgeleid ¬q → ¬p

Wordt het hiermee wat duidelijker?

Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

Hartelijk bedankt.

Het wordt een beetje duidelijker. Dus nu zegt u dat zowel q als ¬q afgeleid worden uit p?

“Als we p toevoegen levert dit de tegenstrijdigheid q EN ¬q”, maar p levert toch samen met p → q q op en niet ¬q? Want ¬q is toch een aanname? Of neem je aan dat p zowel q als ¬q oplevert?

Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

RedCat schreef: zo 18 okt 2020, 00:23 ψ = p (maar die gebruiken we niet om ¬q af te leiden)
Maar volgens de definitie moet je dat toch wel doen?

Berichten: 217

Re: [informatica] Propositielogica: afleidingsregels

We gaan uit van Σ = { p → q } en hulpaanname ¬q (de geldigheid van deze hulpaanname wordt gelegitimeerd door de →I regel).

Er zijn dus 2 formules geldig voordat we de ¬I regel toepassen:
p → q en ¬q

De ¬I regel voegt p toe,
uit p en p → q leiden we q af.

We hebben nu:
¬q (we hebben aangenomen dat deze geldig is wegens →I)
en
q (afgeleid uit p en p → q).
Dit is een tegenstrijdigheid, dus
concludeert de ¬I regel: ¬p, en trekt gelijktijdig de formule p weer in: ¬I,[-1].


In het rechter bovendeel van de boom hebben we volgens de definitie van de ¬I regel " Φ,ψ " staan.
In dit geval is
Φ = ∅
ψ = p
Maar dit betekent niet dat we ¬q (= ¬φ uit de definitie) MOETEN afleiden uit p.
Als de geldigheid van ¬q NIET gelegitimeerd zou zijn door →I, dan hadden we ¬q WEL zelf moeten afleiden uit Φ en ψ.
Omdat we ¬q niet uit alleen p kunnen afleiden, zouden we in dat geval extra formules in Φ nodig gehad hebben, bijvoorbeeld (p→¬q) ∈ Φ.
Maar in ons geval (= voorbeeld 4.6) hoeven we ¬q niet af te leiden, we nemen aan dat deze geldig is wegens →I.
Daarnaast neemt de ¬I regel aan dat ook p geldt, maar we zijn niet verplicht om deze formule te gebruiken om nogmaals de geldigheid van ¬q aan te tonen (als deze al aangetoond is of aangenomen is).

Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

Hartelijk bedankt, maar ik snap het nog steeds niet.

"Er zijn dus 2 formules geldig voordat we de ¬I regel toepassen:
p → q en ¬q"
En p en q dan?

"De ¬I regel voegt p toe,
uit p en p → q leiden we q af."
Bedoelt u niet dat de ->E-regel q toevoegt?

"Als de geldigheid van ¬q NIET gelegitimeerd zou zijn door →I,"
Ik snap niet zo goed wat u bedoelt met gelegitimeerd zijn door →I. Maar oké, ¬q is een hulpaanname en die is geldig omdat die gelegitimeerd zou zijn door →I, maar mag je dan zomaar zeggen "ah die ¬q is afgeleid uit p"? Dus in plaats van die p kon er bijvoorbeeld ¬p staan gewoon omdat je aanneemt dat ¬q waar is?
Want dat is wat u hier zegt, u zegt dat ψ = p en dat is waar omdat ¬q gelegitimeerd is.

Berichten: 217

Re: [informatica] Propositielogica: afleidingsregels

SlimmeRick schreef: "Er zijn dus 2 formules geldig voordat we de ¬I regel toepassen:
p → q en ¬q"
En p en q dan?
p wordt geintroduceerd door ¬I
q wordt afgeleid uit p (die nu beschikbaar is) en p → q



"De ¬I regel voegt p toe,
uit p en p → q leiden we q af."
Bedoelt u niet dat de ->E-regel q toevoegt?
Ja, dus vollediger:
"De ¬I regel voegt p toe,
uit p en p → q leiden we via de →E regel q af."


"Als de geldigheid van ¬q NIET gelegitimeerd zou zijn door →I,"
Ik snap niet zo goed wat u bedoelt met gelegitimeerd zijn door →I.
We nemen aan dat ¬q geldig (= WAAR) is omdat →I zegt dat dat zo is.
Zie de definitie van →I op pagina 52.


Maar oké, ¬q is een hulpaanname en die is geldig omdat die gelegitimeerd
zou zijn door →I
maar mag je dan zomaar zeggen "ah die ¬q is afgeleid uit p"?
Nee: ¬q is NIET afgeleid uit p, ¬q is geldig omdat we dat aannemen (ondanks en los van het feit dat p daar ook geldig is). Een aanname is per definitie geldig

Dus in plaats van die p kon er bijvoorbeeld ¬p staan gewoon omdat je aanneemt dat ¬q waar is?
Klopt: er had elke willekeurige verzameling formules boven ¬q kunnen staan omdat je geen enkele formule nodig hebt om ¬q af te leiden: ¬q wordt nergens uit afgeleid: ¬q is een aanname en is daarom geldig

Want dat is wat u hier zegt, u zegt dat ψ = p en dat is waar omdat ¬q gelegitimeerd is.
Nee:
ψ = p = geldig volgens de definitie van ¬I
en los daarvan is
¬φ = ¬q = geldig volgens de definitie van →I
Daarom zijn we vrij p en ¬q in de afleiding te gebruiken:
- p totdat ¬I deze weer intrekt (in voorbeeld 4.6 bij ¬I,[-1] )
- ¬q totdat →I deze weer intrekt (in voorbeeld 4.6 bij →I,[-2] )

Berichten: 206

Re: [informatica] Propositielogica: afleidingsregels

"De ¬I regel voegt p toe"
Wat bedoelt u hiermee? Voordat de ¬I-regel werd toegepast stond p daar toch al? En p zelf is toch ook een hulpaanname?

Berichten: 217

Re: [informatica] Propositielogica: afleidingsregels

Zie de definitie van de ¬I regel op pagina 56.
Uit een formuleverzameling Σ ∪ Φ willen we ¬ψ afleiden.
De ¬I regel zegt: stel dat
- toevoeging van ψ aan verzameling Σ leidt tot φ
- toevoeging van ψ aan verzameling Φ leidt tot ¬φ
dan leidt toevoeging van ψ aan Σ ∪ Φ tot een tegenstrijdigheid: φ en ¬φ kunnen immers niet tegelijkertijd geldig zijn.
Daarom zegt ¬I: ψ is ongeldig (trek deze weer in) en omdat ψ ongeldig (=ONWAAR) is moet ¬ψ wel geldig (=WAAR) zijn.
Conclusie van de ¬I regel: ¬ψ.

Uit de formuleverzameling Σ ∪ Φ hebben we nu afgeleid ¬ψ.

In voorbeeld 4.6 is Σ ∪ Φ = { p→q } ∪ ∅ = { p→q }
Dus uit p→q leiden we af: ¬q→¬p
Als we de ¬I regel NIET zouden gebruiken in de afleiding, dan stond p ook niet bovenaan.
p ∉ (Σ ∪ Φ)
¬q ∉ (Σ ∪ Φ)
We mogen aannemen ("hulpaanname") dat p geldig is wegens ¬I, en die mogen we overal boven de ¬I streep gebruiken in onze afleiding.
We mogen aannemen ("hulpaanname") dat ¬q geldig is wegens →I, en die mogen we overal boven de →I streep gebruiken in onze afleiding.

NOOT: in dit voorbeeld zorgt →I voor verwarring in ¬I:
hier wordt ¬q niet geldig verklaard via een afleiding uit Φ en ψ,
maar wordt ¬q direct geldig verklaard vanuit →I (en hebben we dus geen verdere afleiding van ¬q nodig: ¬q is al geldig verklaard).

Reageer