كيف يتم التخلص من المكمّمات؟

بقلم: رينهارد أولدنبورغ Reinhard Oldenburg و ميشال أرتيغ Michele Artigue

كيف يمكن لبرامج الحاسوب أن تختصر طرح المسائل الجبرية مثل عبارة: “من أجل كل عدد $x$ “، أو معرفة ما إذا كان عدد حقيقي $x$ موجودا عندما نقيّده بشروط معيّنة؟ تعتمد التطوّرات الحديثة على مبرهنات المنطق الرياضي، فضلا عن إدخال تحسينات في مجال الحوسبة.

يتعلّم طلاب المدارس الثانوية كيفية حل مسائل، مثل: “من أجل أية قيم للعدد الحقيقي $c$ ، يكون لكثير الحدود $P(x) = x^2 + cx + c$ جذران حقيقيان متمايزان؟” وستكون الإجابة الحسابية: $c < 0$ أو $c > 4$ . وهكذا، تمّ العثور على طريقة تحويل عبارة المسألة

$\exists x_1 \, \exists x_2 \, (x_1 \neq x_2 \wedge P(x_1) = 0 \wedge P(x_2) = 0)$

التي يتخللها المكممان الوجوديان: “يوجد $x_1$ ” و”يوجد $x_2$ ” إلى العبارة “ $c < 0$ أو $c > 4$ ” التي لم تعد تحتوي على المكمّمات. نتساءل: من أجل أيّ نوع من المسائل يكون هذا ممكنا نظريّا، وأيضا عمليّا باستخدام برنامج معلوماتي فعّال؟ في عام 1938، وبفضل مبرهنة حذف المكمّمات التي أثبتها عالم المنطق ألفريد تارسكي Alfred Tarski، تمّ تحقيق خطوة حاسمة بشأن هذه المسائل. ولكن ذلك لم يكن على الإطلاق نهاية القصة… دعنا نتعرّف على المزيد في هذا الموضوع.

لقد حاول علماء الرياضيات، منذ العصور الغابرة، ابتكار خوارزميات تسمح لهم بحل أصناف من المسائل الرياضية حلا مباشرا. على سبيل المثال، هناك مسألة إيجاد تقنيات منهجية لحل المسائل التي ننمذجها اليوم بواسطة معادلات تربيعية. كما أن خوارزمية إقليدس التي تحدد عددين أوليين فيما بينهما كانت معروفة منذ أكثر من ألف سنة. ومع ذلك، نحن نعلم أيضا أنه لا يمكن إيجاد خوارزمية عامة تتيح حل المعادلات الجبرية التي لها درجة أكبر من $4$ . وهذا الطرح تأكّد أيضا منذ ظهور نظرية عدم الاكتمال لغودل Gödel القائلة إنه يستحيل الحصول على طريقة تمكّن من البتّ في صحة كل صيغ أية نظرية تتضمن نظرية الأعداد الأولية¹. ورغم ذلك فإن تطوّر المنطق الرياضي وعلاقته مع علم الحاسوب أدّيا إلى بروز أدوات جديدة تعالج هذا النوع من المسائل. ستستعرض هذه المقالة القصيرة بعض أفكار هذا الموضوع.

يمكن التعبير عن العديد من المسائل في الرياضيات بواسطة معادلات أو متباينات يظهر فيها المكمم الكلي (أو الكوني) أو الوجودي كما كان الشأن بالنسبة للمسألة السابقة، أو تلك التي تنطوي على أشكال أكثر تعقيما. على سبيل المثال، فإن التعبير عن دالة معينة $f$ بأنها مستمرة عند نقطة معلومة $x_0$ يتطلب دمج المكمم الكلي (أي، من أجل كل) والمكمم الوجودي (أي، يوجد):

$\forall \varepsilon > 0 \; \exists \delta > 0 \; \forall x: |x - x_0| < \delta \Rightarrow |f(x) - f(x_0)| < \varepsilon.$

