الجبر البولياني (البنية)

في الرياضيات ، يُعرف الجبر البولياني أو الشبكة البوليانية بأنه شبكة توزيعية مكملة . يجسد هذا النوع من البنية الجبرية الخصائص الأساسية لكل من عمليات المجموعات والعمليات المنطقية . يمكن اعتبار الجبر البولياني تعميمًا لجبر مجموعات القوى أو حقل المجموعات ، أو يمكن اعتبار عناصره قيمًا حقيقية معممة . كما أنه حالة خاصة من جبر دي مورغان وجبر كلين (مع الانعكاس) .

كل جبر بولياني يُنتج حلقة بوليانية ، والعكس صحيح، حيث يُقابل ضرب الحلقة الاقتران أو التقاطع ∧، وتُقابل جمع الحلقة الفصل الحصري أو الفرق المتناظر (ليس الفصل ∨). ومع ذلك، فإن نظرية الحلقات البوليانية تنطوي على عدم تناظر جوهري بين هذين العاملين، بينما تُعبّر بديهيات ونظريات الجبر البولياني عن تناظر النظرية الموصوفة بمبدأ الازدواجية . ^{[ 1 ]}

تاريخ

يُنسب مصطلح "الجبر البولياني" إلى جورج بول (1815-1864)، عالم الرياضيات الإنجليزي العصامي. قدّم بول هذا النظام الجبري في البداية في كتيب صغير بعنوان "التحليل الرياضي للمنطق" ، نُشر عام 1847 ردًا على جدل عام قائم بين أوغسطس دي مورغان وويليام هاميلتون ، ثم في كتاب أكثر شمولًا بعنوان " قوانين الفكر "، نُشر عام 1854. يختلف صياغة بول عن الصياغة المذكورة أعلاه في بعض الجوانب المهمة. فعلى سبيل المثال، لم يكن الربط والفصل في جبر بول عمليتين متناظرتين. ظهر الجبر البولياني في ستينيات القرن التاسع عشر، في أبحاث كتبها ويليام جيفونز وتشارلز ساندرز بيرس .

يعود الفضل في أول عرض منهجي للجبر البولياني والشبكات التوزيعية إلى محاضرات إرنست شرودر عام 1890. أما أول معالجة شاملة للجبر البولياني باللغة الإنجليزية فهي كتاب "الجبر الشامل" لـ أ. ن. وايتهيد عام 1898. بدأ الجبر البولياني كبنية جبرية بديهية بالمعنى البديهي الحديث مع ورقة بحثية لإدوارد ف . هنتنغتون عام 1904. ^[²^] بلغ الجبر البولياني مرحلة النضج كفرع جاد من الرياضيات مع أعمال مارشال ستون في ثلاثينيات القرن العشرين، ومع نظرية الشبكات لغاريت بيركوف عام 1940. في ستينيات القرن العشرين، توصل بول كوهين ودانا سكوت وآخرون إلى نتائج جديدة عميقة في المنطق الرياضي ونظرية المجموعات البديهية باستخدام فروع من الجبر البولياني، وتحديدًا نماذج الإجبار والنماذج ذات القيم البوليانية .

تعريف

الجبر البولياني هو مجموعة A $،$ مزودة بعمليتين ثنائيتين $\land$ (تسمى "التقاء" أو "و")، $و\lor$ (تسمى "الضم" أو "أو")، وعملية أحادية $\neg (تسمى "المكمل" أو "ليس")$ $،$ وعنصرين $0$ و $1$ في $A$ (يسميان "الأسفل" و"الأعلى"، أو "العنصر الأصغر" و"العنصر الأكبر"، ويرمز لهما أيضًا بالرمزين $⊥$ و⊤ على التوالي)، بحيث تتحقق البديهيات التالية لجميع العناصر $a$ و $b$ و $c$ من $A$ : ^[³^]

$a \lor (b \lor c) = (a \lor b) \lor c$	$أ \land (ب \land ج) = (أ \land ب) \land ج$	الترابطية
$أ \lor ب = ب \lor أ$	$أ \land ب = ب \land أ$	خاصية التبادلية
$أ \lor (أ \land ب) = أ$	$a \land (a \lor b) = a$	امتصاص
$a \lor 0 = a$	$أ \land ١ = أ$	هوية
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	خاصية التوزيع
$أ \lor \neg أ = 1$	$a \land \neg a = 0$	مكملات

لاحظ، مع ذلك، أنه يمكن استبعاد قانون الامتصاص وحتى قانون التجميع من مجموعة البديهيات حيث يمكن اشتقاقها من البديهيات الأخرى (انظر الخصائص المثبتة ).

يُطلق على الجبر البولياني الذي يحتوي على عنصر واحد فقط اسم الجبر البولياني التافه أو الجبر البولياني المنحط . (في الأعمال القديمة، اشترط بعض المؤلفين أن يكون $0$ و $1 عنصرين$ مختلفين لاستبعاد هذه الحالة).

ويترتب على ذلك من أزواج البديهيات الثلاثة الأخيرة المذكورة أعلاه (الهوية، والتوزيعية، والمكملات)، أو من بديهية الامتصاص، أن

a = b \land a

إذا وفقط إذا كان

a

\lor

b

=

b

.

العلاقة $\leq$ المعرفة بواسطة $a \leq b$ إذا تحققت هذه الشروط المتكافئة، هي ترتيب جزئي بأصغر عنصر 0 وأكبر عنصر 1. يتطابق التقاطع $a \land b$ والوصل $a \lor b$ لعنصرين مع أدنى وأعلى قيمهما ، على التوالي، بالنسبة إلى ≤.

تشكل الأزواج الأربعة الأولى من البديهيات تعريفًا للشبكة المحدودة .

ويترتب على أول خمسة أزواج من البديهيات أن أي مكمل فريد من نوعه.

مجموعة البديهيات ذاتية التناظر ، بمعنى أنه إذا استبدلنا $\lor$ بـ $\land$ و $0$ بـ $1$ في بديهية ما، فإن النتيجة تكون بديهية أخرى. لذلك، بتطبيق هذه العملية على جبر بولياني (أو شبكة بوليانية)، نحصل على جبر بولياني آخر بنفس العناصر؛ ويُسمى هذا الجبر ثنائيته . ^{[ 4 ]}

