Recimo, da obstajata dve formuli, X in Y. Ti formuli bosta znani kot ekvivalenca, če je X ↔ Y tavtologija. Če sta dve formuli X ↔ Y tavtologija, potem jo lahko zapišemo tudi kot X ⇔ Y, to razmerje pa lahko beremo kot X enakovrednost Y.
Opomba: Pri linearni enakovrednosti formule moramo upoštevati nekaj točk, ki so opisane takole:
- ⇔ se uporablja le za označevanje simbola, ni pa povezovalni.
- Resnična vrednost X in Y bo vedno enaka, če je X ↔ Y tavtologija.
- Ekvivalenčna relacija vsebuje dve lastnosti, in sicer simetrično in tranzitivno.
1. metoda: Metoda tabele resnic:
Pri tej metodi bomo izdelali tabele resnic katere koli formule z dvema stavkoma in nato preverili, ali sta ti stavki enakovredni.
Primer 1: V tem primeru moramo dokazati X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
rešitev: Resnična tabela X ∨ Y ⇔ ¬(¬X ∧ ¬Y) je opisana takole:
| X | IN | X ∨ Y | ¬X | ¬In | ¬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 |
Kot lahko vidimo, je X ∨ Y in ¬(¬X ∧ ¬Y) tavtologija. Zato X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Primer 2: V tem primeru moramo dokazati (X → Y) ⇔ (¬X ∨ Y).
rešitev: Resnična tabela (X → Y) ⇔ (¬X ∨ Y) je opisana takole:
| X | IN | 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 |
Kot lahko vidimo, sta X → Y in (¬X ∨ Y) tavtologija. Zato (X → Y) ⇔ (¬X ∨ Y)
Formula enakovrednosti:
Obstajajo različni zakoni, ki se uporabljajo za dokazovanje enakovredne formule, ki je opisana na naslednji način:
Idempotentni zakon: Če obstaja ena formula izjave, bo imela naslednje lastnosti:
X ∨ X ⇔ X X ∧ X ⇔ X
Asociativni zakon: Če obstajajo tri formule stavkov, bo imela naslednje lastnosti:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutativni zakon: Če obstajata dve formuli izjave, bo imela naslednje lastnosti:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Distributivni zakon: Če obstajajo tri formule stavkov, bo imela naslednje lastnosti:
ukaz grep v linuxu
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Zakon o identiteti: Če obstaja ena formula izjave, bo imela naslednje lastnosti:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Zakon o dopolnitvi: Če obstaja ena formula izjave, bo imela naslednje lastnosti:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorpcijski zakon: Če obstajata dve formuli izjave, bo imela naslednje lastnosti:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Iz Morganovega zakona: Če obstajata dve formuli izjave, bo imela naslednje lastnosti:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
2. način: Postopek zamenjave
Pri tej metodi bomo predpostavili formulo A : X → (Y → Z). Formulo Y → Z lahko poznamo kot del formule. Če zamenjamo ta del formule, tj. Y → Z, s pomočjo ekvivalenčne formule ¬Y ∨ Z v A, potem dobimo drugo formulo, to je B : X → (¬Y ∨ Z). Preverjanje, ali sta dani formuli A in B enakovredni ali ne, je enostaven postopek. S pomočjo postopka zamenjave lahko dobimo B iz A.
Primer 1: V tem primeru moramo dokazati, da {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
rešitev: Tukaj bomo vzeli levi stranski del in poskušali dobiti desni stranski del.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Zdaj bomo uporabili asociativni zakon takole:
⇔ (¬X ∨ ¬Y) ∨ Z
Zdaj bomo uporabili De Morganov zakon takole:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Zato dokazano
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Primer 2: V tem primeru moramo dokazati, da je {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
rešitev: Tukaj bomo vzeli levi stranski del in poskušali dobiti desni stranski del.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Zato dokazano
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Primer 3: V tem primeru moramo dokazati, da je X → (Y → X) ⇔ ¬X → (X → Y).
rešitev: Tukaj bomo vzeli levi stranski del in poskušali dobiti desni stranski del.
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
Zato dokazano
X → (Y → X) ⇔ ¬X → (X → Y)
Primer 4: V tem primeru moramo dokazati, da (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
rešitev: Tukaj bomo vzeli levi stranski del in poskušali dobiti desni stranski del.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Zdaj bomo uporabili asociativne in distribucijske zakone takole:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Zdaj bomo uporabili De Morganov zakon takole:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Zdaj bomo uporabili distribucijski zakon takole:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Zato dokazano
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Primer 5: V tem primeru moramo pokazati, da je ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) tavtologija.
rešitev: Tukaj bomo vzeli majhne dele in jih rešili.
Najprej bomo uporabili De Morganov zakon in dobili naslednje:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
zato
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
tudi
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Zato
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
torej
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Zato lahko rečemo, da je navedena formula tavtologija.
Primer 6: V tem primeru moramo pokazati, da je (X ∧ Y) → (X ∨ Y) tavtologija.
združitve in vrste združitev
rešitev: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Zdaj bomo uporabili De Morganov zakon takole:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Zdaj bomo uporabili asociativni zakon in komutativni zakon takole:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Zdaj bomo uporabili Negacijski zakon takole:
⇔ (T ∨ T) ⇔ T
Zato lahko rečemo, da je navedena formula tavtologija.
Primer 7: V tem primeru moramo zapisati zanikanje nekaterih izjav, ki so opisane takole:
- Marry bo dokončala izobraževanje ali sprejela pristopno pismo podjetja XYZ.
- Harry bo šel jutri na jahanje ali tek.
- Če dobim dobre ocene, bo moj bratranec ljubosumen.
rešitev: Najprej bomo prvo izjavo rešili takole:
1. Recimo, da bo X: Marry dokončala svoje izobraževanje.
Y: Sprejmite pristopno pismo podjetja XYZ.
Za izražanje te izjave lahko uporabimo naslednjo simbolično obliko:
X ∨ Y
Negacija X ∨ Y je opisana takole:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na koncu bo negacija dane izjave:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Recimo X: Harry se bo šel peljati
Y: Harry bo tekel jutri
Za izražanje te izjave lahko uporabimo naslednjo simbolično obliko:
X ∨ Y
Negacija X ∨ Y je opisana takole:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Na koncu bo negacija dane izjave:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Recimo X: Če dobim dobre ocene.
Y: Moj bratranec bo ljubosumen.
Za izražanje te izjave lahko uporabimo naslednjo simbolično obliko:
X → Y
Negacija X → Y je opisana takole:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Na koncu bo negacija dane izjave:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Primer 8: V tem primeru moramo zapisati negacijo nekaterih trditev s pomočjo De Morganovega zakona. Te izjave so opisane na naslednji način:
- Potrebujem diamantni komplet in vreden zlatega prstana.
- Dobiš dobro službo ali pa ne boš dobil dobrega partnerja.
- Prevzamem veliko dela in tega ne zmorem.
- Moj pes gre na potovanje ali pa dela nered v hiši.
rešitev: Negacijo vseh trditev s pomočjo De Morganovega zakona eno za drugo opišemo takole:
- Ne potrebujem diamantnega kompleta ali nisem vreden zlatega prstana.
- Ne morete dobiti dobre službe, dobrega partnerja pa boste.
- Ne prevzemam veliko dela oziroma ga zmorem.
- Moj pes ne gre na izlet in ne dela nereda v hiši.
Primer 9: V tem primeru imamo nekaj izjav in zapisati moramo zanikanje teh izjav. Izjave so opisane na naslednji način:
- Če dežuje, potem načrt za odhod na plažo odpade.
- Če se pridno učim, bom na izpitu dobil dobre ocene.
- Če grem na nočno zabavo, me bo oče kaznoval.
- Če ne želiš govoriti z mano, potem moraš blokirati mojo številko.
rešitev: Negacija vseh izjav je ena za drugo opisana takole:
- Če je načrt za odhod na plažo odpovedan, potem dežuje.
- Če dobim na izpitu dobre ocene, se pridno učim.
- Če bom dobil kazen od očeta, grem na nočno zabavo.
- Če moraš blokirati mojo številko, potem ne želiš govoriti z mano.
Primer 10: V tem primeru moramo preveriti, ali sta (X → Y) → Z in X → (Y → Z) logično enakovredna ali ne. Svoj odgovor moramo utemeljiti s pomočjo tabel resnic in s pomočjo logičnih pravil, da poenostavimo oba izraza.
rešitev: Najprej bomo uporabili metodo 1, da preverimo, ali sta (X → Y) → Z in X → (Y → Z) logično enakovredna, kar je opisano takole:
poveži bazo podatkov java
1. način: Tukaj bomo predpostavili naslednje:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
in
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
2. način: Zdaj bomo uporabili drugo metodo. Pri tej metodi bomo uporabili tabelo resnic.
| X | IN | Z | 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 |
V tej tabeli resnic lahko vidimo, da stolpca (X → Y) → Z in X → (Y → Z) ne vsebujeta enakih vrednosti.