إن الشيء الذي طوّره تارسكي في الثلاثينيات من القرن العشرين كان إيجاد طريقة لحذف المكمّمات في نظرية معينة، وهي تلك الخاصة بالحقول الحقيقية المغلقة، أبرز نماذجها حقل الأعداد الحقيقية. وهكذا، أثبت تارسكي أن صحة أية جملة مغلقة في هذه النظرية يمكن البتّ فيها. كما يمكن أيضا تحويل الجملة التي تحتوي متغيرات أو وسيطات (كما هو الحال في المثال التمهيدي حيث كان $c$ وسيطا) إلى نتائج مكافئة في شكل مجموعات منتهية من الشروط حول تلك المتغيرات. لكن طريقة تارسكي كانت بالغة التعقيد، ولا تمكّن من الوصول إلى خوارزمية عملية. كانت هناك حاجة للمزيد من الأبحاث كي نبلغ المرحلة الحالية التي دُمجت فيها خوارزميات فعالة في مجموعات رمزية، مثل برنامجي ماثيماتيكا Mathematica أو ماكسيما Maxima، كما هو مبيّن في الأمثلة أدناه.

في المثال الأول، استُخدم برنامج ماثيماتيكا من أجل إيجاد قيم الوسيط $c$ التي من أجلها يكون للدالة $f(x) = x^3 - cx^2 + cx + c$ على الأقل جذران حقيقيان متمايزان. في البداية تم إدخال الدالة باستخدام قواعد برنامج ماثيماتيكا، ثم أُدخلت عبارة تترجم المسألة بصيغة صورية. وأخيرا أُجريت على تلك العبارة عملية تسمى Resolve في البرنامج، وهي عملية تقوم بحذف المكمّمات. والنتيجة هي: $c \leq -1$ أو $c \geq \frac{27}{5}$ .

في المثال الثاني، يتم استخدام نفس البرنامج لإيجاد قيم $c$ التي من أجلها تقبل الدالة $f$ جذرا حقيقيا يعطي انحناءا موجبا للدالة $f$ (يعني ذلك أن المشتق الثاني للدالة $f$ موجب). كانت النتيجة هذه المرة هي: $c \leq 0$ أو $c \geq \frac{27}{5}$ .

في المثال الثالث، يتم استخدام البرنامج ماكسيما للبت في مسألة استمرار كثير الحدود $P_1(x) = (x-5)^2 + x + 1$ ، والدالة الناطقة $r_1(x) = x/(x-3)$ ، وذلك في النقطة $2$ ، ثم في نقطة كيفية $a$ . مرة أخرى، نلاحظ أن استمرار دالة $f$ في نقطة معطاة $x_0$ يتم التعبير عنه بطريقة صورية (شكلية) تترجم التعريف المعطى أعلاه وفق قواعد برنامج ماكسيما حيث يُرمز للمكمم الكلي “مهما كان” بالحرف $A$ وللمكمم الوجودي بــ $E$ . نشير إلى أن الشروط التي تتضمن القيمة المطلقة في التعريف المعتاد تكتب هنا باستخدام متباينات بين المربعات. ثم يتم تطبيق عملية حذف المكمّمات في هذه العبارة. تسمى هذه العملية في ماكسيما $qe$ . كما تُطبّق أيضا على العبارات الناطقة مثلما هو موضح في المثال. إن الأجوبة المقدمة في آخر المطاف تخبرنا أن الدالتين مستمرتان من أجل $x = 2$ ، وأن الدالة الثانية مستمرة عند $a$ شريطة أن يكون $a \neq 3$ .

كيف يشتغل؟

ما رأيناه في هذه الأمثلة هو تطبيق طريقة تقدم البيانات الرياضية، بل تبرهن على أنها ستكون ناجحة في مجالات أوسع. والآن نتساءل: كيف يمكن للحاسوب أن يقوم بذلك التقدم “الفكري”؟

لغةُ نظرية الحقول الحقيقية المغلقة

