التكرار (المنطق)

في المنطق الرياضي ، تُعرف الحُثالة (من اليونانية القديمة : ταυτολογία ) بأنها صيغة صحيحة بغض النظر عن تفسير عناصرها ، حيث تكون الثوابت المنطقية فقط هي ذات المعنى الثابت. إنها حقيقة منطقية . على سبيل المثال، الصيغة التي تنص على "الكرة خضراء أو الكرة ليست خضراء" صحيحة دائمًا، بغض النظر عن ماهية الكرة أو لونها. تُستخدم الحُثالة عادةً، وإن لم يكن دائمًا، للإشارة إلى الصيغ الصحيحة في منطق القضايا .

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

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

رمز البوابة الدوارة المزدوجة${\displaystyle \vDash S}$يُستخدم للإشارة إلى أن S عبارة عن تكرار. يُرمز للتكرار أحيانًا بـ "V pq "، وللتناقض بـ "O pq ". رمز حرف T${\displaystyle \top }$يُستخدم أحيانًا للدلالة على التكرار العشوائي، مع الرمز المزدوج${\displaystyle \bot }$( falsum ) يمثل تناقضًا اعتباطيًا؛ في أي رمزية، يمكن استبدال القيمة الحقيقية " صحيح " بتكرار، كما هو مرمز إليه، على سبيل المثال، بـ "1". ^{[ 1 ]}

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

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

استخدم الإغريق القدماء كلمة "التكرار" لوصف عبارة يُزعم صحتها بمجرد تكرارها مرتين، وهو معنى ازدرائي لا يزال يُستخدم في سياق التكرار البلاغي . بين عامي 1800 و1940، اكتسبت الكلمة معنى جديدًا في المنطق، وتُستخدم حاليًا في المنطق الرياضي للدلالة على نوع معين من الصيغ القانونية، دون الدلالات الازدرائية التي كانت تحملها في الأصل.

في عام 1800، كتب إيمانويل كانط في كتابه "المنطق" :

يمكن أن تكون هوية المفاهيم في الأحكام التحليلية صريحة ( صريحة ) أو ضمنية ( ضمنية ). في الحالة الأولى، تكون القضايا التحليلية تحصيل حاصل.

هنا، تشير القضية التحليلية إلى حقيقة تحليلية ، وهي عبارة في اللغة الطبيعية تكون صحيحة فقط بسبب المصطلحات المعنية.

في عام 1884، اقترح غوتلوب فريجه في كتابه "Grundlagen" أن الحقيقة تكون تحليلية إذا أمكن استنتاجها باستخدام المنطق. ومع ذلك، فقد حافظ على التمييز بين الحقائق التحليلية (أي الحقائق القائمة فقط على معاني مصطلحاتها) والتكرارات (أي العبارات الخالية من المحتوى).

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

كل ما يُصنَّف كقضية منطقية لا بد أن يكون، بشكل أو بآخر، أشبه بالتكرار المنطقي. لا بد أن يكون ذا صفة مميزة، لا أعرف كيف أُعرّفها، تنتمي إلى القضايا المنطقية دون غيرها.

هنا، تشير القضية المنطقية إلى قضية يمكن إثباتها باستخدام قوانين المنطق.

استخدم العديد من علماء المنطق في أوائل القرن العشرين مصطلح "التكرار" للإشارة إلى أي صيغة صحيحة عالميًا، سواء أكانت صيغة منطقية للقضايا أم منطقية للمحمولات . وبهذا المعنى الواسع، فإن التكرار هو صيغة صحيحة في جميع التأويلات ، أو مكافئة منطقيًا لنفي التناقض. وقد اتبع تارسكي وغودل هذا الاستخدام، ويظهر في كتب دراسية مثل كتاب لويس ولانغفورد. ^{[ 3 ]} هذا الاستخدام الواسع للمصطلح أقل شيوعًا اليوم، مع أن بعض الكتب الدراسية لا تزال تستخدمه. ^{[ 4 ] [ 5 ]}