أمثلة

أبسط أنواع الجبر البولياني غير التافه، وهو الجبر البولياني ذو العنصرين ، يحتوي على عنصرين فقط، $0$ و $1$ ، ويتم تعريفه بالقواعد التالية:

$\land$	$0$	$1$
$0$	$0$	$0$
$1$	$0$	$1$

$\lor$	$0$	$1$
$0$	$0$	$1$
$1$	$1$	$1$

$أ$	$0$	$1$
$\neg أ$	$1$	$0$

تُستخدم هذه القاعدة في المنطق ، حيث تُفسَّر القيمة $0$ على أنها خطأ ، $والقيمة 1$ على أنها صواب ، $وعلامة \land$ على أنها " و" ، $وعلامة \lor$ على أنها "أو "، وعلامة ¬ على أنها $"$ ليس" . تمثل التعبيرات التي تتضمن متغيرات وعمليات منطقية صيغًا جملية، ويمكن إثبات تساوي تعبيرين من هذا النوع باستخدام البديهيات المذكورة أعلاه إذا وفقط إذا كانت الصيغ الجملية المقابلة متكافئة منطقيًا .

يُستخدم الجبر البولياني ثنائي العناصر أيضًا في تصميم الدوائر الكهربائية ؛ ^{[ ملاحظة 1 ]} حيث يُمثل 0 و1 حالتين مختلفتين لبت واحد في دائرة رقمية ، وعادةً ما تكونان جهدًا عاليًا ومنخفضًا . تُوصف الدوائر بتعبيرات تحتوي على متغيرات، ويتساوى تعبيران من هذا النوع لجميع قيم المتغيرات إذا وفقط إذا كانت الدوائر المقابلة لها نفس سلوك الإدخال والإخراج. علاوة على ذلك، يمكن نمذجة كل سلوك إدخال وإخراج ممكن بتعبير بولياني مناسب.

يُعدّ الجبر البولياني ذو العنصرين مهمًا أيضًا في النظرية العامة للجبر البولياني، لأن المعادلة التي تتضمن عدة متغيرات تكون صحيحة عمومًا في جميع أنواع الجبر البولياني إذا وفقط إذا كانت صحيحة في الجبر البولياني ذي العنصرين (وهو ما يمكن التحقق منه باستخدام خوارزمية بحث شاملة بسيطة لأعداد صغيرة من المتغيرات). ويمكن استخدام ذلك، على سبيل المثال، لإثبات أن القوانين التالية ( نظريات التوافق ) صحيحة عمومًا في جميع أنواع الجبر البولياني:
- $(أ \lor ب) \land (\negأ \lor ج) \land (ب \lor ج) \equiv (أ \lor ب) \land (\negأ \lor ج)$
- $(أ \land ب) \lor (\negأ \land ج) \lor (ب \land ج) \equiv (أ \land ب) \lor (\negأ \land ج)$

تُشكّل مجموعة القوى (مجموعة جميع المجموعات الجزئية) لأي مجموعة غير فارغة $S$ جبرًا بوليانيًا، وهو جبر المجموعات ، مع العمليتين $\lor := \cup$ (الاتحاد) و $\land := \cap$ (التقاطع). أصغر عنصر هو 0 يُمثّل المجموعة الفارغة ، وأكبر عنصر هو $1$ يُمثّل المجموعة $S$ نفسها.

بعد الجبر البولياني ذي العنصرين، فإن أبسط أنواع الجبر البولياني هو ذلك المحدد بواسطة مجموعة القوى لذرتين:

$\land$	$0$	$أ$	$ب$	$1$
$0$	$0$	$0$	$0$	$0$
$أ$	$0$	$أ$	$0$	$أ$
$ب$	$0$	$0$	$ب$	$ب$
$1$	$0$	$أ$	$ب$	$1$

$\lor$	$0$	$أ$	$ب$	$1$
$0$	$0$	$أ$	$ب$	$1$
$أ$	$أ$	$أ$	$1$	$1$
$ب$	$ب$	$1$	$ب$	$1$
$1$	$1$	$1$	$1$	$1$

$x$	$0$	$أ$	$ب$	$1$
$\neg x$	$1$	$ب$	$أ$	$0$

تُعرف المجموعة $A$ ، التي تضم جميع المجموعات الجزئية من $S$ التي تكون إما منتهية أو متقاربة في النهاية، بأنها جبر بولياني وجبر للمجموعات يُسمى جبر المجموعات المنتهية والمتقاربة في النهاية . إذا كانت $S$ لانهائية، فإن مجموعة جميع المجموعات الجزئية المتقاربة في النهاية من $S$ ، والتي تُسمى مرشح فريشيه ، تُشكل مرشحًا فائقًا حرًا على $A.$ مع ذلك، فإن مرشح فريشيه ليس مرشحًا فائقًا على مجموعة القوى لـ $S.$
انطلاقًا من حساب القضايا باستخدام رموز الجمل $κ ، تُشكَّل$ جبر ليندنبوم (أي مجموعة الجمل في حساب القضايا بتردد التكافؤ المنطقي ). ينتج عن هذا البناء جبر بولياني، وهو في الواقع الجبر البولياني الحر على مولدات $κ$ . وبالتالي، فإن تعيين الصدق في حساب القضايا هو تشاكل جبر بولياني من هذا الجبر إلى الجبر البولياني ذي العنصرين.
بالنظر إلى أي مجموعة مرتبة خطيًا $L$ ذات عنصر أصغر، فإن جبر الفترات هو أصغر جبر بولياني للمجموعات الجزئية من $L$ التي تحتوي على جميع الفترات نصف المفتوحة $[a, b)$ بحيث يكون $a$ في $L$ و $b$ إما في $L$ أو يساوي $\infty$ . تُعد جبر الفترات مفيدة في دراسة جبر ليندنبوم-تارسكي ؛ فكل جبر بولياني قابل للعد متماثل مع جبر فترات.

