Tarkime, kad yra dvi formulės, X ir Y. Šios formulės bus žinomos kaip ekvivalentiškumas, jei X ↔ Y yra tautologija. Jei dvi formulės X ↔ Y yra tautologija, tai taip pat galime parašyti kaip X ⇔ Y, o šį ryšį galime perskaityti kaip X yra lygiavertiškumas Y.
Pastaba: Yra keletas punktų, į kuriuos turėtume turėti omenyje tiesinį formulės lygiavertiškumą, kurie aprašomi taip:
- ⇔ naudojamas tik simboliui nurodyti, bet jis nėra jungiamasis.
- X ir Y tiesos reikšmė visada bus lygi, jei X ↔ Y yra tautologija.
- Ekvivalentiškumo santykis turi dvi savybes, ty simetrinę ir tranzityvinę.
1 metodas: tiesos lentelės metodas:
Šiuo metodu sudarysime bet kurios dviejų teiginių formulės tiesos lenteles ir patikrinsime, ar šie teiginiai yra lygiaverčiai.
1 pavyzdys: Šiame pavyzdyje turime įrodyti X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Sprendimas: Tiesos lentelė X ∨ Y ⇔ ¬(¬X ∧ ¬Y) aprašoma taip:
| X | IR | X ∨ Y | ¬X | ¬Ir | ¬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 |
Kaip matome, X ∨ Y ir ¬(¬X ∧ ¬Y) yra tautologija. Taigi X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
2 pavyzdys: Šiame pavyzdyje turime įrodyti (X → Y) ⇔ (¬X ∨ Y).
Sprendimas: (X → Y) ⇔ (¬X ∨ Y) tiesos lentelė aprašoma taip:
| X | IR | 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 |
Kaip matome, X → Y ir (¬X ∨ Y) yra tautologija. Taigi (X → Y) ⇔ (¬X ∨ Y)
Lygiavertiškumo formulė:
Egzistuoja įvairūs dėsniai, naudojami lygiavertiškumo formulei įrodyti, kuri apibūdinama taip:
Idempotentinis įstatymas: Jei yra viena teiginio formulė, ji turės šias savybes:
X ∨ X ⇔ X X ∧ X ⇔ X
Asociacinė teisė: Jei yra trys teiginių formulės, ji turės šias savybes:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutacinė teisė: Jei yra dvi teiginių formulės, ji turės šias savybes:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Paskirstymo įstatymas: Jei yra trys teiginių formulės, ji turės šias savybes:
java len of masyvo
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Tapatybės įstatymas: Jei yra viena teiginio formulė, ji turės šias savybes:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Papildyti įstatymą: Jei yra viena teiginio formulė, ji turės šias savybes:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorbcijos įstatymas: Jei yra dvi teiginių formulės, ji turės šias savybes:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Iš Morgano įstatymo: Jei yra dvi teiginių formulės, ji turės šias savybes:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
2 būdas: pakeitimo procesas
Šiuo metodu priimsime formulę A : X → (Y → Z). Formulė Y → Z gali būti žinoma kaip formulės dalis. Jei šią formulės dalį, t.y., Y → Z, pakeisime lygiavertiškumo formule ¬Y ∨ Z A, tai gausime kitą formulę, ty B : X → (¬Y ∨ Z). Patikrinti, ar pateiktos formulės A ir B yra lygiavertės viena kitai, yra paprastas procesas. Pakeitimo proceso pagalba galime gauti B iš A.
1 pavyzdys: Šiame pavyzdyje turime įrodyti, kad {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Sprendimas: Čia mes paimsime kairę šoninę dalį ir bandysime gauti dešinę.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Dabar mes naudosime asociacinį įstatymą taip:
⇔ (¬X ∨ ¬Y) ∨ Z
Dabar naudosime De Morgano dėsnį taip:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Taigi įrodyta
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z 2 pavyzdys: Šiame pavyzdyje turime įrodyti, kad {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Sprendimas: Čia mes paimsime kairę šoninę dalį ir bandysime gauti dešinę.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Taigi įrodyta
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
3 pavyzdys: Šiame pavyzdyje turime įrodyti, kad X → (Y → X) ⇔ ¬X → (X → Y).
Sprendimas: Čia mes paimsime kairę šoninę dalį ir bandysime gauti dešinę.
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
Taigi įrodyta
X → (Y → X) ⇔ ¬X → (X → Y)
4 pavyzdys: Šiame pavyzdyje turime įrodyti, kad (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Sprendimas: Čia mes paimsime kairę šoninę dalį ir bandysime gauti dešinę.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Dabar naudosime tokius asociatyvinius ir paskirstymo įstatymus:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Dabar naudosime De Morgano dėsnį taip:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Dabar mes naudosime paskirstymo įstatymą taip:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Taigi įrodyta
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
5 pavyzdys: Šiame pavyzdyje turime parodyti, kad ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) yra tautologija.
Sprendimas: Čia mes paimsime mažas dalis ir jas išspręsime.
Pirmiausia naudosime De Morgano dėsnį ir gausime:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Todėl,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Taip pat
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Vadinasi
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Taigi
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Taigi galime sakyti, kad pateikta formulė yra tautologija.
6 pavyzdys: Šiame pavyzdyje turime parodyti, kad (X ∧ Y) → (X ∨ Y) yra tautologija.
Sprendimas: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Dabar naudosime De Morgano dėsnį taip:
pašalinimas iš masyvo sąrašo
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Dabar mes naudosime asociatyvųjį ir komutacinį įstatymą taip:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Dabar mes naudosime neigimo įstatymą taip:
⇔ (T ∨ T) ⇔ T
Taigi galime sakyti, kad pateikta formulė yra tautologija.
7 pavyzdys: Šiame pavyzdyje turime parašyti kai kurių teiginių, kurie aprašomi taip, neigimą:
- Marry baigs mokslus arba priims XYZ Company prisijungimo laišką.
- Haris rytoj eis pasivažinėti ar bėgti.
- Jei gausiu gerus pažymius, pusbrolis pavydės.
Sprendimas: Pirmiausia išspręsime pirmąjį teiginį taip:
1. Tarkime, X: Marry baigs mokslus.
Y: Priimkite XYZ bendrovės prisijungimo laišką.
Šiam teiginiui išreikšti galime naudoti šią simbolinę formą:
X ∨ Y
X ∨ Y neigimas apibūdinamas taip:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Apibendrinant, pateikto teiginio neigimas bus toks:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Tarkime X: Haris eis pasivažinėti
Y: Haris rytoj bėgs
Šiam teiginiui išreikšti galime naudoti šią simbolinę formą:
X ∨ Y
X ∨ Y neigimas apibūdinamas taip:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Apibendrinant, pateikto teiginio neigimas bus toks:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Tarkime, X: jei gaunu gerus balus.
Y: Mano pusbrolis bus pavydus.
Šiam teiginiui išreikšti galime naudoti šią simbolinę formą:
X → Y
X → Y neigimas apibūdinamas taip:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Apibendrinant, pateikto teiginio neigimas bus toks:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
8 pavyzdys: Šiame pavyzdyje mes turime parašyti kai kurių teiginių neigimą naudodami De Morgano dėsnį. Šie teiginiai apibūdinami taip:
- Man reikia deimantų rinkinio ir vertas auksinio žiedo.
- Gauni gerą darbą arba negausi gero partnerio.
- Dirbu daug ir negaliu su juo susitvarkyti.
- Mano šuo išvyksta į kelionę arba namuose daro netvarką.
Sprendimas: Visų teiginių neigimas De Morgano dėsnio pagalba aprašomas po vieną taip:
- Man nereikia deimantų rinkinio ar neverto auksinio žiedo.
- Negalite gauti gero darbo ir gausite gerą partnerį.
- Nepriimu daug darbo arba galiu susitvarkyti.
- Mano šuo nevažiuoja į kelionę ir nedaro netvarkos namuose.
9 pavyzdys: Šiame pavyzdyje turime keletą teiginių ir turime parašyti tų teiginių neigimą. Teiginiai aprašomi taip:
- Jei lyja, planas vykti į paplūdimį atšaukiamas.
- Jei sunkiai mokysiuos, tai iš egzamino gausiu gerus balus.
- Jei eisiu į vakarėlį vėlyvą vakarą, mane nubaus tėvas.
- Jei nenorite su manimi kalbėtis, turite užblokuoti mano numerį.
Sprendimas: Visų teiginių neigimas aprašomas po vieną taip:
- Jei planas vykti į paplūdimį atšaukiamas, vadinasi, lyja.
- Jei iš egzamino gaunu gerus balus, tada sunkiai mokausi.
- Jei mane nubaus tėvas, einu į vėlyvą vakarėlį.
- Jei turite užblokuoti mano numerį, tada nenorite su manimi kalbėtis.
10 pavyzdys: Šiame pavyzdyje turime patikrinti, ar (X → Y) → Z ir X → (Y → Z) yra logiškai lygiaverčiai, ar ne. Turime pagrįsti savo atsakymą tiesos lentelėmis ir logikos taisyklėmis, kad supaprastintume abi išraiškas.
Sprendimas: Pirmiausia naudosime 1 metodą, kad patikrintume, ar (X → Y) → Z ir X → (Y → Z) yra logiškai lygiaverčiai, o tai aprašoma taip:
kūrėjo režimo išjungimas
1 būdas: Čia darysime prielaidą, kad:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Ir
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
2 būdas: Dabar naudosime antrąjį metodą. Šiuo metodu naudosime tiesos lentelę.
| X | IR | SU | 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 |
Šioje tiesos lentelėje matome, kad (X → Y) → Z ir X → (Y → Z) stulpeliuose nėra identiškų reikšmių.