التعريف التكراري

أربع مراحل في بناء ندفة ثلج كوخ . وكما هو الحال مع العديد من الأشكال الكسورية الأخرى ، يتم الحصول على المراحل من خلال تعريف تكراري.

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

يُعرّف التعريف التكراري للدالة قيمها لبعض المدخلات بدلالة قيمها لنفس الدالة لمدخلات أخرى (أصغر عادةً). على سبيل المثال، تُعرّف دالة المضروب $n$ $!$ بالقواعد التالية:

{\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}

هذا التعريف صالح لكل عدد طبيعي $n$ ، لأن التكرار يصل في النهاية إلى الحالة الأساسية وهي 0. ويمكن أيضًا اعتبار التعريف بمثابة إجراء لحساب قيمة الدالة $n$ $!،$ بدءًا من $n$ $= 0$ والمضي قدمًا مع $n$ $= 1، 2، 3،$ إلخ.

تنص نظرية الاستدعاء الذاتي على أن هذا التعريف يُعرّف بالفعل دالة فريدة. ويستخدم البرهان الاستقراء الرياضي . ^{[ 1 ]}

يُعرّف التعريف الاستقرائي للمجموعة عناصرها بدلالة عناصر أخرى فيها. على سبيل المثال، أحد تعريفات المجموعة هو $\mathbb {N}$ من الأعداد الطبيعية هو:

0 موجود في $\mathbb {N} .$ ⁠
إذا كان العنصر n موجودًا في $\mathbb {N}$ إذن ، $n + 1$ موجود في $\mathbb {N} .$ ⁠
⁠ $\mathbb {N}$ ⁠ هي أصغر مجموعة تحقق الشرطين (1) و (2).

توجد العديد من المجموعات التي تحقق الشرطين (1) و(2) - على سبيل المثال، المجموعة ${0، 1، 1.649، 2، 2.649، 3، 3.649، ...}$ تحقق التعريف. مع ذلك، يحدد الشرط (3) مجموعة الأعداد الطبيعية بحذف المجموعات التي تحتوي على عناصر دخيلة.

يمكن إثبات خصائص الدوال والمجموعات المعرفة بشكل تكراري في كثير من الأحيان باستخدام مبدأ الاستقراء الرياضي الذي يتبع التعريف التكراري. على سبيل المثال، يُشير تعريف الأعداد الطبيعية المُقدّم هنا مباشرةً إلى مبدأ الاستقراء الرياضي للأعداد الطبيعية: إذا تحققت خاصية ما للعدد الطبيعي 0 (أو 1)، وتحققت هذه الخاصية للعدد $n + 1$ كلما تحققت للعدد $n$ ، فإن هذه الخاصية تتحقق لجميع الأعداد الطبيعية (Aczel 1977:742).

شكل من أشكال التعريفات المتكررة

تعتمد معظم التعريفات الاستقرائية على أساسين: حالة أساسية (الأساس) وجملة استقرائية.

الفرق بين التعريف الدائري والتعريف التكراري هو أن التعريف التكراري يجب أن يحتوي دائمًا على حالات أساسية ، وهي حالات تحقق التعريف دون أن تُعرَّف بدلالة التعريف نفسه، وأن جميع الحالات الأخرى في العبارات الاستقرائية يجب أن تكون "أصغر" بمعنى ما (أي أقرب إلى تلك الحالات الأساسية التي تُنهي التكرار) - وهي قاعدة تُعرف أيضًا باسم "التكرار فقط مع حالة أبسط". ^{[ 2 ]}

في المقابل، قد لا يحتوي التعريف الدائري على حالة أساسية، بل قد يُعرّف قيمة الدالة بدلالة تلك القيمة نفسها، بدلاً من تعريفها بدلالة قيم أخرى للدالة. سيؤدي هذا الوضع إلى تسلسل لا نهائي .

إن صحة التعريفات الاسترجاعية - أي أن التعريف الاسترجاعي يُحدد دالة فريدة - هي نظرية في نظرية المجموعات تُعرف بنظرية الاسترجاع ، وبرهانها ليس بالأمر البسيط. ^{[ 3 ]} عندما يكون مجال الدالة هو الأعداد الطبيعية، فإن الشروط الكافية لصحة التعريف هي أن تكون قيمة $f (0)$ (أي الحالة الأساسية) مُعطاة، وأنه بالنسبة $لـ n > 0$ ، توجد خوارزمية لتحديد $f (n)$ بدلالة $n$ . $f(0),f(1),\dots ,f(n-1)$ (أي، جملة استقرائية).

