سرفصل‌های این مبحث

منطق گزاره

فرم نرمال

آخرین ویرایش: 08 اسفند 1402

دسته‌بندی: منطق گزاره

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

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

$T o u t o \log y$ یک گزاره همیشه درست است.
$C o n t r a d i c t i a n$ یک گزاره همیشه نادرست است.
$S a t i s f i a b l e$ حداقل به‌ازای یکی از ترکیبات، ارزش ممکنه برای متغیرهای دارای ارزش $T$ است.

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

روش $D N F$

$D N F = D i s j u n c t i v e N o r m a l F o r m$

از این به بعد به‌جای ترکیب فصلی $(\lor)$ یا $(D i s j u n c t i v e)$ از کلمه $s u m$ یا حاصل جمع استفاده می‌کنیم.

هم‌ارز یک فرمول را که به‌صورت مجموع حاصل ضرب مانند زیر بیان شده باشد را $D N F$ گویند و با نماد $\sum_{}^{}$ نشان می‌دهند:

$(p \land ~ p) \lor (p \land q)$

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

$(p \land ~ p) \Leftrightarrow F$

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

$(p \lor ~ p) \Leftrightarrow T$

رویه به‌دست آوردن $D N F$

لفظ‌های پیوند دهنده $(↓, ↑, \bar{\lor}, ⇄, \to)$ را با فرمول‌های هم‌ارز جایگزین می‌کنیم که فقط در آن $(~, \land, \lor)$ ظاهر شوند.
در صورتی‌که بخشی از فرمول به‌صورت نفی ظاهر شده باشد با استفاده از قوانین دمورگان سعی می‌کنیم نفی فقط در متغیرها ظاهر شود.
اگر بخشی از فرمول به‌صورت حاصل‌ضرب مجموع‌ها بیان شده باشد با استفاده از قانون توزیع‌پذیری آن را به‌صورت مجموع حاصل‌ضرب تبدیل می‌کنیم.

دریافت مثال

دریافت فایل PDF

مینترم $(m int e r m)$

دو متغیر گزاره‌ای $p$ و $q$ را در نظر بگیرید، با این دو متغیر $2^{2} = 4$ ترکیب عطفی متمایز می‌توان نوشت که عبارتند از:

$\begin{array}{l} p \land q \end{array}$

$\begin{array}{l} p \land ~ q \end{array}$

$\begin{array}{l} ~ p \land q \end{array}$

$~ p \land ~ q$

هر ترکیب عطفی دیگری که بتوان به‌وسیله $p$ و $q$ یا $~ p$ و $~ q$ نوشت، قطعا با یکی از ترکیبات فوق هم‌ارز خواهد بود.

فرم نرمال - پیمان گردلو

ترکیب عطفی متغیرهای دل‌خواه (گزاره‌نما) که در آن هر متغیر تنها یک‌بار یا به‌صورت اصلی یا به‌صورت نفی ظاهر شده باشد را $(m int e r m)$ نامیده می‌شود و آن را با $m$ نمایش می‌دهیم.

خواص $(m int e r m)$ ها به‌صورت زیر است:

$(m int e r m)$ های متمایز، هم‌ارز نیستند.
هر $(m int e r m)$ تنها به‌ازای یکی از ترکیبات ارزش ممکنه برای متغیرها دارای ارزش $T$ می‌باشد، این امر در جدول بالا نشان داده شده است.
اگر $n$ متغیر وجود داشته باشد، آن‌گاه $2^{n}$ تا $(m int e r m)$ وجود دارد.

تعریف $P D N F$

$P D N F = \Pr i n c i p a l D i s j u c t i v e N o r m a l f o r m$

هم‌ارز یک فرمول را که به‌صورت مجموع $(m int e r m)$ ها بیان شده باشد $P D N F$ آن فرمول گویند.

با استفاده از جدول ارزش و $(m int e r m)$ هایی که دارای ارزش $T$ هستند، می‌توان $P D N F$ فرمولی را به‌دست آورد.

نکته

