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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

قوانین دمرگان، در منطق گزاره‌ها و جبر بولی، یک جفت از قوانین تغییراند که هر دو قوانینشان معتبر استنتاج می‌شوند. این قوانین صرفااز طریق نفی بیان ربط و جدایی، یکدیگر را اثبات می‌کنند. این قوانین را در فارسی بدین صورت می‌توان نمایش داد:

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

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

"نه (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 \and Q) \vdash (\neg P \or \neg Q)

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

\neg(P \or Q) \vdash (\neg P \and \neg Q)

منابع[ویرایش]