[informatica] logica: geldig gevolg

Moderators: ArcherBarry, Fuzzwood

Berichten: 206

[informatica] logica: geldig gevolg

In het boek van het vak "logica voor informatica", staat het volgende:
Capturelogica.JPG
Ik begrijp niet zo goed waarom alles rechts van het o-teken onwaar moet zijn. Als één formule rechts van het o-teken onwaar is, dan is het toch ook voldoende om aan te tonen dat er sprake is van een tegenvoorbeeld?

Wil iemand mij alstublieft hiermee helpen?

Alvast bedankt!

Gebruikersavatar
Berichten: 2.708

Re: [informatica] logica: geldig gevolg

SlimmeRick schreef: di 29 sep 2020, 19:45 Ik begrijp niet zo goed waarom alles rechts van het o-teken onwaar moet zijn.
In dit stukje tekst is het begrip "tegenvoorbeeld" gewoon op die manier gedefinieerd.

Waarom ze voor die definitie hebben gekozen kan niet uit dit ene stukje tekst worden opgemaakt. Dat hangt helemaal af van wat ze er in de rest van de tekst mee doen.

Berichten: 206

Re: [informatica] logica: geldig gevolg

Bedankt.

Ik vraag me af waarom ze juist voor deze definitie gekozen hebben. Zie hier voor het officiële PDF-bestand van het eerste deel van het boek: http://resources.illc.uva.nl/lvi/978904 ... _BW_02.pdf (tot pagina 47 belangrijk)

Gebruikersavatar
Berichten: 2.708

Re: [informatica] logica: geldig gevolg

Ik heb het even vlug bekeken.

Het idee is denk ik dat een sequent feitelijk niets anders is dan een alternatieve manier om een waardering V op te schrijven. Stel bijvoorbeeld dat we de volgende waardering hebben:
\(V(p) = 1, V(q) = 1, V(r)=0.\)
Dan kunnen we dit ook opschrijven als:
\(p,q\circ r\)
Deze nieuwe notatie is iets compacter, en bovendien kunnen we hiermee ook een waardering geven aan een samengestelde formule zoals \(p\rightarrow q\) voordat we een waardering voor de atomen \(p\) en \(q\) hebbben gekozen. We kunnen bijvoorbeeld opschrijven:
\(p \rightarrow q\circ r\)
Hiermee zeggen we dat \(p\rightarrow q\) waar is, en dat \(r\) onwaar is, maar dit zegt nog niks over de vraag of \(p\) waar of onwaar is. Die keuze blijft open.

Berichten: 206

Re: [informatica] logica: geldig gevolg

Hartelijk bedankt!
Maar ik snap niet zo goed waarom...
tegenvoorbeeld.PNG
tegenvoorbeeld.PNG (13.55 KiB) 524 keer bekeken
Waarom moeten ze ALLEMAAL aan de rechterkant onwaar zijn zodat je een tegenvoorbeeld hebt?

Gebruikersavatar
Berichten: 2.708

Re: [informatica] logica: geldig gevolg

Okee, ik snap je verwarring.

Het idee is dat ze de volgende stelling willen bewijzen:

1) voor alle modelen van \(\Sigma\) geldt dat \(\phi\) ook waar moet zijn.

Dat doen ze, door een sequent op te stellen voor de omgekeerde stelling:
2) er is een model van \(\Sigma\) waarvoor \(\phi\) niet waar is.
Oftewel, een sequent met alle formules van \(\Sigma\) aan de linker kant, en \(\phi\) aan de rechter kant.

Met deze sequent kan gespeeld worden door dingen van links naar rechts te verplaatsen etcetera. Als men dan op een gegeven moment een waardering vindt waarbij alles aan de linker kant waar is, en alles aan de rechterkant onwaar, dan wil dat zeggen dat deze waardering een model is die stelling 2) waar maakt.

En een model dat stelling 2) waar maakt is een tegenvoorbeeld voor stelling 1).

Berichten: 206

Re: [informatica] logica: geldig gevolg

Hartelijk bedankt!

Maar, nogmaals, mijn verwarring gaat om het feit dat ik niet snap waarom ALLE formules rechts onwaar moeten zijn.
U beschouwt hier maar één formule rechts van het o-teken, namelijk ϕ. Maar wat als we ervan uitgaan dat het rechts ook om een formuleverzameling gaat? Zullen we hier de verzameling Ψ nemen.

De definitie zegt dat voor alle modellen van Σ geldt dat ze ook modellen zijn van Ψ. Dus als links allemaal 1-en staan en rechts een 0, dan heb je toch ook een tegenvoorbeeld gevonden? Want alles van de verzameling Σ is waar, terwijl niet alles van de verzameling Ψ waar is (je hebt namelijk een nul staan voor één van de formules uit de verzameling Ψ).

--------
"Als men dan op een gegeven moment een waardering vindt waarbij alles aan de linker kant waar is, en alles aan de rechterkant onwaar, dan wil dat zeggen dat deze waardering een model is die stelling 2) waar maakt."
Waarom alles?

