دالة الحقيقة

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

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

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

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

" تعتقد ماري أن آل غور كان رئيسًا للولايات المتحدة الأمريكية في 20 أبريل 2000 "

صحيح بينما

" ماري تعتقد أن القمر مصنوع من الجبن الأخضر "

هذا غير صحيح. في كلتا الحالتين، كل جملة من الجمل المكونة (مثل " كان آل غور رئيسًا للولايات المتحدة الأمريكية في 20 أبريل 2000 " و" القمر مصنوع من الجبن الأخضر ") خاطئة، لكن كل جملة مركبة تتكون من عبارة " ماري تعتقد أن " تختلف في قيمتها الصوابية. أي أن القيمة الصوابية لجملة من نوع " ماري تعتقد أن... " لا تُحدد فقط بالقيمة الصوابية لجملتها المكونة، وبالتالي فإن الرابط (الأحادي) (أو ببساطة العامل لأنه أحادي) غير وظيفي من الناحية الصوابية.

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

في المنطق الثنائي القيم، توجد ست عشرة دالة صدق محتملة، تُسمى أيضًا الدوال البوليانية ، لمدخلين P و Q. تُقابل كل دالة من هذه الدوال جدول صدق لرابط منطقي معين في المنطق الكلاسيكي، بما في ذلك حالات شاذة مثل دالة لا تعتمد على أحد أو كلا وسيطيها. يُرمز للصدق والكذب بالرقمين 1 و 0 على التوالي في جداول الصدق التالية اختصارًا.

تكرار / صحيح الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين ${\displaystyle \top }$"قمة" P${\displaystyle \lor }$${\displaystyle \neg }$P V pq   سؤال 0 1 P 0    1   1  1    1   1	تناقض / خطأ الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين ${\displaystyle \bot }$"قاع" P${\displaystyle \land }$${\displaystyle \neg }$P O pq   سؤال 0 1 P 0    0   0  1    0   0
الاقتراح P الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P p I pq   سؤال 0 1 P 0    0   0  1    1   1	نفي P الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين ${\displaystyle \neg }$P ~ P NOT P  N p F pq   سؤال 0 1 P 0    1   1  1    0   0
الفرضية Q الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين سؤال q H pq   سؤال 0 1 P 0    0   1  1    0   1	نفي Q الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين ${\displaystyle \neg }$Q ~ Q ليس Q  N q G pq   سؤال 0 1 P 0    1   0  1    1   0
اِقتِران الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \land }$كيو بي${\displaystyle \cap }$Q P · Q P AND Q     P${\displaystyle \not \rightarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \not \leftarrow }$سؤال${\displaystyle \neg }$P${\displaystyle \downarrow }$${\displaystyle \neg }$Q K pq   سؤال 0 1 P 0    0   0  1    0   1	عدم الاقتران/الإنكار البديل الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle {\overline {\land }}}$كيو بي${\displaystyle \uparrow }$Q P  NAND Q  ${\displaystyle \neg }$P${\displaystyle \lor }$${\displaystyle \neg }$كيو بي${\displaystyle \rightarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \leftarrow }$Q D pq   سؤال 0 1 P 0    1   1  1    1   0
الانفصال الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \lor }$كيو بي${\displaystyle \cup }$كيو بي${\displaystyle +}$Q P  OR Q  P${\displaystyle \leftarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \rightarrow }$سؤال${\displaystyle \neg }$P${\displaystyle \uparrow }$${\displaystyle \neg }$س أ ب ق   سؤال 0 1 P 0    0   1  1    1   1	عدم الانفصال/الإنكار المشترك الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle {\overline {\lor }}}$كيو بي${\displaystyle \downarrow }$Q P  NOR Q  ${\displaystyle \neg }$P${\displaystyle \land }$${\displaystyle \neg }$كيو بي${\displaystyle \not \leftarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \not \rightarrow }$Q X pq   سؤال 0 1 P 0    1   0  1    0   0
الآثار المادية الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \rightarrow }$كيو بي${\displaystyle \subseteq }$كيو بي${\displaystyle \leq }$Q P  تعني Q  ${\displaystyle \neg }$P${\displaystyle \lor }$كيو بي${\displaystyle \uparrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \leftarrow }$${\displaystyle \neg }$Q C pq   سؤال 0 1 P 0    1   1  1    0   1	عدم وجود دلالة مادية الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \not \rightarrow }$كيو بي${\displaystyle \not \subseteq }$كيو بي${\displaystyle >}$Q P  NIMPLY Q  P${\displaystyle \land }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \downarrow }$سؤال${\displaystyle \neg }$P${\displaystyle \not \leftarrow }$${\displaystyle \neg }$Q L pq   سؤال 0 1 P 0    0   0  1    1   0
الاستلزام العكسي الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \leftarrow }$كيو بي${\displaystyle \supseteq }$كيو بي${\displaystyle \geq }$Q Q  IMPLY P  P${\displaystyle \lor }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \uparrow }$سؤال${\displaystyle \neg }$P${\displaystyle \rightarrow }$${\displaystyle \neg }$Q B pq   سؤال 0 1 P 0    1   0  1    1   1	عكس عدم الاستلزام الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \not \leftarrow }$كيو بي${\displaystyle \not \supseteq }$كيو بي${\displaystyle <}$Q Q  NIMPLY P  ${\displaystyle \neg }$P${\displaystyle \land }$كيو بي${\displaystyle \downarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \not \rightarrow }$${\displaystyle \neg }$Q M pq   سؤال 0 1 P 0    0   1  1    0   0
التكافؤ/الشرط الثنائي الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \leftrightarrow }$كيو بي${\displaystyle \equiv }$كيو بي${\displaystyle \odot }$Q P  XNOR Q  P${\displaystyle \not \leftrightarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \not \leftrightarrow }$سؤال${\displaystyle \neg }$P${\displaystyle \leftrightarrow }$${\displaystyle \neg }$Q E pq   سؤال 0 1 P 0    1   0  1    0   1	عدم التكافؤ/الفصل الحصري الترميز الصيغ المتكافئة جدول الحقيقة مخطط فين P${\displaystyle \not \leftrightarrow }$كيو بي${\displaystyle \not \equiv }$Q P ⨁ Q P  XOR Q  P${\displaystyle \leftrightarrow }$${\displaystyle \neg }$سؤال${\displaystyle \neg }$P${\displaystyle \leftrightarrow }$سؤال${\displaystyle \neg }$P${\displaystyle \not \leftrightarrow }$${\displaystyle \neg }$Q J pq   سؤال 0 1 P 0    0   1  1    1   0

