Antag, at der er to formler, X og Y. Disse formler vil blive kendt som ækvivalens, hvis X ↔ Y er en tautologi. Hvis to formler X ↔ Y er en tautologi, så kan vi også skrive det som X ⇔ Y, og vi kan læse denne relation som X er ækvivalens til Y.
Bemærk: Der er nogle punkter, som vi bør huske på, mens formlens lineære ækvivalens er beskrevet som følger:
- ⇔ bruges kun til at angive symbol, men det er ikke forbindende.
- Sandhedsværdien af X og Y vil altid være ens, hvis X ↔ Y er en tautologi.
- Ækvivalensrelationen indeholder to egenskaber, nemlig symmetrisk og transitiv.
Metode 1: Sandhedstabelmetode:
I denne metode vil vi konstruere sandhedstabellerne for enhver to-sætningsformel og derefter kontrollere, om disse udsagn er ækvivalente.
Eksempel 1: I dette eksempel skal vi bevise X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Løsning: Sandhedstabellen 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, er X ∨ Y og ¬(¬X ∧ ¬Y) en tautologi. Derfor X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Eksempel 2: I dette eksempel skal vi bevise (X → Y) ⇔ (¬X ∨ Y).
Løsning: Sandhedstabellen for (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, er X → Y og (¬X ∨ Y) en tautologi. Derfor (X → Y) ⇔ (¬X ∨ Y)
Ækvivalensformel:
Der er forskellige love, der bruges til at bevise ækvivalensformlen, som er beskrevet som følger:
Idempotent lov: Hvis der er én udsagnsformel, vil den indeholde følgende egenskaber:
X ∨ X ⇔ X X ∧ X ⇔ X
Associativ ret: Hvis der er tre udsagnsformler, vil det indeholde følgende egenskaber:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Kommutativ lov: Hvis der er to udsagnsformler, vil det indeholde følgende egenskaber:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Fordelingslov: Hvis der er tre udsagnsformler, vil det indeholde følgende egenskaber:
ordbog initialisering c#
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identitetslov: Hvis der er én udsagnsformel, vil den indeholde følgende egenskaber:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Supplerende lov: Hvis der er én udsagnsformel, vil den indeholde følgende egenskaber:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorptionslov: Hvis der er to udsagnsformler, vil det indeholde følgende egenskaber:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Fra Morgans lov: Hvis der er to udsagnsformler, vil det indeholde følgende egenskaber:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Metode 2: Udskiftningsproces
I denne metode vil vi antage en formel A : X → (Y → Z). Formlen Y → Z kan være kendt som en del af formlen. Hvis vi erstatter denne del af formlen, dvs. Y → Z, ved hjælp af ækvivalensformlen ¬Y ∨ Z i A, så får vi en anden formel, dvs. B : X → (¬Y ∨ Z). Det er en nem proces at verificere, om de givne formler A og B er ækvivalente med hinanden eller ej. Ved hjælp af udskiftningsproces kan vi få B fra A.
Eksempel 1: I dette eksempel skal vi bevise, at {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Løsning: Her vil vi tage den venstre sidedel og forsøge at få den højre sidedel.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Nu vil vi bruge den associative lov på denne måde:
⇔ (¬X ∨ ¬Y) ∨ Z
Nu vil vi bruge De Morgans lov sådan her:
⇔ ¬(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 eksempel skal vi bevise, at {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Løsning: Her vil vi tage den venstre sidedel og forsøge at få den højre 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 eksempel skal vi bevise, at X → (Y → X) ⇔ ¬X → (X → Y).
Løsning: Her vil vi tage den venstre sidedel og forsøge at få den højre 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 eksempel skal vi bevise, at (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Løsning: Her vil vi tage den venstre sidedel og forsøge at få den højre sidedel.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Nu vil vi bruge de associative og distribuerende love som denne:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nu vil vi bruge De Morgans lov sådan her:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nu vil vi bruge fordelingsloven sådan her:
⇔ (¬(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 eksempel skal vi vise, at ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) er en tautologi.
Løsning: Her vil vi tage små dele og løse dem.
Først vil vi bruge 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å
python // operator
¬(¬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 sige, at den givne formel er en tautologi.
Eksempel 6: I dette eksempel skal vi vise, at (X ∧ Y) → (X ∨ Y) er en tautologi.
Løsning: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Nu vil vi bruge De Morgans lov sådan her:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Nu vil vi bruge den associative lov og den kommutative lov på denne måde:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Nu vil vi bruge negationsloven sådan her:
⇔ (T ∨ T) ⇔ T
Derfor kan vi sige, at den givne formel er en tautologi.
Eksempel 7: I dette eksempel skal vi skrive negationen af nogle udsagn, som er beskrevet som følger:
- Marry vil afslutte sin uddannelse eller acceptere tiltrædelsesbrevet fra XYZ Company.
- Harry tager en tur eller løber i morgen.
- Hvis jeg får gode karakterer, bliver min kusine jaloux.
Løsning: Først vil vi løse det første udsagn sådan:
1. Antag, at X: Gift vil fuldføre sin uddannelse.
Y: Accepter tiltrædelsesbrevet fra XYZ Company.
Vi kan bruge følgende symbolske form til at udtrykke denne erklæring:
X ∨ Y
Negationen af X ∨ Y beskrives som følger:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Afslutningsvis vil negationen af den givne erklæring være:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Antag, at X: Harry tager en tur
Y: Harry løber i morgen
Vi kan bruge følgende symbolske form til at udtrykke denne erklæring:
X ∨ Y
Negationen af X ∨ Y beskrives som følger:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Afslutningsvis vil negationen af den givne erklæring være:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Antag X: Hvis jeg får gode karakterer.
Y: Min kusine vil være jaloux.
Vi kan bruge følgende symbolske form til at udtrykke denne erklæring:
X → Y
Negationen af X → Y er beskrevet som følger:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Afslutningsvis vil negationen af den givne erklæring være:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Eksempel 8: I dette eksempel skal vi skrive negationen af nogle udsagn ved hjælp af De Morgans lov. Disse udsagn er beskrevet som følger:
- Jeg skal bruge et diamantsæt og en guldring værd.
- Du får et godt job, eller du får ikke en god partner.
- Jeg tager meget arbejde, og jeg kan ikke klare det.
- Min hund tager på tur, eller den laver rod i huset.
Løsning: Negationen af alle udsagn ved hjælp af De Morgans lov er beskrevet en efter en sådan:
- Jeg har ikke brug for et diamantsæt eller ikke en guldring værd.
- Du kan ikke få et godt job, og du får en god partner.
- Jeg tager ikke meget arbejde, eller jeg kan klare det.
- Min hund tager ikke på tur, og den roder ikke i huset.
Eksempel 9: I dette eksempel har vi nogle udsagn, og vi skal skrive negationen af disse udsagn. Udtalelserne er beskrevet som følger:
- Hvis det regner, så er planen om at tage til stranden aflyst.
- Hvis jeg studerer hårdt, så får jeg gode karakterer på eksamen.
- Hvis jeg går til en aftenfest, så får jeg straf af min far.
- Hvis du ikke vil tale med mig, så skal du spærre mit nummer.
Løsning: Negationen af alle udsagn er beskrevet en efter en sådan:
- Hvis planen om at tage til stranden aflyses, så regner det.
- Hvis jeg får gode karakterer på eksamen, så læser jeg hårdt.
- Hvis jeg får en straf af min far, så tager jeg til en aftenfest.
- Hvis du skal spærre mit nummer, så gider du ikke tale med mig.
Eksempel 10: I dette eksempel skal vi kontrollere, om (X → Y) → Z og X → (Y → Z) er logisk ækvivalente eller ej. Vi er nødt til at begrunde vores svar ved hjælp af sandhedstabeller og ved hjælp af logiske regler for at forenkle begge udtryk.
Løsning: Først vil vi bruge metode 1 til at kontrollere, om (X → Y) → Z og X → (Y → Z) er logisk ækvivalente, hvilket er beskrevet som følger:
vært linux
Metode 1: Her vil vi antage 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: Nu vil vi bruge den anden metode. I denne metode vil vi bruge sandhedstabellen.
| x | OG | MED | X → Y | (X → Y) → Z | Y → Z | 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 sandhedstabel kan vi se, at kolonnerne (X → Y) → Z og X → (Y → Z) ikke indeholder identiske værdier.