--------
"Voor alle modellen van Σ geldt dat ϕ ook waar moet zijn."
Stel ϕ = {p,q}
als p waar is en q onwaar, dan is ϕ onwaar.
Dus als enkel 1 van de elementen van de verzameling bij een bepaalde waardering onwaar is, dan is de verzameling voor die waardering onwaar.

Berichten: 7.010

Re: [informatica] logica: geldig gevolg

SlimmeRick schreef: zo 04 okt 2020, 21:56Maar, nogmaals, mijn verwarring gaat om het feit dat ik niet snap waarom ALLE formules rechts onwaar moeten zijn.
Het volgende:
\(\phi_1, \cdots, \phi_n \circ \psi_1, \cdots, \psi_m\)
betekent in woorden:
Als alle condities \(\phi_i\) waar zijn dan is er ten minste een \(\psi_j\) waar.

Berichten: 206

Re: [informatica] logica: geldig gevolg

Bent u zeker? Want zie de laatste zin van mijn eerste foto. Dan klopt die zin toch niet?
"Als twee eenzelfde formules aan beide kanten van het o-teken voorkomen, dan is er geen tegenvoorbeeld."
Maar volgens uw definitie is dit onwaar.

Gebruikersavatar
Berichten: 2.708

Re: [informatica] logica: geldig gevolg

Het idee is het volgende:

We willen bewijzen (of ontkrachten) dat voor alle modellen waarin \(\phi_1\), \(\phi_2\), en \(\lnot \phi_3 \) waar zijn, er ook geldt dat \(\psi\) waar is.

Om dit te ontkrachten moeten we een model vinden waarvoor geldt dat \(\phi_1\), \(\phi_2\), en \(\lnot \phi_3\) waar zijn, maar \(\psi\) niet waar is. Dit kunen we ook opschrijven als: \(\phi_1, \phi_2 , \lnot \phi_3 \circ \psi\)

Maar dit is hetzelfde als het vinden van een model waarvoor geldt dat \(\phi_1\), \(\phi_2\) allebei waar zijn en \(\phi_3\) en \(\psi\) allebei niet waar zijn. Dit kunen we ook opschrijven als \(\phi_1, \phi_2 \circ \phi_3 , \psi\)

Dus, als we een waardering vinden die \(\phi_1\) en \( \phi_2\) allebei waar maakt, en die \(\phi_3\) en \(\psi \) allebei onwaar maakt, dan hebben we een tegenvoorbeeld voor de oorspronkelijke stelling gevonden.

Berichten: 215

Re: [informatica] logica: geldig gevolg

Een voorbeeld:
Stel je wil de geldigheid aantonen van de bewering:
uit (¬p) en (¬p → q) volgt (q).

Je moet dan aantonen dat als (¬p) waar is en tegelijkertijd (¬p → q) waar is, dat dan ook (q) waar is.

Dit is hetzelfde als aantonen dat er geen tegenvoorbeeld is, dus dat het niet mogelijk is dat
als (¬p) waar is en tegelijkertijd (¬p → q) waar is, dat dan (q) ONWAAR is,
ofwel dat het niet mogelijk is dat:
als V(¬p) = 1 is en tegelijkertijd V(¬p → q) = 1 is, dat dan V(q) = 0 is.

Het tegenvoorbeeld dat we zoeken levert dit sequent:
¬p, ¬p → q o q
met links elke waardering 1 en rechts elke waardering 0.

Omdat er maar 2 variabelen zijn, zijn er 4 waarderingen:

Code: Selecteer alles

   |  p  q  | not(p) ,  not(p) -> q    o    q
---+--------+--------+-----------------+---------
V1 |  0  0  |    1   |         0       |    0
V2 |  0  1  |    1   |         1       |    1
V3 |  1  0  |    0   |         1       |    0 
V4 |  1  1  |    0   |         1       |    1
Alleen waardering V2 maakt links zowel (¬p) = 1 als (¬p → q) = 1, maar dan is rechts (q) = 1.
Er is dus geen tegenvoorbeeld (links alles 1, rechts alles 0), dus het gevolg is geldig.

Terug naar het sequent hierboven:
¬p, ¬p → q o q
met tegenvoorbeeld = links elke waardering 1 en rechts elke waardering 0.

Elke waardering die links (¬p) = 1 maakt, maakt tegelijkertijd (p) = 0:
(V(¬p) = 1) ↔ (V(p) = 0)
(¬p) = 1 maken (links) is dus gelijk aan (p) = 0 maken (rechts).
We komen dan uit op een gelijkwaardig sequent:
¬p → q o q, p
dat dan en slechts dan een tegenvoorbeeld is als links alles 1 is, en rechts alles 0.
(hier ging je vraag over)

Ter controle:

Code: Selecteer alles

   |  p  q  | not(p) -> q    o    q    ,    p
---+--------+----------------+---------+---------
V1 |  0  0  |        0       |    0    |    0
V2 |  0  1  |        1       |    1    |    0
V3 |  1  0  |        1       |    0    |    1
V4 |  1  1  |        1       |    1    |    1
Nu maken V2, V3 en V4 links alles 1, maar in geen van de 3 validaties is rechts alles 0.
Er is dus geen tegenvoorbeeld, dus de gevolgtrekking is geldig.

