Pretpostavimo da postoje dvije formule, X i Y. Ove formule će biti poznate kao ekvivalencija ako je X ↔ Y tautologija. Ako su dvije formule X ↔ Y tautologija, onda je također možemo napisati kao X ⇔ Y, a ovu relaciju možemo čitati kao da je X ekvivalent Y.
Napomena: Postoje neke točke koje bismo trebali imati na umu tijekom linearne ekvivalencije formule, a koje su opisane kako slijedi:
- ⇔ koristi se samo za označavanje simbola, ali nije vezivno.
- Istinosna vrijednost X i Y uvijek će biti jednaka ako je X ↔ Y tautologija.
- Relacija ekvivalencije sadrži dva svojstva, simetričnost i tranzitivnost.
Metoda 1: Metoda tablice istinitosti:
U ovoj metodi ćemo konstruirati tablice istinitosti bilo koje formule s dvije tvrdnje i zatim provjeriti jesu li te tvrdnje ekvivalentne.
Primjer 1: U ovom primjeru moramo dokazati X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Riješenje: Tablica istinitosti X ∨ Y ⇔ ¬(¬X ∧ ¬Y) opisana je na sljedeći način:
| x | I | X ∨ Y | ¬X | ¬I | ¬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 |
Kao što vidimo da je X ∨ Y i ¬(¬X ∧ ¬Y) tautologija. Dakle X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Primjer 2: U ovom primjeru moramo dokazati (X → Y) ⇔ (¬X ∨ Y).
Riješenje: Tablica istinitosti (X → Y) ⇔ (¬X ∨ Y) opisana je na sljedeći način:
| x | I | 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 |
Kao što vidimo da su X → Y i (¬X ∨ Y) tautologija. Dakle (X → Y) ⇔ (¬X ∨ Y)
Formula ekvivalencije:
Postoje različiti zakoni koji se koriste za dokazivanje formule ekvivalencije, koja je opisana na sljedeći način:
Idempotentni zakon: Ako postoji jedna formula izjave, ona će imati sljedeća svojstva:
X ∨ X ⇔ X X ∧ X ⇔ X
Asocijativni zakon: Ako postoje tri formule iskaza, tada će imati sljedeća svojstva:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutativni zakon: Ako postoje dvije formule iskaza, tada će imati sljedeća svojstva:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Distributivni zakon: Ako postoje tri formule iskaza, tada će imati sljedeća svojstva:
Glumica Rakul Preet Singh
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Zakon o identitetu: Ako postoji jedna formula izjave, ona će imati sljedeća svojstva:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Zakon komplementa: Ako postoji jedna formula izjave, ona će imati sljedeća svojstva:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Zakon apsorpcije: Ako postoje dvije formule iskaza, tada će imati sljedeća svojstva:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Iz Morganova zakona: Ako postoje dvije formule iskaza, tada će imati sljedeća svojstva:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Metoda 2: Proces zamjene
U ovoj metodi pretpostavit ćemo formulu A : X → (Y → Z). Formula Y → Z može biti poznata kao dio formule. Ako ovaj dio formule, tj. Y → Z, zamijenimo pomoću formule ekvivalencije ¬Y ∨ Z u A, tada ćemo dobiti drugu formulu, tj. B : X → (¬Y ∨ Z). Jednostavan je postupak za provjeru jesu li dane formule A i B međusobno ekvivalentne ili ne. Uz pomoć procesa zamjene, možemo dobiti B od A.
Primjer 1: U ovom primjeru, moramo dokazati da je {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Riješenje: Ovdje ćemo uzeti lijevi dio i pokušati dobiti desni dio.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Sada ćemo koristiti asocijativni zakon ovako:
⇔ (¬X ∨ ¬Y) ∨ Z
Sada ćemo koristiti De Morganov zakon ovako:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Stoga dokazano
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Primjer 2: U ovom primjeru moramo dokazati da je {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Riješenje: Ovdje ćemo uzeti lijevi dio i pokušati dobiti desni dio.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Stoga dokazano
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Primjer 3: U ovom primjeru moramo dokazati da je X → (Y → X) ⇔ ¬X → (X → Y).
Riješenje: Ovdje ćemo uzeti lijevi dio i pokušati dobiti desni dio.
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
Stoga dokazano
X → (Y → X) ⇔ ¬X → (X → Y)
Primjer 4: U ovom primjeru moramo dokazati da je (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Riješenje: Ovdje ćemo uzeti lijevi dio i pokušati dobiti desni dio.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Sada ćemo koristiti asocijativne i distributivne zakone ovako:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Sada ćemo koristiti De Morganov zakon ovako:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Sada ćemo koristiti zakon distribucije ovako:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Stoga dokazano
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Primjer 5: U ovom primjeru moramo pokazati da je ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) tautologija.
Riješenje: Ovdje ćemo uzeti male dijelove i riješiti ih.
Prvo ćemo koristiti De Morganov zakon i dobiti sljedeće:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Stoga,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Također
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Stoga
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Tako
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Stoga možemo reći da je navedena formula tautologija.
Primjer 6: U ovom primjeru moramo pokazati da je (X ∧ Y) → (X ∨ Y) tautologija.
uvozni mrav
Riješenje: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Sada ćemo koristiti De Morganov zakon ovako:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Sada ćemo koristiti asocijativni zakon i komutativni zakon ovako:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Sada ćemo koristiti zakon negacije ovako:
⇔ (T ∨ T) ⇔ T
Stoga možemo reći da je navedena formula tautologija.
Primjer 7: U ovom primjeru moramo napisati negaciju nekih izjava koje su opisane na sljedeći način:
- Marry će završiti svoje obrazovanje ili prihvatiti pristupno pismo XYZ Company.
- Harry će sutra otići na vožnju ili trčanje.
- Ako dobijem dobre ocjene, moj rođak će biti ljubomoran.
Riješenje: Prvo ćemo riješiti prvu izjavu ovako:
1. Pretpostavimo da će X: Marry završiti svoje obrazovanje.
Y: Prihvatite pristupno pismo tvrtke XYZ.
Možemo koristiti sljedeći simbolički oblik da izrazimo ovu izjavu:
X ∨ Y
Negacija X ∨ Y opisana je na sljedeći način:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Zaključno, negacija date tvrdnje će biti:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Pretpostavimo X: Harry će se provozati
Y: Harry će trčati sutra
Možemo koristiti sljedeći simbolički oblik da izrazimo ovu izjavu:
X ∨ Y
Negacija X ∨ Y opisana je na sljedeći način:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Zaključno, negacija date tvrdnje će biti:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Pretpostavimo X: Ako dobijem dobre ocjene.
Y: Moj rođak će biti ljubomoran.
Možemo koristiti sljedeći simbolički oblik da izrazimo ovu izjavu:
X → Y
Negacija X → Y opisana je na sljedeći način:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Zaključno, negacija date tvrdnje će biti:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Primjer 8: U ovom primjeru moramo napisati negaciju nekih iskaza uz pomoć De Morganovog zakona. Ove izjave su opisane kako slijedi:
- Trebam dijamantni set i vrijedan zlatnog prstena.
- Dobiješ dobar posao ili nećeš dobiti dobrog partnera.
- Prihvaćam puno posla i ne mogu to podnijeti.
- Moj pas ide na put ili pravi nered u kući.
Riješenje: Negacija svih izjava uz pomoć De Morganovog zakona opisuje se jednu po jednu ovako:
- Ne treba mi dijamantni set ili nije vrijedan zlatnog prstena.
- Ne možete dobiti dobar posao, a dobit ćete dobrog partnera.
- Ne preuzimam puno posla ili mogu to podnijeti.
- Moj pas ne ide na put i ne pravi nered u kući.
Primjer 9: U ovom primjeru imamo neke izjave i moramo napisati negaciju tih izjava. Izjave su opisane na sljedeći način:
- Ako pada kiša, plan za odlazak na plažu se otkazuje.
- Ako marljivo učim, dobit ću dobre ocjene na ispitu.
- Ako odem na noćnu zabavu, onda ću dobiti kaznu od svog oca.
- Ako ne želiš razgovarati sa mnom, moraš blokirati moj broj.
Riješenje: Negacija svih izjava je opisana jedna po jedna ovako:
- Ako je plan za odlazak na plažu otkazan, onda pada kiša.
- Ako dobijem dobre ocjene na ispitu, marljivo učim.
- Ako ću dobiti kaznu od oca, onda idem na kasnu zabavu.
- Ako moraš blokirati moj broj, onda ne želiš razgovarati sa mnom.
Primjer 10: U ovom primjeru moramo provjeriti jesu li (X → Y) → Z i X → (Y → Z) logički ekvivalentni ili ne. Moramo opravdati svoj odgovor uz pomoć tablica istinitosti i uz pomoć logičkih pravila da bismo pojednostavili oba izraza.
Riješenje: Prvo ćemo koristiti metodu 1 da provjerimo jesu li (X → Y) → Z i X → (Y → Z) logički ekvivalentni, što je opisano na sljedeći način:
kako spojiti nizove u Javi
Metoda 1: Ovdje ćemo pretpostaviti sljedeće:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
I
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Metoda 2: Sada ćemo koristiti drugu metodu. U ovoj metodi koristit ćemo tablicu istinitosti.
| x | I | S | 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 |
U ovoj tablici istine možemo vidjeti da stupci (X → Y) → Z i X → (Y → Z) ne sadrže identične vrijednosti.