در یک فرمول $T o u t o \log y$ همه ترکیبات عطفی ممکنه برای متغیرها در $P D N F$ آن فرمول ظاهر خواهند شد، بدون در نظر گرفتن ترتیب قرار گرفتن $(m int e r m)$ ها در $P D N F$ یک فرمول $P D N F$ هر فرمولی منحصربه‌فرد است.

رویه به‌دست آوردن $P D N F$

$D N F$ فرمول را به‌دست می‌آوریم.
جملات حاصلضرب همیشه نادرست را حذف می‌کنیم.
با به‌کار گرفتن متغیرهای مفقود، $(m int e r m)$ ها را به‌دست می‌آوریم. $(p \lor ~ p) \Leftrightarrow T$
$(m int e r m)$ های مشابه را حذف می‌کنیم.

تذکر

اگر $P D N F$ فرمول $A$ در دست باشد، $P D N F$ فرمول $~ A$ مجموع $(m int e r m)$ هایی است که در $P D N F$ فرمول $A$ ظاهر نشده است.

دریافت مثال

دریافت فایل PDF

روش $C N F$

$C N F = C o n j u n c t i v e N o r m a l F o r m$

از این به بعد به‌جای ترکیب عطفی $(\land)$ یا $(C o n j u n c t i v e)$ از کلمه $p r o d u c t$ یا حاصل ضرب استفاده می‌کنیم.

هم‌ارز یک فرمول را که به‌صورت حاصل ضرب مجموع‌ها مانند زیر بیان شده باشد را $C N F$ گویند و با نماد $\prod_{}^{}$ نشان می‌دهند:

$(p \lor q) \land (~ p \lor ~ q)$

رویه به‌دست آوردن $C N F$

لفظ‌های پیوند دهنده $(↓, ↑, \bar{\lor}, ⇄, \to)$ را با فرمول‌های هم‌ارز جایگزین می‌کنیم که فقط در آن $(~, \land, \lor)$ ظاهر شوند.
در صورتی‌که بخشی از فرمول به‌صورت نفی ظاهر شده باشد با استفاده از قوانین دمورگان سعی می‌کنیم نفی فقط در متغیرها ظاهر شود.
اگر بخشی از فرمول به‌صورت مجموع حاصل‌ضرب‌ها بیان شده باشد با استفاده از قانون توزیع‌پذیری آن را به‌صورت حاصل‌ضرب مجموع تبدیل می‌کنیم.

دریافت مثال

دریافت فایل PDF

ماکسترم $(M a x t e r m)$

دو متغیر گزاره‌ای $p$ و $q$ را در نظر بگیرید، با این دو متغیر $2^{2} = 4$ ترکیب فصلی متمایز می‌توان نوشت که عبارتند از:

$\begin{array}{l} p \lor q \end{array}$

$\begin{array}{l} p \lor ~ q \end{array}$

$\begin{array}{l} ~ p \lor q \end{array}$

$~ p \lor ~ q$

هر ترکیب فصلی دیگری که بتوان به‌وسیله $p$ و $q$ یا $~ p$ و $~ q$ نوشت، قطعا با یکی از ترکیبات فوق هم‌ارز خواهد بود.

ترکیب فصلی متغیرهای دل‌خواه (گزاره‌نما) که در آن هر متغیر تنها یک‌بار یا به‌صورت اصلی یا به‌صورت نفی ظاهر شده باشد را $(M a x t e r m)$ نامیده می‌شود و آن را با $M$ نمایش می‌دهیم.

فرم نرمال - پیمان گردلو

خواص $(M a x t e r m)$ ها به‌صورت زیر است:

$(M a x t e r m)$ های متمایز، هم‌ارز نیستند.
هر $(M a x t e r m)$ تنها به‌ازای یکی از ترکیبات ارزش ممکنه برای متغیرها دارای ارزش $F$ می‌باشد، این امر در جدول بالا نشان داده شده است.
اگر $n$ متغیر وجود داشته باشد، آن‌گاه $2^{n}$ تا $(M a x t e r m)$ وجود دارد.

تعریف $P C N F$

