المنطق
دراسة النتائج التي تلزم فعلًا عن مقدمات بعينها.
يدرس المنطق صورة الاستدلال لا مادته. ويستبدل المنطق الصوري بالجمل رموزًا، فيصير لزوم النتيجة أمرًا تحسمه صورة الحجة وحدها، ويمكن التحقق منه آليًا.
قاموس المنطق
كل المصطلحات التي تستعملها الحاسبة والأدلة والتمارين، معرَّفة في مكان واحد.
ابحث عن مصطلح، وانظر رمزه، وافتح المثال في الحاسبة لتراه يعمل. المصطلحات المعرَّفة هنا تُبرَز عند أول ورودها في أي دليل.
كل المصطلحات (62)
الأسس
قضية
قول إما صادق وإما كاذب، لا كلاهما.
القضية جملة خبرية لها قيمة صدق واحدة بالضبط. «تمطر السماء» قضية، أما السؤال أو الأمر فليس كذلك، إذ ليس فيهما ما يوصف بالصدق أو الكذب.
قيمة الصدق
⊤ / ⊥إحدى القيمتين اللتين تأخذهما القضية: الصدق أو الكذب.
يمنح المنطق الكلاسيكي كل قضية قيمة صدق واحدة بالضبط، تُكتب ⊤ و⊥ (أو 1 و0). وكل سطر من جدول الصدق هو إسناد قيم للمتغيرات، مع القيمة التي تأخذها الصيغة عنده.
قضية ذرية
قضية لا يدخل في تركيبها أي رابط.
القضية الذرية لا تُحلَّل إلى قضايا أصغر: ليس فيها نفي ولا عطف ولا أي رابط آخر. وما عداها مركّب، مبني من الذرات، وقيمة صدقه تتبع قيمها.
متغير قضوي
حرف مثل p أو A ينوب عن قضية كيفما كانت.
المتغير القضوي موضع خالٍ لأي قضية. وتقبل الحاسبة الحروف المفردة متغيرات، وتخصص لكل متغير عمودًا في جدول الصدق، وسطرًا لكل تركيبة ممكنة من القيم.
في الحاسبةp → qصيغة حسنة التكوين
سلسلة رموز تسمح بها قواعد اللغة فعلًا.
تُبنى الصيغة حسنة التكوين وفق القواعد: المتغير صيغة، وكذلك كل صيغة تنشأ من صيغ أصغر برابط. أما «p ∧ ∨ q» فليست كذلك، ولهذا تبلّغ الحاسبة عن خطأ بدل أن تخمّن.
تأويل
إسناد قيم صدق إلى كل متغيرات الصيغة.
يحدد التأويل قيمة كل متغير، فيثبّت بذلك قيمة الصيغة كلها. وللصيغة ذات n متغيرًا 2ⁿ تأويلًا، وهي بعينها سطور جدول صدقها.
حجة
مقدمات تُساق تأييدًا لنتيجة.
تدّعي الحجة أن نتيجتها تلزم عن مقدماتها. اكتبها في الحاسبة برمز الاستلزام — المقدمات قبله والنتيجة بعده — فيُفحص كل سطر بحثًا عن حالة تصدق فيها المقدمات وتكذب النتيجة.
في الحاسبةp → q, p ⊨ qمقدمة
قول تفترضه الحجة كي تبلغ نتيجتها.
المقدمات هي منطلق الحجة. ولا تسأل الصحة إلا: هل تصدق النتيجة حيثما صدقت كل المقدمات؟ أما صدق المقدمات في الواقع فمسألة أخرى، وهي ما تضيفه السلامة.
في الحاسبةp → q, p ⊨ qنتيجة
القول الذي تسعى الحجة إلى إثباته.
النتيجة هي ما تُساق المقدمات تأييدًا له. وهي في الحاسبة العبارة التالية لرمز الاستلزام، وتكون الحجة صحيحة متى لم يوجد تأويل يصدّق المقدمات ويكذّب النتيجة.
في الحاسبةp → q, p ⊨ qالروابط
رابط منطقي
رمز يبني قضية مركّبة من قضايا أبسط.
الرابط مثل ¬ و∧ و∨ و→ و↔ يجمع قضايا في قضية أكبر لا تتوقف قيمة صدقها إلا على قيمها. وهذا التوقف بعينه هو ما يسجله جدول الصدق، بسطر لكل تركيبة من المدخلات.
نفي
¬يقلب قيمة الصدق: ¬p صادقة تمامًا حين تكذب p.
النفي هو الرابط الأحادي الوحيد في منطق القضايا. يُكتب ¬p أو ~p أو !p، ويحوّل الصدق كذبًا والكذب صدقًا، ولذا يعيدك النفي مرتين إلى القضية الأصلية.
في الحاسبة¬pعطف
∧لا يصدق إلا إذا صدق الطرفان: p ∧ q.
يؤكد العطف طرفيه معًا. وهو يصدق في سطر واحد بالضبط من جدول صدقه — السطر الذي يصدق فيه الطرفان — وبذلك يكون أشد الروابط الثنائية صرامة.
في الحاسبةp ∧ qفصل
∨يصدق متى صدق أحد الطرفين على الأقل: p ∨ q.
الفصل في المنطق جامع: تصدق p ∨ q إذا صدقت p، وإذا صدقت q، وإذا صدقتا معًا. أما «أو» المانعة، التي لا تصدق إلا إذا اختلف الطرفان، فرابط مستقل.
في الحاسبةp ∨ qفصل مانع
⊕يصدق حين تصدق قضية واحدة بالضبط من القضيتين.
الفصل المانع، ويُكتب ⊕ أو XOR، يتحقق حين يختلف طرفاه ويفشل حين يتفقان. وهو نفي التكافؤ الشرطي، ويمكن كتابته (p ∨ q) ∧ ¬(p ∧ q).
في الحاسبة(p ∨ q) ∧ ¬(p ∧ q)شرطية
→p → q، ولا تكذب إلا حين تصدق p وتكذب q.
لا تقول الشرطية المادية أكثر من «ليس: المقدَّم صادق والتالي كاذب»، ولذلك تتحقق تلقائيًا كلما كذب المقدَّم. ومن هنا كانت p → q مكافئة لـ ¬p ∨ q.
في الحاسبةp → qتكافؤ شرطي
↔p ↔ q، ويصدق حين تتساوى قيمتا صدق الطرفين.
يؤكد التكافؤ الشرطي كل طرف بشرط الآخر: فيصدق حين يصدق الطرفان، وحين يكذبان معًا. والتكافؤ الشرطي الذي يكون تحصيل حاصل هو بالضبط تقرير لتكافؤ منطقي.
في الحاسبةp ↔ qمقدَّم
جزء «إذا» من الشرطية — أي p في p → q.
المقدَّم هو الشرط الذي تتوقف عليه الشرطية. فإذا كذب صدقت الشرطية كلها مهما يكن التالي، ومن هنا يأتي أكثر ما يفاجئ في جدول →.
في الحاسبةp → qتالٍ
جزء «فإن» من الشرطية — أي q في p → q.
التالي هو ما تقرر الشرطية لزومه إذا تحقق مقدَّمها. وصدق التالي يصدّق الشرطية لكنه لا يصدّق المقدَّم: واستنتاج ذلك مغالطة صورية.
في الحاسبةp → qعكس الشرطية
الشرطية بعد تبديل طرفيها: q → p.
عكس p → q هو q → p، وليسا متكافئين: إذ تجد الحاسبة سطرًا يصدق فيه أحدهما ويكذب الآخر. ومعاملتهما كأنهما سواء هي مغالطة تصديق التالي.
في الحاسبةq → pنقيض العكس
¬q → ¬p، وقيمة صدقه دائمًا كقيمة p → q.
نقيض العكس ينفي طرفي الشرطية ويبدل بينهما. وهو، خلافًا للعكس، مكافئ حقًا للأصل، ولهذا كان البرهان بنقيض العكس مشروعًا في الرياضيات.
في الحاسبة(p → q) ≡ (¬q → ¬p)NAND
↑نفي العطف: يصدق إلا حين يصدق المدخلان معًا.
NAND، ويُكتب ↑، هو ¬(p ∧ q). وهو تام وظيفيًا: يمكن بناء كل رابط آخر منه وحده، ولذلك صار عماد تصميم الدارات الرقمية.
في الحاسبة¬(p ∧ q)NOR
↓نفي الفصل: لا يصدق إلا حين يكذب المدخلان معًا.
NOR، ويُكتب ↓، هو ¬(p ∨ q). وهو مثل NAND تام وظيفيًا بمفرده، حتى إن الدارة يمكن أن تُبنى كلها من بوابات NOR.
في الحاسبة¬(p ∨ q)أولوية الأدوات
أي رابط يُطبَّق أولًا عند غياب الأقواس.
أشد الروابط ربطًا النفي، ثم العطف، ثم الفصل، ثم الشرطية، وأخيرًا التكافؤ الشرطي. فتُقرأ ¬p ∧ q ∨ r هكذا: ((¬p) ∧ q) ∨ r؛ والأقواس تنقض هذا الترتيب متى اختلفت القراءة المقصودة.
في الحاسبة¬p ∧ q ∨ rالصدق والاستلزام
جدول الصدق
سطر لكل إسناد للقيم، وفيه قيمة الصيغة.
يعدّد جدول الصدق كل التأويلات 2ⁿ لمتغيرات الصيغة العددية n، ويحسب قيمتها عند كل تأويل. ولأنه مستوعب فإنه يحسم كل سؤال دلالي في منطق القضايا: التكافؤ والصحة والقابلية للإشباع وسواها.
في الحاسبةp → qتحصيل حاصل
⊤صيغة تصدق في كل تأويل.
التحصيل الحاصل يصدق في كل سطر من جدول صدقه، ولذا لا يقول شيئًا عن العالم: فـ p ∨ ¬p صادقة مهما تكن p. وتتكافأ صيغتان بالضبط حين يكون التكافؤ الشرطي بينهما تحصيل حاصل.
في الحاسبةp ∨ ¬pتناقض
⊥صيغة تكذب في كل تأويل.
التناقض مثل p ∧ ¬p يكذب في كل سطر من جدول صدقه. واستخراج تناقض من مجموعة فروض يبيّن أنها لا يمكن أن تصدق كلها، وهذا هو محرّك البرهان بالخلف.
في الحاسبةp ∧ ¬pصيغة ممكنة
صيغة تصدق في بعض التأويلات وتكذب في غيرها.
الصيغة الممكنة ليست تحصيل حاصل ولا تناقضًا: ففي جدول صدقها سطر صادق واحد على الأقل وسطر كاذب واحد على الأقل. وأكثر ما يكتبه الناس من صيغ من هذا الصنف، ولذلك كانت مفيدة.
في الحاسبةp ∧ qالقابلية للإشباع
هل يوجد تأويل يجعل الصيغة صادقة.
تكون الصيغة قابلة للإشباع متى صدق سطر واحد على الأقل من جدول صدقها، وذلك السطر نموذج لها. والبتّ في القابلية للإشباع هو المسألة المركزية لحلّالات SAT، ومن ثَمّ لكثير من الاستدلال الآلي.
في الحاسبةp ∧ (p → q)تكافؤ منطقي
≡صيغتان لهما جدولا صدق متطابقان.
تتفق الصيغتان المتكافئتان في كل تأويل، فيمكن أن تحل إحداهما محل الأخرى في أي موضع دون تغيير المعنى. ضع علامة المساواة بين عبارتين، فتقارن الحاسبة عموديهما سطرًا سطرًا.
في الحاسبة(p → q) ≡ (¬p ∨ q)استلزام منطقي
⊨تصدق النتيجة في كل تأويل تصدق فيه المقدمات.
الاستلزام المنطقي، ويُكتب Γ ⊨ φ، هو ما تدّعيه الحجة الصحيحة. ويُتحقق منه بالبحث عن مثال مضاد: تأويل يصدّق كل المقدمات ويكذّب النتيجة. فإن لم يوجد ثبت الاستلزام.
في الحاسبةp → q, p ⊨ qصحة الحجة
لا تأويل يصدّق المقدمات ويكذّب النتيجة.
الصحة خاصية لصورة الحجة لا للوقائع: فقد تكون الحجة الصحيحة ذات مقدمات كاذبة ونتيجة كاذبة. أما ما لا يمكن أن يكون فهو مقدمات صادقة مع نتيجة كاذبة.
في الحاسبةp → q, p ⊨ qسلامة الحجة
حجة صحيحة مقدماتها صادقة أيضًا.
تضيف السلامة إلى الدعوى الصورية دعوى واقعية: الحجة صحيحة ومقدماتها صادقة. والمنطق وحده يحسم الشطر الأول؛ أما الثاني فيعود إلى موضوع الحجة أيًّا كان.
نموذج مضاد
تأويل يصدّق المقدمات ويكذّب النتيجة.
النموذج المضاد برهان على فساد الحجة — ويكفي سطر واحد. وتعرض الحاسبة السطر الذي تجده، فتحوّل قولك «هذا لا يلزم» إلى إسناد محدد يمكنك التحقق منه بيدك.
في الحاسبةp → q ⊨ q → pاتساق
وجود تأويل يصدّق كل أقوال المجموعة معًا.
تكون مجموعة المقدمات متسقة متى أمكن أن تصدق كلها معًا. والمقدمات غير المتسقة تستلزم أي شيء كان، فالحجة المبنية عليها صحيحة تقنيًا ولا قيمة لها.
في الحاسبةp → q, ¬q ⊨ ¬pالصور القياسية
حد بسيط
متغير أو نفيه، مثل p أو ¬p.
الحدود البسيطة ذرات الصور القياسية: فالبند فصلٌ لحدود بسيطة، والحد الأصغر عطفٌ لها. ويكون الحد البسيط موجبًا حين يرد المتغير مجردًا، وسالبًا حين يرد منفيًا.
في الحاسبة¬pبند
فصل لحدود بسيطة، مثل p ∨ ¬q ∨ r.
البند إحدى المجموعات بين الأقواس التي تتألف منها الصورة العطفية القياسية. ولأن العطف لا يصدق إلا بصدق كل أجزائه، فإن صيغة CNF تتحقق بالضبط حين تتحقق كل بنودها.
في الحاسبةp ∨ ¬q ∨ rالصورة الفصلية القياسية
«أو» من «و»: فصل لعطوف من حدود بسيطة.
لكل صيغة صورة فصلية قياسية، وتُقرأ مباشرة من جدول الصدق: عطف واحد لكل سطر صادق، وتُوصل بـ ∨. وتعطي الحاسبة كذلك صورة فصلية مختصرة تقول الشيء نفسه بحدود أقل.
في الحاسبة(p ∧ q) ∨ (¬p ∧ r)الصورة العطفية القياسية
«و» من «أو»: عطف لبنود.
تُقرأ الصورة العطفية القياسية من السطور الكاذبة في جدول الصدق، ببند لكل سطر. وهي صيغة الإدخال التي تنتظرها حلّالات SAT، ولذا صار التحويل إلى CNF خطوة معتادة في الاستدلال الآلي.
في الحاسبة(p ∨ q) ∧ (¬p ∨ r)حد أصغر
عطف يعيّن سطرًا واحدًا بالضبط من جدول الصدق.
يذكر الحد الأصغر كل متغير مرة واحدة، منفيًا أو غير منفي، فلا يُشبعه إلا تأويل واحد. وجمع حدود السطور الصادقة ووصلها بـ ∨ يعطي الصورة الفصلية القياسية للصيغة.
في الحاسبةp ∧ ¬q ∧ rحد أكبر
فصل يستبعد سطرًا واحدًا بالضبط من جدول الصدق.
يذكر الحد الأكبر كل متغير مرة واحدة، ولا يكذب إلا في تأويل واحد. وأخذ الحد الأكبر لكل سطر كاذب ووصلها بـ ∧ يعطي الصورة العطفية القياسية للصيغة.
في الحاسبةp ∨ ¬q ∨ rقانونا دي مورغان
النفي يحوّل ∧ إلى ∨ و∨ إلى ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
يدفع قانونا دي مورغان النفي إلى داخل العطف أو الفصل، ويقلبان الرابط في الطريق. وبهذا تُساق الصيغة نحو صورة قياسية، وبهذا تُبسَّط النفيات في الشيفرة وفي الدارات.
في الحاسبة¬(p ∧ q) ≡ ¬p ∨ ¬qالنفي المزدوج
النفي مرتين يعيد الأصل: ¬¬p ≡ p.
النفي المزدوج صالح في المنطق الكلاسيكي في الاتجاهين، فـ ¬¬p وp قابلتان للتبادل دائمًا. أما المنطق الحدسي فيبقي على اتجاه واحد من p إلى ¬¬p، وعند هذا الحد يفترق النظامان.
في الحاسبة¬¬p ≡ pجبر بوول والدارات
جبر بوول
جبر القيمتين، وعملياته ∧ و∨ و¬.
جبر بوول هو منطق القضايا مكتوبًا حسابًا على 0 و1، بقوانين — الإبدال والتوزيع والامتصاص ودي مورغان — تتيح إعادة كتابة العبارات وتبسيطها. وهو الرياضيات التي تُصمَّم بها الدارات الرقمية.
في الحاسبة(p ∧ q) ∨ (p ∧ ¬q) ≡ pخريطة كارنو
شبكة لجدول الصدق تجعل التبسيطات ظاهرة للعين.
ترتّب خريطة كارنو السطور بحيث لا تختلف الخانتان المتجاورتان إلا في متغير واحد، وتلتقي الحواف بعضها ببعض. وتُكتب أيضًا K-map أو kmap. وعندئذ تُقرأ المستطيلات المؤلفة من آحاد متجاورة بأحجام 1 أو 2 أو 4 أو 8 حدودًا في أبسط عبارة.
في الحاسبة(p ∧ q) ∨ (p ∧ ¬r)مستلزم أولي
مجموعة على الخريطة لا يمكن توسيعها أكثر.
المستلزم عطف من حدود بسيطة يفرض صدق الصيغة؛ ويكون أوليًا حين يُبطل حذف أي حد منه ذلك الفرض. وعلى خريطة كارنو تكون المستلزمات الأولية أكبر المستطيلات المؤلفة من آحاد.
مستلزم أولي جوهري
المستلزم الأولي الوحيد الذي يغطي واحدًا بعينه.
إذا لم ينتمِ واحد على الخريطة إلا إلى مجموعة كبرى واحدة، وجب أن ترد تلك المجموعة في كل تغطية صغرى، فتؤخذ أولًا. وما يتبقى هو الجزء الذي يحتاج فعلًا إلى بحث.
بوابة منطقية
عنصر دارة يحسب رابطًا واحدًا على مدخلاته.
بوابات AND وOR وNOT وNAND وNOR وXOR هي نظائر الروابط في العتاد. والصيغة والدارة شيء واحد مرسوم مرتين، ولهذا تستطيع الحاسبة عرض عبارة على هيئة مخطط بوابات.
في الحاسبة(p ∧ q) ∨ ¬rالبرهان والاستدلال
قاعدة استدلال
خطوة مأذون بها من صيغ مستخرجة إلى صيغة جديدة.
قاعدة الاستدلال نمط مثل رفع المقدَّم، يجوز تطبيقه متى توافرت صيغ على الشكل المطلوب. وتُبنى أنظمة البرهان من حفنة منها، مختارة بحيث لا تُستخرج إلا نتائج لازمة.
رفع المقدَّم
من p → q ومن p يلزم q.
رفع المقدَّم هو القاعدة الأساس للشرطية: فمتى توافرت شرطية ومقدَّمها لزم التالي. وصحتها ظاهرة في جدول الصدق: فالسطر الوحيد الذي تصدق فيه المقدمتان تصدق فيه النتيجة أيضًا.
في الحاسبةp → q, p ⊨ qرفع التالي
من p → q ومن ¬q يلزم ¬p.
يسير رفع التالي في الشرطية إلى الوراء: فإذا كذب التالي استحال أن يصدق المقدَّم. وهو نقيض العكس في العمل، وهو صورة كل حجة تدحض فرضية باختبار تنبؤاتها.
في الحاسبةp → q, ¬q ⊨ ¬pالقياس الشرطي
من p → q ومن q → r يلزم p → r.
يصل القياس الشرطي الشرطيات بعضها ببعض، وهذا ما يجعل الاشتقاقات الطويلة ممكنة: إذ تحمل كل حلقة الحجة خطوة أبعد دون تأكيد أي مقدمة.
في الحاسبةp → q, q → r ⊨ p → rالقياس الفصلي
من p ∨ q ومن ¬p يلزم q.
يحذف القياس الفصلي البديل المستبعد: فإن صدق أحد بديلين ولم يصدق الأول وجب أن يصدق الثاني. وهذه هي القاعدة وراء الاستدلال بالحذف.
في الحاسبةp ∨ q, ¬p ⊨ qالاستنباط الطبيعي
إثبات نتيجة بتطبيق قواعد الاستدلال خطوة خطوة.
يستخرج الاستنباط الطبيعي نتيجة من المقدمات بقواعد إدخال وحذف لكل رابط، مع السماح بفروض مؤقتة تُرفع لاحقًا. وهو يبرهن ما يتحقق منه جدول الصدق، لكن دون استعراض كل سطر.
البرهان بالخلف
افترض النقيض، استخرج تناقضًا، فاثبت الأصل.
لإثبات φ يُفترض ¬φ ويُستخرج شيء على صورة ψ ∧ ¬ψ. ولما كان لا تأويل يصدّق تناقضًا، بطل الفرض ولزمت φ. وعلى هذا النحو تمضي عادة براهين اللاجذرية واللانهاية.
في الحاسبةp ∧ ¬pتصديق التالي
الخطوة الفاسدة من p → q ومن q إلى p.
صدق التالي لا يثبت المقدَّم: فقد يكون شيء آخر هو ما أحدثه. وتعرض الحاسبة النموذج المضاد — p كاذبة وq صادقة — وهو السطر الذي يفصل هذا عن رفع المقدَّم.
في الحاسبةp → q, q ⊨ pرفع المقدَّم بالنفي
الخطوة الفاسدة من p → q ومن ¬p إلى ¬q.
لا تقول الشرطية شيئًا عما يحدث حين يكذب مقدَّمها، فاستبعاد المقدَّم يترك التالي مفتوحًا. والنموذج المضاد هو السطر الذي تكذب فيه p وتصدق q.
في الحاسبةp → q, ¬p ⊨ ¬qما بعد منطق القضايا
منطق المحمولات
منطق ينظر داخل القضايا إلى الأشياء وخصائصها.
يضيف منطق المحمولات محمولات وحدودًا وأسوارًا، فتصير «كل عدد أولي أكبر من اثنين فردي» صيغة لا حرفًا واحدًا. وهو أقوى تعبيرًا من منطق القضايا قطعًا، ولا يمكن لجدول صدق أن يبتّ فيه.
سور
∀ / ∃رمز يبيّن على كم شيء يصدق المحمول.
السوران الكلاسيكيان هما ∀ (كل) و∃ (واحد على الأقل)، وكل منهما نفي للآخر مع نفي مضمونه. والمتغير الذي يقيده السور هو ما يميز منطق المحمولات من منطق القضايا.
السور الكلي
∀∀x φ: تصدق φ على كل شيء في المجال.
تُدحض الدعوى الكلية بمثال مضاد واحد، وتصدق صدقًا خاويًا على مجال خالٍ. و∀x φ مكافئة لـ ¬∃x ¬φ، وهي نظير قانوني دي مورغان في الأسوار.
السور الوجودي
∃∃x φ: تصدق φ على شيء واحد على الأقل في المجال.
تثبت الدعوى الوجودية بإبراز شاهد واحد. و∃x φ مكافئة لـ ¬∀x ¬φ، فيمكن تعريف كل سور بالآخر مع النفي.
منطق الجهات
□ / ◇منطق يزاد عليه «بالضرورة» (□) و«بالإمكان» (◇).
يقوّم منطق الجهات الصيغ في عوالم ممكنة لا في تأويل واحد: فتصدق □φ متى صدقت φ في كل عالم متاح، وتصدق ◇φ متى صدقت في عالم ما. وتغيير معنى «متاح» يعطي الأنظمة الجهية المختلفة.