Logica voor informatici - voorbeeld 4.5

Moderators: ArcherBarry, Fuzzwood

Reageer

Bericht 07-10-'07, 11:21

barrel

Berichten: 42

Logica voor informatici - voorbeeld 4.5

Hallo allemaal,

Ik maak gebruik van het boek 'Logica voor Informatici', tweede druk. Voorbeeld 4.5 vraagt de afleiding van

(p of q) -> r uit (p -> r) en (q -> r)

(p->r) en (q->r) wordt gesplist via de en-eliminatie tot twee formules waarbij de introductie van de hulpaannames p resp q leiden tot de (tussentijdse) conclusie r. Nu zou ik verwachten dat de hulpaannames p en q tot de formule (p en q) zou leiden waarna we via de -> introductie de hulpaannames kunnen elimineren door hetvolgende af te leiden: (p en q) -> r. Het boek introduceert echter een derde hulpaanname (p of q) en komt tot de afleiding (p of q) -> r.

Ofwel (hopelijk ziet dit er duidelijk uit na het plaatsen van dit bericht ;-)

Code: Selecteer alles

(p -> r) en (q -> r)

   (p -> r) en (q -> r)

____________________

   ____________________

(p -> r)

 p (1)		 (q -> r)

 q (2)	 p (1)  q (2)

____________________________	   __________________________	 ____________

   r

r

(p en q)

   __________________________________________________________________

(p en q) -> r
Analoog meen ik ook (p en q) te kunnen gebruiken als hulpaannames, p resp. q hieruit af te leiden. Ik denk dat men de -> introductie op de laatste regel dus direct hulpaannames 1 en twee worden ingetrokken, dit zou in ieder geval wel het geval zijn als ik vertrokken was de hulpaanname (p en q).

Met de waarheidstabellen zie ik dat er bijv. voor p=1, q=0 en r=0 de gevraagde uitwerking klopt en die van mij niet, ik doe dus iets fout ;-)

Kan iemand wat uitleg geven over de fout die ik maak?
Omhoog

Bericht 07-10-'07, 19:59

barrel

Berichten: 42

Re: Logica voor informatici - voorbeeld 4.5

Oei... :D is er niemand die hier de dit kan uitleggen? Dit lijkt me nogtans een beginnersprobleem?
Omhoog

Bericht 07-10-'07, 20:08

oscar2

Gebruikersavatar
Berichten: 271

Re: Logica voor informatici - voorbeeld 4.5

Als je haast hebt kun je misschien beter nog wat uitleggen. Je gebruikt m.i. een nogal exotische notatie. Wat bedoel je met "afleiden van"? Ik zie alleen drie afbeeldingen. Wat bedoel je met het splitsen? Etc.
Omhoog

Bericht 07-10-'07, 20:22

barrel

Berichten: 42

Re: Logica voor informatici - voorbeeld 4.5

Als je haast hebt kun je misschien beter nog wat uitleggen. Je gebruikt m.i. een nogal exotische notatie. Wat bedoel je met "afleiden van"? Ik zie alleen drie afbeeldingen. Wat bedoel je met het splitsen? Etc.
Echt haast heb ik niet, ik heb wel het idee dat dit een fundamenteel probleem is wat ik moet begrijpen om verder te kunnen.

Het is de notatie die door het boek gebruikt wordt. Aangezien ik dat indertijd op de UTwente gezien heb en nu ook op de VUB nam ik aan dat het een soort standaard notatie is... onterecht blijkbaar.

Anyway, het doel is dus dat je met een gegeven stelling (propositielogica) begint en er een andere uit af kan leiden.

Hetvolgende is gegeven: (p -> r) en (q -> r). De 'en' hier is de logische 'n', de '->' staat voor implicatie.

In mijn boomstructuur (die op sommige PCs er goed uitziet, op andere niet ;-)... Toch maar LaTeX gebruiken?) Start ik dus met het gegeven "p impliceert r" (p -> r) en ik maak gebruik van een hulpaannamen p (dit is de reden waarom er een 1 tussen haakjes achter de p staat), zo'n hulpaanname moet later weer weggehaald worden.

Twee termen staan boven een streep, en onder de streep staat dan de conclusie van die twee termen. Zo leidt bijvoorbeeld de term '(p -> r)' enerzijds en 'p' anderzijds tot het logische gevolg 'r'

Hopelijk is dit wat duidelijker? Veel meer kan ik er ook niet van maken, ben zelf nog mijn weg aan het zoeken in de logica (heh... en dit is niet eens een woordgrap ;-) achter de notaties.

Barry
Omhoog

Bericht 07-10-'07, 21:20

oscar2

Gebruikersavatar
Berichten: 271

Re: Logica voor informatici - voorbeeld 4.5

OK, je combineert dus zowel variabelen: p of q, maar ook afbeeldingen (p->r) en (q->r). Maar de boomstructuur en de truuk met de hulpvariabelen snap ik nog niet (misschien iemand anders wel hoor!). Waarom mag je zomaar ergens een hulpvariabele bij zetten. En hoe laat je die dan weer weg?
Omhoog

Bericht 07-10-'07, 21:25

barrel

