Tegyük fel, hogy van két összetett állítás, az X és az Y, amelyeket akkor és csak akkor nevezünk logikai ekvivalenciának, ha mindkettő igazságtáblázata ugyanazokat az igazságértékeket tartalmazza az oszlopaiban. Az = vagy ⇔ szimbólum segítségével ábrázolhatjuk a logikai ekvivalenciát. Tehát X = Y vagy X ⇔ Y lesz ezeknek az állításoknak a logikai ekvivalenciája.
A logikai ekvivalencia definíció segítségével tisztáztuk, hogy ha az X és Y összetett állítások logikai ekvivalenciák, akkor ebben az esetben az X ⇔ Y a Tautológia kell, hogy legyen.
A logikai ekvivalencia törvényei
Ebben a törvényben az „ÉS” és „VAGY” szimbólumokat fogjuk használni a logikai ekvivalencia törvényének magyarázatára. Itt az ÉS-t a ∧ szimbólum, a VAGY pedig a ∨ szimbólum segítségével jelöljük. A logikai ekvivalenciának különféle törvényei vannak, amelyek leírása a következő:
Idempotens törvény:
8-1 multiplexer
Az idempotens törvényben csak egyetlen állítást használunk. E törvény szerint, ha két azonos állítást kombinálunk a ∧(és) és ∨(vagy) szimbólummal, akkor az eredő utasítás maga az állítás lesz. Tegyük fel, hogy van egy összetett P állítás. A következő jelölést használjuk az idempotens törvény jelzésére:
P ∨ P ? P P ∧ P ? P
Ennek a törvénynek az igazságtáblázatát a következőképpen írjuk le:
| P | P | P ∨ P | P ∧ P |
|---|---|---|---|
| T | T | T | T |
| F | F | F | F |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza a P, P ∨ P és P ∧ P oszlopaiban.
Ezért azt mondhatjuk, hogy P ∨ P = P és P ∧ P = P.
Kommutatív törvények:
A két állítás a kommutatív törvény bemutatására szolgál. E törvény szerint, ha két állítást ∧(és) vagy ∨(vagy) jellel kombinálunk, akkor az eredő utasítás akkor is ugyanaz lesz, ha megváltoztatjuk az állítások helyzetét. Tegyük fel, hogy két állítás van, P és Q. Ezen állítások állítása hamis lesz, ha mind a P, mind a Q állítás hamis. Minden más esetben igaz lesz. A kommutatív törvény jelölésére a következő jelölést használjuk:
P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | K | P ∨ Q | Q ∨ P |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | F |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza P ∨ Q és Q ∨ P oszlopaiban.
Ezért azt mondhatjuk, hogy P ∨ Q ? Q ∨ P.
Ugyanaz, amit be tudjuk bizonyítani P ∧ Q ? Q ∧ P.
Társulási jog:
A három állítás az asszociációs törvény bemutatására szolgál. E törvény szerint, ha három állítást zárójelek segítségével ∧(és) vagy ∨(vagy) jellel kombinálunk, akkor az eredő utasítás akkor is ugyanaz lesz, ha megváltoztatjuk a zárójelek sorrendjét. Ez azt jelenti, hogy ez a törvény független a csoportosulástól vagy társulástól. Tegyük fel, hogy három P, Q és R állítás van. Ezen állítások állítása hamis lesz, ha P, Q és R hamis. Minden más esetben igaz lesz. A következő jelölést használják az asszociációs törvény jelzésére:
P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | K | 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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza a P ∨ (Q ∨ R) és (P ∨ Q) ∨ R oszlopaiban.
Ezért azt mondhatjuk, hogy P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.
Ugyanaz, amit be tudjuk bizonyítani P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Elosztási törvény:
A három állítás az elosztási törvény bemutatására szolgál. E törvény szerint, ha egy ∨(OR) jelű állítást kombinálunk a másik két ∧(AND) jellel összekapcsolt kijelentéssel, akkor az eredő utasítás akkor is ugyanaz lesz, ha az állításokat külön kombináljuk a ∨(OR) szimbólumot és az egyesített utasításokat ∧(AND)-al kombináljuk. Tegyük fel, hogy három P, Q és R állítás létezik. A következő jelölést használjuk az eloszlási törvény jelzésére:
P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | K | 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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza a P ∨ (Q ∧ R) és (P ∨ Q) ∧ (P ∨ R) oszlopaiban.
Ezért azt mondhatjuk, hogy P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Ugyanaz, amit be tudjuk bizonyítani P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)
nfa-dfa konverzió
Személyazonossági törvény:
Egyetlen utasítást használnak az azonosságtörvény bemutatására. E törvény szerint, ha egy állítást és egy igaz értéket kombinálunk a ∨(or) szimbólummal, akkor az Igaz értéket generálja. Ha egy állítást és egy hamis értéket kombinálunk az ∧(and) szimbólummal, akkor magát az állítást generálja. Hasonlóképpen fogjuk ezt megtenni az ellenkező szimbólumokkal. Ez azt jelenti, hogy ha egy állítást és egy igaz értéket kombinálunk a ∧(and) szimbólummal, akkor magát az állítást generálja, ha pedig egy állítást és egy hamis értéket kombinálunk a ∨(or) szimbólummal, akkor generálja a Hamis érték. Tegyük fel, hogy van egy összetett P állítás, egy igaz T érték és egy hamis F érték. A következő jelölést használjuk az azonosságtörvény jelzésére:
P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | T | F | P ∨ T | P ∨ F |
|---|---|---|---|---|
| T | T | F | T | T |
| F | T | F | T | F |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza P ∨ T és T oszlopaiban. Ezért azt mondhatjuk, hogy P ∨ T = T. Hasonlóképpen, ez a táblázat is ugyanazokat az igazságértékeket tartalmazza P ∨ F és P oszlopaiban. azt mondhatjuk, hogy P ∨ F = P.
Ugyanaz, amit be tudjuk bizonyítani P ∧ T ? P és P ∧ F ? F
Kiegészítő törvény:
Egyetlen állítást használnak a komplement törvényben. E törvény szerint, ha egy állítást a komplementer utasításával kombinálunk a ∨(or) szimbólummal, akkor az Igaz értéket generálja, ha pedig ezeket az állításokat az ∧(and) szimbólummal kombináljuk, akkor a False-t generálja. érték. Ha egy igaz értéket tagadunk, akkor az hamis értéket generál, ha pedig hamis értéket, akkor az igazi értéket.
A következő jelölést használják a komplementer törvény jelzésére:
P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| 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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza P ∨ ¬P és T oszlopaiban. Ezért azt mondhatjuk, hogy P ∨ ¬P = T. Hasonlóképpen, ez a táblázat is ugyanazokat az igazságértékeket tartalmazza P ∧ ¬P és T oszlopaiban. F. Ezért azt mondhatjuk, hogy P ∧ ¬P = F.
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza ¬T és F oszlopaiban. Ezért azt mondhatjuk, hogy ¬T = F. Hasonlóképpen, ez a táblázat ugyanazokat az igazságértékeket tartalmazza ¬F és T oszlopaiban. ¬F = T.
A kettős tagadás törvénye vagy az involúciós törvény
Egyetlen állítást használunk a kettős tagadás törvényének bemutatására. E törvény szerint, ha egy tagadó állítást tagadunk, akkor az eredő állítás maga az állítás lesz. Tegyük fel, hogy van egy P állítás és egy ¬P tagadó állítás. A következő jelölést használják a kettős tagadás törvényének jelzésére:
¬(¬P) ? P
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | ¬P | ¬(¬P) |
|---|---|---|
| T | F | T |
| F | T | F |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza a ¬(¬P) és P oszlopokban. Ebből azt mondhatjuk, hogy ¬(¬P) = P.
Morgan törvényéből:
A két állítás De Morgan törvényének bemutatására szolgál. E törvény szerint, ha két állítást kombinálunk az ∧(AND) szimbólummal, majd ezeket a kombinált utasításokat tagadjuk, akkor az eredő utasítás akkor is ugyanaz lesz, ha mindkét állítás tagadását külön-külön kombináljuk a ∨( VAGY). Tegyük fel, hogy két összetett állítás létezik, a P és a Q. A következő jelölést használjuk a De Morgan törvényének jelzésére:
¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | K | ¬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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza a ¬(P ∧ Q) és ¬ P ∨ ¬Q oszlopaiban. Ezért azt mondhatjuk, hogy ¬(P ∧ Q) = ¬ P ∨ ¬Q.
Ugyanaz, amit be tudjuk bizonyítani ¬(P ∨ Q) ? ¬P ∧ ¬Q
Abszorpciós törvény:
A két állítás az abszorpciós törvény bemutatására szolgál. E törvény szerint, ha egy P állítást ∨(OR) szimbólummal kombinálunk ugyanazzal a P utasítással és egy másik Q utasítással, amelyeket ∧(AND) jellel kapcsolunk össze, akkor az eredő utasítás lesz az első P állítás. Ugyanezt az eredményt kapjuk, ha a szimbólumokat felcseréljük. Tegyük fel, hogy két összetett állítás létezik, a P és a Q. A következő jelölést használjuk az abszorpciós törvény jelzésére:
P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P
Ezeknek a jelöléseknek az igazságtáblázatát a következőképpen írjuk le:
| P | K | 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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza P ∨ (P ∧ Q) és P oszlopaiban. Ezért azt mondhatjuk, hogy P ∨ (P ∧ Q) ? P.
Hasonlóképpen, ez a táblázat is ugyanazokat az igazságértékeket tartalmazza P ∧ (P ∨ Q) és P oszlopaiban. Ezért azt mondhatjuk, hogy P ∧ (P ∨ Q) ? P.
Példák a logikai ekvivalenciára
A logikai egyenértékűségre számos példa van. Némelyikük leírása a következő:
1. példa: Ebben a példában meg fogjuk határozni az ekvivalencia tulajdonságot egy utasításhoz, amelyet a következőképpen írunk le:
cdr teljes formában
p → q ? ¬p ∨ q
Megoldás:
Ezt egy igazságtáblázat segítségével fogjuk igazolni, amelyet a következőképpen írunk le:
| P | K | ¬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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza p → q és ¬p ∨ q oszlopaiban. Ezért azt mondhatjuk, hogy p → q ? ¬p ∨ q.
2. példa: Ebben a példában meg fogjuk határozni az ekvivalencia tulajdonságot egy utasításhoz, amelyet a következőképpen írunk le:
P ↔ Q ? ( P → Q ) ∧ ( Q → P )
Megoldás:
| P | K | 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 |
Ez a táblázat ugyanazokat az igazságértékeket tartalmazza P ↔ Q és (P → Q) ∧ (Q → P) oszlopaiban. Ezért azt mondhatjuk, hogy P ↔ Q ? (P → Q) ∧ (Q → P).
3. példa: Ebben a példában az ekvivalens tulajdonságot fogjuk használni a következő állítás bizonyítására:
p ↔ q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬ q )
Megoldás:
Ennek bizonyítására a fent leírt törvények közül néhányat használunk, és ebből a törvényből a következőket kapjuk:
p ↔ q ? (¬p ∨ q) ∧ (¬q ∨ p) ...........(1)
Most a kommutatív törvényt fogjuk használni a fenti egyenletben, és a következőket kapjuk:
? (p ∨ q) ∧ (p ∨ ¬q)
Most az eloszlási törvényt fogjuk használni ebben az egyenletben, és a következőket kapjuk:
? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))
Most az eloszlási törvényt fogjuk használni ebben az egyenletben, és a következőket kapjuk:
? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)
Most a komplement törvényt fogjuk használni ebben az egyenletben, és a következőket kapjuk:
? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F
Most az identitástörvényt fogjuk használni, és a következőket kapjuk:
? (¬ p ∧ ¬ q) ∨ (q ∧ p)
Most a kommutatív törvényt fogjuk használni ebben az egyenletben, és a következőket kapjuk:
? (p ∧ q) ∨ (¬ p ¬q)
Végül az (1) egyenlet a következő lesz:
p ↔ q ? (p ∧ q) ∨ (¬ p ¬q)
Végül elmondhatjuk, hogy az (1) egyenletből p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)