Закон де Моргана є найпоширенішим законом у теорії множин і булевій алгебрі, а також у теорії множин. У цій статті ми дізнаємося про закон Де Моргана, закон Де Моргана в теорії множин і закон Де Моргана в булевій алгебрі разом із його доказами, таблицями істинності та діаграмами логічних воріт. Стаття також містить розв’язаний приклад закону Де Моргана та поширені запитання щодо закону Де Моргана. Давайте дізнаємося про закон Де Моргана.

Зміст

• Що таке закон де Моргана
• Закон де Моргана в теорії множин
• Перший закон де Моргана
• Другий закон де Моргана
• Доведення за допомогою алгебри множин
• Закон де Моргана в булевій алгебрі
• З формули закону Моргана
• Розв’язані приклади на закон де Моргана
• Логічні застосування закону Де Моргана

Що таке закон де Моргана

Закон де Моргана — це закон, який визначає зв’язок між об’єднанням, перетином і доповненнями в теорії множин. У булевій алгебрі він дає відношення між І, АБО та доповненнями до змінної, а в логіці він дає відношення між І, АБО або запереченням оператора. За допомогою закону Де Моргана ми можемо оптимізувати різні булеві схеми, що включають логічні вентилі, які допомагають нам виконувати ту саму операцію, але з дуже невеликою кількістю апаратури.

Закон де Моргана в теорії множин

Закон де Моргана в теорія множин визначає відношення між об’єднанням, перетином і доповненнями множин і надається як для доповнення об’єднання, так і для перетину двох множин. У теорії множин існують два закони Де Моргана:

• Перший закон де Моргана
• Другий закон де Моргана

Розглянемо ці закони докладніше, як показано нижче:

Перший закон де Моргана

Перший закон Де Моргана говорить про це Доповнення об’єднання двох множин дорівнює перетину доповнень кожної множини.

Нехай A і B — дві множини, тоді перший закон Де Моргана математично виглядає як:

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

Де

• IN представляє операцію об'єднання між наборами,
• ∩ представляє операцію перетину між множинами, і
• ' представляє операцію доповнення на множині.

Його також називають Закон союзу де Моргана.

Деталізуйте доказ закону Де Моргана

Доведення за допомогою алгебри множин

Нам потрібно довести, (A ∪ B)’ = A’ ∩ B’

Нехай X = (A ∪ B)’ і Y = A’ ∩ B’

Нехай p будь-який елемент із X, тоді p ∈ X ⇒ p ∈ (A ∪ B)’

⇒ p ∉ (A ∪ B)

⇒ p ∉ A або p ∉ B

⇒ p ∈ A’ і p ∈ B’

⇒ p ∈ A’ ∩ B’

⇒ p ∈ Y

∴X ⊂ Y. . . (йо)

Знову ж таки, нехай q будь-який елемент з Y, тоді q ∈ Y ⇒ q ∈ A’ ∩ B’

⇒ q ∈ A’ і q ∈ B’

⇒ q ∉ A або q ∉ B

⇒ q ∉ (A ∪ B)

⇒ q ∈ (A ∪ B)’

⇒ q ∈ X

∴Y ⊂X. . . (іі)

З (i) і (ii) X = Y

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

Читайте також – Доведення законів Де Моргана в булевій алгебрі

Доведення за допомогою діаграми Венна

Діаграма Венна для (A ∪ B)’

Діаграма Венна для A’ ∩ B’

З обох діаграм ми можемо чітко сказати,

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

Це перший закон Де Моргана.

Другий закон де Моргана

Другий закон Де Моргана говорить про це Доповнення перетину двох множин дорівнює об'єднанню доповнень кожної множини.

Нехай A і B — дві множини, тоді перший закон Де Моргана математично виглядає як:

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

Де

• IN представляє операцію об'єднання між наборами,
• ∩ представляє операцію перетину між множинами, і
• ' представляє операцію доповнення на множині.

Його також називають Закон перетину де Моргана .

