منطق المتغيرين

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

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

على النقيض من ذلك، بالنسبة لجزء المنطق من الدرجة الأولى ذي المتغيرات الثلاثة بدون رموز الدوال، فإن قابلية الإرضاء غير قابلة للتقرير. ^{[ 3 ]}

من المعروف أن جزء المنطق من الدرجة الأولى ذي المتغيرين، والذي لا يحتوي على رموز دوال، قابل للتقرير حتى مع إضافة مُكمِّمات العد ، ^{[ 4 ]} وبالتالي مع إضافة تحديد التفرد . وهذه نتيجة أكثر أهمية، إذ لا يمكن التعبير عن مُكمِّمات العد للقيم العددية العالية في هذا المنطق.

تعمل أدوات العد الكمية في الواقع على تحسين قدرة منطق المتغيرات المحدودة على التعبير، حيث تسمح بالقول إن هناك عقدة ذات${\displaystyle n}$الجيران، أي${\displaystyle \Phi =\exists x\exists ^{\geq n}yE(x,y)}$بدون عدّ الكميات${\displaystyle n+1}$المتغيرات ضرورية لنفس الصيغة.

ثمة ارتباط وثيق بين منطق المتغيرين وخوارزمية وايسفيلر-ليمان (أو تحسين الألوان ). فعند وجود رسمين بيانيين، يكون لأي عقدتين نفس اللون الثابت في تحسين الألوان إذا وفقط إذا كان لهما نفس${\displaystyle C^{2}}$^{[ 5 ]}​