دوگانگی عطف/فصل

**دوگانگی عطف/فصل**  در منطق ریاضی و جبر بولی، اصلّی است که ...

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

## رابطه با قوانین دمورگان
*در منطق گزاره‌ای، رابهطه منطقی برای عطف منطقی و فصل منطقی می توانه با خودشان تعریف بشه، فقط یکی از آنها نیاز دارد که به عنوان اولیه در نظر گرفته بشه.
*اگر \varphi^{D} یه نتیشان که استفاده می کنیم برای جواب اوزکردن عطف منطقی با فصل منطقی، مثال p \lor q با p \land q یا برعکس ). اگر \lnot \varphi استفاده می کنیم برای نقیض φ، مثال (P با \lnot p). اگر \vDash استفاده می کیم برای ‌نتایج معنایی‌ و \equiv برای هم‌ارزی معنایی‌ بین فرمول منطقی، \varphi^{D} \equiv \lnot \overline{\varphi} هم \varphi \vDash \psi اگر و تنها اگر \psi^{D} \vDash \varphi^{D} پس می توانیم بگیم که اگر \varphi \equiv \psi ، پس \varphi^{D} \equiv \psi^{D} ( این به نامه فرمول دوگان یک تابع.)

## تعریف‌پذیری متقابل
می‌توانیم این روابط‌ها منطقی را بر اساس یکدیگر به صورت زیر تعریف بکردیم:
# \varphi \lor \psi :\equiv \lnot (\lnot \varphi \land \lnot \psi)
# \varphi \land \psi :\equiv \lnot(\lnot \varphi \lor \lnot \psi) 
# \lnot(\lnot \varphi \lor \lnot \psi) \equiv \lnot\lnot(\lnot\lnot \varphi \land \lnot\lnot \psi) \equiv \varphi \land \psi

** کامل بودن عملکردی:**
چون صورت بهنجار فصلی می گن که مجموعه رابط منطقی \{\land, \lor, \lnot\} تابع کامل است، نتایج این می گن که مجموعه رابط منطقی \{\land, \lnot\} و \{\lor, \lnot\} هم تابع کامل است.

**قضیه دِمورگان:**
قوانین دمورگان هم تریف حرف رابط منطقی استفاده می کند برای خودش.
# \lnot(\varphi \lor \psi) \equiv \lnot \varphi \land \lnot \psi
# \lnot(\varphi \land \psi) \equiv \lnot \varphi \lor \lnot \psi

## خواص دوگانگی
دوگان یک تابع یه جیزی می گریرم در وقتی که هر  \land  و  \lor  در جمله اوز می کنیم و با اوز کردن ثابت‌های گزاره‌ای با نقیضشان. مثال، دوگانِ  (A \land B \lor C) می شه  (\lnot A \lor \lnot B \land \lnot C). دوگان یک فرمول  \varphi  با نتیشان  \varphi^{*} استفاده می کنیم. قضیه دوگان یک تابع می گن که در منطق گزاره‌ای هر جوملات هم ارزی با نقض دوگانش.

**قضیه دوگان یک تابع:** به اضایه هر  \varphi، \varphi = \lnot (\varphi^{*}).
 
**اثپات:** به استقرا روی پیچیدگی. برای صادترین پیچیدگی، یک جمله اتمی دلخواه A در نظر می‌گیریم، چون  \lnot A نقیضش می شه و  \lnot  \lnot A دوگانش بشه، پس ما متوانیم بگیم که  \lnot  \lnot A هم ارز با A بشه. برای گام استقری، می توانیم فرض بکنیم که نوتیشان  \varphi نتیجه هر جملات که پیچیدگی کمتر دارد. سه تا کیس داریم: 
# اگر  \varphi مساوی با  \lnot \psi برای  \psi ، پس دوگانش بشه  \lnot \lnot (\psi^{*}). چون  \psi پیچیدگیش کمتر از  \varphi می شه، فرض استقراش\psi = \lnot  (\psi^{*}) می دهد و با  جایگذاری \varphi = \lnot \lnot  (\psi^{*}). پس \varphi هم ارز با نقیض دوگان خودش بشه.
# اگر \varphi با(\psi \lor \chi) برای  \psi و  \chi پس دوگانش می شه (\psi^{*} \land \chi^{*}) و نقیض دوگانش می شه \lnot (\psi^{*} \land \chi^{*}) پس \psi و \chi پیچیدگیش کمتر از \varphi می شه. با فرض استقرایش \varphi = \lnot (\varphi^{*}) و  \lnot  (\chi^{*}) = \chi  می دهد. با جایگذاری،\varphi = \lnot (\psi^{*}) \lor \lnot (\chi^{*}) می مگریم و با قضیه دمارگان، این اوز می کنه به \varphi = \lnot ( \psi^{*} \land \chi^{*})  پس \varphi هم ارز با نقیض دوگان خودش بشه.
# اگر \varphi مساوی با \psi \lor \chi بشه، نتیجه با استدلالی مشابه حاصل می‌شود.

## بیشتر قضایای دوگانگی
فرض کنید که \varphi \vDash \psi بشه، پس \overline \varphi \vDash \overline \psi  با جایگذاری \lnot P_i برای P_i، پس \lnot \psi \vDash \lnot \varphi شه با عکس نقیض ما می توانیم بگیم که  \psi^{D} \vDash \varphi^{D} بشه با خواص \lnot \overline \varphi \equiv \varphi^{D} که اثپات کردیم بلا. چون \varphi^{DD} = \varphi شه، پس \varphi \vDash \psi درست است اگر وتنها اگر \psi^{D} \vDash \varphi^{D}. اگر \varphi \vDash \lnot \psi  بشه، پس ما می توانیم بگیم که \varphi^{D} \vDash \lnot \psi^{D}  است.

## فرم‌های نرمال اتصالی و انفصالی
ما نوتیشان  \varphi  استفاده می کنیم برای فرم‌های نرمال انفصالی و نوتیشان \overline \varphi^{D}  استفاده می کنیم برای فرم‌های نرمال اتصالی. از اثپات بالا می دانیم که نقیض جملات هم ارزه با دوگان خودش، پس نوتیشان \overline \varphi^{D}  هم ارز با \lnot \varphi بشه. این راه می ده برای اوز کردن فرم‌های نرمال اتصالی و فرم‌های نرمال انفصالی. چون صورت بهنجار فصلی می گه که برای هر فرمول منطق گزاره‌ای که می توانیم با فرم‌های نرمال انفصالی تعریف کنیم، ما می توانیم با فرم‌های نرمال اتصالی هم تعریف بکنیم با استفاده کردن دوگان خودش.

## جستارهای وابسته
* جبر بولی
* قوانین دمورگان
* منطق گزاره‌ای

## منابع

## پیوند به بیرون

ایجاد صفحه با ساختار اولیه
رده:منطق ریاضی