Predpokladajme, že existujú dva vzorce, X a Y. Tieto vzorce budú známe ako ekvivalencia, ak X ↔ Y je tautológia. Ak sú dve formuly X ↔ Y tautológia, môžeme ju napísať aj ako X ⇔ Y a tento vzťah môžeme čítať ako X je ekvivalent Y.
Poznámka: Existuje niekoľko bodov, ktoré by sme mali mať na pamäti pri lineárnej ekvivalencii vzorca, ktoré sú opísané nasledovne:
- ⇔ sa používa len na označenie symbolu, ale nie je spájací.
- Pravdivostná hodnota X a Y bude vždy rovnaká, ak X ↔ Y je tautológia.
- Vzťah ekvivalencie obsahuje dve vlastnosti, t. j. symetrickú a tranzitívnu.
Metóda 1: Metóda pravdivostnej tabuľky:
V tejto metóde zostrojíme pravdivostné tabuľky ľubovoľného vzorca s dvoma výrokmi a potom skontrolujeme, či sú tieto výroky ekvivalentné.
Príklad 1: V tomto príklade musíme dokázať X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Riešenie: Pravdivostná tabuľka X ∨ Y ⇔ ¬(¬X ∧ ¬Y) je opísaná takto:
| X | A | X ∨ Y | ¬X | ¬A | ¬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 |
Ako vidíme, X ∨ Y a ¬(¬X ∧ ¬Y) je tautológia. Preto X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Príklad 2: V tomto príklade musíme dokázať (X → Y) ⇔ (¬X ∨ Y).
Riešenie: Pravdivostná tabuľka (X → Y) ⇔ (¬X ∨ Y) je opísaná takto:
| X | A | 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 |
Ako vidíme, X → Y a (¬X ∨ Y) sú tautológia. Preto (X → Y) ⇔ (¬X ∨ Y)
Vzorec ekvivalencie:
Existujú rôzne zákony, ktoré sa používajú na preukázanie vzorca ekvivalencie, ktorý je opísaný takto:
Idempotentný zákon: Ak existuje jeden vzorec príkazu, potom bude mať nasledujúce vlastnosti:
X ∨ X ⇔ X X ∧ X ⇔ X
Asociačné právo: Ak existujú tri vzorce príkazov, bude mať nasledujúce vlastnosti:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutatívny zákon: Ak existujú dva vzorce príkazov, bude mať nasledujúce vlastnosti:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Distribučné právo: Ak existujú tri vzorce príkazov, bude mať nasledujúce vlastnosti:
Sharwanand
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Zákon o identite: Ak existuje jeden vzorec príkazu, potom bude mať nasledujúce vlastnosti:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Doplnkový zákon: Ak existuje jeden vzorec príkazu, potom bude mať nasledujúce vlastnosti:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorpčný zákon: Ak existujú dva vzorce príkazov, bude mať nasledujúce vlastnosti:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Z Morganovho zákona: Ak existujú dva vzorce príkazov, bude mať nasledujúce vlastnosti:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Metóda 2: Proces výmeny
V tejto metóde budeme predpokladať vzorec A : X → (Y → Z). Vzorec Y → Z môže byť známy ako časť vzorca. Ak nahradíme túto časť vzorca, t.j. Y → Z, pomocou vzorca ekvivalencie ¬Y ∨ Z v A, dostaneme iný vzorec, t. j. B : X → (¬Y ∨ Z). Je to jednoduchý proces, ako si overiť, či sú dané vzorce A a B navzájom ekvivalentné alebo nie. Pomocou procesu výmeny môžeme získať B z A.
Príklad 1: V tomto príklade musíme dokázať, že {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Riešenie: Tu vezmeme ľavú bočnú časť a pokúsime sa získať pravú bočnú časť.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Teraz použijeme asociačný zákon takto:
⇔ (¬X ∨ ¬Y) ∨ Z
Teraz použijeme De Morganov zákon takto:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Preto dokázané
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Príklad 2: V tomto príklade musíme dokázať, že {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Riešenie: Tu vezmeme ľavú bočnú časť a pokúsime sa získať pravú bočnú časť.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Preto dokázané
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Príklad 3: V tomto príklade musíme dokázať, že X → (Y → X) ⇔ ¬X → (X → Y).
Riešenie: Tu vezmeme ľavú bočnú časť a pokúsime sa získať pravú bočnú časť.
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
Preto dokázané
X → (Y → X) ⇔ ¬X → (X → Y)
Príklad 4: V tomto príklade musíme dokázať, že (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Riešenie: Tu vezmeme ľavú bočnú časť a pokúsime sa získať pravú bočnú časť.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Teraz použijeme asociatívne a distribučné zákony takto:
zaujatosť a rozptyl
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Teraz použijeme De Morganov zákon takto:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Teraz použijeme distribučný zákon takto:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Preto dokázané
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Príklad 5: V tomto príklade musíme ukázať, že ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) je tautológia.
Riešenie: Tu vezmeme malé časti a vyriešime ich.
Najprv použijeme De Morganov zákon a získame nasledovné:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
preto
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Tiež
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Preto
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Teda
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Môžeme teda povedať, že daný vzorec je tautológia.
Príklad 6: V tomto príklade musíme ukázať, že (X ∧ Y) → (X ∨ Y) je tautológia.
Riešenie: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Teraz použijeme De Morganov zákon takto:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Teraz použijeme asociatívny zákon a komutatívny zákon takto:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Teraz použijeme negačný zákon takto:
⇔ (T ∨ T) ⇔ T
Môžeme teda povedať, že daný vzorec je tautológia.
Príklad 7: V tomto príklade musíme napísať negáciu niektorých tvrdení, ktoré sú opísané nasledovne:
- Marry si dokončí vzdelanie alebo prijme vstupný list spoločnosti XYZ.
- Harry si zajtra pôjde zajazdiť alebo zabehať.
- Ak dostanem dobré známky, môj bratranec bude žiarliť.
Riešenie: Najprv vyriešime prvé tvrdenie takto:
1. Predpokladajme, že X: Marry dokončí vzdelanie.
Y: Prijmite vstupný list spoločnosti XYZ.
Na vyjadrenie tohto tvrdenia môžeme použiť nasledujúcu symbolickú formu:
X ∨ Y
Negácia X ∨ Y je opísaná takto:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na záver, negácia daného tvrdenia bude:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Predpokladajme, že X: Harry pôjde na jazdu
Y: Harry zajtra pobeží
Na vyjadrenie tohto tvrdenia môžeme použiť nasledujúcu symbolickú formu:
X ∨ Y
Negácia X ∨ Y je opísaná takto:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na záver, negácia daného tvrdenia bude:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Predpokladajme, že X: Ak dostanem dobré známky.
Y: Môj bratranec bude žiarliť.
Na vyjadrenie tohto tvrdenia môžeme použiť nasledujúcu symbolickú formu:
X → Y
Negácia X → Y je opísaná takto:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Na záver, negácia daného tvrdenia bude:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Príklad 8: V tomto príklade musíme napísať negáciu niektorých výrokov pomocou De Morganovho zákona. Tieto vyhlásenia sú opísané nasledovne:
- Potrebujem sadu diamantov v hodnote zlatého prsteňa.
- Získate dobrú prácu alebo nedostanete dobrého partnera.
- Beriem veľa práce a nezvládam to.
- Môj pes ide na výlet alebo robí neporiadok v dome.
Riešenie: Negácia všetkých tvrdení pomocou De Morganovho zákona je opísaná jeden po druhom takto:
- Nepotrebujem diamantový set ani nestojím za zlatý prsteň.
- Nemôžete získať dobrú prácu a získate dobrého partnera.
- Neberiem veľa práce alebo to zvládnem.
- Môj pes nechodí na výlet a nerobí neporiadok v dome.
Príklad 9: V tomto príklade máme niekoľko výrokov a musíme napísať negáciu týchto výrokov. Vyhlásenia sú opísané takto:
- Ak prší, plán ísť na pláž sa ruší.
- Ak sa budem tvrdo učiť, budem mať dobré známky na skúške.
- Ak pôjdem na večernú párty, dostanem od otca trest.
- Ak so mnou nechceš hovoriť, musíš zablokovať moje číslo.
Riešenie: Negácia všetkých tvrdení je opísaná jeden po druhom takto:
- Ak sa zruší plán ísť na pláž, tak prší.
- Ak mám na skúške dobré známky, potom sa tvrdo učím.
- Ak dostanem od otca trest, pôjdem na večernú párty.
- Ak si musíš zablokovať moje číslo, tak sa so mnou nechceš rozprávať.
Príklad 10: V tomto príklade musíme skontrolovať, či (X → Y) → Z a X → (Y → Z) sú logicky ekvivalentné alebo nie. Našu odpoveď musíme zdôvodniť pomocou pravdivostných tabuliek a pomocou pravidiel logiky, aby sme oba výrazy zjednodušili.
Riešenie: Najprv použijeme metódu 1 na kontrolu, či (X → Y) → Z a X → (Y → Z) sú logicky ekvivalentné, čo je opísané nasledovne:
previesť z char na int java
Metóda 1: Tu budeme predpokladať nasledovné:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
A
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Metóda 2: Teraz použijeme druhú metódu. V tejto metóde použijeme pravdivostnú tabuľku.
| X | A | S | 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 |
V tejto pravdivostnej tabuľke môžeme vidieť, že stĺpce (X → Y) → Z a X → (Y → Z) neobsahujú rovnaké hodnoty.