دالة بوليانية
في الرياضيات، الدالة البوليانية هي دالة formula_1 مع n متغيرات formula_2 نقول أنَّ f تقبل متجه formula_3 اذا 1 =(f(a ونقول انها ترفضه اذا 0 =(f(a . دالة بوليانية ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير x  اذا يوجد اعداد ثابتة formula_4 بحيث أنَّ :
بما أنَّه يوجد formula_6 متجهات في formula_7 فإن عدد الدوال البوليانية formula_2 هو formula_9.
دالة بوليانية نقول عنها متناظرة (symmetric) اذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها اي على توزيعها على المتغيرات , لذا فانه يوجد formula_10 دوال كهذه , امثلة لدوال كهذه :
يمكن ترجمة كل خاصية او صفة إلى دالة بوليانية ملائمة وهذه الصفة يمكن ان تحقق او لا , مثال : الصفة "العدد أولي" ملائم للدالة PRIME بحيث :
ولنترجم خصائص المُخططات (graphs) على المجموعة formula_16 نُعرف لكل ضلع متغير formula_17 وهذا المتغير 1 اذا formula_18 و-0 خلاف هذا . لذا اي مُتجه قيمه 0-1 بطول formula_19 يعطينا مُخطط G . عندها خاصية يمكن ترجمتها بشكل مناسب , بشكل عام :
مثال :
دالة المخطط الكامل (the clique function) او (Clique(n,k : وهذه الدالة تقبل متجه x اذا وفقط اذا G يحوي مخطط كامل مع k رؤوس .
مصفوفة بوليانية هي مصفوفة بحيث أنَّ كل الخلايا قيمتها اما 0 او 1 .
اذا (f(x,y دالة بوليانية مع 2n متغيرات حينها يمكن النظر اليها على انها مصفوفة ,A, بكبر formula_21 بحيث أن كل سطر وعامود موسوم بواسطة مُتجه من formula_7 , ويتحقق : (A[x,y]=f(x,y .
العمليات البوليانية الاساسية هي : 
من هذه العمليات يمكن تركيب دوال بوليانية أكثر تعقيدا من دوال بسيطة .
مثال :
لنفرض أنَّ formula_29 حينها يمكن أن نبني دالة جديدة : formula_30
المعكب الثنائي هو مجموعة كل المتجهات ( اي formula_31 ) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب formula_32 رؤوس وكل رأس موسوم بواسطة مُتجه(vector) من المجموعة formula_33 ويوجد ضلع بين رأسين اذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد . لذا فانه يوجد formula_34 اضلاع في هذا المخطط , كما انَّه مخطط ثنائي . نرمز لمكعب مع formula_6 رؤوس ب- formula_36 . 
A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي : formula_37 بحيث أنَّ كل A هو أحد المجموعات : formula_38 بالاضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي : formula_39 .
كل دالة بوليانية formula_2 يمكن النظر اليها على انها تلوين (coloring) formula_41 بلونين . المخطط الثنائي الجزئي formula_42 نحصل عليه بازالة كل الاضلاع التي رؤوسها تشترك بنفس اللون . الكثافة في المخطط formula_42 له فائدة في تعقيد الدوائر البوليانية للدالة f .
هنالك شكلان طبيعيان للدوال البوليانية : CNF , DNF . لعل أكثر الوسائل بديهية لتمثيل دالة بوليانية هو جدول الحقيقة الخاص بالدالة اي قائمة بكل formula_6 الازواج formula_45 لكل formula_46 . هذه الطريقة اغلب الاحيان غير ملائمة , وسيلة أكثر ملائمة هي DNF و-CNF .
متغير بسيط (literal) هو المتغير البولياني او ضده اي اما ان يكون formula_47 او formula_48. بشكل عام الترميز التالي شائع الاستخدام : formula_49 و- formula_50 لذا فانه لكل سلسلة formula_51 يتحقق التالي : 
احادي الحدود (monomial) هو AND متغيرات بسيطة , والتعبير (clause) هو or متغيرات بسيطة . مثال :
DNF هو OR آحاد الحدود و- CNF هو AND تعابير . كل دالة بوليانية (f(x يمكن التعبير عنها بواسطة (DNF D(x او (CNF C(x :
لكل دالة بوليانية يمكن تعريف دالة بوليانية اخرى formula_54 وتسمى هذه الدالة ثنائي f . وهي كالتالي : 
لهذه الدالة عدة تطبيقات بشكل طبيعي منها في نظرية التصويت (voting theory) .
لهذه الدالة كثير من الخصال منها :
لنفرض أن f,g هما دالتين بوليانيتين حينها :
لكل مجموعة جزئية S من المجموعة formula_60 نعرف دالة التشخيص (Characteristic function) formula_61 والتي تحقق:
حينها يمكن تعريف الدالة البوليانية على انها علاقة (predicate) formula_63 . ويستطيع المرئ ان ينظر إلى دالة بوليانية formula_64 على انها عائلة المجموعات الجزئية التالية : formula_65 .
لكل مُتجهين formula_66 نكتب formula_67 اذا formula_68 . دالة بوليانية احادية التوجه اذا formula_69 . لو نظرنا ل- f على انها علاقة اي formula_63 حينها الدالة f احادية الاتجاه اذا وفقط اذا formula_71 حينها لكل formula_72 يتحقق formula_73 .
امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة formula_74 ...