logo

Lov om logisk ekvivalens i diskret matematikk

Anta at det er to sammensatte utsagn, X og Y, som vil bli kjent som logisk ekvivalens hvis og bare hvis sannhetstabellen til begge inneholder de samme sannhetsverdiene i kolonnene deres. Ved hjelp av symbol = eller ⇔ kan vi representere den logiske ekvivalensen. Så X = Y eller X ⇔ Y vil være den logiske ekvivalensen til disse utsagnene.

Ved hjelp av den logiske ekvivalensdefinisjonen har vi klart at hvis de sammensatte setningene X og Y er logisk ekvivalens, i dette tilfellet, må X ⇔ Y være Tautologi.

Lover om logisk ekvivalens

I denne loven vil vi bruke 'OG'- og 'ELLER'-symbolene for å forklare loven om logisk ekvivalens. Her er AND indikert ved hjelp av ∧-symbolet og OR er indikert ved hjelp av ∨-symbolet. Det er forskjellige lover for logisk ekvivalens, som er beskrevet som følger:

Idempotent lov:

I den idempotente loven bruker vi kun et enkelt utsagn. I følge denne loven, hvis vi kombinerer to samme utsagn med symbolet ∧(og) og ∨(eller), vil den resulterende utsagnet være selve utsagnet. Anta at det er en sammensatt setning P. Følgende notasjon brukes for å indikere den idempotente loven:

 P ∨ P ? P P ∧ P ? P 

Sannhetstabellen for denne loven er beskrevet som følger:

P P P ∨ P P ∧ P
T T T T
F F F F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P, P ∨ P og P ∧ P.

Derfor kan vi si at P ∨ P = P og P ∧ P = P.

Kommutative lover:

De to utsagnene brukes for å vise den kommutative loven. I følge denne loven, hvis vi kombinerer to utsagn med symbolet ∧(og) eller ∨(eller), vil den resulterende utsagn være den samme selv om vi endrer plasseringen av utsagnene. Anta at det er to utsagn, P og Q. Forslaget til disse utsagnene vil være usant når begge utsagnene P og Q er usanne. I alle de andre tilfellene vil det være sant. Følgende notasjon brukes for å indikere den kommutative loven:

java røring til int
 P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P Q P ∨ Q Q ∨ P
T T T T
T F T T
F T T T
F F F F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ Q og Q ∨ P.

Derfor kan vi si at P ∨ Q ? Q ∨ P.

Samme som vi kan bevise P ∧ Q ? Q ∧ P.

Assosiativ lov:

De tre utsagnene brukes for å vise assosiasjonsloven. I henhold til denne loven, hvis vi kombinerer tre utsagn ved hjelp av parenteser ved symbolet ∧(og) eller ∨(or), vil den resulterende setningen være den samme selv om vi endrer rekkefølgen på parenteser. Det betyr at denne loven er uavhengig av gruppering eller forening. Anta at det er tre utsagn P, Q og R. Forslaget til disse utsagnene vil være usant når P, Q og R er usanne. I alle de andre tilfellene vil det være sant. Følgende notasjon brukes for å indikere den assosiative loven:

 P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P Q R P ∨ Q Q ∨ R (P ∨ Q) ∨ R P ∨ (Q ∨ R)
T T T T T T T
T T F T T T T
T F T T T T T
T F F T F T T
F T T T T T T
F T F T T T T
F F T F T T T
F F F F F F F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ (Q ∨ R) og (P ∨ Q) ∨ R.

Derfor kan vi si at P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.

Samme som vi kan bevise P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R

Fordelingslov:

De tre utsagnene brukes for å vise fordelingsloven. I henhold til denne loven, hvis vi kombinerer et utsagn med ∨(ELLER)-symbolet med de to andre utsagnene som er forbundet med symbolet ∧(AND), vil den resulterende utsagn være den samme selv om vi kombinerer utsagnene separat med symbolet ∨(ELLER) og kombinere de sammenføyde setningene med ∧(AND). Anta at det er tre utsagn P, Q og R. Følgende notasjon brukes for å indikere distribusjonsloven:

P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)

objektlikhet i java

P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P Q R Q ∧ R P∨(Q ∧R) P ∨ Q P ∨ R (P ∨ Q) ∧ (P ∨ R)
T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ (Q ∧ R) og (P ∨ Q) ∧ (P ∨ R).

Derfor kan vi si at P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

Samme som vi kan bevise P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

Identitetslov:

En enkelt uttalelse brukes for å vise identitetsloven. I henhold til denne loven, hvis vi kombinerer et utsagn og en sann verdi med symbolet ∨(eller), vil det generere den sanne verdien. Hvis vi kombinerer et utsagn og en falsk verdi med symbolet ∧(og), vil det generere selve utsagnet. På samme måte vil vi gjøre dette med de motsatte symbolene. Det betyr at hvis vi kombinerer et utsagn og en sann verdi med symbolet ∧(og), vil det generere selve utsagnet, og hvis vi kombinerer et utsagn og en usann verdi med symbolet ∨(eller), vil det generere Falsk verdi. Anta at det er en sammensatt setning P, en sann verdi T og en falsk verdi F. Følgende notasjon brukes for å indikere identitetsloven:

 P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P T F P ∨ T P ∨ F
T T F T T
F T F T F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ T og T. Derfor kan vi si at P ∨ T = T. På samme måte inneholder denne tabellen også de samme sannhetsverdiene i kolonnene P ∨ F og P. Derfor vi kan si at P ∨ F = P.

Samme som vi kan bevise P ∧ T ? P og P ∧ F ? F

Komplementlov:

En enkelt uttalelse brukes i komplementloven. I henhold til denne loven, hvis vi kombinerer en setning med dens komplementsetning med symbolet ∨(eller), vil den generere den sanne verdien, og hvis vi kombinerer disse setningene med symbolet ∧(og), vil den generere falsk verdi. Hvis vi negerer en sann verdi, vil den generere en falsk verdi, og hvis vi negerer en falsk verdi, vil den generere den sanne verdien.

Følgende notasjon brukes for å indikere komplementloven:

 P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P ¬P T ¬T F ¬F P ∨ ¬P P ∧ ¬P
T F T F F T T F
F T T F F T T F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ ¬P og T. Derfor kan vi si at P ∨ ¬P = T. På samme måte inneholder denne tabellen også de samme sannhetsverdiene i kolonnene P ∧ ¬P og F. Derfor kan vi si at P ∧ ¬P = F.

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene til ¬T og F. Derfor kan vi si at ¬T = F. På samme måte inneholder denne tabellen de samme sannhetsverdiene i kolonnene til ¬F og T. Derfor kan vi si at ¬F = T.

Dobbel negasjonslov eller involusjonslov

Et enkelt utsagn brukes for å vise den doble negasjonsloven. I følge denne loven, hvis vi gjør negasjonen av en negert uttalelse, vil den resulterende uttalelsen være selve utsagnet. Anta at det er en setning P og en negativ setning ¬P. Følgende notasjon brukes for å indikere den doble negasjonsloven:

 ¬(¬P) ? P 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P ¬P ¬(¬P)
T F T
F T F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene ¬(¬P) og P. Derfor kan vi si at ¬(¬P) = P.

Fra Morgans lov:

De to uttalelsene brukes for å vise De Morgans lov. I henhold til denne loven, hvis vi kombinerer to utsagn med symbolet ∧(AND) og deretter negerer disse kombinerte utsagnene, vil den resulterende utsagn være den samme selv om vi kombinerer negasjonen av begge utsagnene separat med symbolet ∨( ELLER). Anta at det er to sammensatte utsagn, P og Q. Følgende notasjon brukes for å indikere De Morgans lov:

 ¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P Q ¬P ¬Q P ∧ Q ¬(P ∧ Q) ¬ P ∨ ¬Q
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene ¬(P ∧ Q) og ¬ P ∨ ¬Q. Derfor kan vi si at ¬(P ∧ Q) = ¬ P ∨ ¬Q.