Op deze wijze breek je alle formules één voor één af tot atomen, en van sequenten met alleen atomen is zeer eenvoudig te zien of er een tegenvoorbeeld is of niet:
als een atoom links EN rechts voorkomt, dan is er geen tegenvoorbeeld: een atoom kan niet tegelijkertijd 0 en 1 zijn.
Bv:
sequent
p, q, r, s o p, t, u, v, w
levert GEEN tegenvoorbeeld want p komt links en rechts voor.
sequent
p, q, r o s, t
levert WEL een tegenvoorbeeld: maak V(p)=V(q)=V(r)=1 en V(s)=V(t)=0

Het voordeel van sequenten is dat je niet meer een volledige waarheidstabel hoeft op te stellen (met n variabelen levert dat een tabel met 2^n rijen).


Nog een voorbeeld
Nu met een ongeldige gevolgtrekking (= er zijn 1 of meer tegenvoorbeelden):
Uit (¬p∧q) volgt (p):
¬p∧q o p
V(¬p∧q) = 1 maken betekent tegelijkertijd V(¬p) = 1 maken en V(q) = 1 maken.
Dit levert equivalente sequent:
¬p, q o p
(¬p) kunnen we net als in het voorbeeld hierboven als (p) naar de andere kant brengen:
q o p, p
maar V(p) = 0 maken en V(p) = 0 maken is hetzelfde, dus dit wordt:
q o p
Nu lezen we direct af:
V(q) = 1 (links) en V(p) = 0 (rechts) levert een tegenvoorbeeld.
Ter controle in de oorspronkelijke gevolgtrekking:
Als V(p) = 0 en V(q) = 1, dan is V(¬p∧q) = 1 terwijl V(p) = 0, een ongeldige gevolgtrekking.

Gebruikersavatar
Berichten: 2.708

Re: [informatica] logica: geldig gevolg

SlimmeRick schreef: zo 04 okt 2020, 21:56 Maar wat als we ervan uitgaan dat het rechts ook om een formuleverzameling gaat? Zullen we hier de verzameling Ψ nemen.
De definitie zegt dat voor alle modellen van Σ geldt dat ze ook modellen zijn van Ψ.
Ah,okee, dat kan ook, maar dat iets iets anders dan wat ze in de tekst willen doen.

In de tekst (en in mijn voorbeeld hierboven) heeft de oorspronkelijke stelling die men wil bewijzen of ontkrachten maar één formule aan de rechter kant. Om die stelling te ontkrachten probeert men een model te vinden die een aantal formules waar maakt, en tegelijkertijd een aantal andere formules onwaar. Nou ja, zie hierboven.

Berichten: 7.010

Re: [informatica] logica: geldig gevolg

SlimmeRick schreef: ma 05 okt 2020, 09:33 Bent u zeker? Want zie de laatste zin van mijn eerste foto. Dan klopt die zin toch niet?
"Als twee eenzelfde formules aan beide kanten van het o-teken voorkomen, dan is er geen tegenvoorbeeld."
Maar volgens uw definitie is dit onwaar.
Ik zie niet in waarom dit dan onwaar zou zijn volgens 'mijn' definitie.

Berichten: 206

Re: [informatica] logica: geldig gevolg

O N T Z E T T E N D bedankt voor de tijd en moeite die jullie gestoken hebben in het uitgebreid wegwerken van mijn verwarring. Nu snap ik het eindelijk!

Ik zou graag nog de volgende vraag stellen: Wat als het om deze gevolgtrekking gaat? uit (niks) volgt ψ
In mijn boek staat dat dit het geval is enkel en alleen als elke waardering een model is voor ψ en dus m.a.w. ψ een tautologie is.
Dus als ik het goed begrijp staat dan aan de linkerkant van het o-teken niks wat betekent dat er aan de linkerkant allemaal "1"-en staan*? Zo ja, waarom is dat zo?

*aan de linkerkant van het o-teken staan allemaal "1"-en de gevolgtrekking is geldig -> ψ is een tautologie (is nooit onwaar), toch?

Berichten: 206

Re: [informatica] logica: geldig gevolg

SlimmeRick schreef: ma 05 okt 2020, 14:55 O N T Z E T T E N D bedankt voor de tijd en moeite die jullie gestoken hebben in het uitgebreid wegwerken van mijn verwarring. Nu snap ik het eindelijk!

Ik zou graag nog de volgende vraag stellen: Wat als het om deze gevolgtrekking gaat? uit (niks) volgt ψ
In mijn boek staat dat dit het geval is enkel en alleen als elke waardering een model is voor ψ en dus m.a.w. ψ een tautologie is.
Dus als ik het goed begrijp staat dan aan de linkerkant van het o-teken niks wat betekent dat er aan de linkerkant allemaal "1"-en staan*? Zo ja, waarom is dat zo?

*aan de linkerkant van het o-teken staan allemaal "1"-en en de gevolgtrekking is geldig -> ψ is een tautologie (is nooit onwaar), toch?

Reageer