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:

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:

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:

1. Marry suorittaa koulutuksensa tai hyväksyy XYZ Companyn liittymiskirjeen.
2. Harry menee ratsastamaan tai juoksemaan huomenna.
3. 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:

1. Tarvitsen kultasormuksen arvoisen timanttisarjan.
2. Saat hyvän työn tai et saa hyvää kumppania.
3. Teen paljon työtä, enkä kestä sitä.
4. Koirani lähtee retkelle tai se tekee sotkua talossa.

Ratkaisu: Kaikkien väitteiden kieltäminen De Morganin lain avulla kuvataan yksitellen näin:

1. En tarvitse timanttisarjaa tai kultasormuksen arvoista.
2. Et voi saada hyvää työtä ja saat hyvän kumppanin.
3. En tee paljoa työtä tai selviän siitä.
4. 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:

1. Jos sataa, niin suunnitelma mennä rannalle perutaan.
2. Jos opiskelen ahkerasti, saan kokeesta hyvät arvosanat.
3. Jos menen myöhäisillan juhliin, saan isäni rangaistuksen.
4. Jos et halua puhua minulle, sinun on estettävä numeroni.

Ratkaisu: Kaikkien väitteiden negaatio kuvataan yksitellen näin:

1. Jos suunnitelma mennä rannalle peruuntuu, silloin sataa.
2. Jos saan kokeesta hyvät arvosanat, opiskelen ahkerasti.
3. Jos saan isäni rangaistuksen, menen myöhäisillan juhliin.
4. 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.

Tässä totuustaulukossa näemme, että sarakkeet (X → Y) → Z ja X → (Y → Z) eivät sisällä identtisiä arvoja.