prioritert kø c++

Samme som vi kan bevise ¬(P ∨ Q) ? ¬P ∧ ¬Q

Absorpsjonslov:

De to utsagnene brukes for å vise absorpsjonsloven. I henhold til denne loven, hvis vi kombinerer et utsagn P med ∨(ELLER)-symbolet med det samme utsagnet P og ett annet utsagn Q, som er forbundet med symbolet ∧(AND), vil den resulterende utsagnet være den første utsagn P. Det samme resultatet vil bli generert hvis vi bytter ut symbolene. Anta at det er to sammensatte utsagn, P og Q. Følgende notasjon brukes for å indikere Absorpsjonsloven:

 P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P 

Sannhetstabellen for disse notasjonene er beskrevet som følger:

P Q P ∧ Q P ∨ Q P ∨ (P ∧ Q) P ∧ (P ∨ Q)
T T T T T T
T F F T T T
F T F T F F
F F F F F F

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ∨ (P ∧ Q) og P. Derfor kan vi si at P ∨ (P ∧ Q) ? P.

På samme måte inneholder denne tabellen også de samme sannhetsverdiene i kolonnene P ∧ (P ∨ Q) og P. Derfor kan vi si at P ∧ (P ∨ Q) ? P.

Eksempler på logisk ekvivalens

Det finnes ulike eksempler på logisk ekvivalens. Noen av dem er beskrevet som følger:

Eksempel 1: I dette eksemplet vil vi etablere ekvivalensegenskapen for et utsagn, som er beskrevet som følger:

p → q ? ¬p ∨ q

konverter streng til int

Løsning:

Vi vil bevise dette ved hjelp av en sannhetstabell, som er beskrevet som følger:

P Q ¬s p → q ¬p ∨ q
T T F T T
T F F F F
F T T T T
F F T T T

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene p → q og ¬p ∨ q. Derfor kan vi si at p → q ? ¬p ∨ q.

Eksempel 2: I dette eksemplet vil vi etablere ekvivalensegenskapen for et utsagn, som er beskrevet som følger:

P ↔ Q ? ( P → Q ) ∧ ( Q → P )

Løsning:

P Q P → Q Q → P P ↔ Q ( P → Q ) ∧ ( Q → P )
T T T T T T
T F F T F F
F T T F F F
F F T T T T

Denne tabellen inneholder de samme sannhetsverdiene i kolonnene P ↔ Q og (P → Q) ∧ (Q → P). Derfor kan vi si at P ↔ Q ? (P → Q) ∧ (Q → P).

Eksempel 3: I dette eksemplet vil vi bruke den tilsvarende egenskapen for å bevise følgende utsagn:

p ↔ q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )

Løsning:

For å bevise dette vil vi bruke noen av lovene ovenfor, og fra denne loven har vi:

p ↔ q ? (¬p ∨ q) ∧ (¬q ∨ p) ...........(1)

Nå skal vi bruke den kommutative loven i ligningen ovenfor og få følgende:

? (p ∨ q) ∧ (p ∨ ¬q)

Nå skal vi bruke fordelingsloven i denne ligningen og få følgende:

? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))

Nå skal vi bruke distributiv lov i denne ligningen og få følgende:

? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)

Nå skal vi bruke komplementloven i denne ligningen og få følgende:

? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F

Nå skal vi bruke identitetsloven og få følgende:

myflixr

? (¬ p ∧ ¬ q) ∨ (q ∧ p)

Nå skal vi bruke den kommutative loven i denne ligningen og få følgende:

? (p ∧ q) ∨ (¬ p ¬q)

Til slutt blir ligning (1) følgende:

p ↔ q ? (p ∧ q) ∨ (¬ p ¬q)

Til slutt kan vi si at ligningen (1) blir p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)