Předpokládejme, že existují dvě formule, X a Y. Tyto formule budou známé jako ekvivalence, pokud X ↔ Y je tautologie. Pokud jsou dvě formule X ↔ Y tautologie, pak ji můžeme také napsat jako X ⇔ Y a tento vztah můžeme číst jako X je ekvivalence s Y.
Poznámka: Při lineární ekvivalenci vzorce bychom měli mít na paměti některé body, které jsou popsány následovně:
- ⇔ se používá k označení pouze symbolu, ale není spojovací.
- Pravdivostní hodnota X a Y bude vždy stejná, pokud X ↔ Y je tautologie.
- Relace ekvivalence obsahuje dvě vlastnosti, tj. symetrickou a tranzitivní.
Metoda 1: Metoda pravdivostní tabulky:
V této metodě sestrojíme pravdivostní tabulky libovolného vzorce se dvěma výroky a poté zkontrolujeme, zda jsou tato tvrzení ekvivalentní.
Příklad 1: V tomto příkladu musíme dokázat X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Řešení: Pravdivostní tabulka X ∨ Y ⇔ ¬(¬X ∧ ¬Y) je popsána následovně:
| 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 |
Jak vidíme, X ∨ Y a ¬(¬X ∧ ¬Y) je tautologie. Proto X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Příklad 2: V tomto příkladu musíme dokázat (X → Y) ⇔ (¬X ∨ Y).
Řešení: Pravdivostní tabulka (X → Y) ⇔ (¬X ∨ Y) je popsána následovně:
| 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 |
Jak vidíme, X → Y a (¬X ∨ Y) jsou tautologie. Odtud (X → Y) ⇔ (¬X ∨ Y)
Ekvivalenční vzorec:
Existují různé zákony, které se používají k prokázání rovnice ekvivalence, která je popsána takto:
Idempotentní zákon: Pokud existuje jeden vzorec příkazu, bude mít následující vlastnosti:
X ∨ X ⇔ X X ∧ X ⇔ X
Asociační právo: Pokud existují tři vzorce příkazů, bude mít následující vlastnosti:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutativní zákon: Pokud existují dva vzorce příkazů, bude mít následující vlastnosti:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Distribuční právo: Pokud existují tři vzorce příkazů, bude mít následující vlastnosti:
zrušit poslední potvrzení
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Zákon o identitě: Pokud existuje jeden vzorec příkazu, bude mít následující vlastnosti:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Doplňkový zákon: Pokud existuje jeden vzorec příkazu, bude mít následující vlastnosti:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorpční zákon: Pokud existují dva vzorce příkazů, bude mít následující vlastnosti:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Z Morganova zákona: Pokud existují dva vzorce příkazů, bude mít následující vlastnosti:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Metoda 2: Proces výměny
V této metodě budeme předpokládat vzorec A : X → (Y → Z). Vzorec Y → Z může být znám jako část vzorce. Nahradíme-li tuto část vzorce, tedy Y → Z, pomocí vzorce ekvivalence ¬Y ∨ Z v A, dostaneme jiný vzorec, tedy B : X → (¬Y ∨ Z). Je to snadný proces, jak ověřit, zda jsou dané vzorce A a B vzájemně ekvivalentní či nikoliv. Pomocí procesu výměny můžeme získat B z A.
Příklad 1: V tomto příkladu musíme dokázat, že {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Řešení: Zde vezmeme levou boční část a pokusíme se získat pravou boční část.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Nyní použijeme asociativní zákon takto:
⇔ (¬X ∨ ¬Y) ∨ Z
Nyní použijeme De Morganův zákon takto:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Tím pádem prokázáno
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Příklad 2: V tomto příkladu musíme dokázat, že {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Řešení: Zde vezmeme levou boční část a pokusíme se získat pravou boční část.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Tím pádem prokázáno
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Příklad 3: V tomto příkladu musíme dokázat, že X → (Y → X) ⇔ ¬X → (X → Y).
Řešení: Zde vezmeme levou boční část a pokusíme se získat pravou boční část.
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
Tím pádem prokázáno
X → (Y → X) ⇔ ¬X → (X → Y)
Příklad 4: V tomto příkladu musíme dokázat, že (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Řešení: Zde vezmeme levou boční část a pokusíme se získat pravou boční část.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Nyní použijeme asociativní a distribuční zákony takto:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nyní použijeme De Morganův zákon takto:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nyní použijeme distribuční zákon takto:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Tím pádem prokázáno
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Příklad 5: V tomto příkladu musíme ukázat, že ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) je tautologie.
js replace
Řešení: Zde vezmeme malé části a vyřešíme je.
Nejprve použijeme De Morganův zákon a získáme následující:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Proto,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Taky
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Proto
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Tím pádem
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Můžeme tedy říci, že daný vzorec je tautologie.
Příklad 6: V tomto příkladu musíme ukázat, že (X ∧ Y) → (X ∨ Y) je tautologie.
Řešení: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Nyní použijeme De Morganův zákon takto:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Nyní použijeme asociativní zákon a komutativní zákon takto:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Nyní použijeme zákon negace takto:
⇔ (T ∨ T) ⇔ T
Můžeme tedy říci, že daný vzorec je tautologie.
Příklad 7: V tomto příkladu musíme napsat negaci některých výroků, které jsou popsány takto:
- Marry dokončí své vzdělání nebo přijme vstupní dopis společnosti XYZ.
- Harry půjde zítra na projížďku nebo běh.
- Pokud dostanu dobré známky, můj bratranec bude žárlit.
Řešení: Nejprve vyřešíme první tvrzení takto:
1. Předpokládejme, že X: Marry dokončí své vzdělání.
Y: Přijměte připojovací dopis společnosti XYZ.
K vyjádření tohoto tvrzení můžeme použít následující symbolickou formu:
X ∨ Y
Negace X ∨ Y je popsána takto:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na závěr bude negace daného tvrzení:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Předpokládejme, že X: Harry půjde na projížďku
Y: Harry zítra poběží
K vyjádření tohoto tvrzení můžeme použít následující symbolickou formu:
X ∨ Y
Negace X ∨ Y je popsána takto:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na závěr bude negace daného tvrzení:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Předpokládejme X: Pokud dostanu dobré známky.
Y: Můj bratranec bude žárlit.
K vyjádření tohoto tvrzení můžeme použít následující symbolickou formu:
X → Y
Negace X → Y je popsána takto:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Na závěr bude negace daného tvrzení:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Příklad 8: V tomto příkladu musíme napsat negaci některých výroků pomocí De Morganova zákona. Tato prohlášení jsou popsána následovně:
- Potřebuji sadu diamantů v hodnotě zlatého prstenu.
- Získáte dobrou práci, nebo nedostanete dobrého partnera.
- Beru hodně práce a nezvládám to.
- Můj pes jede na výlet nebo dělá nepořádek v domě.
Řešení: Negace všech výroků pomocí De Morganova zákona je popsána jeden po druhém takto:
- Nepotřebuji diamantovou sadu nebo nestojím za zlatý prsten.
- Nemůžete získat dobrou práci a získáte dobrého partnera.
- Neberu si moc práce nebo to zvládnu.
- Můj pes nejezdí na výlet a nedělá nepořádek v domě.
Příklad 9: V tomto příkladu máme nějaké výroky a musíme napsat negaci těchto výroků. Výroky jsou popsány takto:
- Pokud prší, pak se plán jít na pláž ruší.
- Pokud se budu pilně učit, dostanu u zkoušky dobré známky.
- Pokud půjdu na noční párty, dostanu trest od otce.
- Pokud se mnou nechceš mluvit, musíš moje číslo zablokovat.
Řešení: Negace všech výroků je popsána jeden po druhém takto:
- Pokud se zruší plán jít na pláž, pak prší.
- Když mám dobré známky u zkoušky, pak se pilně učím.
- Pokud dostanu trest od svého otce, půjdu na noční párty.
- Jestli si musíš zablokovat moje číslo, tak se mnou nechceš mluvit.
Příklad 10: V tomto příkladu musíme zkontrolovat, zda (X → Y) → Z a X → (Y → Z) jsou logicky ekvivalentní nebo ne. Svou odpověď musíme zdůvodnit pomocí pravdivostních tabulek a pomocí logických pravidel, abychom oba výrazy zjednodušili.
Řešení: Nejprve použijeme metodu 1 ke kontrole, zda (X → Y) → Z a X → (Y → Z) jsou logicky ekvivalentní, což je popsáno následovně:
java mvc
Metoda 1: Zde budeme předpokládat následující:
(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)
Metoda 2: Nyní použijeme druhou metodu. V této metodě použijeme pravdivostní tabulku.
| 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 této pravdivostní tabulce můžeme vidět, že sloupce (X → Y) → Z a X → (Y → Z) neobsahují stejné hodnoty.