matematikk.net

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]

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!

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.

En tredje metode er å tegne opp en sannhetstabell. Da ser man at man får de samme verdiene og dermed ekvivalens.