تُقيّد الكتب الدراسية الحديثة استخدام مصطلح "التكرار" في الغالب على الجمل الصحيحة في منطق القضايا، أو الجمل الصحيحة في منطق المسندات التي يمكن اختزالها إلى تكرارات قضايا عن طريق الاستبدال. ^{[ 6 ] [ 7 ]}

يبدأ المنطق الافتراضي بمتغيرات افتراضية ، وهي وحدات ذرية تمثل قضايا محددة. تتكون الصيغة من متغيرات افتراضية متصلة بروابط منطقية، مبنية بطريقة تسمح باستنتاج صحة الصيغة الكلية من صحة أو خطأ كل متغير. التقييم هو دالة تُسند لكل متغير افتراضي إما T (للصحة) أو F (للخطأ). لذا، باستخدام المتغيرين الافتراضيين A و B ، الروابط الثنائية...${\displaystyle \lor }$و${\displaystyle \land }$يمثلان الانفصال والوصل على التوالي، والرابط الأحادي${\displaystyle \lnot }$لتمثيل النفي ، يمكن الحصول على الصيغة التالية:${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$.

يجب أن يُحدد التقييم هنا لكل من A و B إما T أو F. ولكن بغض النظر عن كيفية إجراء هذا التحديد، ستكون الصيغة العامة صحيحة. لأنه إذا كان الفصل الأول${\displaystyle (A\land B)}$إذا لم يتم استيفاء الشرط بتقييم معين، فيجب تعيين F لـ A أو B ، مما سيؤدي إلى تعيين T لأحد الخيارات التالية. باللغة الطبيعية، إما أن يكون كل من A و B صحيحًا أو أن يكون أحدهما على الأقل خاطئًا.

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

في العديد من الأمثلة التالية، يُمثل الحرف A العبارة "الشيء X مُجلّد"، ويمثل الحرف B العبارة "الشيء X كتاب"، ويمثل الحرف C العبارة "الشيء X موجود على الرف". بدون مرجع محدد للشيء X ،${\displaystyle A\to B}$ يتوافق ذلك مع المقولة "كل الأشياء المجلدة هي كتب".

• ${\displaystyle (A\lor \lnot A)}$(" أ أو ليس أ ")، قانون الوسط المرفوع . تحتوي هذه الصيغة على متغير منطقي واحد فقط، وهو أ . أي تقييم لهذه الصيغة يجب، بحكم التعريف، أن يُسند إلى أ إحدى قيمتي الصواب: صحيح أو خطأ ، ويُسند إلى${\displaystyle \lnot }$أما القيمة الصحيحة الأخرى فهي: "القطة سوداء أو القطة ليست سوداء".
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$(إذا كان أ يستلزم ب ، فإن نفي ب يستلزم نفي أ ، والعكس صحيح)، وهو ما يعبر عن قانون التناقض . على سبيل المثال، "إذا كان مجلداً، فهو كتاب؛ وإذا لم يكن كتاباً، فهو غير مجلد" والعكس صحيح.
• ${\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}$(إذا كان نفي أ يستلزم كلاً من ب ونفيه نفي ب ، فإن نفي أ يجب أن يكون خاطئًا، وبالتالي فإن أ يجب أن يكون صحيحًا)، وهو المبدأ المعروف باسم البرهان بالخلف . على سبيل المثال، "إذا لم يكن مجلدًا، فنحن نعلم أنه كتاب؛ وإذا لم يكن مجلدًا، فنحن نعلم أيضًا أنه ليس كتابًا، إذن فهو مجلد".
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$(إذا لم يكن كل من أ و ب ، فإما ليس أ أو ليس ب ، والعكس صحيح)، وهو ما يُعرف بقانون دي مورغان . "إذا لم يكن كتابًا ومجلدًا في نفس الوقت، فنحن متأكدون من أنه ليس كتابًا أو أنه ليس مجلدًا" والعكس صحيح.
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}$(إذا كان أ يستلزم ب، وب يستلزم ج ، فإن أ يستلزم ج )، وهو المبدأ المعروف بالقياس المنطقي الافتراضي . "إذا كان مجلداً، فهو كتاب، وإذا كان كتاباً، فهو على هذا الرف، لذا إذا كان مجلداً، فهو على هذا الرف".
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$(إذا كان أحد الشرطين أ أو ب صحيحًا على الأقل، وكل منهما يستلزم ج ، فإن ج يجب أن يكون صحيحًا أيضًا)، وهو المبدأ المعروف باسم البرهان بالحالات . "الكتب والمجلدات موجودة على ذلك الرف. إذا كان الشيء كتابًا أو مجلدًا، فهو موجود على ذلك الرف".

