Pieņemsim, ka ir divas formulas, X un Y. Šīs formulas būs pazīstamas kā ekvivalence, ja X ↔ Y ir tautoloģija. Ja divas formulas X ↔ Y ir tautoloģija, tad mēs to varam rakstīt arī kā X ⇔ Y, un mēs varam nolasīt šo sakarību kā X ir līdzvērtīga Y.
Piezīme: Lineārās formulas ekvivalences laikā mums jāpatur prātā daži punkti, kas aprakstīti šādi:
- ⇔ tiek izmantots, lai norādītu tikai simbolu, bet tas nav savienojošs.
- X un Y patiesības vērtība vienmēr būs vienāda, ja X ↔ Y ir tautoloģija.
- Ekvivalences attiecība satur divas īpašības, t.i., simetrisko un pārejošo.
1. metode: patiesības tabulas metode:
Izmantojot šo metodi, mēs izveidosim jebkuras divu apgalvojumu formulas patiesuma tabulas un pēc tam pārbaudīsim, vai šie apgalvojumi ir līdzvērtīgi.
1. piemērs: Šajā piemērā mums ir jāpierāda X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Risinājums: X ∨ Y ⇔ ¬(¬X ∧ ¬Y) patiesības tabula ir aprakstīta šādi:
| X | UN | X ∨ Y | ¬X | ¬ Un | ¬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 |
Kā redzams, X ∨ Y un ¬(¬X ∧ ¬Y) ir tautoloģija. Tādējādi X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
2. piemērs: Šajā piemērā mums ir jāpierāda (X → Y) ⇔ (¬X ∨ Y).
Risinājums: (X → Y) ⇔ (¬X ∨ Y) patiesības tabula ir aprakstīta šādi:
| X | UN | 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 |
Kā redzams, X → Y un (¬X ∨ Y) ir tautoloģija. Tādējādi (X → Y) ⇔ (¬X ∨ Y)
Ekvivalences formula:
Ir dažādi likumi, kas tiek izmantoti, lai pierādītu ekvivalences formulu, kas aprakstīta šādi:
Idempotents likums: Ja ir viena formulējuma formula, tai būs šādas īpašības:
X ∨ X ⇔ X X ∧ X ⇔ X
Asociatīvās tiesības: Ja ir trīs priekšrakstu formulas, tai būs šādas īpašības:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Komutatīvais likums: Ja ir divas priekšrakstu formulas, tai būs šādas īpašības:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Izplatīšanas likums: Ja ir trīs priekšrakstu formulas, tai būs šādas īpašības:
datumu atšķirība programmā Excel
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identitātes likums: Ja ir viena formulējuma formula, tai būs šādas īpašības:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Papildināt likumu: Ja ir viena formulējuma formula, tai būs šādas īpašības:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorbcijas likums: Ja ir divas priekšrakstu formulas, tai būs šādas īpašības:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
No Morgana likuma: Ja ir divas priekšrakstu formulas, tai būs šādas īpašības:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
2. metode: aizstāšanas process
Šajā metodē mēs pieņemsim formulu A : X → (Y → Z). Formulu Y → Z var saukt par formulas daļu. Ja šo formulas daļu, t.i., Y → Z, aizstāsim ar ekvivalences formulas ¬Y ∨ Z palīdzību A, tad iegūsim citu formulu, t.i., B : X → (¬Y ∨ Z). Tas ir vienkāršs process, lai pārbaudītu, vai dotās formulas A un B ir viena otrai līdzvērtīgas. Ar aizstāšanas procesa palīdzību mēs varam iegūt B no A.
1. piemērs: Šajā piemērā mums jāpierāda, ka {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Risinājums: Šeit mēs paņemsim kreiso sānu daļu un mēģināsim iegūt labo sānu daļu.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Tagad mēs izmantosim asociatīvo likumu šādi:
⇔ (¬X ∨ ¬Y) ∨ Z
Tagad mēs izmantosim De Morgana likumu šādi:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Līdz ar to pierādīts
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z 2. piemērs: Šajā piemērā mums jāpierāda, ka {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Risinājums: Šeit mēs paņemsim kreiso sānu daļu un mēģināsim iegūt labo sānu daļu.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Līdz ar to pierādīts
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
3. piemērs: Šajā piemērā mums jāpierāda, ka X → (Y → X) ⇔ ¬X → (X → Y).
Risinājums: Šeit mēs paņemsim kreiso sānu daļu un mēģināsim iegūt labo sānu daļu.
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
Līdz ar to pierādīts
X → (Y → X) ⇔ ¬X → (X → Y)
4. piemērs: Šajā piemērā mums jāpierāda, ka (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Risinājums: Šeit mēs paņemsim kreiso sānu daļu un mēģināsim iegūt labo sānu daļu.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Tagad mēs izmantosim asociatīvos un sadales likumus, piemēram:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Tagad mēs izmantosim De Morgana likumu šādi:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Tagad mēs izmantosim sadales likumu šādi:
alfabēts pēc cipariem
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Līdz ar to pierādīts
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
5. piemērs: Šajā piemērā mums jāparāda, ka ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ir tautoloģija.
Risinājums: Šeit mēs paņemsim mazas daļas un atrisināsim tās.
Pirmkārt, mēs izmantosim De Morgana likumu un iegūsim sekojošo:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Tāpēc
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Arī
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Līdz ar to
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Tādējādi
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Tādējādi mēs varam teikt, ka dotā formula ir tautoloģija.
6. piemērs: Šajā piemērā mums jāparāda, ka (X ∧ Y) → (X ∨ Y) ir tautoloģija.
Risinājums: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Tagad mēs izmantosim De Morgana likumu šādi:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Tagad mēs izmantosim asociatīvo likumu un komutatīvo likumu šādi:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Tagad mēs izmantosim negācijas likumu šādi:
⇔ (T ∨ T) ⇔ T
Tādējādi mēs varam teikt, ka dotā formula ir tautoloģija.
7. piemērs: Šajā piemērā mums ir jāraksta dažu apgalvojumu noliegums, kas aprakstīti šādi:
- Marry pabeigs izglītību vai pieņems XYZ Company pievienošanās vēstuli.
- Harijs rīt dosies pavizināties vai skriet.
- Ja saņemšu labas atzīmes, mans brālēns būs greizsirdīgs.
Risinājums: Pirmkārt, mēs atrisināsim pirmo apgalvojumu šādi:
1. Pieņemsim, ka X: Marry pabeigs izglītību.
Y: Pieņemiet XYZ Company pievienošanās vēstuli.
Lai izteiktu šo apgalvojumu, mēs varam izmantot šādu simbolisku formu:
X ∨ Y
X ∨ Y noliegums ir aprakstīts šādi:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Noslēgumā dotā apgalvojuma noliegums būs:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Pieņemsim, ka X: Harijs dosies vizināties
J: Harijs rīt skries
Lai izteiktu šo apgalvojumu, mēs varam izmantot šādu simbolisku formu:
X ∨ Y
X ∨ Y noliegums ir aprakstīts šādi:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Noslēgumā dotā apgalvojuma noliegums būs:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Pieņemsim, ka X: Ja es saņemu labas atzīmes.
J: Mans brālēns būs greizsirdīgs.
Lai izteiktu šo apgalvojumu, mēs varam izmantot šādu simbolisku formu:
X → Y
X → Y noliegums ir aprakstīts šādi:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Noslēgumā dotā apgalvojuma noliegums būs:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
8. piemērs: Šajā piemērā mums ir jāraksta dažu apgalvojumu noliegums ar De Morgana likuma palīdzību. Šie paziņojumi ir aprakstīti šādi:
- Man vajag dimantu komplektu un zelta gredzena vērtībā.
- Jūs iegūsit labu darbu vai arī neiegūsit labu partneri.
- Es daru daudz darba un nevaru ar to tikt galā.
- Mans suns dodas ceļojumā, vai arī tas mājā rada nekārtību.
Risinājums: Visu apgalvojumu noliegums ar De Morgana likuma palīdzību tiek aprakstīts pa vienam šādi:
- Man nav vajadzīgs dimanta komplekts vai tas nav zelta gredzena vērts.
- Jūs nevarat iegūt labu darbu, un jūs iegūsit labu partneri.
- Es neņemu daudz darba vai varu tikt galā.
- Mans suns nedodas ceļojumā, un tas nerada nekārtību mājā.
9. piemērs: Šajā piemērā mums ir daži apgalvojumi, un mums ir jāraksta šo apgalvojumu noliegums. Paziņojumi ir aprakstīti šādi:
- Ja līst, tad plāns doties uz pludmali tiek atcelts.
- Ja cītīgi mācos, tad eksāmenā dabūšu labas atzīmes.
- Ja es iešu uz vakara ballīti, tad saņemšu sodu no tēva.
- Ja nevēlies ar mani runāt, tad tev ir jābloķē mans numurs.
Risinājums: Visu apgalvojumu noliegums pa vienam ir aprakstīts šādi:
- Ja plāns doties uz pludmali tiek atcelts, tad līst.
- Ja eksāmenā saņemu labas atzīmes, tad cītīgi mācos.
- Ja es saņemšu sodu no tēva, tad es eju uz vēlu vakaru.
- Ja jums ir jābloķē mans numurs, tad jūs nevēlaties ar mani runāt.
10. piemērs: Šajā piemērā mums ir jāpārbauda, vai (X → Y) → Z un X → (Y → Z) ir vai nav loģiski ekvivalenti. Mums ir jāpamato sava atbilde ar patiesības tabulu palīdzību un ar loģikas noteikumu palīdzību, lai vienkāršotu abus izteicienus.
Risinājums: Pirmkārt, mēs izmantosim 1. metodi, lai pārbaudītu, vai (X → Y) → Z un X → (Y → Z) ir loģiski līdzvērtīgi, kas aprakstīts šādi:
pilna forma
1. metode: Šeit mēs pieņemsim sekojošo:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Un
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
2. metode: Tagad mēs izmantosim otro metodi. Šajā metodē mēs izmantosim patiesības tabulu.
| X | UN | AR | 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 |
Šajā patiesumu tabulā redzams, ka (X → Y) → Z un X → (Y → Z) kolonnas nesatur identiskas vērtības.