دالة منطقية متوازنة

في الرياضيات وعلوم الحاسوب ، الدالة المنطقية المتوازنة هي دالة منطقية يكون ناتجها مساوياً لعدد الأصفار والآحاد ضمن مجموعة مدخلاتها . وهذا يعني أنه بالنسبة لسلسلة بتات عشوائية منتظمة، فإن احتمال الحصول على الرقم 1 هو 1/2. ^{[ 1 ]}

من أمثلة الدوال المنطقية المتوازنة دالة الأغلبية ، ^{[ 1 ]} و"دالة الديكتاتورية" التي تنسخ البت الأول من مدخلاتها إلى المخرجات، ^{[ 1 ]} ودالة فحص التكافؤ التي تنتج عملية " أو الحصرية" لبتات المدخلات. ^{[ 2 ]}

لو${\displaystyle f}$هي دالة منحنية على${\displaystyle n}$قطع صغيرة، و${\displaystyle \alpha }$أي متجه غير صفري من${\displaystyle n}$البتات، ثم الدالة التي تقوم بالتحويل${\displaystyle x}$ل${\displaystyle f(x)\oplus f(x\oplus \alpha )}$متوازنة. الدوال المنحنية هي بالضبط الدوال التي يكون هذا صحيحًا بالنسبة لها، لجميع الخيارات غير الصفرية لـ${\displaystyle \alpha }$[ ^{3 ]​}

يمكن تقييم دالة الديكتاتورية بعد فحص بت واحد فقط من المدخلات، ولكن يجب فحص هذا البت دائمًا. يصف بنجاميني وشرام وويلسون مثالًا أكثر تعقيدًا قائمًا على نظرية الترشيح، حيث تتميز خوارزمية لاس فيغاس العشوائية بقدرتها على حساب الدالة بدقة مع ضمان أن احتمال قراءة أي بت معين من المدخلات صغير، ويتناسب عكسيًا تقريبًا مع الجذر التربيعي لعدد البتات. ^{[ 1 ]}

تُستخدم الدوال المنطقية المتوازنة في علم التشفير ، حيث يُعد التوازن أحد "أهم معايير قوة الدوال المنطقية في التشفير". ^{[ 3 ]} إذا لم تكن الدالة متوازنة، فسيكون لها تحيز إحصائي ، مما يجعلها عرضة لتحليل التشفير مثل هجوم الارتباط .