لأي عدد طبيعي $n$ ، تُشكّل مجموعة جميع القواسم الموجبة لـ $n$ ، والتي تُعرّف $a \leq b$ إذا كان $a$ يقسم $b$ ، شبكة توزيعية . تُسمى هذه الشبكة جبرًا بوليانيًا إذا وفقط إذا كان $n$ خاليًا من المربعات . العنصران السفلي والعلوي لهذا الجبر البولياني هما العددان الطبيعيان $1$ و $n$ على التوالي. مُتمّم $a$ يُعطى بالصيغة $n / a$ . يُعطى تقاطع $a$ و $b$ بالصيغة القاسم المشترك الأكبر ( $gcd$ ) والمضاعف المشترك الأصغر ( $lcm$ ) لـ $a$ و $b$ على التوالي. يُعطى جمع الحلقة $a + b$ $بالصيغة lcm(a, b) / gcd(a, b)$ . يُظهر الشكل مثالًا لـ $n = 30.$ كمثال مضاد، عند النظر إلى $n = 60$ غير الخالي من المربعات ، سيكون القاسم المشترك الأكبر لـ 30 ومُتمّمه 2 هو 2، بينما يجب أن يكون العنصر السفلي 1.
تنشأ أمثلة أخرى للجبر البولياني من الفضاءات الطوبولوجية : إذا كان $X$ فضاءً طوبولوجيًا، فإن مجموعة جميع المجموعات الفرعية من $X$ التي تكون مفتوحة ومغلقة تشكل جبرًا بوليانيًا مع العمليات $\lor := \cup$ (الاتحاد) و $\land := \cap$ (التقاطع).
إذا كانت $R$ حلقة عشوائية، فإن مجموعة العناصر المركزية المتساوية القوة فيها هي مجموعة

$A=\left\{e\in R:e^{2}=e{\text{ و }}ex=xe\;{\text{ لجميع }}\;x\in R\right\},$ يصبح جبرًا منطقيًا عندما يتم تعريف عملياته بواسطة $e \lor f := e + f - ef$ و $e \land f := ef$ .

التشاكلات والتماثلات

التشاكل بين جبرين بوليانيين $A$ و $B$ هو دالة $f$ $:$ $A$ $\to$ $B$ بحيث يكون لكل $a$ و $b$ في $A$ :

f (a \lor b) = f (a) \lor f (b)

,

f (a \land b) = f (a) \land f (b)

,

f (0) = 0

,

f (1) = 1

.

ويترتب على ذلك أن $f (\neg a) = \neg f (a)$ لجميع $a$ في $A.$ تشكل فئة جميع الجبر البولياني، جنبًا إلى جنب مع مفهوم التشكل هذا، فئة فرعية كاملة من فئة الشبكات.

التشاكل بين جبرين بوليانيين $A$ و $B$ هو تشاكل $f$ $:$ $A$ $\to$ $B$ مع تشاكل عكسي، أي تشاكل $g$ $:$ $B$ → $A$ بحيث يكون $التركيب$ g $\circ$ $f$ $:$ $A$ $\to$ $A$ $دالة$ التطابق على A $،$ والتركيب $f$ $\circ$ $g$ $:$ $B$ $\to$ $B$ دالة التطابق على $B.$ يكون تشاكل الجبر البولياني متماثلاً إذا وفقط إذا كان تقابلياً .

حلقات منطقية

كل جبر بولياني $(A, \land, \lor)$ يُنتج حلقة $(A, +, \cdot)$ بتعريف $a + b := (a \land \negb) \lor (b \land \nega) = (a \lor b) \land \neg(a \land b)$ (تُسمى هذه العملية بالفرق المتناظر في حالة المجموعات و XOR في حالة المنطق) و $a \cdot b := a \land b$ . العنصر الصفري لهذه الحلقة يُطابق الصفر في الجبر البولياني؛ والعنصر المحايد الضربي للحلقة هو $الواحد$ في الجبر البولياني. تتميز هذه الحلقة بالخاصية $a \cdot a = a$ لكل $a$ في $A$ ؛ وتُسمى الحلقات التي تتمتع بهذه الخاصية بالحلقات البوليانية .

على النقيض، إذا عُلمت حلقة بولية $A$ ، يُمكننا تحويلها إلى جبر بولي بتعريف $x \lor y := x + y + (x \cdot y)$ و $x \land y := x \cdot y$ . ^{[ 5 ]}^{[ 6 ]} ولأن هذين البناءين معكوسان لبعضهما، يُمكننا القول إن كل حلقة بولية تنشأ من جبر بولي، والعكس صحيح. علاوة على ذلك، فإن التطبيق $f : A \to B$ يكون تشاكلاً بين الجبر البولي إذا وفقط إذا كان تشاكلاً بين الحلقات البولية. فئات الحلقات البولية والجبر البولي متكافئة ؛ ^{[ 7 ]} بل إن الفئات متماثلة .

قدم هسيانغ (1985) خوارزمية قائمة على القواعد للتحقق مما إذا كان تعبيران عشوائيان يدلان على نفس القيمة في كل حلقة منطقية. ^{[ 8 ]}

وبشكل أعم، قدم بوديه، وجوانود ، وشميدت-شاوس (1989) ^{[ 9 ]} خوارزمية لحل المعادلات بين تعبيرات الحلقة البوليانية العشوائية. وباستخدام تشابه الحلقات البوليانية والجبر البولياني، فإن لكلتا الخوارزميتين تطبيقات في إثبات النظريات الآلي .

المُثُل والفلاتر

