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

قوانین دمورگان، (به انگلیسی: 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