De Morganin laki on yleisin laki joukkoteoriassa ja Boolen algebrassa sekä joukkoteoriassa. Tässä artikkelissa opimme De Morganin laista, De Morganin laista joukkoteoriassa ja De Morganin laista Boolen algebrassa sekä sen todisteita, totuustaulukoita ja logiikkaporttikaavioita. Artikkelissa on myös ratkaistu De Morganin lakiesimerkki ja De Morganin lakia koskevat usein kysytyt kysymykset. Opitaan De Morganin laki.

Sisällysluettelo

• Mikä on De Morganin laki
• De Morganin laki joukkoteoriassa
• Ensimmäinen De Morganin laki
• Toinen De Morganin laki
• Todistus käyttäen joukkoalgebraa
• De Morganin laki Boolen algebrassa
• Morganin lain kaavasta
• Ratkaistiin esimerkkejä De Morganin laista
• De Morganin lain logiikkasovellukset

Mikä on De Morganin laki

De Morganin laki on laki, joka määrittää liiton, leikkauspisteen ja komplementtien välisen suhteen joukkoteoriassa. Boolen algebrassa se antaa suhteen AND-, OR- ja muuttujan komplementtien välillä, ja logiikassa se antaa suhteen lauseen AND-, OR- tai Negaation välillä. De Morganin lain avulla voimme optimoida erilaisia ​​loogisia portteja sisältäviä loogisia piirejä, jotka auttavat meitä suorittamaan saman toiminnon, mutta hyvin harvoilla laitteilla.

De Morganin laki joukkoteoriassa

De Morganin laki vuonna joukko teoria määrittelee joukkojen liiton, leikkauspisteen ja komplementtien välisen suhteen ja on annettu sekä liiton komplementille että kahden joukon leikkauspisteelle. Joukkoteoriassa on kaksi De Morganin lakia, jotka ovat:

• Ensimmäinen De Morganin laki
• Toinen De Morganin laki

Ymmärretään nämä lait yksityiskohtaisesti alla:

Ensimmäinen De Morganin laki

Ensin De Morganin laki sanoo sen Kahden joukon liiton komplementti on yhtä suuri kuin kunkin joukon komplementtien leikkauspiste.

Olkoon A ja B kaksi joukkoa, niin matemaattisesti Ensin De Morganin laki annetaan seuraavasti:

(A ∪ B)’ = A’ ∩ B’

Missä

• SISÄÄN edustaa unionin toimintaa joukkojen välillä,
• ∩ edustaa leikkausoperaatiota joukkojen välillä, ja
• ' edustaa komplementtioperaatiota joukossa.

Sitä kutsutaan myös De Morganin unionin laki.

Yksityiskohta De Morganin lain todiste

Todistus käyttäen joukkoalgebraa

Meidän on todistettava, (A ∪ B)’ = A’ ∩ B’

Olkoon X = (A ∪ B)’ ja Y = A’ ∩ B’

Olkoon p mikä tahansa X:n alkio, sitten p ∈ X ⇒ p ∈ (A ∪ B)'

⇒ p ∉ (A ∪ B)

⇒ p ∉ A tai p ∉ B

⇒ p ∈ A’ ja p ∈ B’

⇒ p ∈ A’ ∩ B’

⇒ p ∈ Y

∴X ⊂Y. . . (joo)

Olkoon q jälleen mikä tahansa Y:n alkio, sitten q ∈ Y ⇒ q ∈ A’ ∩ B’

⇒ q ∈ A’ ja q ∈ B’

⇒ q ∉ A tai q ∉ B

⇒ q ∉ (A ∪ B)

⇒ q ∈ (A ∪ B)'

⇒ q ∈ X

∴Y ⊂X. . . (ii)

Kohdasta (i) ja (ii) X = Y

(A ∪ B)’ = A’ ∩ B’

Lue myös - Todiste De-Morganin laeista boolen algebrassa

Todistus Venn-kaavion avulla

Venn-kaavio (A ∪ B)'

Venn-kaavio: A' ∩ B'

Molemmista kaavioista voimme selvästi sanoa,

(A ∪ B)’ = A’ ∩ B’

