قوانین دمورگان

در حساب گزاره‌ای و جبر بولی، قوانین دمورگان (به انگلیسی: De Morgan's Laws)،[1][2][3] یک جفت قواعد تبدیل اند که هردو قواعد استنتاجی معتبری می باشند. این تبدیل‌ها را براساس نام آگوستوس دمورگان نامگذاری کرده اند که یک ریاضیدان بریتانیایی قرن 19م میلادی است. این قواعد امکان می دهند تا عطف و فصل به طور محض، از طریق نقیض بیان شوند.

قوانین دمورگان که با نمودار ون نشان داده شده. در هر مورد، مجموعه حاصل با رنگ آبی مشخص شده است.

قاعده استنتاج
حساب گزاره‌ای
قاعده استنتاج
Implication introduction / قیاس استثنائی Biconditional introduction / elimination Conjunction introduction / elimination Disjunction introduction / elimination Disjunctive / hypothetical syllogism Constructive / destructive dilemma Absorption / نفی تالی / modus ponendo tollens
Rules of replacement
شرکت‌پذیری خاصیت جابه‌جایی توزیع‌پذیری نقیض مضاعف قوانین دمورگان Transposition Material implication Exportation Tautology Negation introduction
منطق مرتبه اول
Universal generalization / instantiation Existential generalization / instantiation

این قواعد را به زبان فارسی می‌توان به این صورت بیان کرد:

• نقیض فصل، عطف نقیض‌هاست.
• نقیض عطف، فصل نقیض‌هاست.

یا

• متمم اجتماع دو مجموعه، همان اشتراک متمم‌هایشان است.
• متمم اشتراک دو مجموعه، همان اجتماع متمم‌هایشان است.

یا

• نقیض (A یا B) = نقیض A و نقیض B
• نقیض (A و B) = نقیض A یا نقیض B

در نظریه مجموعه‌ها و جبر بولی، این عبارات را می توان به صورت زیر نوشت:

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

که در آن:

• ${\displaystyle A}$ و ${\displaystyle B}$ مجموعه هستند،
• ${\displaystyle {\overline {A}}}$ متمم ${\displaystyle A}$ است،
• ${\displaystyle \cap }$ اشتراک است و،
• ${\displaystyle \cup }$ اجتماع است.

این قواعد را برحسب زبان صوری می توان به صورت زیر نوشت:

${\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q)}$

و

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$

که در آن:

• P و Q گزاره هستند،
• ${\displaystyle \neg }$ عملگر نقیض منطقی است (NOT)،
• ${\displaystyle \land }$ عملگر منطقی عطف است (AND)،
• ${\displaystyle \lor }$ عملگر منطقی فصل است (OR)،
• ${\displaystyle \iff }$ نماد فرامنطقی است که معنای آن اینگونه است: «می‌توان آن را در یک اثبات صوری جایگزین کرد با»

کاربردهای این قواعد منطقی شامل عبارات منطقی در برنامه‌های کامپیوتری و طراحی مدارهای دیجیتالی است. قواعد دمورگان مثالی از مفهوم کلی‌تری از دوگان ریاضیاتی است.

منابع

1. Copi and Cohen
2. Hurley, Patrick J. (2015), A Concise Introduction to Logic (12th ed.), Cengage Learning, ISBN 978-1-285-19654-1
3. Moore and Parker

• مشارکت‌کنندگان ویکی‌پدیا. «De Morgan's Laws». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۷ مهٔ ۲۰۲۱.

پیوندهای بیرونی

• "Duality principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "de Morgan's Laws". MathWorld.
• de Morgan's laws در PlanetMath.
• Duality in Logic and Language, Internet Encyclopedia of Philosophy.