التمام الوظيفي

دوال الصدق

أسند الدرس الخاص بـدلالات منطق القضايا إلى كل صيغة، في كل إسناد، قيمةَ صدق، وبيّن أن هذه القيمة لا تتوقف إلا على قيم المتغيرات التي ترد فيها؛ ومن ثم فلكل صيغة ذات $n$ من المتغيرات جدول صدق من $2^{n}$ سطرًا. والسؤال في هذا الدرس هو السؤال العكسي. إذا أُعطي جدول ما، أي عمود من الآحاد والأصفار مكتوب كيفما اتفق بجانب الأسطر الـ$2^{n}$، فهل توجد صيغة يكون هو جدولها؟ إن صح ذلك لكل جدول، فليس في اللغة ثغرات تعبيرية: كل ما يمكن قوله عن قيمة صدق $n$ من الجمل الخبرية، بدلالة قيمها، يُقال بصيغة. ولما كانت كل صيغة مركبة في هذه الدورة نفيًا مشتركًا، فإن الجواب سيقول أيضًا هل يكفي رابط واحد لقول كل شيء.

ما يُستعمل من الدروس السابقة

الإسناد دالة $v$ من مجموعة المتغيرات $\{v_1, v_2, \ldots\}$ إلى $\{0, 1\}$، حيث $1$ هو الصواب و$0$ هو الخطأ؛ وتمديده إلى جميع الصيغ، الذي يُكتب أيضًا $v$، معرَّف بالتراجع: $v((\varphi \downarrow \psi)) = 1$ إذا وفقط إذا كان $v(\varphi) = 0$ و$v(\psi) = 0$. وانطلاقًا من الاختصارات المعتمدة، حسب الدرس نفسه، في مبرهنة قيم الروابط المشتقة، قيمة كل رابط؛ وهي، مكتوبةً بالجمع والضرب، كما يلي، لكل إسناد $v$ ولجميع الصيغ $\varphi$ و$\psi$:

وفوق ذلك، $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$، وهي تساوي $1$ إذا وفقط إذا كان $v(\varphi) = v(\psi)$، و$v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$، وهي تساوي $1$ إذا وفقط إذا كان $v(\varphi) \neq v(\psi)$. ولما كانت القيم $0$ أو $1$، فإن مربع القيمة هو القيمة نفسها، $v(\varphi)\,v(\varphi) = v(\varphi)$، وحاصل ضرب قيم يساوي $1$ إذا وفقط إذا ساوى كل عامل $1$؛ وستُستعمل الملاحظتان دون تكرارهما. ويُستعمل أيضًا توطئة التطابق: إذا تطابق إسنادان على متغيرات $\varphi$، أي على المتغيرات التي هي صيغ جزئية من $\varphi$، أعطيا $\varphi$ القيمة نفسها. ومن الدرس الخاص بـالنتيجة الدلالية والتكافؤ الدلالي يؤخذ التكافؤ الدلالي: $\varphi \eqsem \psi$ حين يكون $v(\varphi) = v(\psi)$ لكل إسناد $v$. وأخيرًا، يسري اصطلاح الحروف من الدرس الخاص بـالصورنة: $p$ و$q$ و$r$ تدل على المتغيرات $v_1$ و$v_2$ و$v_3$.

دوال الصدق وعددها

ليكن $n$ عددًا طبيعيًا. السطر ذو $n$ من القيم متتالية $a = (a_1, \ldots, a_n)$ يكون فيها كل $a_i$ مساويًا لـ$0$ أو لـ$1$؛ ومجموعتها كلها يُرمز إليها بـ$\{0, 1\}^{n}$. ودالة الصدق ذات $n$ من الوسائط دالة

تُسند إلى كل سطر قيمة صدق. وتُعرض في جدول: تُكتب الأسطر بترتيب الجدول، بدءًا من السطر الذي تكون فيه جميع القيم $1$ (لوسيطين: $1\,1$، $1\,0$، $0\,1$، $0\,0$)، وبجانب كل سطر تُكتب قيمته. فدالة الصدق إذن جدول صدق بلا صيغة: العمود الأيمن، دون أن يُكتب شيء في رأسه.

صيغ تمثّل دوالّ

ترتبط الصيغة ودالة الصدق على النحو التالي. إذا كانت $\varphi$ صيغة متغيراتها من بين $v_1, \ldots, v_n$، يقال إن $\varphi$ تمثّل دالة الصدق $f$ ذات $n$ من الوسائط حين يكون، لكل إسناد $v$،

أي حين يكون جدول $\varphi$، مكتوبًا بالمتغيرات $v_1, \ldots, v_n$، هو جدول $f$. والشرط على المتغيرات ليس تفصيلًا: فالصيغة $(p \wedge q)$ لا تمثّل أي دالة ذات وسيط واحد، لأن قيمتها لا تتوقف على قيمة $p$ وحدها.

توجد صيغ لا متناهية العدد متغيراتها من بين $v_1, \ldots, v_n$ ولا يوجد إلا $2^{2^{n}}$ من الدوال؛ ومن ثم تمثّل صيغ كثيرة الدالة نفسها، والقضية تقول إنها بالضبط الصيغ المتكافئة فيما بينها. وما بقي أن يُعرف هو هل كل دالة تمثّلها صيغة ما، أم أن بعض الجداول تبقى بلا صيغة يكون هو جدولها.