De Morganov zákon je najbežnejším zákonom v teórii množín a Booleovej algebre, ako aj v teórii množín. V tomto článku sa dozvieme o De Morganovom zákone, De Morganovom zákone v teórii množín a De Morganovom zákone v Booleovej algebre spolu s jeho dôkazmi, pravdivostnými tabuľkami a diagramami logických brán. Článok obsahuje aj vyriešený príklad De Morganovho zákona a často kladené otázky o De Morganovom práve. Dozvieme sa o De Morganovom zákone.

Obsah

• Čo je De Morganov zákon
• De Morganov zákon v teórii množín
• Prvý De Morganov zákon
• Druhý De Morganov zákon
• Dôkaz pomocou algebry množín
• De Morganov zákon v Booleovej algebre
• Zo vzorca Morganovho zákona
• Vyriešené príklady De Morganovho zákona
• Logické aplikácie De Morganovho zákona

Čo je De Morganov zákon

De Morganov zákon je zákon, ktorý dáva vzťah medzi zjednotením, prienikom a doplnkami v teórii množín. V booleovskej algebre udáva vzťah medzi AND, OR a doplnkami premennej a v logike dáva vzťah medzi AND, OR alebo negáciou príkazu. Pomocou De Morganovho zákona môžeme optimalizovať rôzne booleovské obvody zahŕňajúce logické brány, ktoré nám pomáhajú vykonávať rovnakú operáciu, ale s veľmi malým počtom zariadení.

De Morganov zákon v teórii množín

De Morganov zákon v teória množín definuje vzťah medzi zjednotením, prienikom a doplnkami množín a je uvedený pre doplnok zjednotenia aj prienik dvoch množín. V teórii množín existujú dva De Morganove zákony, ktoré sú:

• Prvý De Morganov zákon
• Druhý De Morganov zákon

Poďme pochopiť tieto zákony podrobne, ako je uvedené nižšie:

Prvý De Morganov zákon

Prvý De Morganov zákon to hovorí Doplnok spojenia dvoch množín sa rovná priesečníku doplnkov každej množiny.

Nech A a B sú dve množiny, potom je matematicky prvý De Morganov zákon daný ako:

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

Kde

• IN predstavuje operáciu Únie medzi súbormi,
• ∩ predstavuje priesečníkovú operáciu medzi množinami a
• ' predstavuje operáciu komplementu na množine.

Je to aj tzv De Morganov zákon únie.

Podrobne o Dôkaze De Morganovho zákona

Dôkaz pomocou algebry množín

Musíme dokázať, (A ∪ B)‘ = A‘ ∩ B‘

Nech X = (A ∪ B)‘ a Y = A‘ ∩ B‘

Nech p je ľubovoľný prvok X, potom p ∈ X ⇒ p ∈ (A ∪ B)’

⇒ p ∉ (A ∪ B)

⇒ p ∉ A alebo p ∉ B

⇒ p ∈ A’ a p ∈ B’

⇒ p ∈ A’ ∩ B’

⇒ p ∈ Y

∴X ⊂ Y. . . (yo)

Opäť nech q je ľubovoľný prvok Y, potom q ∈ Y ⇒ q ∈ A’ ∩ B’

⇒ q ∈ A’ a q ∈ B’

⇒ q ∉ A alebo q ∉ B

⇒ q ∉ (A ∪ B)

⇒ q ∈ (A ∪ B)“

⇒ q ∈ X

∴Y ⊂X. . . (ii)

Z (i) a (ii) X = Y

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

Prečítajte si tiež - Dôkaz De-Morganových zákonov v booleovej algebre

Dôkaz pomocou Vennovho diagramu

Vennov diagram pre (A ∪ B)“

Vennov diagram pre A' ∩ B'

Z oboch diagramov môžeme jasne povedať,

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

To je prvý De Morganov zákon.

Druhý De Morganov zákon

Hovorí to druhý De Morganov zákon Doplnok priesečníka dvoch množín sa rovná spojeniu doplnkov každej množiny.

Nech A a B sú dve množiny, potom je matematicky prvý De Morganov zákon daný ako:

(A ∩ B)‘ = A‘ ∪ B‘

Kde

• IN predstavuje operáciu Únie medzi súbormi,
• ∩ predstavuje priesečníkovú operáciu medzi množinami a
• ' predstavuje operáciu komplementu na množine.

Je to aj tzv De Morganov zákon priesečníka .