بما أن الدالة يمكن التعبير عنها كتركيب ، فإن حساب التفاضل والتكامل المنطقي القائم على دوال الصدق لا يحتاج إلى رموز مخصصة لجميع الدوال المذكورة أعلاه ليكون كاملاً وظيفيًا . يُعبَّر عن ذلك في حساب القضايا كتكافؤ منطقي لبعض العبارات المركبة. على سبيل المثال، في المنطق الكلاسيكي، يكون ¬P ∨ Q مكافئًا لـ P → Q. وبالتالي ، فإن عامل الشرط "→" ليس ضروريًا لنظام منطقي قائم على المنطق الكلاسيكي إذا كان "¬" (ليس) و"∨" (أو) مستخدمين بالفعل.

تُسمى المجموعة الدنيا من المؤثرات التي يمكنها التعبير عن كل عبارة قابلة للتعبير عنها في حساب القضايا مجموعة وظيفية كاملة دنيا . وتتحقق المجموعة الوظيفية الكاملة الدنيا باستخدام NAND فقط {↑} و NOR فقط {↓}.

فيما يلي الحد الأدنى من المجموعات الوظيفية الكاملة للمؤثرات التي لا تتجاوز عدد معاملاتها 2: ^{[ 5 ]}

عنصر واحد

{↑}, {↓}.

عنصران

