Predpokladajme, že existujú dva zložené výroky, X a Y, ktoré budú známe ako logická ekvivalencia vtedy a len vtedy, ak pravdivostná tabuľka oboch z nich obsahuje v ich stĺpcoch rovnaké pravdivostné hodnoty. Pomocou symbolu = alebo ⇔ môžeme reprezentovať logickú ekvivalenciu. Takže X = Y alebo X ⇔ Y bude logická ekvivalencia týchto tvrdení.
Pomocou definície logickej ekvivalencie sme objasnili, že ak sú zložené výroky X a Y logickou ekvivalenciou, v tomto prípade X ⇔ Y musí byť tautológia.
Zákony logickej ekvivalencie
V tomto zákone budeme používať symboly „AND“ a „ALEBO“ na vysvetlenie zákona logickej ekvivalencie. Tu je AND označené pomocou symbolu ∧ a OR je označené pomocou symbolu ∨. Existujú rôzne zákony logickej ekvivalencie, ktoré sú opísané takto:
Idempotentný zákon:
V idempotentnom zákone používame iba jeden výrok. Podľa tohto zákona, ak spojíme dva rovnaké výroky so symbolom ∧(and) a ∨(alebo), potom výsledný výrok bude samotný výrok. Predpokladajme, že existuje zložený výrok P. Na označenie idempotentného zákona sa používa nasledujúci zápis:
P ∨ P ? P P ∧ P ? P
Pravdivostná tabuľka pre tento zákon je opísaná takto:
| P | P | P ∨ P | P ∧ P |
|---|---|---|---|
| T | T | T | T |
| F | F | F | F |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P, P ∨ P a P ∧ P.
Môžeme teda povedať, že P ∨ P = P a P ∧ P = P.
Komutatívne zákony:
Tieto dva výroky sa používajú na znázornenie komutatívneho zákona. Podľa tohto zákona, ak spojíme dva výroky so symbolom ∧(and) alebo ∨(alebo), potom bude výsledný výrok rovnaký, aj keď zmeníme polohu výrokov. Predpokladajme, že existujú dva výroky, P a Q. Tvrdenie týchto výrokov bude nepravdivé, keď oba výroky P aj Q budú nepravdivé. Vo všetkých ostatných prípadoch to bude pravda. Na označenie komutatívneho zákona sa používa nasledujúci zápis:
P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P
Pravdivostná tabuľka pre tieto zápisy je opísaná takto:
| P | Q | P ∨ Q | Q ∨ P |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | F |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ Q a Q ∨ P.
Môžeme teda povedať, že P ∨ Q ? Q ∨ P.
Rovnako ako môžeme dokázať P ∧ Q ? Q ∧ P.
Asociačné právo:
Tieto tri výroky sa používajú na znázornenie asociačného zákona. Podľa tohto zákona, ak spojíme tri výroky pomocou zátvoriek symbolom ∧(and) alebo ∨(alebo), potom bude výsledný výrok rovnaký, aj keď zmeníme poradie zátvoriek. To znamená, že tento zákon je nezávislý od zoskupenia alebo združenia. Predpokladajme, že existujú tri výroky P, Q a R. Tvrdenie týchto výrokov bude nepravdivé, keď P, Q a R sú nepravdivé. Vo všetkých ostatných prípadoch to bude pravda. Na označenie asociačného zákona sa používa nasledujúci zápis:
P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Pravdivostná tabuľka pre tieto zápisy je opísaná takto:
| 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ (Q ∨ R) a (P ∨ Q) ∨ R.
Môžeme teda povedať, že P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.
Rovnako ako môžeme dokázať P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Distribučné právo:
Tieto tri výroky sa používajú na znázornenie distributívneho zákona. Podľa tohto zákona, ak skombinujeme výrok symbolom ∨(OR) s dvoma ďalšími výrokmi, ktoré sú spojené symbolom ∧(AND), potom bude výsledný výrok rovnaký, aj keď oddelene skombinujeme výroky s symbol ∨(OR) a spojenie spojených výrokov s ∧(AND). Predpokladajme, že existujú tri výroky P, Q a R. Na označenie distributívneho zákona sa používa nasledujúci zápis:
P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
Pravdivostná tabuľka pre tieto zápisy je opísaná takto:
koľko filmov s nemožnými úlohami existuje
| 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ (Q ∧ R) a (P ∨ Q) ∧ (P ∨ R).
Môžeme teda povedať, že P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Rovnako ako môžeme dokázať P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
Zákon o identite:
Na zobrazenie zákona o identite sa používa jeden príkaz. Podľa tohto zákona, ak spojíme výrok a hodnotu True so symbolom ∨(alebo), potom to vygeneruje hodnotu True. Ak spojíme príkaz a hodnotu False so symbolom ∧(and), potom to vygeneruje samotný príkaz. Podobne to urobíme s opačnými symbolmi. To znamená, že ak skombinujeme príkaz a hodnotu True so symbolom ∧(and), potom to vygeneruje samotný príkaz, a ak skombinujeme príkaz a hodnotu False so symbolom ∨(alebo), potom to vygeneruje Falošná hodnota. Predpokladajme, že existuje zložený výrok P, pravdivá hodnota T a nepravdivá hodnota F. Na označenie zákona o identite sa používa nasledujúci zápis:
P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F
Pravdivostná tabuľka pre tieto zápisy je opísaná takto:
| P | T | F | P ∨ T | P ∨ F |
|---|---|---|---|---|
| T | T | F | T | T |
| F | T | F | T | F |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ T a T. Môžeme teda povedať, že P ∨ T = T. Podobne aj táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ F a P. môžeme povedať, že P ∨ F = P.
Rovnako ako môžeme dokázať P ∧ T ? P a P ∧ F ? F
Doplnkový zákon:
Jednotné vyhlásenie sa používa v doplnkovom zákone. Podľa tohto zákona, ak skombinujeme výrok s jeho doplnkom so symbolom ∨(alebo), potom vygeneruje hodnotu True a ak tieto výroky skombinujeme so symbolom ∧(and), potom vygeneruje False hodnotu. Ak negujeme skutočnú hodnotu, potom to vygeneruje falošnú hodnotu, a ak negujeme falošnú hodnotu, potom to vygeneruje skutočnú hodnotu.
Na označenie doplnkového zákona sa používa nasledujúci zápis:
P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T
Pravdivostná tabuľka pre tieto zápisy je opísaná 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ ¬P a T. Môžeme teda povedať, že P ∨ ¬P = T. Podobne aj táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∧ ¬P a F. Môžeme teda povedať, že P ∧ ¬P = F.
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch ¬T a F. Môžeme teda povedať, že ¬T = F. Podobne táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch ¬F a T. Môžeme teda povedať, že ¬F = T.
Zákon dvojitej negácie alebo zákon o involúcii
Na znázornenie zákona dvojitej negácie sa používa jeden výrok. Podľa tohto zákona, ak urobíme negáciu negovaného výroku, potom výsledný výrok bude samotný výrok. Predpokladajme, že existuje výrok P a negovaný výrok ¬P. Na označenie zákona dvojitej negácie sa používa nasledujúci zápis:
¬(¬P) ? P
Pravdivostná tabuľka pre tieto zápisy je opísaná takto:
učiť selén
| P | ¬P | ¬(¬P) |
|---|---|---|
| T | F | T |
| F | T | F |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch ¬(¬P) a P. Môžeme teda povedať, že ¬(¬P) = P.
Z Morganovho zákona:
Tieto dva výroky sa používajú na znázornenie De Morganovho zákona. Podľa tohto zákona, ak spojíme dva výroky so symbolom ∧(AND) a potom vykonáme negáciu týchto kombinovaných výrokov, potom výsledný výrok bude rovnaký, aj keď negáciu oboch výrokov spojíme oddelene so symbolom ∨( ALEBO). Predpokladajme, že existujú dva zložené výroky, P a Q. Na označenie De Morganovho zákona sa používa nasledujúci zápis:
¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q
Pravdivostná tabuľka pre tieto zápisy je opísaná 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch ¬(P ∧ Q) a ¬ P ∨ ¬Q. Môžeme teda povedať, že ¬(P ∧ Q) = ¬ P ∨ ¬Q.
Rovnako ako môžeme dokázať ¬(P ∨ Q) ? ¬P ∧ ¬Q
Absorpčný zákon:
Tieto dva výroky sa používajú na znázornenie absorpčného zákona. Podľa tohto zákona, ak spojíme výrok P symbolom ∨(OR) s rovnakým výrokom P a jedným ďalším výrokom Q, ktoré sú spojené so symbolom ∧(AND), potom bude výsledným výrokom prvý výrok P. Rovnaký výsledok sa vygeneruje, ak zameníme symboly. Predpokladajme, že existujú dva zložené výroky, P a Q. Na označenie zákona o absorpcii sa používa nasledujúci zápis:
P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P
Pravdivostná tabuľka pre tieto zápisy je opísaná 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∨ (P ∧ Q) a P. Môžeme teda povedať, že P ∨ (P ∧ Q) ? P.
Podobne aj táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ∧ (P ∨ Q) a P. Môžeme teda povedať, že P ∧ (P ∨ Q) ? P.
Príklady logickej ekvivalencie
Existujú rôzne príklady logickej ekvivalencie. Niektoré z nich sú opísané takto:
Príklad 1: V tomto príklade vytvoríme vlastnosť ekvivalencie pre príkaz, ktorý je opísaný takto:
p → q ? ¬p ∨ q
Riešenie:
Preukážeme to pomocou pravdivostnej tabuľky, ktorá je opísaná 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch p → q a ¬p ∨ q. Môžeme teda povedať, že p → q ? ¬p ∨ q.
Príklad 2: V tomto príklade vytvoríme vlastnosť ekvivalencie pre príkaz, ktorý je opísaný takto:
P ↔ Q ? ( P → Q ) ∧ ( Q → P )
Riešenie:
| 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 |
Táto tabuľka obsahuje rovnaké pravdivostné hodnoty v stĺpcoch P ↔ Q a (P → Q) ∧ (Q → P). Môžeme teda povedať, že P ↔ Q ? (P → Q) ∧ (Q → P).
Príklad 3: V tomto príklade použijeme ekvivalentnú vlastnosť na dôkaz nasledujúceho tvrdenia:
p ↔ q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )
Riešenie:
Aby sme to dokázali, použijeme niektoré z vyššie opísaných zákonov a z tohto zákona máme:
p ↔ q ? (¬p ∨ q) ∧ (¬q ∨ p) ...........(1)
Teraz použijeme komutatívny zákon vo vyššie uvedenej rovnici a získame nasledovné:
? (p ∨ q) ∧ (p ∨ ¬q)
Teraz v tejto rovnici použijeme distribučný zákon a získame nasledovné:
? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))
Teraz v tejto rovnici použijeme distribučný zákon a získame nasledovné:
? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)
Teraz v tejto rovnici použijeme doplnkový zákon a získame nasledovné:
? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F
Teraz použijeme zákon o identite a získame nasledovné:
? (¬ p ∧ ¬ q) ∨ (q ∧ p)
Teraz v tejto rovnici použijeme komutatívny zákon a získame nasledovné:
? (p ∧ q) ∨ (¬ p ¬q)
Nakoniec rovnica (1) bude vyzerať takto:
p ↔ q ? (p ∧ q) ∨ (¬ p ¬q)
Nakoniec môžeme povedať, že rovnica (1) sa stáva p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)