Stel dat er twee formules zijn, X en Y. Deze formules staan bekend als gelijkwaardigheid als X ↔ Y een tautologie is. Als twee formules X ↔ Y een tautologie zijn, dan kunnen we deze ook schrijven als X ⇔ Y, en we kunnen deze relatie lezen als X gelijkwaardigheid aan Y.
Opmerking: Er zijn enkele punten waarmee we rekening moeten houden bij lineaire equivalentie van de formule, die als volgt worden beschreven:
- ⇔ wordt alleen gebruikt om een symbool aan te geven, maar is niet verbindend.
- De waarheidswaarde van X en Y zal altijd gelijk zijn als X ↔ Y een tautologie is.
- De equivalentierelatie bevat twee eigenschappen, namelijk symmetrisch en transitief.
Methode 1: Waarheidstabelmethode:
Bij deze methode construeren we de waarheidstabellen van elke formule met twee uitspraken en controleren we vervolgens of deze uitspraken gelijkwaardig zijn.
Voorbeeld 1: In dit voorbeeld moeten we X ∨ Y ⇔ ¬(¬X ∧ ¬Y) bewijzen.
Oplossing: De waarheidstabel van X ∨ Y ⇔ ¬(¬X ∧ ¬Y) wordt als volgt beschreven:
| X | EN | X ∨ Y | ¬X | ¬En | ¬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 |
Zoals we kunnen zien is X ∨ Y en ¬(¬X ∧ ¬Y) een tautologie. Dus X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Voorbeeld 2: In dit voorbeeld moeten we bewijzen dat (X → Y) ⇔ (¬X ∨ Y).
Oplossing: De waarheidstabel van (X → Y) ⇔ (¬X ∨ Y) wordt als volgt beschreven:
| X | EN | 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 |
Zoals we kunnen zien, zijn X → Y en (¬X ∨ Y) een tautologie. Dus (X → Y) ⇔ (¬X ∨ Y)
Equivalentieformule:
Er zijn verschillende wetten die worden gebruikt om de gelijkwaardigheidsformule te bewijzen, die als volgt wordt beschreven:
Idempotente wet: Als er één instructieformule is, heeft deze de volgende eigenschappen:
X ∨ X ⇔ X X ∧ X ⇔ X
Associatief recht: Als er drie instructieformules zijn, heeft deze de volgende eigenschappen:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Commutatieve wet: Als er twee instructieformules zijn, heeft deze de volgende eigenschappen:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Distributief recht: Als er drie instructieformules zijn, heeft deze de volgende eigenschappen:
bouwer ontwerppatroon
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identiteitsrecht: Als er één instructieformule is, heeft deze de volgende eigenschappen:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Aanvulling wet: Als er één instructieformule is, heeft deze de volgende eigenschappen:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorptiewet: Als er twee instructieformules zijn, heeft deze de volgende eigenschappen:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Uit de wet van Morgan: Als er twee instructieformules zijn, heeft deze de volgende eigenschappen:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Methode 2: Vervangingsproces
Bij deze methode gaan we uit van een formule A: X → (Y → Z). De formule Y → Z staat bekend als het deel van de formule. Als we dit deel van de formule, d.w.z. Y → Z, vervangen met behulp van de equivalentieformule ¬Y ∨ Z in A, dan krijgen we een andere formule, namelijk B: X → (¬Y ∨ Z). Het is een eenvoudig proces om te verifiëren of de gegeven formules A en B gelijkwaardig aan elkaar zijn of niet. Met behulp van het vervangingsproces kunnen we B van A krijgen.
Voorbeeld 1: In dit voorbeeld moeten we bewijzen dat {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Oplossing: Hier nemen we het linkerzijdeel en proberen we het rechterzijdeel te krijgen.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Nu zullen we de associatieve wet als volgt gebruiken:
⇔ (¬X ∨ ¬Y) ∨ Z
Nu zullen we de wet van De Morgan als volgt gebruiken:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Bewezen dus
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Voorbeeld 2: In dit voorbeeld moeten we bewijzen dat {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Oplossing: Hier nemen we het linkerzijdeel en proberen we het rechterzijdeel te krijgen.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Bewezen dus
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Voorbeeld 3: In dit voorbeeld moeten we bewijzen dat X → (Y → X) ⇔ ¬X → (X → Y).
Oplossing: Hier nemen we het linkerzijdeel en proberen we het rechterzijdeel te krijgen.
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
Bewezen dus
X → (Y → X) ⇔ ¬X → (X → Y)
Voorbeeld 4: In dit voorbeeld moeten we bewijzen dat (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Oplossing: Hier nemen we het linkerzijdeel en proberen we het rechterzijdeel te krijgen.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Nu zullen we de associatieve en distributieve wetten als volgt gebruiken:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nu zullen we de wet van De Morgan als volgt gebruiken:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nu zullen we de distributieve wet als volgt gebruiken:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Bewezen dus
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Voorbeeld 5: In dit voorbeeld moeten we aantonen dat ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) een tautologie is.
Oplossing: Hier zullen we kleine onderdelen nemen en deze oplossen.
Eerst zullen we de wet van De Morgan gebruiken en het volgende verkrijgen:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Daarom,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Ook
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Vandaar
bash-variabele
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Dus
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Daarom kunnen we zeggen dat de gegeven formule een tautologie is.
Voorbeeld 6: In dit voorbeeld moeten we laten zien dat (X ∧ Y) → (X ∨ Y) een tautologie is.
Oplossing: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Nu zullen we de wet van De Morgan als volgt gebruiken:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Nu zullen we de associatieve wet en de commutatieve wet als volgt gebruiken:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Nu zullen we de negatiewet als volgt gebruiken:
⇔ (T ∨ T) ⇔ T
Daarom kunnen we zeggen dat de gegeven formule een tautologie is.
Voorbeeld 7: In dit voorbeeld moeten we de ontkenning van enkele uitspraken schrijven, die als volgt worden beschreven:
- Marry zal haar opleiding voltooien of de toetredingsbrief van XYZ Company accepteren.
- Harry gaat morgen een ritje maken of hardlopen.
- Als ik goede cijfers haal, zal mijn neef jaloers zijn.
Oplossing: Eerst zullen we de eerste verklaring als volgt oplossen:
1. Stel X: Marry zal haar opleiding voltooien.
Y: Accepteer de toetredingsbrief van XYZ Company.
We kunnen de volgende symbolische vorm gebruiken om deze verklaring uit te drukken:
X ∨ Y
De ontkenning van X ∨ Y wordt als volgt beschreven:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Concluderend zal de ontkenning van een gegeven verklaring zijn:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Stel X: Harry gaat een ritje maken
Y: Harry zal morgen rennen
We kunnen de volgende symbolische vorm gebruiken om deze verklaring uit te drukken:
X ∨ Y
De ontkenning van X ∨ Y wordt als volgt beschreven:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Concluderend zal de ontkenning van een gegeven verklaring zijn:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Stel X: Als ik goede cijfers haal.
Y: Mijn neef zal jaloers zijn.
We kunnen de volgende symbolische vorm gebruiken om deze verklaring uit te drukken:
X → Y
De ontkenning van X → Y wordt als volgt beschreven:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Concluderend zal de ontkenning van een gegeven verklaring zijn:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Voorbeeld 8: In dit voorbeeld moeten we de ontkenning van enkele uitspraken schrijven met behulp van de wet van De Morgan. Deze verklaringen worden als volgt omschreven:
- Ik heb een diamanten set nodig en een gouden ring waard.
- Je krijgt een goede baan, of je krijgt geen goede partner.
- Ik moet veel werken en ik kan het niet aan.
- Mijn hond gaat op reis of hij maakt er een zooitje van in huis.
Oplossing: De ontkenning van alle uitspraken met behulp van de wet van De Morgan wordt één voor één als volgt beschreven:
- Ik heb geen diamanten set nodig of een gouden ring niet waard.
- Je kunt geen goede baan krijgen en je krijgt wel een goede partner.
- Ik heb niet veel werk nodig of ik kan het aan.
- Mijn hond gaat niet op reis en maakt geen rommel in huis.
Voorbeeld 9: In dit voorbeeld hebben we enkele uitspraken en moeten we de ontkenning van die uitspraken schrijven. De uitspraken worden als volgt omschreven:
- Als het regent, gaat het plan om naar het strand te gaan niet door.
- Als ik hard studeer, haal ik goede cijfers op het examen.
- Als ik laat op de avond naar een feestje ga, krijg ik straf van mijn vader.
- Als je niet met mij wilt praten, moet je mijn nummer blokkeren.
Oplossing: De ontkenning van alle uitspraken wordt één voor één als volgt beschreven:
- Als het plan om naar het strand te gaan niet doorgaat, dan regent het.
- Als ik goede cijfers haal op het examen, dan studeer ik hard.
- Als ik straf krijg van mijn vader, ga ik naar een laatavondfeest.
- Als je mijn nummer moet blokkeren, wil je niet met mij praten.
Voorbeeld 10: In dit voorbeeld moeten we controleren of (X → Y) → Z en X → (Y → Z) logisch equivalent zijn of niet. We moeten ons antwoord rechtvaardigen met behulp van waarheidstabellen en met behulp van logische regels om beide uitdrukkingen te vereenvoudigen.
Oplossing: Eerst zullen we methode 1 gebruiken om te controleren of (X → Y) → Z en X → (Y → Z) logisch equivalent zijn, wat als volgt wordt beschreven:
programmeren in c-arrays
Methode 1: Hierbij gaan we uit van het volgende:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
En
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Methode 2: Nu zullen we de tweede methode gebruiken. Bij deze methode gebruiken we de waarheidstabel.
| X | EN | MET | 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 |
In deze waarheidstabel kunnen we zien dat de kolommen (X → Y) → Z en X → (Y → Z) geen identieke waarden bevatten.