Loading AI tools
من ويكيبيديا، الموسوعة الحرة
في الرياضيات، دالة بُول[1] هي دالة مع n متغيرات نقول أنَّ f تقبل متجه إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a .[2][3][4] دالة بول ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير xi إذا يوجد اعداد ثابتة بحيث أنَّ:
صنف فرعي من | |
---|---|
سُمِّي باسم | |
يدرسه | |
المجال المقابل | |
ممثلة بـ |
بما أنَّه يوجد متجهات في فإن عدد دوال بول هو .
دالة بول نقول عنها متناظرة إذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها أي على توزيعها على المتغيرات، لذا فانه يوجد دوال كهذه، امثلة لدوال كهذه:
يمكن ترجمة كل خاصية أو صفة إلى دالة بول ملائمة وهذه الصفة يمكن ان تحقق أو لا، مثال: الصفة «العدد أولي» ملائم للدالة PRIME بحيث:
ولنترجم خصائص المُخططات (graphs) على المجموعة نُعرف لكل ضلع متغير وهذا المتغير 1 إذا و-0 خلاف هذا. لذا أي مُتجه قيمه 0-1 بطول يعطينا مُخطط G . عندها خاصية يمكن ترجمتها بشكل مناسب، بشكل عام:
مثال:
دالة المخطط الكامل (the clique function) أو (Clique(n,k : وهذه الدالة تقبل متجه x إذا وفقط إذا Gx يحوي مخطط كامل مع k رؤوس.
مصفوفة بول هي مصفوفة بحيث أنَّ كل الخلايا قيمتها اما 0 أو 1 .
إذا (f(x,y دالة بول مع 2n متغيرات حينها يمكن النظر اليها على انها مصفوفة،A, بكبر بحيث أن كل سطر وعامود موسوم بواسطة مُتجه من , ويتحقق: (A[x,y]=f(x,y .
عمليات بول الأساسية هي:
من هذه العمليات يمكن تركيب دوال بول أكثر تعقيدا من دوال بسيطة.
مثال:
لنفرض أنَّ حينها يمكن أن نبني دالة جديدة:
المعكب الثنائي هو مجموعة كل المتجهات (أي ) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب رؤوس وكل رأس موسوم بواسطة مُتجه (vector) من المجموعة ويوجد ضلع بين رأسين إذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد. لذا فانه يوجد اضلاع في هذا المخطط، كما انَّه مخطط ثنائي. نرمز لمكعب مع رؤوس ب- .
A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي: بحيث أنَّ كل Ai هو أحد المجموعات: بالإضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي: .
كل دالة بول يمكن النظر اليها على انها تلوين (coloring) بلونين. المخطط الثنائي الجزئي نحصل عليه بازالة كل الاضلاع التي رؤوسها تشترك بنفس اللون. الكثافة في المخطط له فائدة في تعقيد دوائر بول للدالة f .
هنالك شكلان طبيعيان لدوال بول: CNF , DNF . لعل أكثر الوسائل بديهية لتمثيل دالة بول هو جدول الحقيقة الخاص بالدالة أي قائمة بكل الازواج لكل . هذه الطريقة اغلب الاحيان غير ملائمة، وسيلة أكثر ملائمة هي DNF و-CNF .
متغير بسيط (literal) هو متغير بول أو ضده أي اما ان يكون أو . بشكل عام الترميز التالي شائع الاستخدام: و- لذا فانه لكل سلسلة يتحقق التالي:
احادي الحدود (monomial) هو AND متغيرات بسيطة، والتعبير (clause) هو or متغيرات بسيطة. مثال:
DNF هو OR آحاد الحدود و- CNF هو AND تعابير. كل دالة بول (f(x يمكن التعبير عنها بواسطة (DNF D(x أو (CNF C(x :
لكل دالة بول يمكن تعريف دالة بول أخرى وتسمى هذه الدالة ثنائي f . وهي كالتالي:
لهذه الدالة عدة تطبيقات بشكل طبيعي منها في نظرية التصويت (voting theory).
لهذه الدالة كثير من الخصال منها:
لنفرض أن f,g هما دالتين بوليتين حينها:
لكل مجموعة جزئية S من المجموعة نعرف دالة التشخيص (Characteristic function) والتي تحقق:
حينها يمكن تعريف دالة البول على انها علاقة (predicate) . ويستطيع المرئ ان ينظر إلى دالة بول على انها عائلة المجموعات الجزئية التالية: .
لكل مُتجهين نكتب إذا . دالة بول احادية التوجه إذا . لو نظرنا ل- f على انها علاقة أي حينها الدالة f احادية الاتجاه إذا وفقط إذا حينها لكل يتحقق .
امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة ,...
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.