Dôkaz pomocou algebry množín

Druhý De Morganov zákon: (A ∩ B)‘ = A‘ ∪ B‘

Nech X = (A ∩ B)‘ a Y = A‘ ∪ B‘

Nech p je ľubovoľný prvok X, potom p ∈ X ⇒ p ∈ (A ∩ B)’

⇒ p ∉ (A ∩ B)

⇒ p ∉ A a p ∉ B

⇒ p ∈ A' alebo p ∈ B'

⇒ p ∈ A’ ∪ B’

⇒ p ∈ Y

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

Opäť nech q je ľubovoľný prvok Y, potom q ∈ Y ⇒ q ∈ A’ ∪ B’

⇒ q ∈ A’ alebo q ∈ B’

⇒ q ∉ A a q ∉ B

⇒ q ∉ (A ∩ B)

⇒ q ∈ (A ∩ B)’

⇒ q ∈ X

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

Z (i) a (ii) X = Y

(A ∩ B)‘ = A‘ ∪ B‘

Dôkaz pomocou Vennovho diagramu

Vennov diagram pre (A ∩ B)“

Vennov diagram pre A' ∪ B'

Z oboch diagramov môžeme jednoznačne povedať

(A ∩ B)‘ = A‘ ∪ B‘

To je druhý De Morganov zákon.

De Morganov zákon v Booleovej algebre

De Morganov zákon Booleovská algebra definuje vzťah medzi OR, AND a doplnkami premenných a je daný pre doplnok AND aj OR dvoch hodnôt. V Booleovej algebre existujú dva De Morganove zákony, ktoré sú:

• Prvý De Morganov zákon
• Druhý De Morganov zákon

Poďme pochopiť tieto zákony podrobne, ako je uvedené nižšie:

Prvý De Morganov zákon v Booleovej algebre

Prvý De Morganov zákon to hovorí Doplnok OR dvoch alebo viacerých premenných sa rovná AND doplnku každej premennej.

otázky na pohovor v jazyku java

Nech A a B sú dve premenné, potom je matematicky prvý De Morganov zákon daný ako:

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

Kde

• + predstavuje operátor OR medzi premennými,
• . predstavuje operátor AND medzi premennými a
• ' predstavuje operáciu komplementu na premennej.

Prvý De Morganov zákon Logic Gates

V súvislosti s logickými hradlami a Booleovou algebrou De Morganov zákon uvádza, že Obidva obvody logického hradla, t. j. hradlo NOT sa pridá k výstupu hradla OR a hradlo NOT sa pridá k vstupu hradla AND, sú ekvivalentné. Tieto dva logické obvody hradla sú uvedené nasledovne:

Prvá pravdivá tabuľka De Morganovho zákona

Pravdivosť pre prvý De Morganov zákon je uvedená takto:

Druhý De Morganov zákon v Booleovej algebre

Hovorí to druhý De Morganov zákon Doplnok AND dvoch alebo viacerých premenných sa rovná ALEBO doplnku každej premennej.

Nech sú A a B dve premenné, potom je druhý De Morganov zákon matematicky daný ako:

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

Kde

• + predstavuje operátor OR medzi premennými,
• . predstavuje operátor AND medzi premennými a
• ' predstavuje operáciu komplementu na premennej.

Druhý De Morganov zákon Logika Gates

V súvislosti s logickými hradlami a Booleovou algebrou De Morganov zákon uvádza, že Obidva obvody logického hradla, t. j. hradlo NOT sa pridáva k výstupu hradla AND a hradlo NOT sa pridáva k vstupu hradla OR, sú ekvivalentné. Tieto dva logické obvody hradla sú uvedené nasledovne:

Druhá De Morganova tabuľka pravdy

Pravdivostná tabuľka pre druhý De Morganov zákon je uvedená takto:

Z logiky Morganovho zákona

V De Morganovom zákone pre logiku sú nižšie uvedené predložky tautológia:

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

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

Kde,

• ∧ predstavuje spojenie výrokov,
• ∨ predstavuje nesúlad výrokov,
• ~ predstavuje negáciu výroku a
• ≡ predstavuje ekvivalenciu výrokov.

Zo vzorca Morganovho zákona

Zostavme všetky vzorce pre De Morganov zákon v nasledujúcom zozname.

Pre teóriu množín:

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

Pre boolovskú algebru:

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

Pre logiku:

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