اللغة التي نعتبرها في نظرية الحقول الحقيقية المغلقة تحتوي على عمليتين هما $+$ ، $*$ ، وعلى علاقة ترتيب $<$ ، وعلى المساواة $=$ . وتحتوي أيضا على رمزين يدلان على العنصرين الحياديين الخاصين بالعمليتين المشار إليهما أعلاه. وعلاوة على ذلك، هناك أعداد ثابتة، ومتغيرات، ومكمّمات. ذلك هو المستوى الأول لهذه اللغة، الذي يقضي بأن تتعامل المكمّمات فقط مع المتغيرات واحدا واحدا، وليس مع مجموعة من المتغيرات أو مع رموز الدالة. وأكثر من ذلك، فالأعداد التي توضع في الأس يجب أن تكون أعدادا طبيعية لا غير (هذا يستبعد، على سبيل المثال، معالجة مبرهنة فيرما Fermat باستخدام النظرية المقدمة هنا).

إن بديهيات (أو مسلمات) هذه النظرية هي تلك التي تضمن أن تكون البُنى المحقّقة لها حقولا حقيقية مغلقة، أي حقولا مرتبة يكون فيها لكل عنصر موجب جذر تربيعي، ولكل كثير حدود ذي درجة فردية جذر. ضمن هذه النظرية، يمكن تعريف عمليات وعلاقات جديدة، مثل عملية الطرح، وعلاقة ترتيب واسعة، ورموز أخرى يمكن إدخالها من الهدف إلى الإشارة إلى العمليات والعلاقات الجديدة، وكذا للدلالة على عناصر معينة، مثل الأعداد الصحيحة، ومقلوب عنصر غير الصفر، والجذر التربيعي لعنصر موجب. تكتب معظم الجمل الأولية على الشكل: $P = 0$ ، $P > 0$ ، $P < 0$ حيث $P$ يمثل كثير الحدود أو عدة متغيرات، كما نجد ضمن تلك الجمل نفيها: $P \neq 0$ ، $P \leq 0$ ، $P \geq 0$ .

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

وضع جميع المكمّمات في المقدمة، وهو ما يسميه علماء المنطق الشكل البادئ Prenex².
ويكون فيها الجزء المتبقي هو فصل الوصل³.

نلاحظ أن ما كتب في الأمثلة الثلاثة أعلاه قد قدمت في الشكل البادئ. ولكن في شكل “فصل-وصل” هو فقط المثالان الأول والثاني. نقترح على القارئ أن يحوّل المثال الأخير إلى هذه الصيغة وذلك باستخدام القاعدتين المواليتين، ثم بالتحقق من الإجابة عن طريق المقارنة مع الهامش 4 أدناه⁴.

قاعدة 1: استبدل $A \Rightarrow B$ بــ $\neg A \vee B$
قاعدة 2: استبدل $\neg(A \wedge B)$ بــ $\neg A \vee \neg B$

عندما تكون الجملة على شكل بادئ، فإنه بالإمكان حذف عدد من المكمّمات بدءا من أكثرها عمقا. نلاحظ أن استخدام النفي في معالجة الجملة من الشكل $\forall x A(x)$ يسمح بكتابتها على النحو $\neg \exists x \neg A(x)$ . يتعلق الأمر في آخر المطاف بمعرفة احتياجاتنا حتى نفهم كيف يمكن حذف المكمم الوجودي في جملة من الشكل $\exists x (A_1 \vee A_2 \vee \ldots \vee A_n)$ . نشير إلى أن كل $A_i$ وارد ضمن هذه الجملة يمثل وصلا بين مساويات ومتباينات من نوع كثير حدود مرتبط بــ $x$ ، وربما يرتبط أيضا بمتغيرات أخرى. في الواقع، فإن هذه الجملة تكافئ $(\exists x A_1) \vee (\exists x A_2) \vee \ldots \vee (\exists x A_n)$ . وبالتالي فما نحتاج إليه هو فهم كيف يمكن حذف المكمم الوجودي في جملة من الشكل

$\exists x \, (P_1(x) = 0 \wedge P_2(x) > 0 \wedge P_3(x) < 0 \ldots)$

حيث $P_i$ يمثل عبارة تكتب في شكل كثير حدود بمتغيرات أخرى قد ترتبط إضافة إلى المتغير $x$ .