المثالي في الجبر البولياني $A$ هو مجموعة جزئية غير فارغة $I$ بحيث أنه لكل $x$ و $y$ في $I،$ يكون x $\lor$ $y$ $في$ I $،$ ولكل $a$ في $A،$ يكون $a$ $\land$ $x$ في $I.$ يتطابق مفهوم المثالي هذا مع مفهوم مثالي الحلقة في الحلقة البوليانية $A.$ يُسمى المثالي $I$ في $A$ أوليًا إذا $كان I$ $\neq$ $A$ ، وإذا كان $a$ $\land$ $b$ في $I$ يستلزم دائمًا $a$ في $I$ أو $b$ في $I.$ علاوة على ذلك، لكل $a$ $\in$ $A$ $،$ يكون $a$ $\land$ $-a$ $= 0 \in$ $I$ ، وبالتالي إذا كان $I$ أوليًا، يكون $a$ $\in$ $I$ أو $-a$ $\in$ $I$ لكل $a$ $\in$ $A.$ يُسمى المثالي $I$ في $A$ أعظميًا إذا $كان I$ $\neq$ $A،$ $وإذا$ كان المثالي الوحيد الذي يحتوي $I$ بشكل صحيح هو $A$ نفسه. بالنسبة للمثالي $I$ ، إذا كان $a$ $\notin$ $I$ و $-a$ $\notin$ $I$ ، فإن $I$ $\cup {$ $a$ $}$ أو $I$ $\cup {$ $-a$ $}$ $يكون$ محصورًا في مثالي مناسب آخر $J.$ وبالتالي، فإن هذا المثالي $I ليس مثاليًا أعظميًا، ومن ثم$ $فإن$ مفهومي المثالي الأولي والمثالي الأعظمي متكافئان في الجبر البولياني. علاوة على ذلك، يتطابق هذان المفهومان مع المفهومين النظريين للمثالي الأولي والمثالي الأعظمي في الحلقة البوليانية $A.$

إنّ ثنائيّ المثاليّ هو مُرشِّح . مُرشِّح الجبر البوليانيّ $A$ هو مجموعة جزئية غير فارغة $p$ بحيث يكون لكلّ $x$ و $y$ في $p$ ، يكون $x \land y$ في $p،$ ولكلّ $a$ في $A،$ يكون $a \lor x$ في $p$ . ثنائيّ المثاليّ الأعظميّ (أو الأوّليّ ) في الجبر البوليانيّ هو مُرشِّح فائق . يمكن وصف المُرشِّحات الفائقة، بدلاً من ذلك، بأنّها تشاكلات ثنائية القيم من $A$ إلى الجبر البوليانيّ ثنائيّ العناصر. تُسمّى العبارة التي تنصّ على إمكانية تمديد كلّ مُرشِّح في الجبر البوليانيّ إلى مُرشِّح فائق بـ" مُبرهنة المُرشِّح الفائق" ، ولا يُمكن إثباتها في نظرية زيرميلو-فرانكل للمجموعات (ZF)، إذا كانت ZF متّسقة . ضمن ZF، تُعتبر مُبرهنة المُرشِّح الفائق أضعف من بديهيّة الاختيار . تحتوي مبرهنة المرشح الفائق على العديد من الصيغ المكافئة: كل جبر بولياني له مرشح فائق ، ويمكن تمديد كل مثالي في الجبر البولياني إلى مثالي أولي ، إلخ.

التمثيلات

يمكن إثبات أن كل جبر بولياني منتهٍ متماثل مع الجبر البولياني لجميع المجموعات الجزئية لمجموعة منتهية. وبالتالي، فإن عدد عناصر كل جبر بولياني منتهٍ هو قوة للعدد اثنين .

تنص نظرية تمثيل ستون للجبر البولياني على أن كل جبر بولياني $A$ متماثل مع الجبر البولياني لجميع المجموعات المفتوحة والمغلقة في فضاء طوبولوجي ( هاوسدورف مضغوط ومنفصل تمامًا ). ^[¹⁰^]

البديهيات

خصائص مثبتة

المعرف الفريد ₁		إذا كان x ∨ o = x لجميع قيم x ، فإن o = 0
دليل:		إذا كان x ∨ o = x ، فإن
		0
	=	0 ∨ o	بافتراض
	=	o ∨ 0	بواسطة Cmm ₁
	=	o	بواسطة Idn ₁

UId ₂ [dual] إذا كان x ∧ i = x لجميع قيم x ، فإن i = 1

Idm ₁		x ∨ x = x
دليل:		x ∨ x
	=	( x ∨ x ) ∧ 1	بواسطة Idn ₂
	=	( x ∨ x ) ∧ ( x ∨ ¬ x )	بقلم العريف ₁
	=	x ∨ ( x ∧ ¬ x )	بواسطة Dst ₁
	=	x ∨ 0	بقلم العريف _الثاني
	=	x	بواسطة Idn ₁

Idm ₂ [dual] x ∧ x = x

المجلد ₁		x ∨ 1 = 1
دليل:		x ∨ 1
	=	( x ∨ 1) ∧ 1	بواسطة Idn ₂
	=	1 ∧ ( x ∨ 1)	بواسطة Cmm ₂
	=	( x ∨ ¬ x ) ∧ ( x ∨ 1)	بقلم العريف ₁
	=	x ∨ (¬ x ∧ 1)	بواسطة Dst ₁
	=	x ∨ ¬ x	بواسطة Idn ₂
	=	1	بقلم العريف ₁

Bnd ₂ [dual] x ∧ 0 = 0

Abs ₁		x ∨ ( x ∧ y ) = x
دليل:		x ∨ ( x ∧ y )
	=	( x ∧ 1) ∨ ( x ∧ y )	بواسطة Idn ₂
	=	x ∧ (1 ∨ y )	بواسطة Dst ₂
	=	x ∧ ( y ∨ 1)	بواسطة Cmm ₁
	=	x ∧ 1	بواسطة Bnd ₁
	=	x	بواسطة Idn ₂

Abs ₂ [dual] x ∧ ( x ∨ y ) = x

الأمم المتحدة		إذا كان x ∨ x _n = 1 و x ∧ x _n = 0، فإن x _n = ¬ x
دليل:		إذا كان x ∨ x _n = 1 و x ∧ x _n = 0، فإن
		س _ن
	=	x _n ∧ 1	بواسطة Idn ₂
	=	x _n ∧ ( x ∨ ¬ x )	بقلم العريف ₁
	=	( x _n ∧ x ) ∨ ( x _n ∧ ¬ x )	بواسطة Dst ₂
	=	( x ∧ x _n ) ∨ (¬ x ∧ x _n )	بواسطة Cmm ₂
	=	0 ∨ (¬ x ∧ x _n )	بافتراض
	=	( x ∧ ¬ x ) ∨ (¬ x ∧ x _n )	بقلم العريف _الثاني
	=	(¬ x ∧ x ) ∨ (¬ x ∧ x _n )	بواسطة Cmm ₂
	=	¬ x ∧ ( x ∨ x _n )	بواسطة Dst ₂
	=	¬ x ∧ 1	بافتراض
	=	¬ x	بواسطة Idn ₂

