Oletetaan, että on kaksi kaavaa, X ja Y. Nämä kaavat tunnetaan ekvivalenssina, jos X ↔ Y on tautologia. Jos kaksi kaavaa X ↔ Y on tautologia, voimme kirjoittaa sen myös muodossa X ⇔ Y, ja voimme lukea tämän suhteen, koska X on ekvivalenssi Y:n kanssa.
Huomautus: On joitain kohtia, jotka meidän tulee pitää mielessä kaavan lineaarista vastaavuutta käytettäessä, jotka kuvataan seuraavasti:
- ⇔ tarkoittaa vain symbolia, mutta se ei ole yhdistävä.
- X:n ja Y:n totuusarvo on aina yhtä suuri, jos X ↔ Y on tautologia.
- Ekvivalenssirelaatio sisältää kaksi ominaisuutta, eli symmetrisen ja transitiivisen.
Menetelmä 1: Totuustaulukkomenetelmä:
Tässä menetelmässä rakennamme minkä tahansa kahden lauseen kaavan totuustaulukot ja tarkistamme sitten, ovatko nämä lauseet ekvivalentteja.
Esimerkki 1: Tässä esimerkissä meidän on todistettava X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Ratkaisu: X ∨ Y ⇔ ¬(¬X ∧ ¬Y) totuustaulukko kuvataan seuraavasti:
| X | JA | X ∨ Y | ¬X | ¬Ja | ¬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 |
Kuten voimme nähdä, että X ∨ Y ja ¬(¬X ∧ ¬Y) on tautologia. Tästä syystä X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Esimerkki 2: Tässä esimerkissä meidän on todistettava (X → Y) ⇔ (¬X ∨ Y).
Ratkaisu: (X → Y) ⇔ (¬X ∨ Y) totuustaulukko kuvataan seuraavasti:
| X | JA | 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 |
Kuten näemme, X → Y ja (¬X ∨ Y) ovat tautologia. Tästä syystä (X → Y) ⇔ (¬X ∨ Y)
Vastaavuuskaava:
On olemassa useita lakeja, joita käytetään todistamaan vastaavuuskaava, joka kuvataan seuraavasti:
Idempotentti laki: Jos lausekkeessa on yksi kaava, sillä on seuraavat ominaisuudet:
X ∨ X ⇔ X X ∧ X ⇔ X
Assosiaatiolaki: Jos lausekaavoja on kolme, sillä on seuraavat ominaisuudet:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Kommutatiivinen laki: Jos lausekaavoja on kaksi, sillä on seuraavat ominaisuudet:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Jakelulaki: Jos lausekaavoja on kolme, sillä on seuraavat ominaisuudet:
foreach silmukan konekirjoitus
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Identiteettilaki: Jos lausekkeessa on yksi kaava, sillä on seuraavat ominaisuudet:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Täydennä lakia: Jos lausekkeessa on yksi kaava, sillä on seuraavat ominaisuudet:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Absorptiolaki: Jos lausekaavoja on kaksi, sillä on seuraavat ominaisuudet:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Morganin laista: Jos lausekaavoja on kaksi, sillä on seuraavat ominaisuudet:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Tapa 2: Korvausprosessi
Tässä menetelmässä oletetaan kaava A : X → (Y → Z). Kaava Y → Z voidaan tuntea kaavan osana. Jos korvaamme tämän kaavan osan, eli Y → Z, ekvivalenssikaavan ¬Y ∨ Z avulla A:ssa, saamme toisen kaavan, eli B : X → (¬Y ∨ Z). On helppo prosessi varmistaa, vastaavatko annetut kaavat A ja B toisiaan vai eivät. Korvausprosessin avulla voimme saada B:stä A.
Esimerkki 1: Tässä esimerkissä meidän on todistettava, että {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Ratkaisu: Tässä otamme vasemman puolen osan ja yritämme saada oikean puolen.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Nyt käytämme assosiaatiolakia näin:
⇔ (¬X ∨ ¬Y) ∨ Z
Nyt käytämme De Morganin lakia seuraavasti:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Siksi todistettu
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Esimerkki 2: Tässä esimerkissä meidän on todistettava, että {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Ratkaisu: Tässä otamme vasemman puolen osan ja yritämme saada oikean puolen.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Siksi todistettu
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Esimerkki 3: Tässä esimerkissä meidän on todistettava, että X → (Y → X) ⇔ ¬X → (X → Y).
Ratkaisu: Tässä otamme vasemman puolen osan ja yritämme saada oikean puolen.
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
Siksi todistettu
rakentajat javassa
X → (Y → X) ⇔ ¬X → (X → Y)
Esimerkki 4: Tässä esimerkissä meidän on todistettava, että (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Ratkaisu: Tässä otamme vasemman puolen osan ja yritämme saada oikean puolen.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Nyt käytämme assosiatiivisia ja jakautuvia lakeja näin:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nyt käytämme De Morganin lakia seuraavasti:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Nyt käytämme jakelulakia näin:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Siksi todistettu
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Esimerkki 5: Tässä esimerkissä meidän on osoitettava, että ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) on tautologia.
Ratkaisu: Täällä otamme pieniä osia ja ratkaisemme ne.
Ensin käytämme De Morganin lakia ja saamme seuraavan:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Siksi,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Myös
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Siten
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Täten
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Tästä syystä voimme sanoa, että annettu kaava on tautologia.
Esimerkki 6: Tässä esimerkissä meidän on osoitettava, että (X ∧ Y) → (X ∨ Y) on tautologia.
Ratkaisu: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Nyt käytämme De Morganin lakia seuraavasti:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Nyt käytämme assosiaatiolakia ja kommutatiivista lakia seuraavasti:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Nyt käytämme negaatiolakia seuraavasti:
⇔ (T ∨ T) ⇔ T
Tästä syystä voimme sanoa, että annettu kaava on tautologia.
Esimerkki 7: Tässä esimerkissä meidän on kirjoitettava joidenkin lauseiden negaatio, jotka kuvataan seuraavasti:
- Marry suorittaa koulutuksensa tai hyväksyy XYZ Companyn liittymiskirjeen.
- Harry menee ratsastamaan tai juoksemaan huomenna.
- Jos saan hyvät arvosanat, serkkuni on mustasukkainen.
Ratkaisu: Ensin ratkaisemme ensimmäisen lauseen seuraavasti:
1. Oletetaan X: Naimisiin valmistuva koulutus.
Y: Hyväksy XYZ Companyn liittymiskirje.
Voimme käyttää seuraavaa symbolista muotoa ilmaisemaan tämän lausunnon:
X ∨ Y
X ∨ Y negaatio kuvataan seuraavasti:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Lopuksi, annetun lausunnon negaatio on:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Oletetaan X: Harry lähtee kyydille
Y: Harry juoksee huomenna
Voimme käyttää seuraavaa symbolista muotoa ilmaisemaan tämän lausunnon:
X ∨ Y
X ∨ Y negaatio kuvataan seuraavasti:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Lopuksi, annetun lausunnon negaatio on:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Oletetaan X: Jos saan hyvät arvosanat.
Y: Serkkuni tulee olemaan mustasukkainen.
Voimme käyttää seuraavaa symbolista muotoa ilmaisemaan tämän lausunnon:
X → Y
X → Y:n negaatio kuvataan seuraavasti:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Lopuksi, annetun lausunnon negaatio on:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Esimerkki 8: Tässä esimerkissä meidän on kirjoitettava joidenkin väitteiden negaatio De Morganin lain avulla. Nämä lausunnot kuvataan seuraavasti:
- Tarvitsen kultasormuksen arvoisen timanttisarjan.
- Saat hyvän työn tai et saa hyvää kumppania.
- Teen paljon työtä, enkä kestä sitä.
- Koirani lähtee retkelle tai se tekee sotkua talossa.
Ratkaisu: Kaikkien väitteiden kieltäminen De Morganin lain avulla kuvataan yksitellen näin:
- En tarvitse timanttisarjaa tai kultasormuksen arvoista.
- Et voi saada hyvää työtä ja saat hyvän kumppanin.
- En tee paljoa työtä tai selviän siitä.
- Koirani ei mene reissuun eikä se sotke talossa.
Esimerkki 9: Tässä esimerkissä meillä on joitain lauseita, ja meidän on kirjoitettava näiden lauseiden negaatio. Lausumat on kuvattu seuraavasti:
- Jos sataa, niin suunnitelma mennä rannalle perutaan.
- Jos opiskelen ahkerasti, saan kokeesta hyvät arvosanat.
- Jos menen myöhäisillan juhliin, saan isäni rangaistuksen.
- Jos et halua puhua minulle, sinun on estettävä numeroni.
Ratkaisu: Kaikkien väitteiden negaatio kuvataan yksitellen näin:
- Jos suunnitelma mennä rannalle peruuntuu, silloin sataa.
- Jos saan kokeesta hyvät arvosanat, opiskelen ahkerasti.
- Jos saan isäni rangaistuksen, menen myöhäisillan juhliin.
- Jos sinun on estettävä numeroni, et halua puhua minulle.
Esimerkki 10: Tässä esimerkissä meidän on tarkistettava, ovatko (X → Y) → Z ja X → (Y → Z) loogisesti ekvivalentteja vai eivät. Meidän on perusteltava vastauksemme totuustaulukoiden avulla ja logiikkasääntöjen avulla molempien lausekkeiden yksinkertaistamiseksi.
Ratkaisu: Ensin käytämme menetelmää 1 tarkistaaksemme, ovatko (X → Y) → Z ja X → (Y → Z) loogisesti ekvivalentteja, mikä kuvataan seuraavasti:
lue csv-tiedostosta javassa
Tapa 1: Tässä oletetaan seuraavaa:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Ja
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Tapa 2: Nyt käytämme toista menetelmää. Tässä menetelmässä käytämme totuustaulukkoa.
| X | JA | KANSSA | 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 |
Tässä totuustaulukossa näemme, että sarakkeet (X → Y) → Z ja X → (Y → Z) eivät sisällä identtisiä arvoja.