$P C N F = \Pr i n c i p a l C o n j u n c t i v e N c r m a l F o r m$

هم‌ارز یک فرمول را که به‌صورت حاصل‌ضرب $(M a x t e r m)$ ها بیان شده باشد $P C N F$ آن فرمول گویند.

با استفاده از جدول ارزش و $(M a x t e r m)$ هایی که دارای ارزش $F$ هستند، می‌توان $P C N F$ فرمولی را به‌دست آورد.

تذکر

اگر $P C N F$ فرمول $A$ در دست باشد، $P C N F$ فرمول $~ A$ حاصل‌ضرب $(M a x t e r m)$ هایی است که در $P C N F$ فرمول $A$ ظاهر نشده است.

تمرین

$P C N F$ فرمول $~ p \land q$ را به‌دست ‌آورید:

$\begin{array}{l} ~ p \land q \end{array}$

$\begin{matrix} \begin{array}{l} \Leftrightarrow ~ p \lor (q \land ~ q) \land q \lor (p \land ~ p) \end{array} \end{matrix}$

$\begin{array}{l} \Leftrightarrow (~ p \lor q) \land (~ p \lor ~ q) \land (q \lor p) \land (q \lor ~ p) \end{array}$

$\begin{array}{l} \Leftrightarrow (p \lor q) \land (~ p \lor q) \land (~ p \lor ~ q) \end{array}$

همان‌طور که مشاهده می‌شود ماکسترمم $(p \lor ~ q)$ وجود ندارد اما اگر فرمول را نقیض کنیم $(M a x t e r m)$ ساخته می‌شود:

$~ (~ p \land q) \Leftrightarrow p \lor ~ q$

رویه به‌دست آوردن $P C N F$

$C N F$ فرمول را به‌دست می‌آوریم.
جملات مجموع همیشه درست را حذف می‌کنیم.
با به‌کار گرفتن متغیرهای مفقود، $(M a x t e r m)$ ها را به‌دست می‌آوریم. $(p \land ~ p) \Leftrightarrow F$
$(M a x t e r m)$ های مشابه را حذف می‌کنیم.

دریافت مثال

دریافت فایل PDF

تذکر

با استفاده از هم‌ارزی $A \Leftrightarrow ~ (~ A)$ و به‌کار گرفتن قوانین دمورگان می‌توان از $P D N F$ یا $P C N F$ فرمول $~ A$ ، $P D N F$ یا $P C N F$ فرمول $A$ را به‌دست آورد.

تمرین

فرض کنید $P C N F$ فرمول $~ S$ به‌صورت زیر تعریف شده باشد:

$~ S : (p \lor q \lor ~ R) \land (~ p \lor ~ Q \lor R) \land (~ p \lor ~ q \lor ~ R)$

از هم‌ارزی $S \Leftrightarrow ~ (~ S)$ استفاده کنید و $P D N F$ فرمول $S$ را به‌دست آورید.

$\begin{array}{l} S \end{array}$

$\begin{array}{l} \Leftrightarrow ~ (~ S) : ~ ((p \lor q \lor ~ R) \land (~ p \lor ~ q \lor R) \land (~ p \lor ~ q \lor ~ R)) \end{array}$

$\begin{array}{l} \Leftrightarrow ~ (p \lor q \lor ~ R) \lor ~ (~ p \lor ~ q \lor R) \lor ~ (~ p \lor ~ q \lor ~ R) \end{array}$

$\begin{array}{l} \Leftrightarrow (~ p \land ~ q \land R) \lor (p \land q \land ~ R) \lor (p \land q \land R) \end{array}$

نکته

در صورتی‌که برای متغیرها، $(M a x t e r m)$ ها، $(m int e r m)$ ها ترتیب خاصی قائل شویم و می‌توانیم $P D N F$ و $P C N F$ فرمولی را به‌طور منحصربه‌فرد نشان داد.

از آنجایی که غالبا برای نمایش متغیرها ازحروف بزرگ انگلیسی استفاده می‌کنیم بنابراین آنها را می‌توان به ترتیب حروف الفبا مرتب نمود.