دي إن جي		¬¬ x = x
دليل:		¬ x ∨ x = x ∨ ¬ x = 1	بواسطة Cmm ₁ ، Cpl ₁
	و	¬ x ∧ x = x ∧ ¬ x = 0	بواسطة Cmm ₂ ، Cpl ₂
	لذلك	x = ¬¬ x	بواسطة UNg

أ ₁		x ∨ (¬ x ∨ y ) = 1
دليل:		x ∨ (¬ x ∨ y )
	=	( x ∨ (¬ x ∨ y )) ∧ 1	بواسطة Idn ₂
	=	1 ∧ ( x ∨ (¬ x ∨ y ))	بواسطة Cmm ₂
	=	( x ∨ ¬ x ) ∧ ( x ∨ (¬ x ∨ y ))	بقلم العريف ₁
	=	x ∨ (¬ x ∧ (¬ x ∨ y ))	بواسطة Dst ₁
	=	x ∨ ¬ x	بواسطة Abs ₂
	=	1	بقلم العريف ₁

A ₂ [dual] x ∧ (¬ x ∧ y ) = 0

ب ₁		( x ∨ y ) ∨ (¬ x ∧ ¬ y ) = 1
دليل:		( س ∨ ص ) ∨ (¬ س ∧ ¬ ذ )
	=	(( x ∨ y ) ∨ ¬ x ) ∧ (( x ∨ y ) ∨ ¬ y )	بواسطة Dst ₁
	=	(¬ س ∨ ( س ∨ ص )) ∧ (¬ ذ ∨ ( ص ∨ س ))	بواسطة Cmm ₁
	=	(¬ س ∨ (¬¬ س ∨ ص )) ∧ (¬ ص ∨ (¬¬ ص ∨ س ))	بقلم دي إن جي
	=	1 ∧ 1	بواسطة A ₁
	=	1	بواسطة Idn ₂

B ₂ [dual] ( x ∧ y ) ∧ (¬ x ∨ ¬ y ) = 0

ج ₁		( x ∨ y ) ∧ (¬ x ∧ ¬ y ) = 0
دليل:		( س ∨ ص ) ∧ (¬ س ∧ ¬ ذ )
	=	(¬ س ∧ ¬ ذ ) ∧ ( س ∨ ص )	بواسطة Cmm ₂
	=	((¬ x ∧ ¬ y ) ∧ x ) ∨ ((¬ x ∧ ¬ y ) ∧ y )	بواسطة Dst ₂
	=	( س ∧ (¬ س ∧ ¬ y )) ∨ ( y ∧ (¬ y ∧ ¬ x ))	بواسطة Cmm ₂
	=	0 ∨ 0	بواسطة A ₂
	=	0	بواسطة Idn ₁

C ₂ [dual] ( x ∧ y ) ∨ (¬ x ∨ ¬ y ) = 1

DMg ₁		¬( x ∨ y ) = ¬ x ∧ ¬ y
دليل:		بواسطة B ₁ و C ₁ و UNg

DMg ₂ [dual] ¬( x ∧ y ) = ¬ x ∨ ¬ y

د ₁		( x ∨( y ∨ z )) ∨ ¬ x = 1
دليل:		( x ∨ ( y ∨ z )) ∨ ¬ x
	=	¬ x ∨ ( x ∨ ( y ∨ z ))	بواسطة Cmm ₁
	=	¬ x ∨ (¬¬ x ∨ ( y ∨ z ))	بقلم دي إن جي
	=	1	بواسطة A ₁

D ₂ [dual] ( x ∧( y ∧ z )) ∧ ¬ x = 0

E ₁		y ∧ ( x ∨( y ∨ z )) = y
دليل:		y ∧ ( x ∨ ( y ∨ z ))
	=	( ذ ∧ س ) ∨ ( ذ ∧ ( ذ ∨ ض ))	بواسطة Dst ₂
	=	( y ∧ x ) ∨ y	بواسطة Abs ₂
	=	y ∨ ( y ∧ x )	بواسطة Cmm ₁
	=	y	بواسطة Abs ₁

E ₂ [ثنائي] y ∨ ( x ∧( y ∧ z ) ) = y

F ₁		( س ∨( ذ ∨ ض )) ∨ ¬ ص = 1
دليل:		( x ∨ ( y ∨ z )) ∨ ¬ y
	=	¬ y ∨ ( x ∨ ( y ∨ z ))	بواسطة Cmm ₁
	=	(¬ ذ ∨ ( س ∨ ( ذ ∨ ض ))) ∧ 1	بواسطة Idn ₂
	=	1 ∧ (¬ ذ ∨ ( س ∨ ( ذ ∨ ض )))	بواسطة Cmm ₂
	=	( ذ ∨ ¬ ذ ) ∧ (¬ ذ ∨ ( س ∨ ( ذ ∨ ض )))	بقلم العريف ₁
	=	(¬ ذ ∨ ذ ) ∧ (¬ ذ ∨ ( س ∨ ( ذ ∨ ض )))	بواسطة Cmm ₁
	=	¬ ذ ∨ ( ذ ∧ ( س ∨ ( ذ ∨ ض )))	بواسطة Dst ₁
	=	¬ y ∨ y	بواسطة E ₁
	=	y ∨ ¬ y	بواسطة Cmm ₁
	=	1	بقلم العريف ₁

F ₂ [dual] ( x ∧( y ∧ z )) ∧ ¬ y = 0

G ₁		( x ∨( y ∨ z )) ∨ ¬ z = 1
دليل:		( x ∨ ( y ∨ z )) ∨ ¬ z
	=	( x ∨ ( z ∨ y )) ∨ ¬ z	بواسطة Cmm ₁
	=	1	بواسطة F ₁

G ₂ [dual] ( x ∧( y ∧ z )) ∧ ¬ z = 0