${\displaystyle \{\vee ,\neg \}}$،${\displaystyle \{\wedge ,\neg \}}$،${\displaystyle \{\to ,\neg \}}$،${\displaystyle \{\gets ,\neg \}}$،${\displaystyle \{\to ,\bot \}}$،${\displaystyle \{\gets ,\bot \}}$،${\displaystyle \{\to ,\nleftrightarrow \}}$،${\displaystyle \{\gets ,\nleftrightarrow \}}$،${\displaystyle \{\to ,\nrightarrow \}}$،${\displaystyle \{\to ,\nleftarrow \}}$،${\displaystyle \{\gets ,\nrightarrow \}}$،${\displaystyle \{\gets ,\nleftarrow \}}$،${\displaystyle \{\nrightarrow ,\neg \}}$،${\displaystyle \{\nleftarrow ,\neg \}}$،${\displaystyle \{\nrightarrow ,\top \}}$،${\displaystyle \{\nleftarrow ,\top \}}$،${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$،${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$.

ثلاثة عناصر

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$،${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$،${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$،${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$،${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$،${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$.

تتمتع بعض دوال الصدق بخصائص يمكن التعبير عنها في النظريات التي تتضمن الرابط المنطقي المقابل. ومن بين هذه الخصائص التي قد تمتلكها دالة الصدق الثنائية (أو الرابط المنطقي المقابل لها):

• الترابطية : ضمن تعبير يحتوي على اثنين أو أكثر من نفس الروابط الترابطية في صف واحد، لا يهم ترتيب العمليات طالما لم يتم تغيير تسلسل المعاملات.
• خاصية التبديل : يمكن تبديل معاملات الرابط دون التأثير على قيمة الصواب للتعبير.
• التوزيعية : الرابط الذي يرمز له بـ · يتوزع على رابط آخر يرمز له بـ +، إذا كان a · ( b + c ) = ( a · b ) + ( a · c ) لجميع المعاملات a ، b ، c .
• خاصية التكرار : عندما تكون معاملات العملية متطابقة، فإن الرابط يعطي نفس المعامل كنتيجة. بعبارة أخرى، تحافظ العملية على الصدق والكذب معًا (انظر أدناه).
• الامتصاص : زوج من الروابط${\displaystyle \land ,\lor }$يحقق قانون الامتصاص إذا${\displaystyle a\land (a\lor b)=a\lor (a\land b)=a}$لجميع المعاملات a و b .

تكون مجموعة دوال الحقيقة كاملة وظيفيًا إذا وفقط إذا كانت تحتوي، لكل خاصية من الخصائص الخمس التالية، على عنصر واحد على الأقل يفتقر إليها:

• دالة رتيبة : إذا كانت _{f (} a1 , ... _{, an} ) ≤ f ( b1 , ..., bn ) لجميع _{a1 ,} ..., an _و b1 ,..., bn ∈ {0,1} بحيث يكون a1 ≤ b1 _و a2 ≤ _{b2 و} ... _و an _≤ bn _. على سبيل _المثال ،${\displaystyle \vee ,\wedge ,\top ,\bot }$.
• التحويل الخطي : بالنسبة لكل متغير، فإن تغيير قيمته إما دائمًا أو لا يغير أبدًا قيمة الصواب للعملية، وذلك لجميع القيم الثابتة لجميع المتغيرات الأخرى. مثال:${\displaystyle \neg ,\leftrightarrow }$، ${\displaystyle \not \leftrightarrow ,\top ,\bot }$.
• الازدواجية الذاتية : إن قراءة قيم الصواب للعملية من أعلى إلى أسفل في جدول الصواب الخاص بها هي نفسها أخذ مكمل قراءتها من أسفل إلى أعلى؛ بعبارة أخرى، f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). على سبيل المثال،${\displaystyle \neg }$.
• الحفاظ على الصدق : التفسير الذي تُسند بموجبه قيمة صدق صحيحة لجميع المتغيرات ينتج عنه قيمة صدق صحيحة كنتيجة لهذه العمليات. مثال:${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$(انظر الصلاحية )
• الحفاظ على الزيف : التفسير الذي تُسند بموجبه قيمة صواب خاطئة لجميع المتغيرات ينتج عنه قيمة صواب خاطئة كنتيجة لهذه العمليات. مثال:${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$(انظر الصلاحية )

بدلاً من استخدام جداول الصواب ، يمكن تفسير رموز الربط المنطقي بواسطة دالة تفسير ومجموعة كاملة وظيفيًا من دوال الصواب (جاموت 1991)، كما هو موضح في مبدأ تركيب المعنى. لنفترض أن I دالة تفسير، و Φ وΨ جملتان، ولنفترض أن دالة الصواب f معرفة كما _{يلي :}

• دالة _nand (T,T) = F؛ دالة _nand (T,F) = دالة _nand (F,T) = دالة _nand (F,F) = T

ثم، من أجل التسهيل، يتم تعريف f _not و f _أو f _و وهكذا بواسطة f _nand :

• f _not ( x ) = f _nand ( x , x )
• f _for ( x , y ) = f _nand ( f _not ( x ), f _not ( y ))
• f _and ( x , y ) = f _not ( f _nand ( x , y ))

أو بدلاً من ذلك، يتم تعريف f و _not و f _و f _و وهكذا بشكل مباشر:

• f _ليس (صحيح) = خطأ؛ f _ليس (خطأ) = خطأ؛
• f _أو (T,T) = f _أو (T,F) = f _أو (F,T) = T؛ f _أو (F,F) = F
• f _و (T,T) = T؛ f _و (T,F) = f _و (F,T) = f _و (F,F) = F

ثم

إلخ.

_{وبالتالي ،} إذا كانت S جملةً عبارة عن سلسلة من الرموز تتكون من رموز منطقية v1 ... vn تمثل روابط منطقية، _{ورموز غير منطقية} c1 ... cn ، _فإنه إذا وفقط إذا تم توفير I ( v1 ₎ ... I ( vn ) لتفسير v1 _إلى vn بواسطة fnand _{( أو أي مجموعة أخرى من دوال الصدق الوظيفية الكاملة) ،} فإن قيمة الصدق لـ${\displaystyle I(s)}$يتم تحديدها بالكامل من خلال قيم الصواب لـ _c1 ... cn ، _أي لـ I ( c1 ) ... I ( cn ) . بعبارة أخرى، وكما _هو متوقع ومطلوب، _فإن S تكون صحيحة أو خاطئة فقط في ظل تفسير جميع رموزها غير المنطقية.

باستخدام الدوال المحددة أعلاه، يمكننا تقديم تعريف رسمي لدالة الصدق الخاصة بالقضية. ^{[ 6 ]}

ليكن PROP مجموعة جميع المتغيرات الافتراضية،

${\displaystyle PROP=\{p_{1},p_{2},\dots \}}$

نُعرّف عملية إسناد الصواب بأنها أي دالة${\displaystyle \phi :PROP\to \{T,F\}}$لذا، فإنّ تعيين القيمة المنطقية هو ربط كل متغير منطقي بقيمة منطقية محددة. وهذا يُشابه فعلياً صفاً معيناً في جدول الصواب الخاص بالقضية.

لمهمة التحقق من الحقيقة،${\displaystyle \phi }$، نُعرّف تعيين الحقيقة الموسّع الخاص به ،${\displaystyle {\overline {\phi }}}$على النحو التالي. وهذا يمتد${\displaystyle \phi }$إلى وظيفة جديدة${\displaystyle {\overline {\phi }}}$والتي يكون مجالها مساوياً لمجموعة جميع الصيغ المنطقية. مدى${\displaystyle {\overline {\phi }}}$لا يزال${\displaystyle \{T,F\}}$.

1. لو${\displaystyle A\in PROP}$ثم${\displaystyle {\overline {\phi }}(A)=\phi (A)}$.
2. إذا كانت A و B أي صيغتين منطقيتين، فإن
   1. ${\displaystyle {\overline {\phi }}(\neg A)=f_{\text{not}}({\overline {\phi }}(A))}$.
   2. ${\displaystyle {\overline {\phi }}(A\land B)=f_{\text{and}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$.
   3. ${\displaystyle {\overline {\phi }}(A\lor B)=f_{\text{or}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$.
   4. ${\displaystyle {\overline {\phi }}(A\to B)={\overline {\phi }}(\neg A\lor B)}$.
   5. ${\displaystyle {\overline {\phi }}(A\leftrightarrow B)={\overline {\phi }}((A\to B)\land (B\to A))}$.

وأخيرًا، بعد أن حددنا تعيين الصدق الموسع، يمكننا استخدام ذلك لتعريف دالة الصدق لقضية ما. بالنسبة لقضية ما، A ، فإن دالة صدقها هي :${\displaystyle f_{A}}$، مجالها يساوي مجموعة جميع قيم الصواب، ومدىها يساوي${\displaystyle \{T,F\}}$.

يتم تعريفها، لكل عملية تعيين قيمة صحيحة${\displaystyle \phi }$، بواسطة${\displaystyle f_{A}(\phi )={\overline {\phi }}(A)}$القيمة المعطاة بواسطة${\displaystyle {\overline {\phi }}(A)}$وهو نفسه المعروض في العمود الأخير من جدول الحقيقة لـ A ، في الصف المحدد بـ${\displaystyle \phi }$.

Logical operators are implemented as logic gates in digital circuits. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gates. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.

The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.

The fact that all truth functions can be expressed with NOR alone is demonstrated by the Apollo Guidance Computer.

• This article incorporates material from TruthFunction on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

• Józef Maria Bocheński (1959), A Précis of Mathematical Logic, translated from the French and German versions by Otto Bird, Dordrecht, South Holland: D. Reidel.
• ألونزو تشيرش (1944)، مقدمة في المنطق الرياضي ، برينستون، نيوجيرسي: مطبعة جامعة برينستون. انظر المقدمة للاطلاع على تاريخ مفهوم دالة الصدق.