Vyriešené príklady De Morganovho zákona

Úloha 1: Vzhľadom na to, že U = {2, 3, 7, 8, 9}, A = {2, 7} a B = {2, 3, 9}. Dokážte druhý De Morganov zákon.

Riešenie:

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

Dokázať: (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‘

Problém 2: Vzhľadom na to, že U = {1, 4, 6, 8, 9}, A = {1, 9} a B = {4, 6, 9}. Dokážte De Morganov prvý zákon.

Riešenie:

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

Dokázať: (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’

Preto Dokázané

Problém 3: Zjednodušte boolovský výraz: Y = [(A + B).C]’

Riešenie:

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

Aplikácia De Morganovho zákona (A . B)‘ = A‘ + B‘

Y = (A + B)' + C'

Aplikovaním De Morganovho zákona (A + B)‘ = A‘. B'

Y = A'. B' + C'

Problém 4: Zjednodušte booleovský výraz: X = [(A + B)’ + C]’

Riešenie:

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

Aplikovaním De Morganovho zákona (A + B)‘ = A‘. B'

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

X = (A + B). C'

Ďalšie informácie nájdete v týchto zdrojoch:

Ukážte príklady De Morganovho zákona

Praktické príklady z Morganovho zákona

Príklad 1: Polevy na pizzu

Predstavte si, že ste na pizzovej párty a povedali vám, že si môžete vybrať akékoľvek polevy okrem húb a olív spolu.

• Použitie De Morganovho zákona : To znamená, že ak nechcete hríby aj olivy (Nie (Huby a Olivy)), môžete na pizzi buď nemať šampiňóny (Not Mushrooms), alebo nemať olivy (Not Olives). Takže by ste si mohli dať pizzu len s hubami, len olivami alebo ani jedno!

Príklad 2: Knihy z knižnice

Váš učiteľ hovorí, že nemôžete nosiť knihy o čarodejníkoch alebo drakoch do triedy.

• Použitie De Morganovho zákona : To znamená, že ak nemáte povolené knihy o čarodejníkoch alebo drakoch (Nie (Wizards or Dragons)), nemôžete si priniesť knihy o čarodejníkoch (Not Wizards) a nemôžete si priniesť knihy o drakoch (Not Dragons). Takže knihy o vesmíre alebo zvieratách sú stále v poriadku!

Príklad 3: Hranie vonku

Vaša mama hovorí, že sa nemôžete hrať vonku, ak prší a zároveň je chladno.

• Použitie De Morganovho zákona : To znamená, že ak nejdete von, pretože prší a je zima (Nie (Raining and Cold)), nevyšli by ste, ak práve prší (Not Raining) alebo je len zima (Not Cold). Ale ak je slnečno a teplo, môžete ísť!

Príklad 4: Výber filmu

Váš priateľ hovorí, že nechcú pozerať film, ktorý je strašidelný alebo nudný.

• Použitie De Morganovho zákona : To znamená, že ak váš priateľ nechce film, ktorý je strašidelný alebo nudný (Not (Scary or Boring)), nechce strašidelný film (Not Scary) a nechce nudný film (Not Boring) . Takže vtipný alebo vzrušujúci film by bol perfektný!

Logické aplikácie De Morganovho zákona

Z Morganovho zákona – často kladené otázky

Prvý zákon State De Morgan v teórii množín.

Prvý De Morganov zákon v teórii množín uvádza, že doplnok spojenia dvoch množín sa rovná priesečníku ich jednotlivých doplnkov.

Druhý zákon State De Morgan v Booleovej algebre.

Druhý De Morganov zákon v Booleovej algebre uvádza, že doplnok AND dvoch alebo viacerých premenných sa rovná OR doplnku každej premennej.

Napíšte vzorec pre De Morganov zákon v teórii množín.

Vzorec pre De Morganov zákon v teórii množín:

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

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

Napíšte vzorec pre De Morganov zákon v Booleovej algebre.

Vzorec pre De Morganov zákon v Booleovej algebre:

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

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

Napíšte niekoľko aplikácií De Morganovho zákona.

Niektoré z aplikácií De Morganovho zákona sú minimalizovať zložitý booleovský výraz a zjednodušiť ho.

Ako dokázať De Morganov zákon?

De Morganov zákon v teórii množín možno dokázať pomocou Vennových diagramov a De Morganov zákon v Booleovej algebre možno dokázať pravdivostnými tabuľkami.