دالة منطقية

الروابط المنطقية
لا ${\displaystyle \neg A}$,${\displaystyle -A}$,${\displaystyle {\overline {A}}}$,${\displaystyle \sim A}$ و ${\displaystyle A\and B}$,${\displaystyle A\cdot B}$,${\displaystyle AB}$,${\displaystyle A\&B}$,${\displaystyle A\&\&B}$ ذاكرة ناند ${\displaystyle A{\overline {\land }}B}$,${\displaystyle A\uparrow B}$,${\displaystyle A\mid B}$,${\displaystyle {\overline {A\cdot B}}}$ أو ${\displaystyle A\أو B}$,${\displaystyle أ+ب}$,${\displaystyle A\mid B}$,${\displaystyle A\parallel B}$ ولا ${\displaystyle A{\overline {\lor }}B}$,${\displaystyle A\downarrow B}$,${\displaystyle {\overline {أ+ب}}}$ إكس نور ${\displaystyle A\ {\text{XNOR}}\ B}$ └ مكافئ ${\displaystyle A\equiv B}$,${\displaystyle A\Leftrightarrow B}$,${\displaystyle A\leftrightharpoons B}$ إكس أو آر ${\displaystyle A{\underline {\lor }}B}$,${\displaystyle A\oplus B}$ └غير متكافئ ${\displaystyle A\not \equiv B}$,${\displaystyle A\not \Leftrightarrow B}$,${\displaystyle A\nleftrightarrow B}$ يعني ${\displaystyle A\Rightarrow B}$,${\displaystyle A\supset B}$,${\displaystyle A\rightarrow B}$ محادثة ${\displaystyle A\السهم الأيسر ب}$,${\displaystyle A\subset B}$,${\displaystyle A\leftarrow B}$
المفاهيم ذات الصلة
حساب القضايا منطق المسند الجبر البولياني جدول الحقيقة دالة الحقيقة دالة منطقية اكتمال وظيفي النطاق (المنطق)
التطبيقات
المنطق الرقمي لغات البرمجة المنطق الرياضي فلسفة المنطق
فئة
ف ت هـ

في الرياضيات ، الدالة المنطقية هي دالة تفترض وسيطاتها ونتيجتها قيمًا من مجموعة مكونة من عنصرين (عادةً {صواب، خطأ}، {0,1} أو {-1,1}). ^[1] [ ^2] الأسماء البديلة هي دالة التبديل ، والتي تُستخدم بشكل خاص في أدبيات علوم الكمبيوتر القديمة ، ^{[3] [4]} ودالة الحقيقة (أو الدالة المنطقية) ، والتي تُستخدم في المنطق . الدوال المنطقية هي موضوع الجبر المنطقي ونظرية التبديل . ^[5]

