پیش‌نویس:جبر دمورگان
جبر دمورگان در ریاضیات یک ساختار منطقی است شامل 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) است.
اگر یک ساختار به صورت ترتیبی تعریف شود، یعنی در آن (A, ≤) یک ترتیب جزئی محدود باشد که برای هر جفت عنصر، حد بالایی کمینه (least upper bound) یا همان سوپریموم و حد پایینی بیشینه یا همان اینفیموم (greatest lower bound) وجود داشته باشد، و عملیات‌های "ملاقات" (meet) که برای بدست آوردن اینفیموم است و "پیوست" (join) که برای بدست آوردن سوپریموم است را داشته باشد که به این ترتیب تعریف شده‌اند و قانون توزیع یا همان پخشی را برای این دو عملگر رعایت کنند، آنگاه می‌توان مکمل‌سازی را به عنوان یک ضد-اتومورفیسم تعریف کرد.
- (الف، ≤) یک ساختار لاتیس محدود است و
- ¬¬ x = x ، و
- x ≤ y → ¬ y ≤ ¬ x .
تعریف لاتیس: در ریاضیات و به‌ویژه در هندسه و «نظریه هندسی اعداد» (Geometry of numbers)، به یک «گروه گسسته» (Discrete Group) در فضای اعداد حقیقی (چند بُعدی)، «مشبکه» (Lattice) یا «توری» گفته می‌شود. یک مشبکه می‌تواند با ترکیبات خطی (با ضرایب صحیح) از چندین بردار ایجاد شود که در نتیجه به چنین مجموعه‌‌ای با کمترین تعداد از بردارها، «پایه مشبکه» (Lattice Basis) می‌گویند
جبرهای دِمورگان حدود سال ۱۹۳۵ توسط گریگوره مویسیل معرفی شدند، هرچند در ابتدا بدون محدودیت داشتن ۰ و ۱ معرفی شده بودند و لزومی به داشتنگزاره همیشه درست یا گزاره همیشه غلط در این ساختار ها نبود. (۰ و ۱ در اینجا به کوچکترین و بزرگترین عضو جبر اشاره دارند. در جبرهای دِمورگان امروزی، وجود ۰ و ۱ الزامی است، اما در ابتدا مویسیل این شرط را قرار نداده بود.) بعدها، این جبرها در مدارس لهستانی (به عنوان مثال توسط راسیووا) با نام‌های مختلفی مانند "جبرهای شبه-بولی" و همچنین توسط جی. ای. کالمن "i-لاتیس توزیعی" نامیده شدند. (i-لاتیس مخفف "لاتیس با دگرگونی" است. لاتیس یک ساختار جبری است که در آن هر دو عضو دارای کوچکترین کران بالا و بزرگترین کران پایین یا همان سوپریموم و اینفیموم که توضیح داده شد هستند. دگرگونی یا Involution یک نوع عملگر خاص در جبر است. در جبرهای دِمورگان، نقیض ¬ نقش دگرگونی را بازی میکند و ارزش گزاره ها را برعکس یا دگرگون میکنند.) این جبرها همچنین در مدرسه‌ی منطق جبری آرژانتینی توسط آنتونیو مونتیرو مورد مطالعات بیشتری قرار گرفته و گسترش یافتند.
جبر های دمورگان در مطالعه ابعاد مختلف جبر فازی اهمیت دارند. جبر فازی استاندارد یک ساختار شامل F = ([0, 1], max(x, y), min(x, y), 0, 1, 1 − x) است که مثالی از جبر های دمورگان است که شامل قانون وسط حذف شده (¬x ∨ x = 1) و عدم تناقض (¬x ∧ x = 0) نیست ولی در بقیه قوانین صدق می کند و برتری که نسبت به جبر های بولی دارد این است که شامل تمام مقادیر بین 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 را برآورده میکند.
جبرهای اکهام: نوعی جبر کلی‌تر که جبرهای دِمورگان و استون زیرمجموعه‌هایی از آن هستند.
همچنین ببینید
[ویرایش]- شبکه ارتوکمپلنت شده