Доведення за допомогою алгебри множин

Другий закон де Моргана: (A ∩ B)’ = A’ ∪ B’

Нехай X = (A ∩ B)’ і Y = A’ ∪ B’

перейменування каталогу в linux

Нехай p будь-який елемент із X, тоді p ∈ X ⇒ p ∈ (A ∩ B)’

⇒ p ∉ (A ∩ B)

⇒ p ∉ A і p ∉ B

⇒ p ∈ A’ або p ∈ B’

⇒ p ∈ A’ ∪ B’

⇒ p ∈ Y

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

Знову ж таки, нехай q — будь-який елемент із Y, тоді q ∈ Y ⇒ q ∈ A’ ∪ B’

⇒ q ∈ A’ або q ∈ B’

⇒ q ∉ A і q ∉ B

⇒ q ∉ (A ∩ B)

⇒ q ∈ (A ∩ B)’

⇒ q ∈ X

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

З (i) і (ii) X = Y

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

Доведення за допомогою діаграми Венна

Діаграма Венна для (A ∩ B)’

Діаграма Венна для A’ ∪ B’

З обох діаграм ми можемо чітко сказати

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

Це другий закон Де Моргана.

Закон де Моргана в булевій алгебрі

Булева алгебра закону Де Моргана визначає відношення між АБО, І та доповненнями до змінних і надається як для доповнення І, так і АБО двох значень. У булевій алгебрі є два закони Де Моргана:

• Перший закон де Моргана
• Другий закон де Моргана

Давайте розберемо ці закони в деталях, як показано нижче:

Перший закон де Моргана в булевій алгебрі

Перший закон Де Моргана говорить про це Доповнення до АБО двох чи більше змінних дорівнює І доповнення кожної змінної.

Нехай A і B — дві змінні, тоді математично перший закон де Моргана подається як:

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

Де

• + представляє оператор АБО між змінними,
• . представляє оператор І між змінними та
• ' представляє операцію доповнення над змінною.

Перший закон де Моргана, логічні ворота

У контексті логічних вентилів і булевої алгебри закон Де Моргана стверджує, що обидві схеми логічних вентилів, тобто вентиль НЕ додається до виходу елемента АБО, а вентиль НЕ додається до входу елемента І, є еквівалентними. Ці дві схеми логічних воріт подано таким чином:

Перша таблиця істинності закону Де Моргана

Таблиця істинності для першого закону Де Моргана представлена ​​таким чином:

Другий закон де Моргана в булевій алгебрі

Другий закон Де Моргана говорить про це Доповнення до І двох або більше змінних дорівнює АБО доповнення кожної змінної.

Нехай A і B — дві змінні, тоді другий закон Де Моргана математично виглядає як:

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

Де

• + представляє оператор АБО між змінними,
• . представляє оператор І між змінними та
• ' представляє операцію доповнення над змінною.

Другий закон Де Моргана Логічні ворота

У контексті логічних вентилів і булевої алгебри закон Де Моргана стверджує, що обидві схеми логічних вентилів, тобто вентиль НЕ додається до виходу елемента І, а вентиль НЕ додається до входу елемента АБО, еквівалентні. Ці дві схеми логічних воріт подано таким чином:

Друга таблиця істинності закону Де Моргана

Таблиця істинності для другого закону Де Моргана представлена ​​таким чином:

З логіки закону Моргана

У законі де Моргана для логіки наведені нижче прийменники є тавтологією:

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

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

Де,

• ∧ представляє сполучення тверджень,
• ∨ представляє диз'юнкцію тверджень,
• ~ представляє заперечення твердження, і
• ≡ представляє еквівалентність тверджень.

З формули закону Моргана

Давайте зберемо всі формули для закону Де Моргана в наведеному нижче списку.

Для теорії множин:

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

Для булевої алгебри:

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

Для логіки:

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

Розв’язані приклади на закон де Моргана

Проблема 1: враховуючи, що U = {2, 3, 7, 8, 9}, A = {2, 7} і B = {2, 3, 9}. Доведіть другий закон Де Моргана.

