قانون دمورگان: پلی میان «و» و «یا» در منطق
عبارتهای ساده و مرکب در منطق
در زندگی روزمره، ما مدام در حال ترکیب کردن گزارهها هستیم. برای مثال، "امروز هوا آفتابی است و باد ملایمی میوزد" یک گزاره مرکب است که با استفاده از «و» (عطف) ساخته شده است. یا جمله "فردا یا به سینما میروم یا در خانه میمانم" یک گزاره مرکب با «یا» (فصل) است. قانون دمورگان به ما کمک میکند تا نقیض (نه) این جملههای ترکیبی را به سادگی بنویسیم. به عبارت دیگر، اگر بخواهیم بگوییم "چنین نیست که امروز هم هوا آفتابی باشد و هم باد ملایمی بوزد"، قانون دمورگان به ما میگوید که این جمله معادل است با: "امروز هوا آفتابی نیست یا باد ملایمی نمیوزد".
برای درک بهتر، دو گزاره ساده الف و ب را در نظر میگیریم. قانون دمورگان شامل دو بخش اصلی است که در قالب فرمولهای ریاضی زیر نمایش داده میشوند. توجه کنید که نماد ¬ به معنای "نقیض" یا "نه" است.
$ \neg (A \land B) \equiv (\neg A) \lor (\neg B) $
$ \neg (A \lor B) \equiv (\neg A) \land (\neg B) $
تبدیل نقیض «و» به «یا»
بخش اول قانون میگوید: نقیض یک عبارت «و» دار، برابر است با یک عبارت «یا» دار که در آن هر یک از اجزا نقیض شدهاند. به زبان سادهتر، اگر بگوییم "چنین نیست که هم الف درست باشد و هم ب"، یعنی حداقل یکی از آنها نادرست است. یک مثال عددی میتواند این موضوع را روشنتر کند:
فرض کنید $A$ به معنای "$x$ یک عدد زوج است" و $B$ به معنای "$x$ بزرگتر از $5$ است" باشد. عبارت $A \land B$ یعنی "$x$ یک عدد زوج و بزرگتر از $5$ است". نقیض این عبارت یعنی $\neg (A \land B)$ یعنی "چنین نیست که $x$ هم زوج باشد و هم بزرگتر از $5$". طبق قانون دمورگان، این جمله معادل است با: "$x$ زوج نیست یا بزرگتر از $5$ نیست" یعنی $(\neg A) \lor (\neg B)$. برای $x=4$، عبارت اصلی نادرست است (چون شرط بزرگتر از ۵ را ندارد) و عبارت تبدیلشده نیز درست است (چون $\neg B$ درست است).
تبدیل نقیض «یا» به «و»
بخش دوم قانون دمورگان عکس بخش اول است: نقیض یک عبارت «یا» دار، برابر است با یک عبارت «و» دار که در آن هر یک از اجزا نقیض شدهاند. اگر بگوییم "چنین نیست که الف یا ب درست باشد"، یعنی هم الف نادرست است و هم ب. برای مثال، با همان تعاریف بالا، عبارت $A \lor B$ یعنی "$x$ زوج است یا بزرگتر از $5$ است". نقیض آن $\neg (A \lor B)$ یعنی "چنین نیست که $x$ زوج باشد یا بزرگتر از $5$ باشد". قانون دمورگان به ما میگوید که این جمله معادل است با: "$x$ زوج نیست و بزرگتر از $5$ نیست" یعنی $(\neg A) \land (\neg B)$. برای $x=3$، عبارت اصلی نادرست است (چون نه زوج است و نه بزرگتر از ۵) و عبارت تبدیلشده نیز درست است.
مقایسه دو بخش قانون دمورگان
برای درک بهتر تفاوت و کاربرد این دو بخش، جدول زیر را بررسی کنید. این جدول به طور خلاصه هر دو قانون و یک مثال ساده از آنها را نشان میدهد.
| عنوان قانون | فرمول ریاضی | ترجمه به زبان ساده | مثال عینی |
|---|---|---|---|
| نقیض عطف (و) | $\neg (A \land B) \equiv (\neg A) \lor (\neg B)$ | نه (الف و ب) یعنی: (نه الف) یا (نه ب) | "چنین نیست که هم باران بیاید و هم برف" یعنی: "باران نمیآید یا برف نمیآید" |
| نقیض فصل (یا) | $\neg (A \lor B) \equiv (\neg A) \land (\neg B)$ | نه (الف یا ب) یعنی: (نه الف) و (نه ب) | "چنین نیست که من چای بنوشم یا قهوه بخورم" یعنی: "نه چای مینوشم و نه قهوه میخورم" |
کاربرد عملی در برنامهنویسی و ریاضیات
قانون دمورگان فقط یک فرمول تئوری نیست؛ در عمل کاربردهای فراوانی دارد. فرض کنید در حال نوشتن یک برنامه هستید و میخواهید بررسی کنید که آیا کاربر عددی خارج از بازه $1$ تا $10$ وارد کرده است یا خیر. شرط "خارج از بازه" معادل است با $\neg (1 \le x \le 10)$. با استفاده از قانون دمورگان، این شرط به $(x \lt 1) \lor (x \gt 10)$ تبدیل میشود که نوشتن آن در کد بسیار سادهتر و خواناتر است.
مثال دیگر در ریاضیات و حل نامعادلات است. فرض کنید میخواهیم مجموعه اعدادی را پیدا کنیم که در شرط $\neg (x \gt 2 \land x \lt 5)$ صدق میکنند. با اعمال قانون دمورگان، این شرط به $(x \le 2) \lor (x \ge 5)$ تبدیل میشود. یعنی مجموعه اعداد مورد نظر، همه اعداد کوچکتر یا مساوی $2$ و بزرگتر یا مساوی $5$ هستند. این تبدیل، مسأله را برای حل بسیار سادهتر میکند.
چالشهای مفهومی
پاسخ: زیرا معنای جمله کاملاً عوض میشود. $\neg (A \land B)$ به معنای این است که هر دو همزمان درست نیستند، در حالی که $(\neg A) \land (\neg B)$ به معنای این است که هیچکدام درست نیستند. این دو با هم تفاوت بنیادی دارند. قانون دمورگان رابطه صحیح را برقرار میکند.
پاسخ: قانون دمورگان برای هر تعداد عبارت قابل تعمیم است. برای مثال، نقیض $ (A \land B \land C) $ برابر است با $ (\neg A) \lor (\neg B) \lor (\neg C) $. به همین ترتیب، نقیض $ (A \lor B \lor C) $ برابر است با $ (\neg A) \land (\neg B) \land (\neg C) $.
پاسخ: این عوض شدن به دلیل نحوه عملکرد نقیض بر روی مجموعهها است. در نظریه مجموعهها، نقیض اشتراک (معادل «و») برابر اجتماع (معادل «یا») مکملهاست و نقیض اجتماع برابر اشتراک مکملها. این یک ویژگی ساختاری منطق است که ریشه در شهود ما از مفهوم "هیچکدام" و "حداقل یکی" دارد.
پاورقی
1 نقیض (Negation): عملگری منطقی که ارزش یک گزاره را به عکس تبدیل میکند؛ اگر گزاره درست باشد، نقیض آن نادرست و بالعکس.
2 عطف (Conjunction): عملگر منطقی "و" که خروجی آن تنها زمانی درست است که تمام گزارههای ورودی درست باشند.
3 فصل (Disjunction): عملگر منطقی "یا" که خروجی آن زمانی درست است که حداقل یکی از گزارههای ورودی درست باشد.
4 آگوستوس دمورگان (Augustus De Morgan): ریاضیدان و منطقدان بریتانیایی قرن نوزدهم که این قوانین به نام او ثبت شده است.
