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

قوانین دمورگان، (به انگلیسی: De Morgan's laws) که به افتخار آگوستوس دمورگان نامگذاری شده و در منطق گزاره‌ها و جبر بولی، یک جفت از قوانین تغییراند که هر دو قوانینشان معتبر استنتاج می‌شوند. این قوانین صرفاً از طریق نفی بیان ربط و جدایی، یکدیگر را اثبات می‌کنند. این قوانین را در فارسی بدین صورت می‌توان نمایش داد:

نفی رابطه، گسست از نفی است. نفی گسست، ارتباط از نفی است.

یا می‌توان به صورت ساده‌تر بدین شکل بیان کرد:

"نه (A و B)" همان "(نه A) یا (نه B)" است یا اینکه "نه (A یا B)" همان "(نه A) و (نه B)" است

قوانین را می‌توان در زبان‌های رسمی با دو گزاره P و Q بیان کرد:

$\neg (P\land Q)\iff (\neg P)\lor (\neg Q)$

$\neg (P\lor Q)\iff (\neg P)\land (\neg Q)$

که در آن:

• ¬ اپراتور نفی (NOT) است.
• $\land$ اپراتور عطف (AND) است.
• $\lor$ اپراتور ترکیب فصلی (OR) است.
• ⇔ نماد فرامنطقی است به معنی «می‌تواند در یک برهان منطقی جایگزین شود».

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

نماد رسمی

نفی رابطه ممکن است در نشان گذاری پی در پی نوشته شده‌است:

$\neg (P\land Q)\vdash (\neg P\lor \neg Q)$

نفی ترکیب فصلی در نشان گذاری چنین نوشته است :

$\neg (P\lor Q)\vdash (\neg P\land \neg Q)$

منابع

• http://en.wikipedia.org/wiki/De_Morgan_Laws