рішення:

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

Щоб довести: (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’

Проблема 2: Враховуючи, що U = {1, 4, 6, 8, 9}, A = {1, 9} і B = {4, 6, 9}. Доведіть перший закон Де Моргана.

рішення:

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

Щоб довести: (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’

Отже, доведено

Проблема 3. Спростіть логічний вираз: Y = [(A + B).C]’

рішення:

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

Застосовуючи закон Де Моргана (A . B)’ = A’ + B’

Y = (A + B)’ + C’

Застосовуючи закон Де Моргана (A + B)’ = A’. B'

Y = A'. B' + C'

Проблема 4. Спростіть логічний вираз: X = [(A + B)’ + C]’

рішення:

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

Застосовуючи закон Де Моргана (A + B)’ = A’. B'

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

X = (A + B). C’

Щоб дізнатися більше, перевірте ці джерела:

Покажіть приклади закону Де Моргана

З практичних прикладів закону Моргана

Приклад 1: начинка для піци

Уявіть, що ви на піцерії, і вам сказали, що ви можете вибрати будь-яку начинку, крім грибів і оливок разом.

• Використання закону Де Моргана : Це означає, що якщо ви не хочете мати гриби й оливки (Not (Mushrooms and Olives)), ви можете не їсти гриби (Not Mushrooms) або оливки (Not Olives) у своїй піці. Отже, ви можете з’їсти піцу лише з грибами, лише з оливками або ні з тим, ні з іншим!

Приклад 2: Бібліотечні книги

Ваш учитель каже, що не можна приносити в клас книги про чарівників чи драконів.

• Використання закону Де Моргана : це означає, що якщо вам заборонено читати книги про чарівників або драконів (Не (Чарівники або Дракони)), ви не можете приносити книги про чарівників (Не Чарівники) і не можете приносити книги про драконів (Не Дракони). Отже, книжки про космос чи тварин — це все одно годі!

Приклад 3: гра на вулиці

Твоя мама каже, що тобі не можна гратися на вулиці, якщо йде дощ і водночас холодно.

• Використання закону Де Моргана : Це означає, що якщо ви не збираєтеся виходити на вулицю, тому що йде дощ і холодно (Not (Raining and Cold)), ви не вийдете, якщо йде просто дощ (Not Raining) або просто холодно (Not Cold). Але якщо сонячно й тепло, тобі все добре!

Приклад 4: Вибір фільму

Ваш друг каже, що не хоче дивитися страшний або нудний фільм.

• Використання закону Де Моргана : Це означає, що якщо ваш друг не хоче фільму, який є страшним або нудним (Не (Страшний або Нудний)), він не хоче страшного фільму (Не Страшний) і не хоче нудного фільму (Не Нудний) . Тому смішний чи захоплюючий фільм підійде ідеально!

Логічні застосування закону Де Моргана

Із закону Моргана – поширені запитання

Перший закон Де Моргана в теорії множин.

Перший закон Де Моргана в теорії множин стверджує, що доповнення об’єднання двох множин дорівнює перетину їх окремих доповнень.

Стверджуйте другий закон де Моргана в булевій алгебрі.

Другий закон де Моргана в булевій алгебрі стверджує, що доповнення І двох або більше змінних дорівнює АБО доповнення кожної змінної.

Напишіть формулу закону Де Моргана в теорії множин.

Формула закону Де Моргана в теорії множин:

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

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

Напишіть формулу закону Де Моргана в булевій алгебрі.

Формула закону де Моргана в булевій алгебрі:

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

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

Напишіть кілька застосувань закону Де Моргана.

Деякі із застосувань закону Де Моргана полягають у мінімізації та спрощенні складного булевого виразу.

Як довести закон де Моргана?

Закон Де Моргана в теорії множин можна довести за допомогою діаграм Венна, а закон Де Моргана в булевій алгебрі можна довести за допомогою таблиць істинності.