Draft:جبر دی مورگان

یک جبر دمورگان در ریاضیات یک ساختار مانند A با ویژگی های (A, ∨, ∧, 0, 1, ¬) است بنابراین هر ساختار منطقی که خواص این جبر را بتواند برآورده کند یک جبر دمورگان خواهد بود این جبر به نام آگوستوس دی مورگان ، ریاضیدان و منطق دان بریتانیایی است.

• ( A، ∨، ∧، 0، 1) یک ساختار منطقی محدود است و
• ¬ یک دگرگونی(نقیض) در دمورگان است: ¬( x ∧ y ) = ¬ x ∨ ¬ y و ¬¬ x = x . (یعنی چرخشی که حاصل آن نیز در قوانین دمورگان صدق می کند)

در جبر دمورگان، قوانین:

• ¬ x ∨ x = 1 (قانون وسط حذف شده) که نشان می دهد از بین یک گزاره و نقیض آن حتما یکی درست است بنابراین فصل آنها یک گزاره همیشه درست یا توتولوژی است.
• ¬ x ∧ x = 0 ( قانون عدم تناقض) که نشان می دهد از بین یک گزاره و نقیض آن حتما یکی غلط است بنابراین عطف آنها یک گزاره همیشه غلط یا تناقض خواهد بود.

روی جبر دمورگان نمی مانیم. در این جبر هر قانون دیگری را نتیجه می دهد و اثبات می کند و هر جبری که این قوانین در آن صادق باشد را یک جبر بولی می نامیم و به جبر های جدید می رسیم.

تذکر: این قوانین شامل

¬(x ∨ y) = ¬x ∧ ¬y

¬1 = 0

¬0 = 1

می شوند. به عنوان مثال با قوانین بالا داریم: ¬1 = ¬1 ∨ 0 = ¬1 ∨ ¬¬0 = ¬(1 ∧ ¬0) = ¬¬0 = 0 بنابراین ¬ یک اتومورفیسم دوگانه از ( A , ∨، ∧، 0، 1) است.

اگر یک ساختار منطقی (lattice) به صورت ترتیبی تعریف شود، یعنی دارای (A, ≤) یک ترتیب جزئی محدود باشد که برای هر جفت عنصر، حد بالایی کمینه (least upper bound) یا همان سوپریموم و حد پایینی بیشینه یا همان اینفیموم (greatest lower bound) وجود داشته باشد، و عملیات‌های "ملاقات" (meet) که برای بدست آوردن اینفیموم است و "پیوست" (join) که برای بدست آوردن سوپریموم است را داشته باشد که به این ترتیب تعریف شده‌اند و قانون توزیع (distributive law) یا همان پخشی را برای این دو عملگر رعایت کنند، آنگاه می‌توان مکمل‌سازی (complementation) را به عنوان یک ضد-اتومورفیسم (involutive anti-automorphism) تعریف کرد.

• (الف، ≤) یک ساختار منطقی محدود است و
• ¬¬ x = x ، و
• x ≤ y → ¬ y ≤ ¬ x .

جبرهای دِمورگان حدود سال ۱۹۳۵ توسط گریگوره مویسیل معرفی شدند، هرچند در ابتدا بدون محدودیت داشتن ۰ یا همان گزاره همیشه غلط و ۱ یا همان گزاره همیشه درست معرفی شده بودند. (در جبرهای دِمورگان امروزی، وجود ۰ و ۱ الزامی است، اما در ابتدا مویسیل این شرط را قرار نداده بود.) بعدها، این جبرها در مدارس لهستانی (به عنوان مثال توسط راسیووا) با نام‌های مختلفی مانند "جبرهای شبه-بولی" و همچنین توسط جی. ای. کالمن "i-لاتیس توزیعی" نامیده شدند. (i-لاتیس مخفف "لاتیس با دگرگونی" است.  لاتیس یک ساختار جبری است که در آن هر دو عضو دارای کوچکترین کران بالا و بزرگترین کران پایین یعنی سوپریموم و اینفیموم هستند. دگرگونی یا Involution  یک نوع عملگر خاص در جبر است. در جبرهای دِمورگان، نقیض ¬ نقش دگرگونی یا چرخش را بازی می‌کند.) این جبرها بعدا در مدارس منطق جبری آرژانتینی توسط آنتونیو مونتیرو بیشتر مورد مطالعه قرار گرفتند.

جبرهای دِمورگان برای مطالعه‌ی ابعاد مختلف ریاضی منطق فازی اهمیت دارند. جبر فازی استاندارد F = ([0, 1], max(x, y), min(x, y), 0, 1, 1 - x) یک مثال از جبر دِمورگان است که در آن قانون وسط حذف شده(¬x ∨ x = 1) و عدم تناقض(¬x ∧ x = 0) برقرار نیستند.