تتخذ الدالة البوليانية الشكل ، حيث تُعرف بالمجال البولياني وهي عدد صحيح غير سلبي يُسمى نطاق الدالة. في الحالة حيث ، تكون الدالة عنصرًا ثابتًا في . الدالة البوليانية ذات المخرجات المتعددة، مع هي دالة بوليانية متجهية أو متجهة القيمة ( صندوق S في التشفير المتماثل ). ^[6]${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$${\displaystyle \{0,1\}}$${\displaystyle k}$${\displaystyle k=0}$${\displaystyle \{0,1\}}$${\displaystyle f:\{0,1\}^{k}\إلى \{0,1\}^{m}}$${\displaystyle m>1}$

هناك وظائف منطقية مختلفة تحتوي على وسيطات؛ تساوي عدد جداول الحقيقة المختلفة التي تحتوي على إدخالات. ${\displaystyle 2^{2^{k}}}$${\displaystyle k}$${\displaystyle 2^{k}}$

يمكن التعبير عن كل دالة بوليانية -ary كصيغة تقريرية في المتغيرات ، وتكون الصيغتان التقريريتان متكافئتين منطقيًا إذا وفقط إذا عبرتا عن نفس الدالة البوليانية. ${\displaystyle k}$${\displaystyle k}$${\displaystyle x_{1},...,x_{k}}$

الدوال المنطقية المتماثلة الأولية ( الروابط المنطقية أو البوابات المنطقية ) هي:

• NOT ، النفي أو المكمل - الذي يتلقى مدخلاً واحدًا ويعيد true عندما يكون هذا المدخل خاطئًا ("ليس")
• AND أو حرف العطف - صحيح عندما تكون جميع المدخلات صحيحة ("كلاهما")
• أو أو الانفصال - صحيح عندما يكون أي إدخال صحيحًا ("إما")
• XOR أو الانفصال الحصري - صحيح عندما يكون أحد مدخلاته صحيحًا والآخر خاطئًا ("غير متساوٍ")
• NAND أو Sheffer stroke - صحيح عندما لا تكون جميع المدخلات صحيحة ("ليس كلاهما")
• NOR أو منطقي nor - صحيح عندما لا يكون أي من المدخلات صحيحًا ("لا شيء")
• XNOR أو المساواة المنطقية - صحيح عندما يكون كلا المدخلين متماثلين ("متساويين")

مثال على وظيفة أكثر تعقيدًا هي وظيفة الأغلبية (لعدد فردي من المدخلات).

يمكن تحديد الدالة المنطقية بعدة طرق:

• جدول الحقيقة : يسرد صراحةً قيمته لجميع القيم الممكنة للحجج
  • مخطط ماركواند: قيم جدول الحقيقة مرتبة في شبكة ثنائية الأبعاد (تستخدم في خريطة كارنو )
  • مخطط القرار الثنائي ، يسرد قيم جدول الحقيقة في أسفل شجرة ثنائية
  • مخطط فين ، يصور قيم جدول الحقيقة كتلوين لمناطق المستوى

جبريًا، كصيغة تقريرية باستخدام وظائف منطقية أولية:

• صيغة النفي الطبيعية ، وهي مزيج عشوائي من AND وOR للحجج ومكملاتها
• صيغة طبيعية منفصلة ، ​​كـ OR لـ AND للحجج ومكملاتها
• صيغة الربط الطبيعية ، كـ AND من ORs للحجج ومكملاتها
• الشكل الطبيعي القياسي ، صيغة موحدة تحدد الدالة بشكل فريد:
  • الشكل الجبري الطبيعي أو متعدد حدود زيجالكين ، كـ XOR لـ ANDs للحجج (لا يُسمح بالمكملات)
  • صيغة طبيعية كاملة (قانونية) منفصلة ، ​​أو من ANDs، كل منها يحتوي على كل وسيطة أو متمم ( minterms )
  • صيغة الجمع الطبيعية الكاملة (القانونية) ، AND من ORs، كل منها يحتوي على كل وسيطة أو متمم ( maxterms )
  • صيغة بليك الكنسية ، أو لجميع المشتقات الأولية للدالة

يمكن أيضًا عرض الصيغ المنطقية على هيئة رسم بياني:

• الرسم البياني غير الدوري الموجه حسب الاقتراح
  • مخطط الدائرة الرقمية للبوابات المنطقية ، دائرة منطقية
  • رسم بياني عاكس و ، باستخدام AND وNOT فقط

من أجل تحسين الدوائر الإلكترونية، يمكن تقليل الصيغ المنطقية باستخدام خوارزمية كوين-ماكلوسكي أو خريطة كارنو .

يمكن أن تحتوي الدالة المنطقية على مجموعة متنوعة من الخصائص: ^[7]

• الثابت : يكون دائمًا صحيحًا أو دائمًا خطأ بغض النظر عن حججه.
• رتيب : بالنسبة لكل مجموعة من قيم الوسيطة، فإن تغيير الوسيطة من false إلى true يمكن أن يتسبب فقط في تحول الناتج من false إلى true وليس من true إلى false. يقال إن الدالة غير متماثلة في متغير معين إذا كانت رتيبة فيما يتعلق بالتغييرات في هذا المتغير.
• خطي : بالنسبة لكل متغير، فإن قلب قيمة المتغير إما أن يحدث فرقًا دائمًا في قيمة الحقيقة أو لا يحدث فرقًا أبدًا ( دالة التكافؤ ).
• متماثل : القيمة لا تعتمد على ترتيب وسيطاتها.
• القراءة مرة واحدة : يمكن التعبير عنها باستخدام أدوات الربط والفصل والنفي مع مثيل واحد لكل متغير.
• متوازنة : إذا كان جدول الحقيقة الخاص بها يحتوي على عدد متساوٍ من الأصفار والواحدات. وزن هامينج للدالة هو عدد الواحدات في جدول الحقيقة.
• منحني : مشتقاته كلها متوازنة (طيف الارتباط الذاتي يساوي صفرًا)
• الارتباط محصن ضد الترتيب m : إذا كان الناتج غير مرتبط بجميع التركيبات (الخطية) المكونة من m وسيطة على الأكثر
• مراوغ : إذا كان تقييم الدالة يتطلب دائمًا قيمة جميع الوسائط
• الدالة المنطقية هي دالة شيفر إذا كان من الممكن استخدامها لإنشاء (عن طريق التركيب) أي دالة منطقية عشوائية (انظر الاكتمال الوظيفي )
• الدرجة الجبرية للدالة هي رتبة أعلى رتبة أحادية الحدود في صورتها الجبرية الطبيعية

تحاول تعقيد الدائرة تصنيف الدوال المنطقية فيما يتعلق بالحجم أو عمق الدوائر التي يمكنها حسابها.

يمكن تحليل الدالة المنطقية باستخدام نظرية توسع بول في عوامل شانون الموجبة والسلبية ( توسع شانون )، وهي الدوال (k-1)-ary الناتجة عن تثبيت أحد الحجج (إلى صفر أو واحد). تُعرف الدوال العامة (k-ary) التي تم الحصول عليها عن طريق فرض قيد خطي على مجموعة من المدخلات (فضاء فرعي خطي) بالدوال الفرعية . ^[8]

المشتقة المنطقية للدالة إلى أحد الحجج هي دالة (k-1)-ary تكون صحيحة عندما يكون خرج الدالة حساسًا لمتغير الإدخال المختار؛ وهي XOR للعامل المساعد المطابقين. يتم استخدام المشتقة والعامل المساعد في توسع ريد-مولر . يمكن تعميم المفهوم كمشتقة k-ary في اتجاه dx، يتم الحصول عليها كفرق (XOR) للدالة عند x وx + dx. ^[8]

تحويل موبيوس ( أو تحويل بول-موبيوس ) للدالة البوليانية هو مجموعة معاملات كثير الحدود ( الشكل الجبري الطبيعي )، كدالة لمتجهات الأسس أحادية الحد. وهو تحويل عكسي ذاتي . ويمكن حسابه بكفاءة باستخدام خوارزمية الفراشة (" تحويل موبيوس السريع ")، على غرار تحويل فورييه السريع . ^{[9] الدوال البوليانية} المتزامنة تساوي تحويل موبيوس الخاص بها، أي أن قيم جدول الحقيقة (minterm) الخاصة بها تساوي معاملاتها الجبرية (أحادية الحد). ^[10] هناك 2^2^( k −1) دالة متزامنة ذات k وسيطة. ^[11]

تحويل والش للدالة البوليانية هو دالة ذات قيمة عددية صحيحة من نوع k-ary تعطي معاملات التحلل إلى دوال خطية ( دوال والش )، على غرار تحلل الدوال ذات القيمة الحقيقية إلى توافقيات بواسطة تحويل فورييه . مربعها هو طيف القدرة أو طيف والش . معامل والش لمتجه بت واحد هو مقياس لارتباط ذلك البت مع مخرجات الدالة البوليانية. يُعرف معامل والش الأقصى (بالقيمة المطلقة) بخطية الدالة . ^[8] يُعرف أعلى عدد من البتات (الترتيب) حيث تكون جميع معاملات والش تساوي 0 (أي أن الدوال الفرعية متوازنة) بالمرونة ، ويقال إن الدالة محصنة ضد الارتباط بهذا الترتيب. ^[8] تلعب معاملات والش دورًا رئيسيًا في تحليل التشفير الخطي .

الارتباط الذاتي للدالة المنطقية هو دالة ذات قيمة عددية صحيحة من نوع k-ary تعطي الارتباط بين مجموعة معينة من التغييرات في المدخلات ومخرجات الدالة. بالنسبة لمتجه بت معين، يكون مرتبطًا بوزن هامينج للمشتق في ذلك الاتجاه. يُعرف معامل الارتباط الذاتي الأقصى (بالقيمة المطلقة) بالمؤشر المطلق . ^{[7] [8]} إذا كانت جميع معاملات الارتباط الذاتي تساوي 0 (أي أن المشتقات متوازنة) لعدد معين من البتات، فيقال إن الدالة تفي بمعيار الانتشار لهذا الترتيب؛ إذا كانت جميعها تساوي صفرًا، فإن الدالة تكون دالة منحنية . ^[12] تلعب معاملات الارتباط الذاتي دورًا رئيسيًا في التحليل التفاضلي للشفرات .

ترتبط معاملات والش للدالة البوليانية ومعاملات الارتباط الذاتي الخاصة بها بما يعادل نظرية وينر-كينشين ، والتي تنص على أن الارتباط الذاتي وطيف القدرة عبارة عن زوج تحويل والش. ^[8]

يمكن توسيع هذه المفاهيم بشكل طبيعي لتشمل الدوال البوليانية المتجهة من خلال النظر في بتات الإخراج ( الإحداثيات ) الخاصة بها بشكل فردي، أو بشكل أكثر شمولاً، من خلال النظر في مجموعة جميع الدوال الخطية لبتات الإخراج، والمعروفة باسم مكوناتها . [ ^6] تُعرف مجموعة تحويلات والش للمكونات باسم جدول التقريب الخطي (LAT) ^{[13] [14]} أو مصفوفة الارتباط ؛ ^{[15] [16]} وهي تصف الارتباط بين مجموعات خطية مختلفة من بتات الإدخال والإخراج. مجموعة معاملات الارتباط الذاتي للمكونات هي جدول الارتباط الذاتي ، ^[14] المرتبط بتحويل والش للمكونات ^[17] بجدول توزيع الفروق (DDT) الأكثر استخدامًا ^{[13] [14]} والذي يسرد الارتباطات بين الاختلافات في بتات الإدخال والإخراج (انظر أيضًا: S-box ).

يمكن تمديد أي دالة بوليانية بشكل فريد (استيفاء) إلى المجال الحقيقي بواسطة كثيرة حدود متعددة الخطوط في ، يتم إنشاؤها عن طريق جمع قيم جدول الحقيقة مضروبة في كثيرات حدود المؤشر : على سبيل المثال، يكون تمديد دالة XOR الثنائية هو الذي يساوي بعض الأمثلة الأخرى هي النفي ( )، وAND ( ) وOR ( ). عندما تكون جميع المتغيرات مستقلة (لا تشترك في أي متغيرات)، يمكن إيجاد شكل كثير حدود الدالة عن طريق تطبيق كثيرات حدود العوامل في صيغة بوليانية بشكل متكرر. عندما يتم حساب المعاملات modulo 2، نحصل على الشكل الطبيعي الجبري ( كثيرة حدود Zhegalkin ). ${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}$$${\displaystyle x\oplus y}$$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$$${\displaystyle x+y-2xy}$$${\displaystyle 1-x}$${\displaystyle xy}$${\displaystyle x+y-xy}$

يمكن اشتقاق التعبيرات المباشرة لمعاملات كثيرة الحدود من خلال أخذ مشتق مناسب: هذا يعمم على أنه عكس موبيوس للمجموعة المرتبة جزئيًا من متجهات البت: حيث يشير إلى وزن متجه البت . إذا أخذنا modulo 2، فهذا هو تحويل موبيوس المنطقي ، مما يعطي معاملات الشكل الطبيعي الجبري : في كلتا الحالتين، يتم أخذ المجموع على جميع متجهات البت a المغطاة بـ m ، أي أن البتات "الواحدة" من a تشكل مجموعة فرعية من البتات الواحدية من m . $${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$$${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$${\displaystyle |a|}$${\displaystyle a}$$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$

عندما يقتصر المجال على المكعب الفائق ذي الأبعاد n ، فإن متعدد الحدود يعطي احتمالية نتيجة إيجابية عندما يتم تطبيق الدالة المنطقية f على n متغير عشوائي مستقل ( برنولي )، مع احتمالات فردية x . هناك حالة خاصة لهذه الحقيقة وهي مبرهنة التراكم لوظائف التكافؤ . يمكن أيضًا استخدام الشكل متعدد الحدود لدالة منطقية كامتداد طبيعي للمنطق الضبابي . ${\displaystyle [0,1]^{n}}$${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$

غالبًا ما يتم أخذ المجال البولياني على أنه ، مع تعيين false ("0") إلى 1 و true ("1") إلى -1 (انظر تحليل الدوال البوليانية ). ثم يتم إعطاء الحدوديات المقابلة لـ بواسطة: يؤدي استخدام المجال البولياني المتماثل إلى تبسيط جوانب معينة من التحليل ، حيث يتوافق النفي مع الضرب في -1 والدوال الخطية هي أحاديات الحدود (XOR هو الضرب). وبالتالي فإن شكل الحدوديات هذا يتوافق مع تحويل والش (المعروف في هذا السياق أيضًا باسم تحويل فورييه ) للدالة (انظر أعلاه). كما أن الحدوديات لها نفس التفسير الإحصائي مثل تلك الموجودة في المجال البولياني القياسي، إلا أنها تتعامل الآن مع القيم المتوقعة (انظر مبرهنة التراكم للحصول على مثال). ${\displaystyle \{-1,1\}}$${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$$${\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}$$${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$

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

تعتبر خصائص الوظائف المنطقية بالغة الأهمية في التشفير ، وخاصة في تصميم خوارزميات المفتاح المتماثل (انظر مربع الاستبدال ).

في نظرية الألعاب التعاونية ، تسمى الوظائف المنطقية الرتيبة بالألعاب البسيطة (ألعاب التصويت)؛ يتم تطبيق هذا المفهوم لحل المشكلات في نظرية الاختيار الاجتماعي .

• كراما، إيف؛ هامر، بيتر إل. (2011)، الدوال المنطقية: النظرية والخوارزميات والتطبيقات ، مطبعة جامعة كامبريدج، doi :10.1017/CBO9780511852008، ISBN 9780511852008
• "الدالة المنطقية"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]
• يانكوفيتش، دراجان؛ ستانكوفيتش، رادومير س؛ موراجا، كلاوديو (نوفمبر 2003). "تحسين التعبيرات الحسابية باستخدام خاصية القطبية المزدوجة". المجلة الصربية للهندسة الكهربائية . 1 ( 71– 80، العدد 1): 71– 80. doi : 10.2298/SJEE0301071J .
• أرنولد، برادفورد هنري (1 يناير 2011). المنطق والجبر البولياني. شركة كورير. رقم ISBN 978-0-486-48385-6.
• مانو، م.م.؛ سيليتي، م.د. (2013)، التصميم الرقمي ، بيرسون