التكرار الأدنى هو تكرار لا يمثل مثالاً على تكرار أقصر.

• ${\displaystyle (A\lor B)\to (A\lor B)}$هي تحصيل حاصل، لكنها ليست تحصيل حاصل بسيط، لأنها تجسيد لـ${\displaystyle C\to C}$.

تُعدّ مسألة تحديد ما إذا كانت الصيغة صحيحة أم خاطئة جوهرية في منطق القضايا. فإذا احتوت الصيغة على n متغيرًا، فإنّ لها 2^ ⁿ قيمة مختلفة. لذا، فإنّ مهمة تحديد ما إذا كانت الصيغة صحيحة أم خاطئة هي مهمة محدودة وآليّة: إذ يكفي تقييم قيمة الصواب للصيغة في كل قيمة من قيمها الممكنة. ومن الطرق الحسابية للتحقق من صحة الصيغة في كل قيمة، إنشاء جدول صواب يتضمن جميع القيم الممكنة. ^{[ 2 ]}

على سبيل المثال، انظر إلى الصيغة

${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).}$

توجد ثماني قيم محتملة للمتغيرات المنطقية A و B و C ، ممثلة بالأعمدة الثلاثة الأولى من الجدول التالي. تُظهر الأعمدة المتبقية صحة الصيغ الفرعية للصيغة المذكورة أعلاه، وصولاً إلى عمود يُظهر قيمة صحة الصيغة الأصلية في ظل كل قيمة محتملة.

⁠${\displaystyle A}$⁠	⁠${\displaystyle B}$⁠	⁠${\displaystyle C}$⁠	${\displaystyle A\land B}$	${\displaystyle (A\land B)\to C}$	${\displaystyle B\to C}$	${\displaystyle A\to (B\to C)}$	${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}$
تي	تي	تي	تي	تي	تي	تي	تي
تي	تي	F	تي	F	F	F	تي
تي	F	تي	F	تي	تي	تي	تي
تي	F	F	F	تي	تي	تي	تي
F	تي	تي	F	تي	تي	تي	تي
F	تي	F	F	تي	F	تي	تي
F	F	تي	F	تي	تي	تي	تي
F	F	F	F	تي	تي	تي	تي

لأن كل صف من العمود الأخير يظهر T ، فقد تم التحقق من أن الجملة المعنية هي جملة تكرارية.

من الممكن أيضًا تعريف نظام استنتاجي (أي نظام إثبات) لمنطق القضايا، باعتباره صيغةً أبسط من الأنظمة الاستنتاجية المستخدمة في منطق الرتبة الأولى (انظر كلين 1967، القسم 1.9 للاطلاع على أحد هذه الأنظمة). قد يكون إثبات التكرار المنطقي في نظام استنتاجي مناسب أقصر بكثير من جدول الصواب الكامل ( تتطلب الصيغة التي تحتوي على n متغيرًا من متغيرات القضايا جدول صواب مكونًا من 2 ^{^n} سطرًا، وهو ما يصبح غير عملي مع ازدياد n ). كما أن أنظمة الإثبات ضرورية لدراسة منطق القضايا الحدسي ، حيث لا يمكن استخدام طريقة جداول الصواب لعدم افتراض قانون الوسط المرفوع.

