Tegyük fel, hogy két képlet létezik, X és Y. Ezeket a képleteket ekvivalenciaként ismerjük, ha X ↔ Y tautológia. Ha két X ↔ Y képlet tautológia, akkor felírhatjuk X ⇔ Y alakban is, és ezt az összefüggést úgy is olvashatjuk, hogy X ekvivalenciája Y-val.
Megjegyzés: Van néhány pont, amelyet szem előtt kell tartanunk a képlet lineáris ekvivalenciája során, amelyek leírása a következő:
- A ⇔ csak szimbólumot jelöl, de nem kapcsolódni képes.
- X és Y igazságértéke mindig egyenlő lesz, ha X ↔ Y tautológia.
- Az ekvivalenciareláció két tulajdonságot tartalmaz, azaz szimmetrikus és tranzitív.
1. módszer: Igazságtábla módszer:
Ebben a módszerben megszerkesztjük bármely két állításból álló képlet igazságtáblázatát, majd ellenőrizzük, hogy ezek az állítások ekvivalensek-e.
1. példa: Ebben a példában be kell bizonyítanunk, hogy X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Megoldás: Az X ∨ Y ⇔ ¬(¬X ∧ ¬Y) igazságtáblázatát a következőképpen írjuk le:
| x | ÉS | X ∨ Y | ¬X | ¬És | ¬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 |
Amint látjuk, X ∨ Y és ¬(¬X ∧ ¬Y) tautológia. Ezért X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
2. példa: Ebben a példában be kell bizonyítanunk (X → Y) ⇔ (¬X ∨ Y).
Megoldás: Az (X → Y) ⇔ (¬X ∨ Y) igazságtáblázatát a következőképpen írjuk le:
| x | ÉS | 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 |
Amint látjuk, X → Y és (¬X ∨ Y) tautológia. Ezért (X → Y) ⇔ (¬X ∨ Y)
Egyenértékűségi képlet:
Különféle törvények használhatók az ekvivalenciaképlet bizonyítására, amelyet a következőképpen írunk le:
Idempotens törvény: Ha van egy állítási képlet, akkor az a következő tulajdonságokkal rendelkezik:
X ∨ X ⇔ X X ∧ X ⇔ X
Társulási jog: Ha három állítási képlet van, akkor a következő tulajdonságokkal rendelkezik:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Kommutatív jog: Ha két állítási képlet van, akkor a következő tulajdonságokkal rendelkezik:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Elosztási törvény: Ha három állítási képlet van, akkor a következő tulajdonságokkal rendelkezik:
karakterlánc keresése c++
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Személyazonossági törvény: Ha van egy állítási képlet, akkor az a következő tulajdonságokkal rendelkezik:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Kiegészítő törvény: Ha van egy állítási képlet, akkor az a következő tulajdonságokkal rendelkezik:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Abszorpciós törvény: Ha két állítási képlet van, akkor a következő tulajdonságokkal rendelkezik:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Morgan törvényéből: Ha két állítási képlet van, akkor a következő tulajdonságokkal rendelkezik:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
2. módszer: Cserefolyamat
Ebben a módszerben egy A : X → (Y → Z) képletet feltételezünk. Az Y → Z képlet a képlet részeként ismert. Ha a képletnek ezt a részét, azaz az Y → Z-t lecseréljük a ¬Y ∨ Z ekvivalenciaformulával A-ban, akkor egy másik képletet kapunk, azaz B : X → (¬Y ∨ Z). Könnyen ellenőrizhető, hogy a megadott A és B képletek ekvivalensek-e egymással vagy sem. A cserefolyamat segítségével B-t kaphatunk A-ból.
1. példa: Ebben a példában bizonyítanunk kell, hogy {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Megoldás: Itt fogjuk a bal oldali részt, és megpróbáljuk megszerezni a jobb oldali részt.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Most a következőképpen fogjuk használni az asszociatív törvényt:
⇔ (¬X ∨ ¬Y) ∨ Z
Most a következőképpen fogjuk használni De Morgan törvényét:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Ezért bebizonyosodott
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z 2. példa: Ebben a példában bizonyítanunk kell, hogy {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Megoldás: Itt fogjuk a bal oldali részt, és megpróbáljuk megszerezni a jobb oldali részt.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Ezért bebizonyosodott
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
3. példa: Ebben a példában bizonyítanunk kell, hogy X → (Y → X) ⇔ ¬X → (X → Y).
Megoldás: Itt fogjuk a bal oldali részt, és megpróbáljuk megszerezni a jobb oldali részt.
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
Ezért bebizonyosodott
X → (Y → X) ⇔ ¬X → (X → Y)
4. példa: Ebben a példában be kell bizonyítanunk, hogy (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Megoldás: Itt fogjuk a bal oldali részt, és megpróbáljuk megszerezni a jobb oldali részt.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Most az asszociatív és eloszlási törvényeket fogjuk használni, így:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Most a következőképpen fogjuk használni De Morgan törvényét:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Most az elosztási törvényt így fogjuk használni:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Ezért bebizonyosodott
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
5. példa: Ebben a példában meg kell mutatnunk, hogy az ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) tautológia.
Megoldás: Itt kis részeket veszünk és megoldjuk őket.
Először De Morgan törvényét használjuk, és a következőket kapjuk:
indiai színésznő, Rani Mukerji
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Ebből adódóan,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Is
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Ennélfogva
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
És így
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Ezért azt mondhatjuk, hogy az adott formula tautológia.
6. példa: Ebben a példában meg kell mutatnunk, hogy (X ∧ Y) → (X ∨ Y) tautológia.
Megoldás: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Most a következőképpen fogjuk használni De Morgan törvényét:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Most a következőképpen fogjuk használni az asszociatív törvényt és a kommutatív törvényt:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Most a tagadás törvényét a következőképpen fogjuk használni:
⇔ (T ∨ T) ⇔ T
Ezért azt mondhatjuk, hogy az adott formula tautológia.
7. példa: Ebben a példában meg kell írnunk néhány állítás tagadását, amelyek leírása a következő:
- Marry befejezi tanulmányait, vagy elfogadja az XYZ Company csatlakozási levelét.
- Harry holnap elmegy lovagolni vagy futni.
- Ha jó jegyeket kapok, az unokatestvérem féltékeny lesz.
Megoldás: Először az első állítást a következőképpen oldjuk meg:
1. Tegyük fel, hogy X: Marry befejezi tanulmányait.
Y: Fogadja el az XYZ Company csatlakozási levelét.
A következő szimbolikus formát használhatjuk ennek az állításnak a kifejezésére:
X ∨ Y
X ∨ Y tagadása a következőképpen írható le:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Végezetül az adott állítás tagadása a következő lesz:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Tegyük fel, hogy X: Harry elmegy egy kört
Y: Harry holnap futni fog
A következő szimbolikus formát használhatjuk ennek az állításnak a kifejezésére:
X ∨ Y
X ∨ Y tagadása a következőképpen írható le:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Végezetül az adott állítás tagadása a következő lesz:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Tegyük fel X: Ha jó jegyeket kapok.
Y: Az unokatestvérem féltékeny lesz.
A következő szimbolikus formát használhatjuk ennek az állításnak a kifejezésére:
X → Y
Az X → Y tagadása a következőképpen írható le:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Végezetül az adott állítás tagadása a következő lesz:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
8. példa: Ebben a példában néhány állítás tagadását kell felírnunk De Morgan törvénye segítségével. Ezeket a kijelentéseket a következőképpen írjuk le:
- Egy gyémánt készletre van szükségem, és megér egy aranygyűrűt.
- Jó munkát kapsz, vagy nem lesz jó partnered.
- Sok munkát vállalok, és nem bírom.
- A kutyám kirándulni megy, vagy rendetlenséget csinál a házban.
Megoldás: Az összes állítás tagadását De Morgan törvénye segítségével egyenként így írjuk le:
- Nincs szükségem gyémánt készletre, vagy nem ér egy aranygyűrűt.
- Nem kaphatsz jó munkát, és kapsz egy jó partnert.
- Nem vállalok sok munkát, vagy bírom.
- A kutyám nem megy kirándulni, és nem csinál rendetlenséget a házban.
9. példa: Ebben a példában van néhány állításunk, és meg kell írnunk ezen állítások tagadását. Az állítások leírása a következő:
- Ha esik az eső, akkor a strandolási terv elmarad.
- Ha keményen tanulok, akkor jó jegyeket kapok a vizsgán.
- Ha elmegyek egy késő esti buliba, akkor apám büntetést kap.
- Ha nem akar velem beszélni, akkor le kell tiltania a számomat.
Megoldás: Az összes állítás tagadása a következőképpen írható le egyenként:
- Ha a strandolási tervet lemondják, akkor esik az eső.
- Ha jó jegyeket kapok a vizsgán, akkor keményen tanulok.
- Ha megbüntet az apám, akkor elmegyek egy késő esti buliba.
- Ha le kell tiltania a számomat, akkor nem akar velem beszélni.
10. példa: Ebben a példában ellenőriznünk kell, hogy (X → Y) → Z és X → (Y → Z) logikailag egyenértékűek-e vagy sem. Válaszunkat igazságtáblázatok és logikai szabályok segítségével kell igazolnunk, hogy mindkét kifejezést leegyszerűsítsük.
Megoldás: Először az 1. módszerrel ellenőrizzük, hogy (X → Y) → Z és X → (Y → Z) logikailag egyenértékűek-e, amit a következőképpen írunk le:
hogyan válasszunk oszlopokat különböző táblákból sql-ben
1. módszer: Itt a következőket feltételezzük:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
És
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
2. módszer: Most a második módszert fogjuk használni. Ebben a módszerben az igazságtáblázatot fogjuk használni.
| x | ÉS | VAL VEL | 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 |
Ebben az igazságtáblázatban láthatjuk, hogy az (X → Y) → Z és az X → (Y → Z) oszlopai nem tartalmaznak azonos értékeket.