نقتصر في هذه المقالة القصيرة على حقل الأعداد الحقيقية كما هو الشأن في معظم الحالات المهمة من الحقول الحقيقية المغلقة، وكذا الأكثر ارتباطا برياضيات المرحلة الثانوية. إن حل مسألة الحذف في هذا الحقل يعني أنه يمكن تطوير خوارزمية لاختزال معالجة قيم كثيرات الحدود $P_i$ المعرفة على المستقيم الحقيقي لتنحصر المعالجة في دراسة عدد منتهٍ من الحالات. إن مبرهنة شتورم Sturm و”التحليل الأسطواني الجبري” (CAD) يتيحان لنا حل هذه المسألة.

مبرهنة شتورم Sturm

يُقَسّم كثير حدود لمتغير واحد $P(x) = a_n x^n + \ldots + a_0$ المستقيم الحقيقي إلى مناطق وفق إشارة قيمه في نقاط معينة. يوجد على الأكثر $n$ جذرا حقيقيا؛ لذلك فإن هذه الجذور تقسم المستقيم إلى $n+1$ مجالا مفتوحا على الأكثر في كل منها يكون $P(x)$ موجبا أو سالبا. أما أطراف هذه المجالات فهي تمثل جذور $P(x)$ . نلاحظ، كما أسلفنا، أنه لا توجد صيغة عامة للتعبير عن هذه الجذور بدقة، بينما نستطيع معرفة عدد الجذور الموجودة داخل أي مجال وذلك بطريقة توضحها مبرهنة شتورم⁵. وهكذا، يمكننا تحديد مختلف الجذور في أية مجالات، والتأكد من أننا لم ننسى أيًّا منها. وهذا يكفي لإجراء عملية حذف المكمّمات.

عندما يتعلق الأمر بأكثر من متغير، يبقى لدينا عدد منتهٍ من المناطق بالنسبة للمتغير الفضائي الذي من أجله يحافظ كثير الحدود على إشارة معينة. لتوضيح ذلك، دعونا نعود إلى المثال الأول. يمكن أن ننظر إلى الدالة $f(x) = x^3 - cx^2 + cx + c$ على أنها كثير حدود بمتغيرين $x$ و $c$ . تبرز الصورة أدناه، المتحصل عليها ببرنامج ماكسيما، ثلاث مناطق مرتبطة بالدالة داخل المربع $[-10,10] \times [-10,10]$ في المستوي $(x, c)$ . يعبر اللون الأحمر عن القيم الموجبة للدالة $f$ ، وأما اللون الأزرق فيمثل القيم السالبة للدالة $f$ .

الشكل 1: المناطق المرتبطة بكثير الحدود $x^3 - cx^2 + cx + c$ التي تم إنشاؤها بواسطة أوامر برنامج ماكسيما:
`f(x):=x^3-c*x^2+c*x+c; wxdraw2d(fill_color=red,region(f(x)>0,x,-10,10,c,-10,10), fill_color=blue,region(f(x)<0,x,-10,10,c,-10,10));`

هناك تفكيكات مشابهة يمكن ربطها بمجموعات كثيرات حدود: في هذه الحالة تتميّز كل منطقة بكون إشارة جميع كثيرات الحدود في المجموعة هي نفسها في كل تلك المنطقة. يوضح الشكل 2 المناطق المرتبطة بكثير الحدود السابق ومشتقه الثاني في المربع $[-10,10] \times [-10,10]$ . وقد تم الحصول على الشكل هنا أيضا ببرنامج ماكسيما.

الشكل 2: المناطق المرتبطة بكثيري الحدود f و f'' — الشكل 2: المناطق المرتبطة بكثيري الحدود $f$ و $f''$ .

إن المنحنيات التي تحدد مختلف المناطق تمثل أجزاءً من المنحنيين $c = \frac{x^3}{x^2 - x - 1}$ و $c = 3x$ مرتبطة بجذور الدالة $f$ ومشتقها الثاني. ومع ذلك، فالوصف الجبري لهذه المناطق ليس سهلا حتى في مثل هذه الحالة البسيطة. ولكي نبسط هذا الوصف، تكمن الفكرة في تقسيم هذه المناطق إلى خلايا أصغر يسهل وصفها، ثم القيام بالحسابات وفق منهجية محددة. يؤدي بنا ذلك إلى مفهوم التفكيك الجبري الأسطواني.