Berichten: 42

Re: Logica voor informatici - voorbeeld 4.5

OK, je combineert dus zowel variabelen: p of q, maar ook afbeeldingen (p->r) en (q->r). Maar de boomstructuur en de truuk met de hulpvariabelen snap ik nog niet (misschien iemand anders wel hoor!). Waarom mag je zomaar ergens een hulpvariabele bij zetten. En hoe laat je die dan weer weg?
Heh ;-) Dat is juist de hele "truc" die ik probeer te doorgronden.

Het idee is dat je ergens vanuit gaan (een hulpaannamen), in mijn geval bijvoorbeeld 'p'. Als je nu later deze hulpaanname weer in kan trekken door een gekende formule 'r' te combineren tot 'p -> r', dan kom je tot de conclusie dat je de hulpaanname 'p' dus eigenlijk niet nodig hebt voor de eindconclusie. Deze is dan weer ingetrokken. Dit heeft weer te maken met de implicatie. Als 'r' waar is, dan maakt het eigenlijk niet uit of 'p' waar of niet waar is, dat verandert de uitkomst niet en daarmee trek je je aanname dus weer in....

Is dit iets duidelijker? Ik hoop het maar ben er zelf ook niet zeker van ;-)

Barry
Omhoog

Bericht 09-10-'07, 10:56

oscar2

Gebruikersavatar
Berichten: 271

Re: Logica voor informatici - voorbeeld 4.5

Ik zie dat nog niemand te hulp is geschoten. Dan zal ik het toch nog maar eens proberen. Ik ben wel benieuwd hoe je variabelen (p) en afbeeldingen (p->r) combineert.

Het klopt dat je hulpvariabelen kunt invoeren als je op een of andere manier kunt constateren dat aan hulpvariabele altijd voldaan wordt. Bij gewone combinatie van logische variabelen kun je bij voorbeeld A+!B vervangen door (A+!B)*(A+!A) (met !A bedoel ik niet(A)) omdat A+!A altijd waar is.

Maar probeer nog eens te vertellen wat je precies doet. Eerst splits je de afbeelding (p->r) en (q->r) in twee losse afbeeldingen. De afbeelding (p->r) een de afbeelding (q-r). Dat snap ik. Immers als p en q allebei r impliceren dan geldt ook dat p r implicieert (en analoog voor q).

Maar dan zet een p en een q naast. Wat bedoel je daarmee? Is dat bij voorbeeld een "en" of een "of". Bij voorbeeld: (p->r) en (p). En bedoel je met p het geval dat p waar is? Dan vind je met mijn voorbeeld inderdaad dat r waar is. Maar dan zie ik niet hoe deze hulpvariabele weer kan verdwijnen.

En wat is de reden dat je dan een derde kolom met p (1) q(1) introduceert? Is dat iets om de hulpvariabelen later te kunnen verwijderen?

Overigens klopt het resultaat natuurlijk gewoon (p->r) en (q->r) betekent dat als r waar is als p waar is, maar ook als q waar is. Het is dus voldoende als p of q waar is. Dus (p of q) ->r. Maar het gaat er natuurlijk om hoe je dit bewijst. Toch?
Omhoog

Bericht 10-10-'07, 13:20

barrel

Berichten: 42

Re: Logica voor informatici - voorbeeld 4.5

Maar dan zet een p en een q naast. Wat bedoel je daarmee? Is dat bij voorbeeld een "en" of een "of". Bij voorbeeld: (p->r) en (p). En bedoel je met p het geval dat p waar is? Dan vind je met mijn voorbeeld inderdaad dat r waar is. Maar dan zie ik niet hoe deze hulpvariabele weer kan verdwijnen.
De p die ernaast gezet wordt is een hulpaanname; voor het gemak nemen we (tijdelijk) aan dat dit waar is.

Dus eigenlijk staat er (p -> r) en onder de voorwaarde p (de hulpaanname) leidt dit tot r
En wat is de reden dat je dan een derde kolom met p (1) q(1) introduceert? Is dat iets om de hulpvariabelen later te kunnen verwijderen?
De getallen duiden aan dat het gaat om een hulpvariabele; via latere reductiestappen moeten deze verwijderd worden.

Via een latere introductie van de implicatie (p of q) -> r zeg je dus eigenlijk dat het niet uitmaakt (als ik het goed begrijp ten minste) welke waarde p heeft, en daarmee trek je de hulpvariabele in als noodzakelijke conditie voor de afleiding.
Overigens klopt het resultaat natuurlijk gewoon (p->r) en (q->r) betekent dat als r waar is als p waar is, maar ook als q waar is. Het is dus voldoende als p of q waar is. Dus (p of q) ->r. Maar het gaat er natuurlijk om hoe je dit bewijst. Toch?
Inderdaad; het gaat erom hoe je dat bewijst. Als ik nu de regeltjes van het boek toepas meen ik ook te kunnen bewijzen dat (p en q) -> r waar is, terwijl de waarheisdtabellen hier duidelijk laten zien dat dit niet het geval is. Ik pas de regels dus op een verkeerde manier toe.....
Omhoog
Reageer

Terug naar “Huiswerk en Practica”