Enkelt bevis - står fast på logikk

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markonan
Euclid
Euclid
Innlegg: 2136
Registrert: 24/11-2006 19:26
Sted: Oslo

Hei.

Leser litt om logikk, og skal bevise følgende likhet.

[tex](A\cup B)\backslash(A\cap B) = (A\backslash B)\cup(B\backslash A)[/tex]

Begynner med å skrive hva det betyr for en vilkårlig variabel x, og får det over på ekvivalent, logisk form.
[tex]x\in (A\cup B)\backslash(A\cap B) \;\Rightarrow\; (x\in A\vee x\in B)\wedge \neg(x\in A\wedge x\in B)[/tex].

[tex]x\in (A\backslash B)\cup(B\backslash A) \;\Rightarrow\; (x\in A\wedge x\not\in B)\vee(x\in B\wedge x\not\in A)[/tex].

Jeg begynner med den første, og skal bruke de vanlige lovene for logiske uttrykk og forhåpentligvis ende opp på det andre uttrykket. :)

[tex](x\in A\vee x\in B)\wedge \neg(x\in A\wedge x\in B)[/tex]

Anvender DeMorgans lov:
[tex](x\in A\vee x\in B)\wedge (x\not\in A\vee x\not\in B)[/tex]
//
Ukjente steg her
//

[tex](x\in A\wedge x\not\in B)\vee(x\in B\wedge x\not\in A)[/tex]

Finnes sikkert mange andre fine måter å bevise dette på, men vil forstå hvordan det gjøres på akkurat denne måten.

Er det noen her som kan fortelle meg hva neste steg blir? Alt jeg prøver ender bare opp med masse kluss og surr. :)

Edit
For å forenkle notasjonen litt, har du samme problemstilling satt opp slik:
[tex](P\vee Q)\wedge\neg(P\wedge Q)[/tex]
[tex](P\vee Q)\wedge(\neg P\vee\neg Q)[/tex] (DeMorgans lov)
//
Ukjente steg her
//

[tex](P\wedge \neg Q)\vee(Q\wedge \neg P)[/tex]
An ant on the move does more than a dozing ox.
Lao Tzu
Markonan
Euclid
Euclid
Innlegg: 2136
Registrert: 24/11-2006 19:26
Sted: Oslo

Eureka! Jeg fant ut av det! :)

[tex](P\vee Q)\wedge\neg(P\wedge Q)[/tex]

[tex](P\vee Q)\wedge(\neg P\vee\neg Q)[/tex] (DeMorgans lov)

[tex][(P\vee Q)\wedge\neg P]\;\vee\;[(P\vee Q)\wedge\neg Q][/tex] (Distributiv lov)

[tex][(P\wedge\neg P)\vee(P\wedge\neg Q)]\vee[(Q\wedge\neg P)\vee(Q\wedge\neg Q)][/tex] (Distributiv lov igjen)

[tex](P\wedge \neg Q)\vee(Q\wedge \neg P)[/tex] (Motsigelsesloven)

QED!
An ant on the move does more than a dozing ox.
Lao Tzu
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Markonan skrev:Eureka! Jeg fant ut av det! :)

[tex](P\vee Q)\wedge\neg(P\wedge Q)[/tex]

[tex](P\vee Q)\wedge(\neg P\vee\neg Q)[/tex] (DeMorgans lov)

[tex][(P\vee Q)\wedge\neg P]\;\vee\;[(P\vee Q)\wedge\neg Q][/tex] (Distributiv lov)

[tex][(P\wedge\neg P)\vee(P\wedge\neg Q)]\vee[(Q\wedge\neg P)\vee(Q\wedge\neg Q)][/tex] (Distributiv lov igjen)

[tex](P\wedge \neg Q)\vee(Q\wedge \neg P)[/tex] (Motsigelsesloven)

QED!
Fint. Kan også ses direkte ved å tegne Venn diagram.
Markonan
Euclid
Euclid
Innlegg: 2136
Registrert: 24/11-2006 19:26
Sted: Oslo

En tredje metode er å tegne opp en sannhetstabell. Da ser man at man får de samme verdiene og dermed ekvivalens.
An ant on the move does more than a dozing ox.
Lao Tzu
Svar