بشكلٍ أعم، يمكن تعريف الدوال تعريفًا تكراريًا عندما يكون مجالها مجموعة مرتبة ترتيبًا جيدًا ، وذلك باستخدام مبدأ التكرار عبر المنتهي . وتكون المعايير الرسمية لما يُعتبر تعريفًا تكراريًا صحيحًا أكثر تعقيدًا في الحالة العامة. يمكن الاطلاع على ملخص للبرهان العام والمعايير في كتاب جيمس مونكرز " الطوبولوجيا" . مع ذلك، سيتم عرض حالة خاصة (حيث يقتصر المجال على الأعداد الصحيحة الموجبة بدلًا من أي مجموعة مرتبة ترتيبًا جيدًا) من التعريف التكراري العام أدناه. ^{[ 4 ]}

مبدأ التعريف التكراري

لتكن $A$ مجموعة، وليكن $a \in$ $A$ عنصرًا منها . إذا كانت $ρ$ دالة تُسند إلى كل دالة $f$ تُسقط قسمًا غير فارغ من الأعداد الصحيحة الموجبة على $A$ ، عنصرًا من $A$ ، فإنه توجد دالة وحيدة. $h:\mathbb {Z} _{+}\to A$ بحيث

{\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1.\end{aligned}}

أمثلة على التعريفات التكرارية

الدوال الأولية

يتم تعريف الجمع بشكل تكراري بناءً على العد كـ

{\begin{aligned}&0+a=a,\\&(1+n)+a=1+(n+a).\end{aligned}}

يُعرَّف الضرب بشكل تكراري على النحو التالي:

{\begin{aligned}&0\cdot a=0,\\&(1+n)\cdot a=a+n\cdot a.\end{aligned}}

يُعرَّف الأسّية بشكل تكراري على النحو التالي:

{\begin{aligned}&a^{0}=1,\\&a^{1+n}=a\cdot a^{n}.\end{aligned}}

يمكن تعريف معاملات ذات الحدين بشكل تكراري على النحو التالي:

{\begin{aligned}&{\binom {a}{0}}=1,\\&{\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}.\end{aligned}}

الأعداد الأولية

يمكن تعريف مجموعة الأعداد الأولية بأنها المجموعة الوحيدة من الأعداد الصحيحة الموجبة التي تحقق الشرط التالي:

2 عدد أولي،
أي عدد صحيح موجب آخر يكون عددًا أوليًا إذا وفقط إذا لم يكن قابلاً للقسمة على أي عدد أولي أصغر منه.

أولية العدد الصحيح 2 هي الحالة الأساسية؛ وللتحقق من أولية أي عدد صحيح أكبر $X$ وفقًا لهذا التعريف، يلزم معرفة أولية كل عدد صحيح بين 2 و $X$ ، وهو ما يُحدد جيدًا بهذا التعريف. يمكن إثبات هذه النقطة الأخيرة بالاستقراء على $X$ ، حيث من الضروري أن تنص العبارة الثانية على "إذا وفقط إذا"؛ فلو كانت تنص فقط على "إذا"، لما كانت أولية العدد 4، على سبيل المثال، واضحة، ولأصبح تطبيق العبارة الثانية مستحيلاً.

الأعداد الزوجية غير السالبة

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

الصفر ينتمي إلى المجموعة $E$ من الأعداد الزوجية غير السالبة (الشرط الأساسي)،
لأي عنصر $x$ في المجموعة $E$ ، فإن $x + 2$ ينتمي إلى $E$ (عبارة استقرائية).
لا يوجد شيء في $المجموعة E$ إلا إذا تم الحصول عليه من الجمل الأساسية والاستقرائية (الجملة المتطرفة).

تركيبة متقنة

يُعرَّف مفهوم الصيغة الصحيحة (wff) في منطق القضايا بشكل متكرر على أنه أصغر مجموعة تحقق القواعد الثلاث التالية:

$p$ عبارة عن صيغة منطقية صحيحة إذا كان $p$ متغيرًا افتراضيًا.
$\neg p$ عبارة عن صيغة منطقية صحيحة إذا كانت $p$ صيغة منطقية صحيحة.
$(p • q)$ هي صيغة منطقية إذا كانت $p$ و $q$ صيغتين منطقيتين و • هي واحدة من الروابط المنطقية ∨، ∧، →، أو ↔.

يمكن استخدام التعريف لتحديد ما إذا كانت أي سلسلة معينة من الرموز تمثل صيغة نصية صحيحة (wff):

$(p \land q)$ هي صيغة منطقية، لأن المتغيرات الافتراضية $p$ و $q$ هي صيغ منطقية و $\land$ هي رابط منطقي.

$\neg (p \land q)$ هي صيغة منطقية، لأن $(p \land q)$ هي صيغة منطقية.

$(\neg p \land \neg q)$ هي صيغة منطقية، لأن $\neg p$ و $\neg q$ هما صيغتان منطقيتان و $\land$ هو رابط منطقي.

التعريفات المتكررة كبرامج منطقية

