17.7: Закони Де Моргана

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

Сучасник Буля, Август Де Морган, формалізував два правила логіки, які раніше були відомі неофіційно. Вони дозволяють переписати заперечення кон'юнкції як диз'юнкції, і навпаки.

Наприклад, припустимо, що ви хочете запланувати зустріч з двома колегами $4: 30 \mathrm{PM}$ на п'ятницю, і вам потрібно, щоб вони обидва були доступні на той час. Яка ситуація унеможливила б зустріч? Це НЕ так, що колега $a$ доступний І колега $b$ доступний: $\sim(a \wedge b) .$ /Ця ситуація еквівалентна або колега $a$ НЕ доступний АБО колега $b$ НЕ доступний: $\sim a \vee \sim b$

Закони Де Моргана

Заперечення кон'юнкції еквівалентно диз'юнкції заперечення тверджень, що складають кон'юнкцію. Щоб заперечувати твердження «і», заперечуйте кожну частину і змініть «і» на «або».

$\sim(p \wedge q)$ еквівалентно $\sim p \vee \sim q$

Заперечення диз'юнкції еквівалентно поєднанню заперечення тверджень, що складають диз'юнкцію. Щоб заперечувати твердження «або», заперечуйте кожну частину і змініть «або» на «і».

$\sim(p \vee q)$ еквівалентно $\sim p \wedge \sim q$

Приклад 28

На День Святого Валентина ви не отримали своїх солодких квітів чи цукерок: Яке з наступних тверджень логічно еквівалентно?

Ви не отримали їм квіти або не отримали їх цукерки.
Ви не отримали їм квіти і не отримали їх цукерки.
Ви отримали їм квіти або отримали цукерки.

Рішення

Це твердження не йде досить далеко; це залишає відкритою можливість того, що ви отримали їх одну з двох речей.
Це твердження еквівалентно оригіналу; $\sim (f \vee c)$ еквівалентно $-f \wedge \sim c$
Це твердження говорить про те, що ви їм щось отримали, але ми знаємо, що ви цього не зробили.

Спробуйте зараз 8

Щоб служити президентом США, людина повинна народилася в США, повинна бути не менше 35 років, і повинна проживати в США не менше 14 років. Який мінімальний набір умов може дискваліфікувати когось з посади президента?

Відповідь: Невиконання лише однієї з трьох умов - це все, що потрібно, щоб бути дискваліфікованим. Людина дискваліфікується, якщо вони не народилися в США, або не мають принаймні 35 років, або не прожили в США принаймні 14 років. Ключове слово тут - «або» замість «і».