يُقال إن الصيغة R تستلزم الصيغة S بشكل تلقائي إذا كان كل تقييم يجعل R صحيحة يجعل S صحيحة أيضًا. ويُرمز إلى هذه الحالة بـ${\displaystyle R\models S}$وهو ما يعادل الصيغة${\displaystyle R\to S}$كونها تكرارًا (Kleene 1967 ص.  27).

على سبيل المثال، لنفترض${\displaystyle S}$يكون${\displaystyle A\land (B\lor \lnot B)}$. ثم${\displaystyle S}$ليست هذه حجة زائدة، لأن أي تقييم يجعل${\displaystyle A}$خطأ سيجعل${\displaystyle S}$خطأ. لكن أي تقييم يجعل${\displaystyle A}$الحقيقة ستجعل${\displaystyle S}$صحيح، لأن${\displaystyle B\lor \lnot B}$هذا تكرار. دع${\displaystyle R}$كن الصيغة${\displaystyle A\land C}$. ثم${\displaystyle R\models S}$لأن أي تقييم يفي بـ${\displaystyle R}$سوف يصنع${\displaystyle A}$صحيح - وبالتالي يجعل${\displaystyle S}$حقيقي.

ويترتب على التعريف أنه إذا كانت الصيغة${\displaystyle R}$إذا كان هذا تناقضاً،${\displaystyle R}$يستلزم كل صيغة بشكل تحصيلي، لأنه لا يوجد تقييم للحقيقة يسبب${\displaystyle R}$لكي يكون صحيحًا، وبالتالي يتحقق تعريف الاستلزام التكراري بشكل بديهي. وبالمثل، إذا${\displaystyle S}$إذا كان هذا تحصيل حاصل،${\displaystyle S}$يُستدل على ذلك بشكل بديهي من كل صيغة.

توجد طريقة عامة، هي قاعدة الاستبدال ، تسمح بإنشاء جمل تكرارية إضافية من جملة تكرارية معينة (كلين، 1967، القسم 3). لنفترض أن S جملة تكرارية، ولكل متغير منطقي A في S ، يتم اختيار جملة ثابتة S _A. عندئذٍ، تكون الجملة الناتجة عن استبدال كل متغير A في S بالجملة المقابلة S _A جملة تكرارية أيضًا.

على سبيل المثال، لنفترض أن S هي التكرار المنطقي:

${\displaystyle (A\land B)\lor \lnot A\lor \lnot B}$.

ليكن S _A​${\displaystyle C\lor D}$وليكن S _B​${\displaystyle C\to E}$.

ويترتب على قاعدة الاستبدال أن الجملة:

${\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}$

وهي أيضاً حشو لغوي.

يكون النظام البديهي كاملاً إذا كانت كل حقيقة بديهية فيه نظرية (مستنتجة من البديهيات). ويكون النظام البديهي سليماً إذا كانت كل نظرية فيه حقيقة بديهية.

تُعد مشكلة بناء خوارزميات عملية لتحديد ما إذا كانت الجمل التي تحتوي على أعداد كبيرة من المتغيرات الافتراضية عبارة عن تحصيل حاصل هي مجال بحث معاصر في مجال إثبات النظريات الآلي .

إن طريقة جداول الصواب الموضحة أعلاه صحيحةٌ بشكلٍ قاطع؛ إذ ينتهي جدول الصواب لعبارةٍ تكراريةٍ بعمودٍ يحتوي على القيمة T فقط ، بينما يحتوي جدول الصواب لجملةٍ ليست تكراريةً على صفٍّ عموده الأخير F ، والقيمة المقابلة لهذا الصف لا تُحقق شرط الجملة قيد الاختبار. تُعدّ هذه الطريقة للتحقق من التكرارات إجراءً فعالاً ، ما يعني أنه في حال توفر موارد حاسوبية غير محدودة، يُمكن استخدامها دائمًا لتحديد ما إذا كانت الجملة تكراريةً بشكلٍ آلي. وهذا يعني، على وجه الخصوص، أن مجموعة التكرارات على أبجديةٍ ثابتةٍ محدودةٍ أو قابلةٍ للعد هي مجموعةٌ قابلةٌ للتقرير .

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

