Bewijs uit het ongerijmde en logica
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 71
Bewijs uit het ongerijmde en logica
Hieronder heb ik enkele tautologieën verzameld. Kan iemand mij vertellen welke nu precies het bewijs uit het ongerijmde aantoont? Want na wat zoekwerk op het net is het er mij niet echt duidelijker op geworden..
(1a) ((~(A -> B) -> ~A) ^ A) -> B
(1b) (~(A -> B) -> ~A) -> (A -> B)
(2) ((~B -> ~A) ^ A) -> B
(3) (~B -> (A ^ ~A)) -> B
Hierbij zijn A en B proposities en ~A betekent "niet A".
Zelf maak ik gebruik van (1b) bij stellingen vd vorm A->B en van (2) bij andere stellingen (B is dan de stelling, A is verworven kennis). (3) heb ik uit een cursus logica maar kan ik niet goed thuisbrengen. (1a) lijkt mij wat omslachtig en niet direct evident, maar is gewoonweg equivalent met (1b).
Mvg
(1a) ((~(A -> B) -> ~A) ^ A) -> B
(1b) (~(A -> B) -> ~A) -> (A -> B)
(2) ((~B -> ~A) ^ A) -> B
(3) (~B -> (A ^ ~A)) -> B
Hierbij zijn A en B proposities en ~A betekent "niet A".
Zelf maak ik gebruik van (1b) bij stellingen vd vorm A->B en van (2) bij andere stellingen (B is dan de stelling, A is verworven kennis). (3) heb ik uit een cursus logica maar kan ik niet goed thuisbrengen. (1a) lijkt mij wat omslachtig en niet direct evident, maar is gewoonweg equivalent met (1b).
Mvg
Re: Bewijs uit het ongerijmde en logica
hmm heb er even naar gekeken:
Is erg lang geleden voor me. Heb het boek Godel Esher Bach eens doorgelezen en logischer wijs kwam ik op de term "propositielogica".
Na googlen:
http://wis.kuleuven.be/algebra/Logica1A.pdf
misschien dat je daar wat aan hebt.
Is erg lang geleden voor me. Heb het boek Godel Esher Bach eens doorgelezen en logischer wijs kwam ik op de term "propositielogica".
Na googlen:
http://wis.kuleuven.be/algebra/Logica1A.pdf
misschien dat je daar wat aan hebt.
Re: Bewijs uit het ongerijmde en logica
Misschien iets dergelijks als dit?
A: "is een rationaal getal."
B: "te schrijven als een breuk p/q met ggd(p,q)=1."
( (~A^B) --> (A^~B) ) --> A
A: "is een rationaal getal."
B: "te schrijven als een breuk p/q met ggd(p,q)=1."
( (~A^B) --> (A^~B) ) --> A
-
- Berichten: 71
Re: Bewijs uit het ongerijmde en logica
Die cursus heb ik hier liggen. 'T is daar dat ik regel (3) heb uitgehaald.
Ik denk niet dat je mijn vraag goed begrijpt. Een bewijs baseert zich (als ik het goed voorheb) op een tautologie in de logica. Men heeft het dikwijls over "bewijs uit het ongerijmde", "reductio ad absurdum", "bewijs door contradictie" enz. Maar telkens (op verschillende websites, in verschillende cursussen) geeft men hierbij andere tautologieën om aan te tonen dat dit een geldige bewijsvorm is, waarvan enkele hierboven genoteerd.
Een andere is ook nog (~p -> p) -> p
Ik vraag mij gewoonweg af welke van die tautologieën nu daadwerkelijk die van het "bewijs uit het ongerijmde" is.
Ik denk niet dat je mijn vraag goed begrijpt. Een bewijs baseert zich (als ik het goed voorheb) op een tautologie in de logica. Men heeft het dikwijls over "bewijs uit het ongerijmde", "reductio ad absurdum", "bewijs door contradictie" enz. Maar telkens (op verschillende websites, in verschillende cursussen) geeft men hierbij andere tautologieën om aan te tonen dat dit een geldige bewijsvorm is, waarvan enkele hierboven genoteerd.
Een andere is ook nog (~p -> p) -> p
Ik vraag mij gewoonweg af welke van die tautologieën nu daadwerkelijk die van het "bewijs uit het ongerijmde" is.
Re: Bewijs uit het ongerijmde en logica
Typische structuur van 'bewijs uit het ongerijmde'. Je neemt aan dat de ontkenning, dus het tegengestelde, 'waar' is en leidt een tegenspraak af.
Gegeven: A1, A2,...
Te bewijzen: B is waar.
Bewijs. Stel NIET, d.w.z. B is NIET waar (de ontkenning). Met behulp van ~B en de gegeven A1, A2,... leidt je een tegenspraak af. Op een gegeven moment vind je iets dat pertinent niet kan zijn: TEGENSPRAAK!
Conclusie: B moet wel waar zijn.
In de predikatenlogica is dit te vatten als:
(~B --> (A / ~A)) --> B
In woorden: ALS B NIET waar DAN is zowel A waar EN NIET A waar, onmogelijk, dus B is waar.
Dus nummer (3) is het bewijs uit het ongerijmde.
Het komt dikwijls voor dat TEN ONRECHTE het bewijs als uit het ongerijmde wordt bestempeld, terwijl dit een toch echt een contrapositioneel bewijs is. De fout wordt ook door ervaren wiskundigen nog immer gemaakt!
Een klassiek voorbeeld:
T.B. sqrt(2) is NIET te schrijven als een breuk.
Bewijs. Stel NIET, d.w.z. neem aan dat sqrt(2) WEL te schrijven is als een breuk, zeg sqrt(2) = m/n. Neem aan dat m en n GEEN gemeenschappelijke factoren bezitten, dus m OF n is ONEVEN. Welnu: 2 = (m/n)^2 <=> 2n^2 = m^2. Dus blijkbaar is m^2 EVEN, dus ook is m EVEN, zeg m = 2q. Maar dan volgt ook dat 2n^2 = (2q)^2 <=> n^2 = 2q^2, dus ook n is EVEN. TEGENSPRAAK! Dus blijkbaar is sqrt(2) NIET te schrijven als een breuk. Q.E.D.
Gegeven: A1, A2,...
Te bewijzen: B is waar.
Bewijs. Stel NIET, d.w.z. B is NIET waar (de ontkenning). Met behulp van ~B en de gegeven A1, A2,... leidt je een tegenspraak af. Op een gegeven moment vind je iets dat pertinent niet kan zijn: TEGENSPRAAK!
Conclusie: B moet wel waar zijn.
In de predikatenlogica is dit te vatten als:
(~B --> (A / ~A)) --> B
In woorden: ALS B NIET waar DAN is zowel A waar EN NIET A waar, onmogelijk, dus B is waar.
Dus nummer (3) is het bewijs uit het ongerijmde.
Het komt dikwijls voor dat TEN ONRECHTE het bewijs als uit het ongerijmde wordt bestempeld, terwijl dit een toch echt een contrapositioneel bewijs is. De fout wordt ook door ervaren wiskundigen nog immer gemaakt!
Een klassiek voorbeeld:
T.B. sqrt(2) is NIET te schrijven als een breuk.
Bewijs. Stel NIET, d.w.z. neem aan dat sqrt(2) WEL te schrijven is als een breuk, zeg sqrt(2) = m/n. Neem aan dat m en n GEEN gemeenschappelijke factoren bezitten, dus m OF n is ONEVEN. Welnu: 2 = (m/n)^2 <=> 2n^2 = m^2. Dus blijkbaar is m^2 EVEN, dus ook is m EVEN, zeg m = 2q. Maar dan volgt ook dat 2n^2 = (2q)^2 <=> n^2 = 2q^2, dus ook n is EVEN. TEGENSPRAAK! Dus blijkbaar is sqrt(2) NIET te schrijven als een breuk. Q.E.D.
- Lorentziaan
- Berichten: 1.433
Re: Bewijs uit het ongerijmde en logica
Ah, dus 'bewijs uit het ongerijmde' is de Nederlandse term voor 'proof by contradiction'? Ik zat al te zoeken naar de goede term...
-
- Berichten: 71
Re: Bewijs uit het ongerijmde en logica
Als dat zo is, kan ik mij niet herinneren dat ik ooit al zo'n bewijs ben tegengekomen! Kan je hier eens een specifiek vbtje van geven? En die gegeven A1 en A2, passen die ook nog ergens in die formule? Omdat je zegt (~B ^ A1 ^ A2)..Anonymous schreef:In de predikatenlogica is dit te vatten als:
(~B --> (A / ~A)) --> B
In woorden: ALS B NIET waar DAN is zowel A waar EN NIET A waar, onmogelijk, dus B is waar.
Dus nummer (3) is het bewijs uit het ongerijmde.
Dat is nr (2) neem ik aan, modus tollens? Ik heb hier een boekje liggen waarin staat dat bewijzen van type (3) vaak parallell lopen met type (2), maar aan de uitleg geraak ik niet veel wijzer.Het komt dikwijls voor dat TEN ONRECHTE het bewijs als uit het ongerijmde wordt bestempeld, terwijl dit een toch echt een contrapositioneel bewijs is. De fout wordt ook door ervaren wiskundigen nog immer gemaakt!
Hm, intuïtief redenerend zou je dan idd kunnen besluiten dat er een contradictie in het bewijs zit. Je neemt aan ONEVEN, maar komt uit op EVEN..vandaar de verwarring?Een klassiek voorbeeld:
T.B. sqrt(2) is NIET te schrijven als een breuk.
Bewijs. Stel NIET, d.w.z. neem aan dat sqrt(2) WEL te schrijven is als een breuk, zeg sqrt(2) = m/n. Neem aan dat m en n GEEN gemeenschappelijke factoren bezitten, dus m OF n is ONEVEN. Welnu: 2 = (m/n)^2 <=> 2n^2 = m^2. Dus blijkbaar is m^2 EVEN, dus ook is m EVEN, zeg m = 2q. Maar dan volgt ook dat 2n^2 = (2q)^2 <=> n^2 = 2q^2, dus ook n is EVEN. TEGENSPRAAK! Dus blijkbaar is sqrt(2) NIET te schrijven als een breuk. Q.E.D.
Ik neem aan dat hier geldt
A: m of n zijn oneven
B: [wortel]2 is geen breuk ?
Dit vraag ik mij nu ook af.. Zijn de termen "bewijs uit ongerijmde", "indirect bewijs", "reductio ad absurdum", "bewijs door contradictie" e.d. nu equivalent met elkaar?Ah, dus 'bewijs uit het ongerijmde' is de Nederlandse term voor 'proof by contradiction'? Ik zat al te zoeken naar de goede term...
Dit lijkt evident maar heb onlangs opgemerkt dat er veel termen verschillen in het engels en nederlands. "mathematical induction" noemt men hier "volledige inductie" en "complete induction" is hier "versterkte volledige inductie"..geraak daar maar eens wijs uit.
Mvg
Re: Bewijs uit het ongerijmde en logica
De verschillende bewijsstrategieen berusten eenvoudigweg op waarheidstabellen. Op oneindig veel manieren kun je hetzelfde bewijzen. Bewijs uit het ongerijmde is toch echt: aannemen dat het tegengestelde waar is en dan een tegenspraak afleiden. Het gegeven voorbeeld is een prachtig examplaar van een bewijs uit het ongerijmde!
Inderdaad, B is de stelling en A zijn condities, voorwaarden die jij oplegt, die jij MAG opleggen. Als we dan aannemen dat ~B waar is, dan blijkt dat zowel A als ~A waar zijn, wat niet kan.
In het voorbeeld is dus B = 'Wortel 2 is NIET rationaal, d.w.z. v/d vorm m/n'. Ik MAG dan veronderstellen dat er GEEN gemeenschappelijke factoren zijn anders kan ik die er gewoon uitdelen en ik MAG veronderstellen dat NIET gelijktijdig m EN n EVEN omdat ik dan gewoon door twee kan delen, dit betekent dus dat TENMINSTE of m, of n of m EN n tegelijkertijd ONEVEN. Dat is dus de bewering A: A = 'n OF m is ONEVEN'. We zien dus later dat als ik aanneem dat ~B waar is, d.w.z. Wortel 2 is WEL rationaal, dat dit leidt tot dat m EN n beide EVEN, wat in tegenspraak is met wat ik aannam, namelijk dat m EN n NIET tegelijkertijd EVEN kunnen zijn. Duidelijker dan dit kan ik het niet brengen!
A1, A2, A3,... en vallen als ware samen onder A. Het komt erop neer dat je tenminste 1 tegenspraak afleidt, maakt niet uit waarin.
Een bewijs uit het ongerijmde is inderdaad een indirect bewijs en de andere genoemde termen betekenen hetzelfde, mijn inziens. Opgemerkt zij dat een direct bewijs altijd de voorkeur heeft. Echter, dit is vaak lastig.
Versterkte volledige inductie wordt ookwel verzwaarde inductie genoemd. Het berust erop dat als je iets voor alle m of m,n of wat dan ook kan bewijzen, dat dit zeker ook geldt voor een selectie uit die m en n.
Bewijs d.m.v. contrapositie is gewoon:
(A --> B) <-> (~B --> ~A)
In woorden: Als ik wil bewijzen dat ALS A waar DAN B waar, is hetzelfde als/equivalent met dat ik zou bewijzen dat ALS NIET B waar DAN NIET A waar. Dit is inzichtelijk met waarheidstabellen. Zo is in het schoolboek Getal & Ruimte vwo een stelling waarvan ten onrechte wordt gezegd dat dit wordt bewezen uit het ongerijmde, terwijl dit contrapositie is.
Forest.
Inderdaad, B is de stelling en A zijn condities, voorwaarden die jij oplegt, die jij MAG opleggen. Als we dan aannemen dat ~B waar is, dan blijkt dat zowel A als ~A waar zijn, wat niet kan.
In het voorbeeld is dus B = 'Wortel 2 is NIET rationaal, d.w.z. v/d vorm m/n'. Ik MAG dan veronderstellen dat er GEEN gemeenschappelijke factoren zijn anders kan ik die er gewoon uitdelen en ik MAG veronderstellen dat NIET gelijktijdig m EN n EVEN omdat ik dan gewoon door twee kan delen, dit betekent dus dat TENMINSTE of m, of n of m EN n tegelijkertijd ONEVEN. Dat is dus de bewering A: A = 'n OF m is ONEVEN'. We zien dus later dat als ik aanneem dat ~B waar is, d.w.z. Wortel 2 is WEL rationaal, dat dit leidt tot dat m EN n beide EVEN, wat in tegenspraak is met wat ik aannam, namelijk dat m EN n NIET tegelijkertijd EVEN kunnen zijn. Duidelijker dan dit kan ik het niet brengen!
A1, A2, A3,... en vallen als ware samen onder A. Het komt erop neer dat je tenminste 1 tegenspraak afleidt, maakt niet uit waarin.
Een bewijs uit het ongerijmde is inderdaad een indirect bewijs en de andere genoemde termen betekenen hetzelfde, mijn inziens. Opgemerkt zij dat een direct bewijs altijd de voorkeur heeft. Echter, dit is vaak lastig.
Versterkte volledige inductie wordt ookwel verzwaarde inductie genoemd. Het berust erop dat als je iets voor alle m of m,n of wat dan ook kan bewijzen, dat dit zeker ook geldt voor een selectie uit die m en n.
Bewijs d.m.v. contrapositie is gewoon:
(A --> B) <-> (~B --> ~A)
In woorden: Als ik wil bewijzen dat ALS A waar DAN B waar, is hetzelfde als/equivalent met dat ik zou bewijzen dat ALS NIET B waar DAN NIET A waar. Dit is inzichtelijk met waarheidstabellen. Zo is in het schoolboek Getal & Ruimte vwo een stelling waarvan ten onrechte wordt gezegd dat dit wordt bewezen uit het ongerijmde, terwijl dit contrapositie is.
Forest.
-
- Berichten: 71
Re: Bewijs uit het ongerijmde en logica
Ahh..ik dacht dat je dat voorbeeld gaf om aan te tonen dat in dat geval een bewijs door contrapositie verward kan worden met een bewijs uit het ongerijmde. Nu is het echter duidelijk!Het gegeven voorbeeld is een prachtig examplaar van een bewijs uit het ongerijmde!
Dus in het vbtje van [wortel]2 VOLGT uit ~B dat ik de conditie A MAG opleggen? Oftewel wat ook kan, als A een gegeven is, dan geldt automatisch "~B -> A" want "A -> (~B -> A)" is een tautologie.Inderdaad, B is de stelling en A zijn condities, voorwaarden die jij oplegt, die jij MAG opleggen. Als we dan aannemen dat ~B waar is, dan blijkt dat zowel A als ~A waar zijn, wat niet kan.
Klopt dat zo'n beetje met wat je bedoelt?
-
- Berichten: 71
Re: Bewijs uit het ongerijmde en logica
Klopt dat zo'n beetje met wat je bedoelt?
Ok, ik veronderstel dus van wel he. Thanks!