حال اگر هر یک از این حروف دارای اندیس هم باشند، می‌توان آنها را به صورت زیر مرتب کرد.

$A, B, \dots, Z, A_{1}, B_{1}, \dots Z_{1}, A_{2}, \dots, Z_{2}, . \dots$

به‌عنوان نمونه $Q_{3}, T_{2}, S_{1} R_{3} Q P_{1}$ به‌ترتیب زیر مرتب می‌گردند:

$Q, P_{1}, S_{1}, T_{2}, Q_{3}, R_{3}$

تذکر

1- فرض کنیم $n$ متغیر دل‌خواه به‌طور مرتب چیده شده باشند، $2^{n}$ تا $(m int e r m)$ مربوط به این $n$ متغیر را می‌توان به‌صورت زیر نشان داد:

$m_{2^{n} - 1}, \dots, m_{1}, m_{0}$

در صورتی‌که اندیس‌ها را به معادل باینری آنها تبدیل کرده و در صورت نیاز تعدادی صفر به‌سمت چپ آنها اضافه کنیم به‌طوری‌که تعداد بیت‌ها با تعداد متغیرها یکسان شوند، می‌توان $(m int e r m)$ ها را به‌صورت زیر به‌دست آورد.

اگر در موضع $i$ ام از سمت چپ $1$ وجود داشته باشد در ترکیب عطفی، نفی متغیر ظاهر می‌شود.

اگر در موضع $i$ ام از سمت چپ $0$ وجود داشته باشد در ترکیب عطفی خود متغیر ظاهر می‌شود.

به‌عنوان نمونه فرض کنید $P$ و $Q$ و $R$ سه متغیر باشند که به‌همین ترتیب چیده شده‌اند، برای نمایش $(m int e r m)$ ها به‌صورت زیر عمل می‌کنیم:

فرم نرمال - پیمان گردلو

در صورتی‌که $(m int e r m)$ ها را فقط با اندیس آنها و ترکیب فصلی (مجموع) را با $\sum_{}^{}$ نشان دهیم، می‌توان مجموع حاصل‌ضرب‌های متناظر را با $m_{k}, m_{j}, m_{i}$ به‌صورت $\sum (i, j, k)$ نشان داد.

تذکر

2- فرض کنیم $n$ متغیر دل‌خواه به‌طور مرتب چیده شده باشند، $2^{n}$ تا $(M a x t e r m)$ مربوط به این $n$ متغیر را می‌توان به‌صورت زیر نشان داد:

$M_{2^{n} - 1}, . \dots ., M_{1}, M_{0}$

در صورتی‌که اندیس‌ها را به معادل باینری آنها تبدیل کرده و در صورت نیاز تعدادی صفر به‌سمت چپ آنها اضافه کنیم به‌طوری‌که تعداد بیت‌ها با تعداد متغیرها یکسان شوند، می‌توان $(M a x t e r m)$ ها را به‌صورت زیر به‌دست آورد.

اگر در موضع $i$ ام از سمت چپ $1$ وجود داشته باشد، در ترکیب فصلی نفی متغیر ظاهر می‌شود.

اگر در موضع $i$ ام از سمت چپ $0$ وجود داشته باشد، در ترکیب فصلی خود متغیر ظاهرمی‌شود.

به‌عنوان نمونه فرض کنید $P$ و $Q$ و $R$ سه متغیر باشند که به‌همین ترتیب چیده شده‌اند، برای نمایش $(M a x t e r m)$ ها به‌صورت زیر عمل می‌کنیم:

فرم نرمال - پیمان گردلو

در صورتی‌که $(M a x t e r m)$ ها را فقط با اندیس آنها و ترکیب عطفی (حاصل‌ضرب) را با $\prod_{}^{}$ نشان دهیم، می‌توان حاصل‌ضرب‌ مجموع‌های متناظر را با $M_{k}, M_{j}, M_{i}$ به‌صورت $\prod_{} (i, j, k)$ نشان داد.

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

فرم نرمال

2,500تومان

برای ارسال نظر وارد سایت شوید

منطق گزاره