järjestelmäohjelmisto

Tämä on ensimmäinen De Morganin laki.

Toinen De Morganin laki

Toinen De Morganin laki sanoo sen Kahden joukon leikkauksen komplementti on yhtä suuri kuin kunkin joukon komplementtien liitto.

Olkoon A ja B kaksi joukkoa, niin matemaattisesti Ensin De Morganin laki annetaan seuraavasti:

(A ∩ B)’ = A’ ∪ B’

Missä

• SISÄÄN edustaa unionin toimintaa joukkojen välillä,
• ∩ edustaa leikkausoperaatiota joukkojen välillä, ja
• ' edustaa komplementtioperaatiota joukossa.

Sitä kutsutaan myös De Morganin leikkauslaki .

Todistus käyttäen joukkoalgebraa

Toinen De Morganin laki: (A ∩ B)’ = A’ ∪ B’

Olkoon X = (A ∩ B)’ ja Y = A’ ∪ B’

Olkoon p mikä tahansa X:n alkio, sitten p ∈ X ⇒ p ∈ (A ∩ B)'

⇒ p ∉ (A ∩ B)

⇒ p ∉ A ja p ∉ B

⇒ p ∈ A’ tai p ∈ B’

⇒ p ∈ A' ∪ B'

⇒ p ∈ Y

∴ X ⊂ Y ————–(i)

Olkoon q jälleen mikä tahansa Y:n alkio, sitten q ∈ Y ⇒ q ∈ A’ ∪ B’

⇒ q ∈ A’ tai q ∈ B’

⇒ q ∉ A ja q ∉ B

⇒ q ∉ (A ∩ B)

⇒ q ∈ (A ∩ B)'

⇒ q ∈ X

∴ Y ⊂ X ————–(ii)

Kohdasta (i) ja (ii) X = Y

(A ∩ B)’ = A’ ∪ B’

Todistus Venn-kaavion avulla

Venn-kaavio (A ∩ B)'

Venn-kaavio A' ∪ B'

Molemmista kaavioista voimme selvästi sanoa

(A ∩ B)’ = A’ ∪ B’

Tämä on toinen De Morganin laki.

De Morganin laki Boolen algebrassa

De Morganin laki Boolen algebra määrittelee suhteen OR-, AND- ja muuttujien komplementtien välillä, ja se on annettu sekä AND- että TAI-komplementille kahden arvon välillä. Boolen algebrassa on kaksi De Morganin lakia, jotka ovat:

• Ensimmäinen De Morganin laki
• Toinen De Morganin laki

Ymmärretään nämä lait yksityiskohtaisesti alla:

Ensimmäinen De Morganin laki Boolen algebrassa

Ensin De Morganin laki sanoo sen Kahden tai useamman muuttujan TAI-komplementti on yhtä suuri kuin kunkin muuttujan komplementin JA.

Olkoon A ja B kaksi muuttujaa, niin matemaattisesti ensimmäinen De Morganin laki annetaan seuraavasti:

(A + B)’ = A’ . B'

Missä

• + edustaa OR-operaattoria muuttujien välillä,
• . edustaa AND-operaattoria muuttujien välillä ja
• ' edustaa komplementtioperaatiota muuttujalle.

Ensimmäinen De Morganin lain logiikkaportit

Logiikkaporttien ja Boolen algebran yhteydessä De Morganin laki sanoo, että molemmat logiikkaporttipiirit eli EI-portti lisätään TAI-portin lähtöön ja EI-portti lisätään JA-portin tuloon, ovat samanarvoisia. Nämä kaksi logiikkaporttipiiriä on annettu seuraavasti:

Ensimmäinen De Morganin lain totuustaulukko

Ensimmäisen De Morganin lain totuustaulukko annetaan seuraavasti:

Toinen De Morganin laki Boolen algebrassa

Toinen De Morganin laki sanoo sen Kahden tai useamman muuttujan JA-komplementti on yhtä suuri kuin kunkin muuttujan komplementin TAI.

Olkoon A ja B kaksi muuttujaa, niin matemaattisesti Toinen De Morganin laki annetaan seuraavasti:

(A . B)' = A' + B'

Missä

• + edustaa OR-operaattoria muuttujien välillä,
• . edustaa AND-operaattoria muuttujien välillä ja
• ' edustaa komplementtioperaatiota muuttujalle.

Toinen De Morganin lain logiikkaportit

Logiikkaporttien ja Boolen algebran yhteydessä De Morganin laki sanoo, että molemmat logiikkaporttipiirit eli EI-portti lisätään JA-portin lähtöön ja EI-portti lisätään TAI-portin tuloon, ovat samanarvoisia. Nämä kaksi logiikkaporttipiiriä on annettu seuraavasti:

Toinen De Morganin lain totuustaulukko

Toisen De Morganin lain totuustaulukko annetaan seuraavasti:

Morganin lakilogiikasta

De Morganin logiikan laissa seuraavat prepositiot ovat tautologiaa:

∼ (a ∧ b) ≡ ∼ a ∨ ∼ b

∼ (a ∨ b) ≡ ∼ a ∧ ∼ b

Missä,

• ∧ edustaa lauseiden konjunktiota,
• ∨ edustaa lausuntojen disjunktiota,
• ~ edustaa lausunnon negaatiota ja
• ≡ edustaa lauseiden vastaavuutta.

Morganin lain kaavasta

Kootaan kaikki De Morganin lain kaavat seuraavaan luetteloon.

Joukkoteorialle:

• (A ∪ B)’ = A’ ∩ B’
• (A ∩ B)’ = A’ ∪ B’

Boolen algebralle:

• (A + B)’ = A’ . B'
• (A . B)' = A' + B'

Logiikka:

• ∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
• ∼ (a ∨ b) ≡ ∼ a ∧ ∼ b

Ratkaistiin esimerkkejä De Morganin laista

Tehtävä 1: Oletetaan, että U = {2, 3, 7, 8, 9}, A = {2, 7} ja B = {2, 3, 9}. Todista De Morganin toinen laki.

Ratkaisu:

U = {2, 3, 7, 8, 9}, A = {2, 7} ja B = {2, 3, 9}

Todistaaksesi: (A ∩ B)’ = A’ ∪ B’

(A ∩ B) = {2}

(A ∩ B)’ = U – (A ∩ B) = {2, 3, 7, 8, 9} – {2}

(A ∩ B)' = {3, 7, 8, 9}

A’ = U – A = {2, 3, 7, 8, 9} – {2, 7}

A' = {3, 8, 9}

B’ = U – B = {2, 3, 7, 8, 9} – {2, 3, 9}

B' = {7, 8}

A’ ∪ B’ = {3, 8, 9} ∪ {7, 8}

A’ ∪ B’ = {3, 7, 8, 9}

(A ∩ B)’ = A’ ∪ B’

Ongelma 2: Kun otetaan huomioon, että U = {1, 4, 6, 8, 9}, A = {1, 9} ja B = {4, 6, 9}. Todista De Morganin ensimmäinen laki.

Ratkaisu:

U = {1, 4, 6, 8, 9}, A = {1, 9} ja B = {4, 6, 9}

Todistaaksesi: (A ∪ B)’ = A’ ∩ B’

(A ∪ B) = {1, 4, 6, 9}

(A ∪ B)’ = U – (A ∪ B) = {1, 4, 6, 8, 9} – {1, 4, 6, 9}

(A ∪ B)' = {8}

A’ = U – A = {1, 4, 6, 8, 9} – {1, 9}

A' = {4, 6, 8}

B’ = U – B = {1, 4, 6, 8, 9} – {4, 6, 9}

B' = {1, 8}

A’ ∩ B’ = {4, 6, 8} ∩ {1, 8}

A’ ∩ B’ = {8}

(A ∪ B)’ = A’ ∩ B’

Siksi todistettu

Tehtävä 3: Yksinkertaista Boolen lauseke: Y = [(A + B).C]'

Ratkaisu:

Y = [(A + B).C]'

De Morganin lakia soveltaen (A . B)’ = A’ + B’

Y = (A + B)' + C'

De Morganin lakia soveltaen (A + B)’ = A’. B'