تُعرف مشكلة تحديد ما إذا كان هناك أي تقييم يجعل صيغة ما صحيحة بمشكلة الإرضاء البولياني ؛ وتُكافئ مشكلة التحقق من صحة التكرارات هذه المشكلة، لأن التحقق من أن الجملة S هي تكرار يُكافئ التحقق من عدم وجود تقييم يُحققها.${\displaystyle \lnot S}$تُعدّ مسألة إرضاء الصيغ المنطقية مسألةً كاملةً من فئة NP ، وبالتالي، فإنّ مسألة التكرار المنطقي هي مسألة كاملة من فئة co-NP . ويُعتقد على نطاق واسع (وبالمثل بالنسبة لجميع المسائل الكاملة من فئة NP) أنه لا توجد خوارزمية ذات زمن متعدد الحدود قادرة على حلّ مسألة الإرضاء، على الرغم من أنّ بعض الخوارزميات تُحقق أداءً جيدًا على فئات خاصة من الصيغ، أو تنتهي بسرعة في العديد من الحالات. ^{[ 8 ]}

يُعرَّف التكرار المنطقي تعريفًا أساسيًا في سياق منطق القضايا. مع ذلك، يمكن توسيع هذا التعريف ليشمل الجمل في منطق الرتبة الأولى . ^{[ 9 ]} قد تحتوي هذه الجمل على مُكمِّمات، على عكس جمل منطق القضايا. في سياق منطق الرتبة الأولى، يُفرَّق بين الصلاحيات المنطقية ، وهي الجمل الصحيحة في كل نموذج، والتكرارات المنطقية (أو الصلاحيات التكرارية )، التي تُشكِّل مجموعة فرعية من الصلاحيات المنطقية في منطق الرتبة الأولى. أما في سياق منطق القضايا، فيتطابق هذان المصطلحان.

الجملة التكرارية في منطق الرتبة الأولى هي جملة يمكن الحصول عليها بأخذ جملة تكرارية في منطق القضايا واستبدال كل متغير من متغيرات القضايا بصيغة من الرتبة الأولى (صيغة واحدة لكل متغير من متغيرات القضايا). على سبيل المثال، لأن${\displaystyle A\lor \lnot A}$هو تكرار منطقي للمنطق الافتراضي،${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$تُعدّ هذه الجملة تحصيل حاصل في منطق الرتبة الأولى. وبالمثل، في لغة من الرتبة الأولى ذات رموز علاقة أحادية R و S و T ، تُعدّ الجملة التالية تحصيل حاصل:

${\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx)).}$

يتم الحصول عليه عن طريق الاستبدال${\displaystyle A}$مع${\displaystyle \exists xRx}$،${\displaystyle B}$مع${\displaystyle \lnot \exists xSx}$، و${\displaystyle C}$مع${\displaystyle \forall xTx}$في التكرار الافتراضي:${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}$.

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

${\displaystyle \neg \neg A\to A}$

• Bocheński, JM (1959) Précis of Mathematical Logic , ترجم من الطبعتين الفرنسية والألمانية بواسطة أوتو بيرد، دوردريخت ، جنوب هولندا : د. ريدل .
• إندرتون، إتش بي (2002) مقدمة رياضية في المنطق ، هاركورت / أكاديميك برس ، رقم ISBN 0-12-238452-0.
• كلين، إس سي (1967) المنطق الرياضي ، أعيد طبعه عام 2002، منشورات دوفر ، رقم ISBN 0-486-42533-9.
• رايشنباخ، هـ. (1947). عناصر المنطق الرمزي ، أعيد طبعه عام 1980، دوفر، رقم ISBN 0-486-24004-5
• فيتجنشتاين، ل. (1921). "Logisch-philosophiche Abhandlung"، Annalen der Naturphilosophie (Leipzig)، v. 14، pp.  185–262، أعيد طبعه في الترجمة الإنجليزية باسم Tractatus logico-philosophicus ، مدينة نيويورك ولندن ، 1922.

• "التكرار" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]