H ₁		¬(( x ∨ y )∨ z ) ∧ x = 0
دليل:		¬(( x ∨ y ) ∨ z ) ∧ x
	=	(¬( x ∨ y ) ∧ ¬ z ) ∧ x	بواسطة DMg ₁
	=	((¬ x ∧ ¬ y ) ∧ ¬ z ) ∧ x	بواسطة DMg ₁
	=	x ∧ ((¬ x ∧ ¬ y ) ∧ ¬ z )	بواسطة Cmm ₂
	=	( x ∧ ((¬ x ∧ ¬ y ) ∧ ¬ z )) ∨ 0	بواسطة Idn ₁
	=	0 ∨ ( x ∧ ((¬ x ∧ ¬ y ) ∧ ¬ z ))	بواسطة Cmm ₁
	=	( x ∧ ¬ x ) ∨ ( x ∧ ((¬ x ∧ ¬ y ) ∧ ¬ z ))	بقلم العريف _الثاني
	=	x ∧ (¬ x ∨ ((¬ x ∧ ¬ y ) ∧ ¬ z ))	بواسطة Dst ₂
	=	x ∧ (¬ x ∨ (¬ z ∧ (¬ x ∧ ¬ y )))	بواسطة Cmm ₂
	=	x ∧ ¬ x	بواسطة E ₂
	=	0	بقلم العريف _الثاني

H ₂ [dual] ¬(( x ∧ y )∧ z ) ∨ x = 1

أنا ₁		¬(( x ∨ y )∨ z ) ∧ y = 0
دليل:		¬(( x ∨ y ) ∨ z ) ∧ y
	=	¬(( y ∨ x ) ∨ z ) ∧ y	بواسطة Cmm ₁
	=	0	بواسطة H ₁

I ₂ [dual] ¬(( x ∧ y )∧ z ) ∨ y = 1

J ₁		¬(( x ∨ y )∨ z ) ∧ z = 0
دليل:		¬(( x ∨ y ) ∨ z ) ∧ z
	=	(¬( x ∨ y ) ∧ ¬ z ) ∧ z	بواسطة DMg ₁
	=	z ∧ (¬( x ∨ y ) ∧ ¬ z )	بواسطة Cmm ₂
	=	z ∧ ( ¬ z ∧ ¬( x ∨ y ))	بواسطة Cmm ₂
	=	0	بواسطة A ₂

J ₂ [dual] ¬(( x ∧ y )∧ z ) ∨ z = 1

