Předpokládejme, že existují dva složené výroky, X a Y, které budou známé jako logická ekvivalence právě tehdy, když pravdivostní tabulka obou z nich obsahuje ve svých sloupcích stejné pravdivostní hodnoty. Pomocí symbolu = nebo ⇔ můžeme reprezentovat logickou ekvivalenci. Takže X = Y nebo X ⇔ Y bude logická ekvivalence těchto tvrzení.
S pomocí definice logické ekvivalence jsme vyjasnili, že pokud jsou složené příkazy X a Y logickou ekvivalencí, v tomto případě musí být X ⇔ Y tautologie.
Zákony logické ekvivalence
V tomto zákoně budeme používat symboly 'AND' a 'OR' k vysvětlení zákona logické ekvivalence. Zde je AND indikováno pomocí symbolu ∧ a OR je indikováno pomocí symbolu ∨. Existují různé zákony logické ekvivalence, které jsou popsány takto:
Idempotentní zákon:
V idempotentním zákoně používáme pouze jediný výrok. Podle tohoto zákona, pokud spojíme dva stejné výroky se symbolem ∧(and) a ∨(nebo), pak výsledný výrok bude samotný výrok. Předpokládejme, že existuje složený výrok P. K označení idempotentního zákona se používá následující zápis:
P ∨ P ? P P ∧ P ? P
Pravdivostní tabulka pro tento zákon je popsána takto:
| P | P | P ∨ P | P ∧ P |
|---|---|---|---|
| T | T | T | T |
| F | F | F | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P, P ∨ P a P ∧ P.
Můžeme tedy říci, že P ∨ P = P a P ∧ P = P.
Komutativní zákony:
Tyto dva výroky se používají k zobrazení komutativního zákona. Podle tohoto zákona, pokud spojíme dva výroky se symbolem ∧(and) nebo ∨(nebo), pak bude výsledný výrok stejný, i když změníme pozici výroků. Předpokládejme, že existují dva výroky, P a Q. Tvrzení těchto výroků bude nepravdivé, když oba výroky P a Q budou nepravdivé. Ve všech ostatních případech to bude pravda. K označení komutativního zákona se používá následující zápis:
P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | Q | P ∨ Q | Q ∨ P |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ Q a Q ∨ P.
Můžeme tedy říci, že P ∨ Q ? Q ∨ P.
Stejně jako můžeme dokázat P ∧ Q ? Q ∧ P.
Asociační právo:
Tyto tři výroky se používají k zobrazení asociativního zákona. Pokud podle tohoto zákona spojíme tři výroky pomocí závorek symbolem ∧(and) nebo ∨(nebo), pak bude výsledný výrok stejný, i když změníme pořadí závorek. To znamená, že tento zákon je nezávislý na seskupení nebo sdružení. Předpokládejme, že existují tři tvrzení P, Q a R. Tvrzení těchto tvrzení bude nepravdivé, když P, Q a R jsou nepravdivé. Ve všech ostatních případech to bude pravda. K označení asociativního zákona se používá následující zápis:
P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Pravdivostní tabulka pro tyto zápisy je popsána takto:
to string metoda java
| P | Q | R | P ∨ Q | Q ∨ R | (P ∨ Q) ∨ R | P ∨ (Q ∨ R) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | F | T | T | T |
| F | F | F | F | F | F | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ (Q ∨ R) a (P ∨ Q) ∨ R.
Můžeme tedy říci, že P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.
Stejně jako můžeme dokázat P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Distribuční právo:
Tyto tři výroky se používají k zobrazení distribučního zákona. Podle tohoto zákona, pokud spojíme výrok symbolem ∨(OR) se dvěma dalšími výroky, které jsou spojeny symbolem ∧(AND), bude výsledný výrok stejný, i když samostatně spojíme výroky s symbol ∨(OR) a spojení spojených příkazů s ∧(AND). Předpokládejme, že existují tři výroky P, Q a R. K označení distributivního zákona se používá následující označení:
P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | Q | R | Q ∧ R | P∨(Q ∧R) | P ∨ Q | P∨ R | (P ∨ Q) ∧ (P ∨ R) |
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ (Q ∧ R) a (P ∨ Q) ∧ (P ∨ R).
Můžeme tedy říci, že P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Stejně jako můžeme dokázat P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
Zákon o identitě:
K zobrazení zákona o identitě se používá jeden příkaz. Podle tohoto zákona, pokud zkombinujeme příkaz a hodnotu True se symbolem ∨(nebo), pak to vygeneruje hodnotu True. Pokud spojíme příkaz a hodnotu False se symbolem ∧(and), pak to vygeneruje samotný příkaz. Podobně to uděláme s opačnými symboly. To znamená, že pokud zkombinujeme příkaz a hodnotu True se symbolem ∧(and), pak to vygeneruje samotný příkaz, a pokud zkombinujeme příkaz a hodnotu False se symbolem ∨(nebo), pak to vygeneruje Falešná hodnota. Předpokládejme, že existuje složený příkaz P, pravdivá hodnota T a nepravdivá hodnota F. K označení zákona o identitě se používá následující zápis:
P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | T | F | P ∨ T | P ∨ F |
|---|---|---|---|---|
| T | T | F | T | T |
| F | T | F | T | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ T a T. Můžeme tedy říci, že P ∨ T = T. Podobně tato tabulka také obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ F a P. můžeme říci, že P ∨ F = P.
Stejně jako můžeme dokázat P ∧ T ? P a P ∧ F ? F
Doplňkový zákon:
V doplňkovém zákoně se používá jediný příkaz. Podle tohoto zákona, pokud spojíme příkaz s jeho komplementárním příkazem se symbolem ∨(nebo), pak to vygeneruje hodnotu True, a pokud zkombinujeme tyto příkazy se symbolem ∧(and), pak to vygeneruje hodnotu False. hodnota. Pokud negujeme skutečnou hodnotu, pak to vygeneruje falešnou hodnotu, a pokud negujeme falešnou hodnotu, pak to vygeneruje skutečnou hodnotu.
K označení zákona doplňku se používá následující zápis:
P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | ¬P | T | ¬T | F | ¬F | P ∨ ¬P | P ∧ ¬P |
|---|---|---|---|---|---|---|---|
| T | F | T | F | F | T | T | F |
| F | T | T | F | F | T | T | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ ¬P a T. Můžeme tedy říci, že P ∨ ¬P = T. Podobně tato tabulka také obsahuje stejné pravdivostní hodnoty ve sloupcích P ∧ ¬P a F. Můžeme tedy říci, že P ∧ ¬P = F.
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích ¬T a F. Můžeme tedy říci, že ¬T = F. Podobně tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích ¬F a T. Můžeme tedy říci, že ¬F = T.
Zákon dvojité negace nebo zákon involuce
K zobrazení zákona dvojí negace se používá jediný příkaz. Podle tohoto zákona, pokud provedeme negaci negovaného výroku, pak výsledný výrok bude samotný výrok. Předpokládejme, že existuje výrok P a negovaný výrok ¬P. K označení zákona dvojité negace se používá následující zápis:
¬(¬P) ? P
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | ¬P | ¬(¬P) |
|---|---|---|
| T | F | T |
| F | T | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích ¬(¬P) a P. Můžeme tedy říci, že ¬(¬P) = P.
Z Morganova zákona:
Tyto dva výroky se používají k zobrazení De Morganova zákona. Podle tohoto zákona, pokud spojíme dva výroky se symbolem ∧(AND) a následně provedeme negaci těchto kombinovaných výroků, bude výsledný výrok stejný, i když negaci obou výroků spojíme samostatně se symbolem ∨( NEBO). Předpokládejme, že existují dva složené výroky, P a Q. Následující zápis se používá k označení De Morganova zákona:
¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | Q | ¬P | ¬Q | P ∧ Q | ¬(P ∧ Q) | ¬ P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | F | T | T | F | T | T |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích ¬(P ∧ Q) a ¬ P ∨ ¬Q. Můžeme tedy říci, že ¬(P ∧ Q) = ¬ P ∨ ¬Q.
Stejně jako můžeme dokázat ¬(P ∨ Q) ? ¬P ∧ ¬Q
Absorpční zákon:
Tyto dva výroky se používají k znázornění zákona absorpce. Podle tohoto zákona, pokud spojíme výrok P pomocí symbolu ∨(OR) se stejným výrokem P a jedním dalším výrokem Q, které jsou spojeny se symbolem ∧(AND), pak bude výsledným výrokem první výrok P. Stejný výsledek bude generován, pokud zaměníme symboly. Předpokládejme, že existují dva složené výroky, P a Q. Následující zápis se používá k označení zákona absorpce:
P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P
Pravdivostní tabulka pro tyto zápisy je popsána takto:
| P | Q | P ∧ Q | P ∨ Q | P ∨ (P ∧ Q) | P ∧ (P ∨ Q) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | T |
| F | T | F | T | F | F |
| F | F | F | F | F | F |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ∨ (P ∧ Q) a P. Můžeme tedy říci, že P ∨ (P ∧ Q) ? P.
Podobně tato tabulka také obsahuje stejné pravdivostní hodnoty ve sloupcích P ∧ (P ∨ Q) a P. Můžeme tedy říci, že P ∧ (P ∨ Q) ? P.
Příklady logické ekvivalence
Existují různé příklady logické ekvivalence. Některé z nich jsou popsány takto:
Příklad 1: V tomto příkladu stanovíme vlastnost ekvivalence pro příkaz, který je popsán následovně:
p → q ? ¬p ∨ q
Řešení:
Prokážeme to pomocí pravdivostní tabulky, která je popsána takto:
| P | Q | ¬p | p → q | ¬p ∨ q |
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích p → q a ¬p ∨ q. Můžeme tedy říci, že p → q ? ¬p ∨ q.
Příklad 2: V tomto příkladu stanovíme vlastnost ekvivalence pro příkaz, který je popsán následovně:
P ↔ Q ? ( P → Q ) ∧ ( Q → P )
Řešení:
| P | Q | P → Q | Q → P | P ↔ Q | ( P → Q ) ∧ ( Q → P ) |
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | F | F | F |
| F | F | T | T | T | T |
Tato tabulka obsahuje stejné pravdivostní hodnoty ve sloupcích P ↔ Q a (P → Q) ∧ (Q → P). Můžeme tedy říci, že P ↔ Q ? (P → Q) ∧ (Q → P).
Příklad 3: V tomto příkladu použijeme ekvivalentní vlastnost k prokázání následujícího tvrzení:
p ↔ q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )
Řešení:
Abychom to dokázali, použijeme některé z výše popsaných zákonů a z tohoto zákona máme:
p ↔ q ? (¬p ∨ q) ∧ (¬q ∨ p) ...........(1)
Nyní použijeme komutativní zákon ve výše uvedené rovnici a získáme následující:
? (p ∨ q) ∧ (p ∨ ¬q)
Nyní v této rovnici použijeme distribuční zákon a získáme následující:
? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))
Nyní v této rovnici použijeme distribuční zákon a získáme následující:
? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)
Nyní v této rovnici použijeme zákon doplňku a získáme následující:
? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F
Nyní použijeme zákon o identitě a získáme následující:
? (¬ p ∧ ¬ q) ∨ (q ∧ p)
Nyní v této rovnici použijeme komutativní zákon a získáme následující:
? (p ∧ q) ∨ (¬ p ¬q)
Nakonec rovnice (1) zní takto:
p ↔ q ? (p ∧ q) ∨ (¬ p ¬q)
Nakonec můžeme říci, že rovnice (1) se stává p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)