Y = A'. B' + C'

Tehtävä 4: Yksinkertaista Boolen lauseke: X = [(A + B)’ + C]’

Ratkaisu:

X = [(A + B)' + C]'

De Morganin lakia soveltaen (A + B)’ = A’. B'

X = [(A + B)']' . C'

X = (A + B). C'

Katso lisää näistä lähteistä:

Esittele esimerkkejä De Morganin laista

Morganin lain käytännön esimerkkejä

Esimerkki 1: Pizzan täytteet

Kuvittele, että olet pizzajuhlissa ja sinulle kerrotaan, että voit valita mitä tahansa täytteitä paitsi sekä sieniä että oliiveja yhdessä.

• De Morganin lain avulla : Tämä tarkoittaa, että jos et halua sekä sieniä että oliiveja (Not (Sienet ja oliivit)), et voi joko olla sieniä (Not Mushrooms) tai ei oliiveja (Ei oliiveja) pizzassasi. Joten voit syödä pizzan vain sienillä, vain oliiveilla tai ei kumpaakaan!

Esimerkki 2: Kirjastokirjat

Opettajasi sanoo, että et voi tuoda luokkahuoneeseen velhoja tai lohikäärmeitä käsitteleviä kirjoja.

• De Morganin lain avulla : Tämä tarkoittaa, että jos et saa tuoda kirjoja velhoista tai lohikäärmeistä (Not (Wizards or Dragons)), et voi tuoda kirjoja velhoista (Not Wizards) etkä voi tuoda kirjoja lohikäärmeistä (Not Dragons). Joten kirjat avaruudesta tai eläimistä ovat edelleen kunnossa!

Esimerkki 3: Ulkona leikkiminen

Äitisi sanoo, että et voi leikkiä ulkona, jos sataa ja on kylmä samaan aikaan.

• De Morganin lain avulla : Tämä tarkoittaa, että jos et mene ulos, koska sataa ja on kylmä (Ei (Raining and Cold)), et menisi ulos, jos vain sataa (Ei sataa) tai vain kylmä (Not Cold). Mutta jos on aurinkoista ja lämmintä, olet hyvä!

Esimerkki 4: Elokuvan valitseminen

Ystäväsi sanoo, että he eivät halua katsoa elokuvaa, joka on pelottava tai tylsä.

• De Morganin lain avulla : Tämä tarkoittaa, että jos ystäväsi ei halua elokuvaa, joka on pelottava tai tylsä ​​(Not (Scary or Boring)), hän ei halua pelottavaa elokuvaa (Not Scary) eikä hän halua tylsää elokuvaa (Not Boring) . Joten hauska tai jännittävä elokuva olisi täydellinen!

De Morganin lain logiikkasovellukset

Morganin laista – UKK

State De Morganin ensimmäinen lakilausunto joukkoteoriassa.

De Morganin ensimmäinen joukkoteorian laki sanoo, että kahden joukon liiton komplementti on yhtä suuri kuin niiden yksittäisten komplementtien leikkauspiste.

State De Morganin toinen lakilause Boolen algebrassa.

De Morganin toinen laki Boolen algebrassa sanoo, että kahden tai useamman muuttujan JA-komplementti on yhtä suuri kuin kunkin muuttujan komplementin TAI.

Kirjoita joukkoteorian kaava De Morganin laille.

De Morganin lain kaava joukkoteoriassa:

(i) (A ∪ B)’ = A’ ∩ B’

(ii) (A ∩ B)’ = A’ ∪ B’

Kirjoita De Morganin lain kaava Boolen algebraan.

De Morganin lain kaava Boolen algebrassa:

(i) (A + B)’ = A’ . B'

(ii) (A . B)' = A' + B'

Kirjoita joitain De Morganin lain sovelluksia.

Jotkut De Morganin lain sovellukset ovat monimutkaisen Boolen lausekkeen minimointi ja yksinkertaistaminen.

Kuinka todistaa De Morganin laki?

De Morganin laki joukkoteoriassa voidaan todistaa Venn-kaavioilla ja De Morganin laki Boolen algebrassa voidaan todistaa totuustaulukoilla.