ك ₁		( x ∨ ( y ∨ z )) ∨ ¬(( x ∨ y ) ∨ z ) = 1
دليل:		( x ∨( y ∨ z )) ∨ ¬(( x ∨ y ) ∨ z )
	=	( x ∨( y ∨ z )) ∨ (¬( x ∨ y ) ∧ ¬ z )	بواسطة DMg ₁
	=	(x∨(y∨z)) ∨ ((¬x ∧ ¬y) ∧ ¬z)	by DMg₁
	=	((x∨(y∨z)) ∨ (¬x ∧ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	by Dst₁
	=	(((x∨(y∨z)) ∨ ¬x) ∧ ((x∨(y∨z)) ∨ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	by Dst₁
	=	(1 ∧ 1) ∧ 1	by D₁,F₁,G₁
	=	1	by Idn₂

K₂ [dual] (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0

L₁		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = 0
Proof:		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z)
	=	¬((x∨y)∨z) ∧ (x ∨ (y ∨ z))	by Cmm₂
	=	(¬((x∨y)∨z) ∧ x) ∨ (¬((x∨y)∨z) ∧ (y ∨ z))	by Dst₂
	=	(¬((x∨y)∨z) ∧ x) ∨ ((¬((x∨y)∨z) ∧ y) ∨ (¬((x∨y)∨z) ∧ z))	by Dst₂
	=	0 ∨ (0 ∨ 0)	by H₁,I₁,J₁
	=	0	by Idn₁

L₂ [dual] (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1

Ass₁		x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z
دليل:		بواسطة K ₁ ، L ₁ ، UNg ، DNg

Ass ₂ [dual] x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z

الاختصارات
المعرف الفريد	هوية فريدة
Idm	العجز الجنسي
Bnd	حدود
ABs	قانون الاستيعاب
الأمم المتحدة	النفي الفريد
دي إن جي	النفي المزدوج
DMg	قانون دي مورغان
مؤخرة	الترابط

بديهيات الجبر البولياني لهنتنغتون عام 1904

الهوية ₁

x ∨ 0 = x

Idn ₂

x ∧ 1 = x

سم ₁

x ∨ y = y ∨ x

سم ₂

x ∧ y = y ∧ x

الوجهة ₁

x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z )

الوجهة ₂

x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z )

العريف ₁

x ∨ ¬ x = 1

العريف ₂

x ∧ ¬ x = 0

الاختصارات
هودن	هوية
سم	التبادلية
التوقيت الصيفي	التوزيعية
عريف	مكملات

قدّم الفيلسوف والرياضي الإنجليزي ألفريد نورث وايتهيد أول مجموعة بديهيات للشبكات/الجبر البولياني بشكل عام عام 1898. ^{[ 11 ]}^{[ 12 ]} وقد تضمنت البديهيات المذكورة أعلاه ، بالإضافة إلى $x \lor 1 = 1$ و $x \land 0 = 0.$ وفي عام 1904، قدّم عالم الرياضيات الأمريكي إدوارد ف. هنتنغتون (1874-1952) على الأرجح أكثر مجموعات البديهيات اقتصادًا، استنادًا إلى $\land$ و $\lor$ و $\neg$ ، بل وأثبت قوانين التجميع (انظر المربع). ^{[ 13 ]} كما أثبت أن هذه البديهيات مستقلة عن بعضها البعض. ^{[ 14 ]}

في عام 1933، وضع هنتنغتون البديهيات الأنيقة التالية للجبر البولياني. ^{[ 15 ]} وهي تتطلب عملية ثنائية واحدة فقط $+$ ورمزًا وظيفيًا أحاديًا $n$ ، يُقرأ على أنه "المكمل"، والذي يحقق القوانين التالية:

خاصية التبديل : $س + ص = ص + س$ .
خاصية التجميع : $(س + ص) + ع = س + (ص + ع)$ .
معادلة هنتنغتون : $n (n (x) + y) + n (n (x) + n (y)) = x$ .

سأل هربرت روبنز على الفور: إذا تم استبدال معادلة هنتنغتون بمعادلتها الثنائية، أي:

معادلة روبنز : $n (n (x + y) + n (x + n (y))) = x$ ،

هل تُشكّل (1) و(2) و(4) أساسًا للجبر البولياني؟ إذا أطلقنا على (1) و(2) و(4) اسم جبر روبنز ، يصبح السؤال: هل كل جبر روبنز هو جبر بولياني؟ ظل هذا السؤال (الذي عُرف فيما بعد باسم حدسية روبنز ) مفتوحًا لعقود، وأصبح سؤالًا مفضلًا لدى ألفريد تارسكي وطلابه.

في عام ١٩٩٦، أجاب ويليام ماكيون في مختبر أرغون الوطني ، مستندًا إلى أعمال سابقة للاري ووس وستيف وينكر وبوب فيروف، على سؤال روبنز بالإيجاب: كل جبر روبنز هو جبر بولياني. وكان برنامج الحاسوب EQP الذي صممه ماكيون عنصرًا أساسيًا في برهانه. للاطلاع على تبسيط لبرهان ماكيون، انظر داهن (١٩٩٨). ^{[ ١٦ ]}

وقد تم بذل المزيد من العمل لتقليل عدد البديهيات؛ انظر البديهيات الدنيا للجبر البولياني .

التعميمات

يؤدي حذف شرط وجود عنصر واحد من بديهيات الجبر البولياني إلى ظهور "جبر بولياني معمّم". رياضيًا، تُعتبر الشبكة التوزيعية $B$ شبكة بوليانية معمّمة إذا كان أصغر عنصر فيها هو $0،$ ولكل عنصرين $a$ و $b$ في $B$ بحيث $a \leq b$ ، يوجد عنصر $x$ بحيث $a \land x = 0$ و $a \lor x = b$ . بتعريف $a \lor b على أنه العنصر$ $x$ الوحيد الذي يحقق $(a \land b) \lor x = a$ و $(a \land b) \land x = 0$ ، نقول إن البنية $(B, \land, \lor, \lor, 0)$ هي جبر بولياني معمّم ، بينما $(B, \lor, 0)$ هي شبه شبكة بوليانية معمّمة . الشبكات البولية المعممة هي بالضبط المثل العليا للشبكات البولية.

يُطلق على البنية التي تُحقق جميع بديهيات الجبر البولياني باستثناء بديهيتي التوزيع اسم الشبكة المتعامدة المُكمِّلة . وتنشأ الشبكات المتعامدة المُكمِّلة بشكل طبيعي في المنطق الكمومي كشبكات من الفضاءات الخطية المغلقة للفضاءات الهيلبرتية القابلة للفصل .

ملحوظات

↑ من الناحية الدقيقة، يميل مهندسو الكهرباء إلى استخدام حالات إضافية لتمثيل ظروف الدائرة الأخرى مثل المعاوقة العالية - انظر IEEE 1164 أو IEEE 1364 .

مراجع

^ جيفانت وهالموس 2009 ، ص. 20.
↑ هانتينغتون 1904 ، ص 288.
↑ Davey & Priestley 1990 ، ص. 109 ، 131 ، 144.
↑ جودستين 2012 ، ص 21 وما بعدها.
↑ ستون 1936. خطأ في ملف sfn: أهداف متعددة (2×): CITEREFStone1936 ( مساعدة )
↑ Hsiang 1985 ، ص 260.
↑ كوهن 2003 ، ص 81 .
↑ هسيانغ، جيه (1985). "إثبات النظريات الدحضية باستخدام أنظمة إعادة كتابة المصطلحات" . الذكاء الاصطناعي . 25 (3): 255-300 . doi : 10.1016/0004-3702(85)90074-8 .
↑ بوديه، أ.؛ جوانو، ج.ب.؛ شميدت-شاوس، م. (1989). "التوحيد في الحلقات البولية والمجموعات الأبيلية" . مجلة الحساب الرمزي . 8 (5): 449-477 . doi : 10.1016/s0747-7171(89)80054-9 .
↑ ستون، إم إتش (1936). "نظرية التمثيل للجبر البولياني" . معاملات الجمعية الرياضية الأمريكية . 40 (1): 37-111 . doi : 10.2307/1989664 . ISSN 0002-9947 .
^ بادمانابهان ورودينو 2008 ، ص. 73 .
↑ وايتهيد 1969 ، ص 37.
↑ هانتينغتون 1904 ، ص 292-293.
↑ هانتينغتون 1904 ، ص 296.
↑ هانتينغتون 1933أ .
↑ داهن، بي آي (1998)، "جبر روبنز هو بولياني: مراجعة لحل ماكيون المُولّد حاسوبيًا لمسألة روبنز"، مجلة الجبر ، 208 (2): 526-532 ، doi : 10.1006/jabr.1998.7467

المراجع

ديفي، بكالوريوس الآداب؛ بريستلي، هـ. أ. (1990). مقدمة في الشبكات والترتيب . كتب كامبريدج الرياضية. مطبعة جامعة كامبريدج.
كوهن، بول م. (2003)، الجبر الأساسي: المجموعات، والحلقات، والحقول ، سبرينغر، الصفحات 51، 70-81 ، ISBN 9781852335878
جيفانت، ستيفن؛ هالموس، بول (2009)، مقدمة في الجبر البولياني ، نصوص جامعية في الرياضيات ، سبرينغر ، ISBN 978-0-387-40293-2.
جودستين، آر إل (2012)، "الفصل 2: نظام البديهيات ذاتي الازدواجية" ، الجبر البولياني ، منشورات كوريير دوفر، ص 21 وما بعدها، رقم ISBN 9780486154978
هنتنغتون، إدوارد ف. (1904). "مجموعات المسلمات المستقلة لجبر المنطق" . معاملات الجمعية الرياضية الأمريكية . 5 (3): 288-309 . doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR 1986459 .
بادمانابهان، رانغاناثان؛ روديانو، سيرجيو (2008)، بديهيات الشبكات والجبر البولياني ، وورلد ساينتيفيك، ISBN 978-981-283-454-6.
ستون، مارشال هـ. (1936). "نظرية التمثيلات للجبر البولياني" . معاملات الجمعية الرياضية الأمريكية . 40 : 37-111 . doi : 10.1090/s0002-9947-1936-1501865-8 .
وايت هيد، أ. ن. (1969) [1898]. رسالة في الجبر الشامل . مطبعة جامعة كامبريدج. رقم ISBN 978-1-4297-0032-0.

مراجع عامة

براون، ستيفن؛ فرانزيك، زفونكو (2002)، أساسيات المنطق الرقمي باستخدام تصميم VHDL (الطبعة الثانية )، ماكجرو هيل ، ISBN 978-0-07-249938-4انظر القسم 2.5
كوري، رينيه؛ لاسكار، دانيال (2000)، المنطق الرياضي: دورة مع تمارين ، مطبعة جامعة أكسفورد ، رقم ISBN 978-0-19-850048-3انظر الفصل الثاني.

هالموس، بول (1963)، محاضرات عن الجبر البولي ، فان نوستراند.
هالموس، بول ؛ جيفانت، ستيفن (1998)، المنطق كجبر ، سلسلة دولسياني للعروض الرياضية، المجلد 21، الجمعية الرياضية الأمريكية ، ISBN 978-0-88385-327-6.
هانتينغتون، إي. في. (1933أ)، "مجموعات جديدة من المسلمات المستقلة لجبر المنطق" (ملف PDF) ، معاملات الجمعية الرياضية الأمريكية ، 35 (1)، الجمعية الرياضية الأمريكية: 274-304 ، doi : 10.2307/1989325 ، JSTOR 1989325 .
هانتينغتون، إي. في. (1933ب)، "الجبر البولياني: تصحيح"، معاملات الجمعية الرياضية الأمريكية ، 35 (2): 557-558 ، doi : 10.2307/1989783 ، JSTOR 1989783
مندلسون، إليوت (1970)، الجبر البولياني ودوائر التبديل ، سلسلة شوم الموجزة في الرياضيات، ماكجرو هيل ، ISBN 978-0-07-041460-0
مونك، ج. دونالد؛ بونيه، ر.، محرران (1989)، دليل الجبر البولياني ، نورث هولاند ، ISBN 978-0-444-87291-3في 3 مجلدات. (المجلد 1: ISBN) 978-0-444-70261-6المجلد 2: ISBN 978-0-444-87152-7المجلد 3: ISBN 978-0-444-87153-4)
سيكورسكي، رومان (1966)، الجبر البوليني ، Ergebnisse der Mathematik und ihrer Grenzgebiete، Springer Verlag.
ستول، آر آر (1979) [1963]، نظرية المجموعات والمنطق ، دبليو إتش فريمان، رقم ISBN 978-0-486-63829-4أعيد طبعه بواسطة دار نشر دوفر ، 1979.

روابط خارجية

"الجبر البولياني" ، موسوعة الرياضيات ، دار نشر EMS، 2001 [1994]
موسوعة ستانفورد للفلسفة : " رياضيات الجبر البولياني "، بقلم ج. دونالد مونك.
ماكيون دبليو، 1997. جبر روبنز هو جبر بولياني، مجلة البحوث التطبيقية 19(3)، 263-276
"الجبر البولياني" بقلم إريك دبليو. وايسشتاين ، مشروع عروض وولفرام ، 2007.
بوريس، ستانلي ن.؛ سانكابانافار، إتش بي، 1981. دورة في الجبر الشامل. سبرينغر-فيرلاغ. ISBN 3-540-90578-2.
وايسشتاين، إريك دبليو. "الجبر البولياني" . عالم الرياضيات .

[5] من الناحية الدقيقة، يميل مهندسو الكهرباء إلى استخدام حالات إضافية لتمثيل ظروف الدائرة الأخرى مثل المعاوقة العالية - انظر IEEE 1164 أو IEEE 1364 .

[FOOTNOTEGivantHalmos200920-1] جيفانت وهالموس 2009 ، ص. 20.

[FOOTNOTEHuntington1904288-2] هانتينغتون 1904 ، ص 288.

[FOOTNOTEDaveyPriestley1990109,_131,_144-3] Davey & Priestley 1990 ، ص. 109 ، 131 ، 144.

[FOOTNOTEGoodstein201221ff-4] جودستين 2012 ، ص 21 وما بعدها.

[FOOTNOTEStone1936-6] ستون 1936. خطأ في ملف sfn: أهداف متعددة (2×): CITEREFStone1936 ( مساعدة )

[FOOTNOTEHsiang1985260-7] Hsiang 1985 ، ص 260.

[FOOTNOTECohn2003[httpsbooksgooglecombooksidVESm0MJOiDQCpgPA81_81]-8] كوهن 2003 ، ص 81 .

[9] هسيانغ، جيه (1985). "إثبات النظريات الدحضية باستخدام أنظمة إعادة كتابة المصطلحات" . الذكاء الاصطناعي . 25 (3): 255-300 . doi : 10.1016/0004-3702(85)90074-8 .

[10] بوديه، أ.؛ جوانو، ج.ب.؛ شميدت-شاوس، م. (1989). "التوحيد في الحلقات البولية والمجموعات الأبيلية" . مجلة الحساب الرمزي . 8 (5): 449-477 . doi : 10.1016/s0747-7171(89)80054-9 .

[11] ستون، إم إتش (1936). "نظرية التمثيل للجبر البولياني" . معاملات الجمعية الرياضية الأمريكية . 40 (1): 37-111 . doi : 10.2307/1989664 . ISSN 0002-9947 .

[FOOTNOTEPadmanabhanRudeanu2008[httpsbooksgooglecombooksidJlXSlpmlSv4CpgPA73_73]-12] بادمانابهان ورودينو 2008 ، ص. 73 .

[FOOTNOTEWhitehead196937-13] وايتهيد 1969 ، ص 37.

[FOOTNOTEHuntington1904292–293-14] هانتينغتون 1904 ، ص 292-293.

[FOOTNOTEHuntington1904296-15] هانتينغتون 1904 ، ص 296.

[FOOTNOTEHuntington1933a-16] هانتينغتون 1933أ .

[17] داهن، بي آي (1998)، "جبر روبنز هو بولياني: مراجعة لحل ماكيون المُولّد حاسوبيًا لمسألة روبنز"، مجلة الجبر ، 208 (2): 526-532 ، doi : 10.1006/jabr.1998.7467

[ 1 ]

[

[

[ 4 ]

[ ملاحظة 1 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ ١٦ ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