يمكن فهم البرامج المنطقية على أنها مجموعات من التعريفات المتكررة . ^{[ 5 ]}^{[ 6 ]} على سبيل المثال، يمكن كتابة التعريف المتكرر للعدد الزوجي على شكل البرنامج المنطقي التالي:

زوجي ( 0 ). زوجي ( s ( s ( X ))) :- زوجي ( X ).

:-يمثل هنا إذا ، ويمثل خليفة ، أي ، كما هو الحال في حساب بيانو .s(X)XX+1

تستخدم لغة البرمجة المنطقية برولوج الاستدلال العكسي لحل الأهداف والإجابة على الاستفسارات. على سبيل المثال، عند إعطاء الاستفسار ، تُنتج الإجابة .?-even(s(s(0)))true?-even(s(0))false

لا يقتصر استخدام البرنامج على التحقق من صحة الاستعلام فحسب، بل يمكن استخدامه أيضًا لتوليد إجابات صحيحة. على سبيل المثال:

?- زوجي ( X ). X = 0 X = s ( s ( 0 )) X = s ( s ( s ( s ( 0 )))) X = s ( s ( s ( s ( s ( s ( 0 )))))) .....

تُوسّع البرامج المنطقية بشكل كبير التعريفات التكرارية من خلال تضمين استخدام الشروط السلبية، والتي يتم تنفيذها عن طريق النفي كفشل ، كما هو الحال في التعريف:

زوجي ( 0 ). زوجي ( s ( X )) :- ليس ( زوجي ( X )).

انظر أيضاً

ملحوظات

↑ هينكين، ليون (1960). "حول الاستقراء الرياضي". المجلة الرياضية الأمريكية الشهرية . 67 (4): 323-338 . doi : 10.2307/2308975 . ISSN 0002-9890 . JSTOR 2308975 .
↑ "كل شيء عن الاستدعاء الذاتي" . www.cis.upenn.edu . مؤرشف من الأصل بتاريخ 2019-08-02 . تم الاطلاع عليه بتاريخ 2019-10-24 .
↑ للحصول على برهان لنظرية الاستدعاء الذاتي، انظر كتاب الاستقراء الرياضي (1960) لليون هينكين .
↑ مونكرز، جيمس (1975). الطوبولوجيا، دورة تمهيدية ( الطبعة الأولى). نيوجيرسي: برنتيس هول. ص 68، التمرينان 10 و12 . ISBN 0-13-925495-1.
↑ دينيكر، م.، تيرنوفسكا، إ.: منطق التعريفات الاستقرائية غير الرتيبة. معاملات ACM في منطق الحاسوب 9(2)، 14:1–14:52 (2008)
↑ وارن، دي إس ودينيكر، إم، 2023. دلالات منطقية أفضل للغة برولوج. في برولوج: الخمسون عامًا القادمة (ص 82-92). تشام: سبرينغر نيتشر سويسرا.

مراجع

هالموس ، بول (1960). نظرية المجموعة الساذجة . فان نوستراند . او سي ال سي 802530334 .
أكسل، بيتر (1977). "مقدمة في التعريفات الاستقرائية". في باروايز، ج. (محرر). دليل المنطق الرياضي . دراسات في المنطق وأسس الرياضيات. المجلد 90. نورث هولاند . الصفحات 739-782 . doi : 10.1016/S0049-237X(08)71120-0 . ISBN 0-444-86388-5.
هاين، جيمس ل. (2010). البنى المنفصلة، والمنطق، والحوسبة . جونز وبارتليت . ISBN 978-0-7637-7206-2. OCLC 636352297 .

[1] هينكين، ليون (1960). "حول الاستقراء الرياضي". المجلة الرياضية الأمريكية الشهرية . 67 (4): 323-338 . doi : 10.2307/2308975 . ISSN 0002-9890 . JSTOR 2308975 .

[2] "كل شيء عن الاستدعاء الذاتي" . www.cis.upenn.edu . مؤرشف من الأصل بتاريخ 2019-08-02 . تم الاطلاع عليه بتاريخ 2019-10-24 .

[3] للحصول على برهان لنظرية الاستدعاء الذاتي، انظر كتاب الاستقراء الرياضي (1960) لليون هينكين .

[Munkres-4] مونكرز، جيمس (1975). الطوبولوجيا، دورة تمهيدية ( الطبعة الأولى). نيوجيرسي: برنتيس هول. ص 68، التمرينان 10 و12 . ISBN 0-13-925495-1.

[5] دينيكر، م.، تيرنوفسكا، إ.: منطق التعريفات الاستقرائية غير الرتيبة. معاملات ACM في منطق الحاسوب 9(2)، 14:1–14:52 (2008)

[6] وارن، دي إس ودينيكر، إم، 2023. دلالات منطقية أفضل للغة برولوج. في برولوج: الخمسون عامًا القادمة (ص 82-92). تشام: سبرينغر نيتشر سويسرا.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]