Anta at det er to formler, X og Y. Disse formlene vil bli kjent som ekvivalens hvis X ↔ Y er en tautologi. Hvis to formler X ↔ Y er en tautologi, kan vi også skrive den som X ⇔ Y, og vi kan lese denne relasjonen som X er ekvivalens til Y.
Merk: Det er noen punkter som vi bør huske på mens lineær ekvivalens av formel, som er beskrevet som følger:
- ⇔ brukes kun til å indikere symbol, men det er ikke bindende.
- Sannhetsverdien til X og Y vil alltid være lik hvis X ↔ Y er en tautologi.
- Ekvivalensrelasjonen inneholder to egenskaper, dvs. symmetrisk og transitiv.
Metode 1: Sannhetstabellmetode:
I denne metoden vil vi konstruere sannhetstabellene for en hvilken som helst to-setningsformel og deretter sjekke om disse utsagnene er likeverdige.
Eksempel 1: I dette eksemplet må vi bevise X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Løsning: Sannhetstabellen for X ∨ Y ⇔ ¬(¬X ∧ ¬Y) er beskrevet som følger:
| X | OG | X ∨ Y | ¬X | ¬Og | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | T | F | T | F | T | T |
| F | T | T | T | F | F | T | T |
| F | F | F | T | T | T | F | T |
Som vi kan se at X ∨ Y og ¬(¬X ∧ ¬Y) er en tautologi. Derav X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Eksempel 2: I dette eksemplet må vi bevise (X → Y) ⇔ (¬X ∨ Y).
Løsning: Sannhetstabellen til (X → Y) ⇔ (¬X ∨ Y) er beskrevet som følger:
| X | OG | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Som vi kan se at X → Y og (¬X ∨ Y) er en tautologi. Derfor (X → Y) ⇔ (¬X ∨ Y)
Ekvivalensformel:
Det er forskjellige lover som brukes for å bevise ekvivalensformelen, som er beskrevet som følger:
Idempotent lov: Hvis det er én setningsformel, vil den inneholde følgende egenskaper:
X ∨ X ⇔ X X ∧ X ⇔ X
Assosiativ lov: Hvis det er tre setningsformler, vil den inneholde følgende egenskaper:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Kommutativ lov: Hvis det er to setningsformler, vil det inneholde følgende egenskaper:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Fordelingslov: Hvis det er tre setningsformler, vil den inneholde følgende egenskaper:
ordbok initialisering c#
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identitetslov: Hvis det er én setningsformel, vil den inneholde følgende egenskaper:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Utfyllende lov: Hvis det er én setningsformel, vil den inneholde følgende egenskaper:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorpsjonslov: Hvis det er to setningsformler, vil det inneholde følgende egenskaper:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Fra Morgans lov: Hvis det er to setningsformler, vil det inneholde følgende egenskaper:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Metode 2: Erstatningsprosess
I denne metoden vil vi anta en formel A : X → (Y → Z). Formelen Y → Z kan være kjent som delen av formelen. Hvis vi erstatter denne delen av formelen, dvs. Y → Z, ved hjelp av ekvivalensformel ¬Y ∨ Z i A, vil vi få en annen formel, dvs. B : X → (¬Y ∨ Z). Det er en enkel prosess å verifisere om de gitte formlene A og B er likeverdige med hverandre eller ikke. Ved hjelp av erstatningsprosess kan vi få B fra A.
Eksempel 1: I dette eksemplet må vi bevise at {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Løsning: Her tar vi venstre sidedel og prøver å få tak i høyre sidedel.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Nå vil vi bruke assosiasjonsloven slik:
⇔ (¬X ∨ ¬Y) ∨ Z
Nå skal vi bruke De Morgans lov slik:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Derfor bevist
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Eksempel 2: I dette eksemplet må vi bevise at {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Løsning: Her tar vi venstre sidedel og prøver å få tak i høyre sidedel.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Derfor bevist
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Eksempel 3: I dette eksemplet må vi bevise at X → (Y → X) ⇔ ¬X → (X → Y).
Løsning: Her tar vi venstre sidedel og prøver å få tak i høyre sidedel.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Derfor bevist
X → (Y → X) ⇔ ¬X → (X → Y)
Eksempel 4: I dette eksemplet må vi bevise at (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Løsning: Her tar vi venstre sidedel og prøver å få tak i høyre sidedel.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Nå vil vi bruke de assosiative og distributive lovene slik:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nå skal vi bruke De Morgans lov slik:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nå vil vi bruke distribusjonsloven slik:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Derfor bevist
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Eksempel 5: I dette eksemplet må vi vise at ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) er en tautologi.
Løsning: Her skal vi ta små deler og løse dem.
Først vil vi bruke De Morgans lov og få følgende:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Derfor,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Også
lateks bord
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Derfor
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Dermed
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Derfor kan vi si at den gitte formelen er en tautologi.
Eksempel 6: I dette eksemplet må vi vise at (X ∧ Y) → (X ∨ Y) er en tautologi.
Løsning: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Nå skal vi bruke De Morgans lov slik:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Nå vil vi bruke assosiativ lov og kommutativ lov slik:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Nå vil vi bruke negasjonsloven slik:
⇔ (T ∨ T) ⇔ T
Derfor kan vi si at den gitte formelen er en tautologi.
Eksempel 7: I dette eksemplet må vi skrive negasjonen av noen utsagn, som er beskrevet som følger:
- Marry vil fullføre utdannelsen eller godta tiltredelsesbrevet til XYZ Company.
- Harry skal ut på tur eller løpe i morgen.
- Hvis jeg får gode karakterer, blir fetteren min sjalu.
Løsning: Først vil vi løse den første setningen slik:
1. Anta at X: Gift vil fullføre utdannelsen.
Y: Godta tilknytningsbrevet til XYZ Company.
Vi kan bruke følgende symbolske form for å uttrykke denne uttalelsen:
X ∨ Y
Negasjonen av X ∨ Y er beskrevet som følger:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Avslutningsvis vil negasjonen av gitt uttalelse være:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Anta at X: Harry vil dra på tur
Y: Harry løper i morgen
Vi kan bruke følgende symbolske form for å uttrykke denne uttalelsen:
X ∨ Y
Negasjonen av X ∨ Y er beskrevet som følger:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Avslutningsvis vil negasjonen av gitt uttalelse være:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Anta X: Hvis jeg får gode karakterer.
Y: Fetteren min vil være sjalu.
Vi kan bruke følgende symbolske form for å uttrykke denne uttalelsen:
X → Y
Negasjonen av X → Y er beskrevet som følger:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Avslutningsvis vil negasjonen av gitt uttalelse være:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Eksempel 8: I dette eksemplet må vi skrive negasjonen av noen utsagn ved hjelp av De Morgans lov. Disse uttalelsene er beskrevet som følger:
- Jeg trenger et diamantsett og verdt en gullring.
- Du får en god jobb ellers får du ikke en god partner.
- Jeg tar mye arbeid og takler det ikke.
- Hunden min drar på tur eller den lager rot i huset.
Løsning: Negasjonen av alle utsagnene ved hjelp av De Morgans lov er beskrevet en etter en slik:
- Jeg trenger ikke et diamantsett eller ikke verdt en gullring.
- Du kan ikke få en god jobb, og du vil få en god partner.
- Jeg tar ikke mye arbeid eller jeg kan håndtere det.
- Hunden min drar ikke på tur og den lager ikke rot i huset.
Eksempel 9: I dette eksemplet har vi noen utsagn, og vi må skrive negasjonen av disse utsagnene. Uttalelsene er beskrevet som følger:
- Hvis det regner, blir planen om å gå til stranden kansellert.
- Hvis jeg studerer hardt, vil jeg få gode karakterer på eksamen.
- Hvis jeg går på en kveldsfest, vil jeg få straff av faren min.
- Hvis du ikke vil snakke med meg, så må du blokkere nummeret mitt.
Løsning: Negasjonen av alle utsagnene er beskrevet en etter en slik:
- Hvis planen om å gå til stranden blir kansellert, så regner det.
- Får jeg gode karakterer på eksamen, så studerer jeg hardt.
- Hvis jeg får straff av faren min, så drar jeg på en kveldsfest.
- Hvis du må blokkere nummeret mitt, så vil du ikke snakke med meg.
Eksempel 10: I dette eksemplet må vi sjekke om (X → Y) → Z og X → (Y → Z) er logisk likeverdige eller ikke. Vi må begrunne svaret vårt ved hjelp av sannhetstabeller og ved hjelp av logikkregler for å forenkle begge uttrykkene.
Løsning: Først vil vi bruke metode 1 for å sjekke om (X → Y) → Z og X → (Y → Z) er logisk likeverdige, som er beskrevet som følger:
mylivecricket alternativ
Metode 1: Her vil vi anta følgende:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Og
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Metode 2: Nå skal vi bruke den andre metoden. I denne metoden vil vi bruke sannhetstabellen.
| X | OG | MED | X → Y | (X → Y) → Z | Y → Å | X → (Y → Z) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | F | F | T |
| F | F | T | T | T | T | T |
| F | F | F | T | F | T | T |
I denne sannhetstabellen kan vi se at kolonnene til (X → Y) → Z og X → (Y → Z) ikke inneholder identiske verdier.