منطق فازی: منطقی است که با مقادیر درستی بین ۰ و ۱ سروکار دارد، برخلاف منطق کلاسیک که فقط مقادیر ۰ (نادرست) و ۱ (درست) را دارد.

مثال دیگر برای جبر دمورگان معناشناسی چهار ارزشی دان است که دارای مقادیر T (rue)، F (alse)، B (oth) و N (either) است. که F معادل 0، T معادل 1، B معادل ∧ و N معادل ∨ است.

• F < B < T یعنی عطف دو گزاره ارزشی بین 0 و 1 دارد،
• F < N < T یعنی فصل دو گزاره ارزشی بین 0 و 1 دارد و
• B و N قابل مقایسه نیستند.

جبر کلینی

اگر جبر دمورگان علاوه بر قوانین قبلی دارای قوانین مقابل باشد x ∧ ¬x ≤ y ∨ ¬y، به آن جبر کلینی می گویند.^۱][۲] (این مفهوم نباید با مفهوم دیگر کلینی در عبارات منظم اشتباه شود.) این مفهوم همچنین به عنوان یک عادی i- لاتیس نوشته شده توسط کالمن شناخته می شود.

مثال‌هایی از جبرهای کلینی (به معنایی که در بالا تعریف شد) عبارتند از: گروه‌های مرتب‌شده با لاتیس، جبرهای پُست و جبرهای  ووکاشیه‌ویچ. (این ساختارهای جبری، ویژگی‌های خاصی دارند که آنها را در دسته‌ی جبرهای کلینی قرار می‌دهد.  برای مثال، همه‌ی آنها دارای عملگرهایی هستند که مشابه "و"، "یا" و "نقیض" در منطق عمل می‌کنند و خواص موجود در آنها را برآورده می کند.) جبرهای بولی نیز طبق این تعریف، خواص جبر کلینی را برآورده می‌کنند. (جبرهای بولی، جبرهای کلینی هستند که در آنها قانون وسط حذف شده و قانون عدم تناقض برقرار است.) ساده‌ترین جبر کلینی غیر بولی، منطق سه‌ارزشی کلینی (K3) است. K3 برای اولین بار در مقاله‌ی کلینی با عنوان "درباره‌ی نمادگذاری برای اعداد ترتیبی" (۱۹۳۸) ظاهر شد. این جبر توسط بریگنول و مونتیرو به نام کلینی نامگذاری شد.

جبرهای دِمورگان تنها راه درست و ممکن برای تعمیم و گسترش جبرهای بولی نیستند. راه دیگر این است که ¬x ∧ x = 0 (یعنی قانون عدم تناقض) را حفظ کنیم، اما قانون وسط حذف شده و قانون نقیض مضاعف را کنار بگذاریم. این رویکرد (که نیم-مکمل‌سازی نامیده می‌شود) حتی برای یک نیم-لاتیس (با عمل "و") نیز خوش تعریف است(قانونی برای اثبات تابع بودن)؛ اگر مجموعه‌ی نیم-مکمل‌ها یک عضو بزرگترین داشته باشد، معمولاً شبه‌مکمل نامیده می‌شود. اگر شبه‌مکمل قانون وسط حذف شده را داشته باشد، جبر حاصل نیز بولی خواهد بود. با این حال، اگر فقط قانون ضعیف‌تر ¬x ∨ ¬¬x = 1  برآورده شود، جبرهای استون حاصل می‌شوند. به‌طور کلی‌تر، هم جبرهای دِمورگان و هم جبرهای استون، زیرمجموعه‌های مناسبی از جبرهای اکهام هستند.

(تعریفی خلاصه برای برخی اصطلاحات به کار رفته:

نیم-مکمل‌سازی: در این رویکرد، به‌جای اینکه نقیض یک عنصر، مکمل کامل آن باشد (مانند جبرهای بولی)، تنها یک "نیم-مکمل" برای آن در نظر گرفته می‌شود که قانون عدم تناقض را برآورده کند.

نیم-لاتیس: یک ساختار جبری با یک عمل دوتایی (معمولاً "و") که دارای خواص شرکت‌پذیری و جابه‌جایی است.

شبه‌مکمل: بزرگترین نیم-مکمل یک عنصر.

قانون نقیض مضاعف: این قانون بیان می‌کند که ¬¬p معادل p است.

جبرهای استون: نوعی جبر که قانون عدم تناقض و قانون ضعیف‌تر  ¬x ∨ ¬¬x = 1  را برآورده می‌کند.

جبرهای اکهام: نوعی جبر کلی‌تر که جبرهای دِمورگان و استون زیرمجموعه‌هایی از آن هستند.)

همچنین ببینید

• orthocomplemented lattice