التفكيك الجبري الأسطواني

التفكيك الجبري الأسطواني لـ $\mathbb{R}^n$ يقسم هذا الفضاء إلى مجموعة منتهية من الخلايا المنفصلة. وهكذا تكون كل نقطة من $\mathbb{R}^n$ في خلية واحدة لا غير. للخلايا شكل خاص نعرفه بصورة تكرارية: من أجل $n = 1$ ، تكون الخلية إما عددا حقيقيا وحيدا وإما مجالا مفتوحا، أي مجالا من الشكل $]-\infty, a[$ أو $]a, b[$ أو $]b, \infty[$ . من أجل $n = 2$ ، تكون الخلية أسطوانة قاعدتها هذه الخلية ذات البعد $1$ ، بمعنى أن الخلية ذات البعد $2$ تأخذ أحد الأشكال الأربعة التالية:

$\{(x, y): x \in C, \, y = f(x)\}, \quad \{(x, y): x \in C, \, y > f(x)\},$

$\{(x, y): x \in C, \, y < f(x)\}, \quad \{(x, y): x \in C, \, f(x) < y < g(x)\}$

حيث $C$ يمثل خلية وحيدة البعد. أما $f$ و $g$ فهما كثيرا حدود أو دالتان ناطقتان. نعرّف خلية ذات البعد $n$ بنفس الطريقة، أي كأسطوانة قاعدتها خلية ذات بعد $n-1$ .

يمكن أن يُنفَّذ التفكيك الجبري الأسطواني خوارزميا بشكل ملحوظ في كل مجموعة كثيرات الحدود لــ $n$ متغيرا التي تنجم عنها مجموعة منتهية من الخلايا بحيث تكون إشارة كثيرات الحدود في كل خلية إشارة ثابتة. إن الخوارزمية معقدة ولا يسعنا هنا إلا أن نقدم فكرة مبسطة عنها. من أجل مجموعة $P$ مؤلفة من كثيرات حدود ذات $n$ متغيرا $x_1, \ldots, x_n$ ، فإن الخوارزمية تقوم من خلال عملية تكرارية على $n$ : الإجراء الخاص بــ $n$ متغيرا يستدعي الإجراء الخاص بــ $n-1$ متغيرا. إنه يشمل، في الواقع، الخطوات الثلاث التالية:

الإسقاط: إنشاء المسقط $P'$ لمجموعة كثيرات الحدود ذات $n-1$ متغيرا $x_1, \ldots, x_{n-1}$ ، انطلاقا من المجموعة $P$ ⁶.
خطوة التكرار: إيجاد تفكيك جبري أسطواني $D'$ لـ $P'$ .
التمديد: في كل خلية من خلايا $D'$ ، نأخذ نقطة ممثِّلة ونضع إحداثياتها مكان متغير كثير الحدود $P$ . يؤدي ذلك إلى ظهور مجموعة كثيرات الحدود لمتغير واحد $x_n$ . نحدد جذورها الحقيقية ونستعملها لتعريف خلايا مرتبطة بخلايا $D'$ .

كما أوضحنا أعلاه، فمن أجل $n = 1$ ، يمكن الحصول على تفكيك جبري أسطواني بفضل مبرهنة شتورم. إن كان هناك أكثر من كثير حدود واحد فما علينا سوى اعتبار تقاطع الخلايا المنبثقة عن كل كثير حدود. نجد برهانا على سلامة هذه العملية التكرارية في المرجع Winkler، 1996.

دعنا نعود الآن إلى الأمثلة التي اعتبرناها أعلاه. من أجل كل مجموعة شروط بدلالة كثيرات حدود معطاة كمدخل، تُنتج خوارزمية التفكيك الجبري الأسطواني تفكيكا جبريا أسطوانيا للفضاء مرتبط بكثيرات الحدود المعنية، ويعود بنا التفكيك إلى الخلايا التي تتمتع بالشروط المعطاة. وإذا استخدمنا، على سبيل المثال، خوارزمية التفكيك الجبري الأسطواني المتوفرة في برنامج ماثيماتيكا باعتبار الشرطين $f > 0$ و $f'' > 0$ ، فإننا نحصل على التفكيك التالي في البعد $2$ . ندعو القارئ إلى التأكد من أنه يناسب التعريف الوارد لمثل هذا التفكيك (يمكن أن ننظر للمجالات المغلقة على أنها اتحاد خلايا مع مجالات مفتوحة وخلايا مكوّنة من نقطة واحدة)، وأنه يصف جبريا المناطق الحمراء في الشكل 2⁷.

إذا قمنا بتغيير مجموعة الشروط، باحثين عن قيم $c$ التي من أجلها يقبل كثير الحدود $f$ جذرا حقيقيا ويكون الانحناء موجبا، فإننا نحصل بطبيعة الحال على خلايا تختلف عن السابقة.

لاحظ أن المتغير $x$ لا يقع في الموضع الثاني في المعطيات المستعملة لأنه يمثّل المتغير الذي ينبغي حذفه في هذه المسألة. من شأن الشرط $f(x) = 0$ أن يجعل جميع الأسطوانات من النمط $C \times \{\alpha_i\}$ (حيث $C$ خلية وحيدة البعد و $\alpha_i$ يساوي أحد الجذور الثلاثة لكثير الحدود). هذه البنية الأسطوانية تسهل قراءة الشروط حول $c$ لكل خلية، ثم ضمها للحصول على الجواب النهائي: $c < 0$ أو $c \geq \frac{27}{5}$ .

إن إجراء العمليات الحسابية يدويا غير ممكن إلا في حالة المسائل السهلة، كما في المثال الذي سنفصله فيما يلي. نوصي القارئ غير المهتم بهذه التفاصيل أن يهمل الاطلاع على هذا الجزء.

المسألة: إيجاد قيم $x$ بحيث تكون الجملة $\exists y \, (P_1(x, y) > 0 \wedge P_2(x, y) > 0)$ صحيحة علما أن $P_1(x, y) = y - x$ و $P_2(x, y) = 1 - x^2 y$ .

تُعنى خطوة الإسقاط في خوارزمية التفكيك الجبري الأسطواني بحساب مميزات ومحصّلات كثيرات الحدود. نحن لن نفصّل هذه الخطوة في هذا المقام، وسنكتفي بتقديم النتيجة الخاصة بها، أي المجموعة $P' = \{1, x^2, 1 - x^3\}$ .

في الخطوة الثانية، علينا أن ننتج التفكيك الجبري الأسطواني من أجل المجموعة $P'$ . الجذور الحقيقية لكثيرات الحدود في $P'$ هي $0$ و $1$ . وهكذا فإن التفكيك الجبري الأسطواني المرتبط بــ $P'$ هو تقسيم $\mathbb{R}$ إلى خمس خلايا: $]-\infty, 0[$ ، $\{0\}$ ، $]0, 1[$ ، $\{1\}$ ، $]1, \infty[$ .

الخطوة الثالثة هي خطوة التمديد. يمكن اعتبار العينة من النقاط من $D'$ بخصوص النقاط $-1$ ، $0$ ، $0,5$ ، $1$ ، $2$ . عندما نعوض $x$ بهذه النقاط في $P_1$ و $P_2$ ، نحصل على مجموعة ثنائيات كثيرات الحدود التالية:

$\{\{1 + y, 1 - y\}, \{1, y\}, \{y - 1/2, 1 - y/4\}, \{y - 1, 1 - y\}, \{y - 2, 1 - 4y\}\}.$

من السهل تحديد جذور كثيرات الحدود في هذه الحالة. على سبيل المثال، في الثنائية الأولى نلاحظ أن الجذور هي $-1$ و $1$ . ومن ثمّ ففي "الخلية $x$ " $]-\infty, 0[$ ستكون لدينا "الخلايا $y$ " $]-\infty, -1[$ ، $\{-1\}$ ، $]-1, 1[$ ، $\{1\}$ ، $]1, \infty[$ . إجمالا يتفكك $\mathbb{R}^2$ إلى $23 = 5 + 5 + 3 + 5 + 5$ خلية.

والآن، يمكن أن ترفق من النقاط بكل خلية من هذه الخلايا. على سبيل المثال، من أجل الخلايا الخمس الأولى الموافقة للنقطة $-1$ (العينة $x$ )، يمكن أن نختار عينة من الثنائيات $(-1, -2)$ ، $(-1, 0)$ ، $(-1, 1)$ ، $(-1, -1.2)$ ، $(-1, 1.1)$ . عند تعويض هذه النقاط في كثيري الحدود $P_1$ و $P_2$ ، نستطيع أن نرتب الحالات بحيث يكون كثيرا الحدود موجبين. لقد تم إيجاد ثلاث حالات فحسب، وهي مستنتجة من الخلايا الثلاث الأولى (العينة $x$ ): $]-\infty, 0[$ ، $\{0\}$ ، $]0, 1[$ . وبالتالي فإن الصيغة الخالية من المكمّمات المكافئة للصيغة $\exists y \, (P_1(x, y) > 0 \wedge P_2(x, y) > 0)$ هي: $x < 1$ .

من الجبر والتحليل إلى الهندسة

يمكن استخدام حذف المكمّمات وخوارزمية التفكيك الجبري الأسطواني لحل مجموعة من المسائل التي تحتوي على دوال كثيرات الحدود. كما نستطيع التعبير عن العديد من المسائل بلغة الحقول الحقيقية المغلقة. يمكن أن تكون هذه المسائل جبرية أو مسائل في الحساب تتعلق بالاستمرار كما في المثال الثالث الذي استعملنا فيه النهايات، والقيم القصوى، أو المتغيرات. وفضلا عن ذلك، هناك معالجات أولية تسمح لنا بالتعامل يدويا أيضا مع الدوال الناطقة مثل $A/B = C$ (التي تكافئ $A = B.C$ و $B \neq 0$ )؛ كما يمكن استبدال الجذور التربيعية بما يكافئها: $\sqrt{A} = B$ تعادل $A = B^2$ و $B \geq 0$ .

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

على سبيل المثال، يمكننا إثبات نظرية طالس Thales (التي تنص على أنه إذا وقعت نقطة $C$ على دائرة قطرها $[A,B]$ ، فإن المستقيمين $(AC)$ و $(BC)$ متعامدان) كما يلي: هب أن النقطتين $A$ و $B$ هما على التوالي $(0,0)$ و $(b,0)$ ، وأن $C$ هي $(x,y)$ ، (لاحظ أن هذا لا يضرّ بعمومية البرهان). يتم التعبير عن التعامد من خلال انعدام الجداء السلمي للشعاعين $AC$ و $CB$ . (نلاحظ أنه يمكن استعمال المكمم الكلي لكافة المتغيرات الأربعة. وبما أن الخاصية تظل صحيحة حتى بدون ذلك الاستعمال فهذا يبيّن أن النتيجة سليمة بدون أية قيود حول المتغيرات).

نلاحظ أن البراهين الهندسية يمكن القيام بها باستعمال قواعد غروبنر Groebner. وهذه الأدوات منبثقة من الهندسة الجبرية العقدية وتسمح، فيما تسمح، بالحل المنهجي لجمل من معادلات كثيرات الحدود المعنية –ولكنها لا تسمح بحل المتراجحات إذ أن حقل الأعداد العقدية ليس مرتبا. وعليه فالنتائج الهندسية لا تقبل كلها التحوّل إلى شكل يتيح الاستفادة من الطرق المبنية على قواعد غروبنر؛ بل حتى إن كان ذلك ممكنا فقد تنصّ الطريقة المتبعة على أن نتيجة معينة صحيحة مع أن بعض الإحداثيات بحاجة إلى أن تكون أعدادا تخيّلية (المبنية على مجموعة الأعداد الحقيقية). وبالتالي فتلك النتيجة لن تقوم في الهندسة الحقيقية. وعلى العكس من ذلك، يمكن أن تكون قضية صحيحة في الهندسة الحقيقية مع أنها ربما تمثل مثالا مضادا وثيق الصلة بالإحداثيات العقدية.

إشكال التعقيد

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

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

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

المراجع

Qepmax: https://github.com/YasuhaikHonda/qepmax: Maxima-qepcad-interface by Y. Honda with contributions by R. Oldenburg
A. Tarski (1948): A decision method for elementary algebra and geometry. Rand Corporation Publication.
F. Winkler (1996): Algorithms for Polynomials. Springer.
St. Wolfram: Mathematica – A system for doing mathematics by Computer.

¹ http://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems

² ينجز ذلك باستخدام خواص حساب الرتبة الأولى الإسنادي. مثال ذلك (باستخدام الرموز المعتادة للمكمم الكلي $\forall$ والمكمم الوجودي $\exists$ واستخدام الرموز الخاصة بالروابط المنطقية: $\neg$ للنفي، والرمز $\wedge$ لــ "و"، والرمز $\vee$ لــ "أو"):

$A \wedge \exists x B(x) \Leftrightarrow \exists x (A \wedge B(x)).$

لاحظ أن $x$ لا يظهر في $A$ . ونحصل على صيغ مماثلة بالمكمم الكلي والرابط "أو":

$\exists x A(x) \vee \exists x B(x) \Leftrightarrow \exists x (A(x) \vee B(x)),$

وكذا بالمكمم الوجودي والرابط "و":

$\exists x A(x) \wedge \exists x B(x) \Leftrightarrow \exists x \exists y (A(x) \wedge B(y))$

حيث $y$ متغير غير موجود في $A$ وفي $B$ . ولدينا أيضا الصيغة:

$\neg (\exists x A(x)) \Leftrightarrow \forall x \neg A(x).$

³ ينجز ذلك باستخدام خواص الروابط المنطقية مثل تلك الواردتين في القاعدتين 1 و 2 الموضحتين في النص.

⁴ $\forall \varepsilon \exists \delta \forall x \, (\delta \leq 0 \vee \varepsilon \leq 0 \vee (x - x_0)^2 \geq \delta^2 \vee (f(x) - f(x_0))^2 < \varepsilon^2)$ .

⁵ تنص مبرهنة شتورم على أن عدد الجذور الحقيقية المتمايزة لكثير حدود في مجال معلوم $(a, b)$ يساوي الفرق $\sigma(b) - \sigma(a)$ حيث $\sigma(c)$ يرمز لعدد مرات تغيرات إشارة عناصر متتالية شتورم عند النقطة $c$ . أما متتالية شتورم لكثير حدود $P$ فهي المنتهية المحصّل عليها عند تطبيق خوارزمية إقليدس على $P$ وعلى مشتقه $P'$ . لدينا $P_0 = P$ ، $P_1 = P'$ ، $P_2$ هو نظير باقي القسمة الإقليدية لــ $P_0$ على $P_1$ ، وهكذا دواليك. بما أن الحدود $P_i$ كثيرات حدود تتناقص درجاتها فإن متتالية شتورم منتهية. كما يمكن القول إن الحد الأخير غير المنعدم في هذه المتتالية هو القاسم المشارك الأكبر لــ $P$ و $P'$ .

⁶ لإنشاء هذا الإسقاط نعتبر المعاملات الرئيسية لكثيرات الحدود $P$ عند النظر إليها ككثيرات الحدود لــ $x_n$ ، كما نأخذ جميع المميزات والمحصّلات التي يمكن حسابها انطلاقا من $P$ .

⁷ نلاحظ في هذا التركيب أن القيمتين $\frac{1}{2}(1-\sqrt{5})$ و $\frac{1}{2}(1+\sqrt{5})$ هما جذران لكثير الحدود $P(x) = x^2 - x - 1$ ، وأن القيمتين $\frac{1}{4}(3-\sqrt{33})$ و $\frac{1}{4}(3+\sqrt{33})$ تمثلان فاصلتي نقطتي تقاطع المنحنيين $c = \frac{x^3}{x^2 - x - 1}$ و $c = 3x$ المرتبطتين بجذور الدالة $f$ ومشتقه الثاني.