Springen naar inhoud

Bewijs uit het ongerijmde en logica


  • Log in om te kunnen reageren

#1

TomMe

    TomMe


  • >25 berichten
  • 71 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2005 - 15:52

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2


  • Gast

Geplaatst op 15 september 2005 - 18:40

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....ra/Logica1A.pdf

misschien dat je daar wat aan hebt.

#3


  • Gast

Geplaatst op 15 september 2005 - 19:31

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

#4

TomMe

    TomMe


  • >25 berichten
  • 71 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2005 - 22:51

Die cursus heb ik hier liggen. 'T is daar dat ik regel (3) heb uitgehaald. :shock:

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.

#5


  • Gast

Geplaatst op 15 september 2005 - 23:01

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.

#6

Brinx

    Brinx


  • >1k berichten
  • 1433 berichten
  • Lorentziaan

Geplaatst op 15 september 2005 - 23:05

Ah, dus 'bewijs uit het ongerijmde' is de Nederlandse term voor 'proof by contradiction'? Ik zat al te zoeken naar de goede term...

#7

TomMe

    TomMe


  • >25 berichten
  • 71 berichten
  • Ervaren gebruiker

Geplaatst op 16 september 2005 - 09:04

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.


Als dat zo is, kan ik mij niet herinneren dat ik ooit al zo'n bewijs ben tegengekomen! :shock: 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)..

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!


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.

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.


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?
Ik neem aan dat hier geldt
A: m of n zijn oneven
B: [wortel]2 is geen breuk ?

Ah, dus 'bewijs uit het ongerijmde' is de Nederlandse term voor 'proof by contradiction'? Ik zat al te zoeken naar de goede term...


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?
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

#8


  • Gast

Geplaatst op 16 september 2005 - 13:01

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.

#9

TomMe

    TomMe


  • >25 berichten
  • 71 berichten
  • Ervaren gebruiker

Geplaatst op 16 september 2005 - 15:54

Het gegeven voorbeeld is een prachtig examplaar van een bewijs uit het ongerijmde!

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! :wink:

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.

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.

Klopt dat zo'n beetje met wat je bedoelt?

#10

TomMe

    TomMe


  • >25 berichten
  • 71 berichten
  • Ervaren gebruiker

Geplaatst op 18 september 2005 - 11:19

Klopt dat zo'n beetje met wat je bedoelt?


Ok, ik veronderstel dus van wel he. Thanks! :wink:





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures