وظيفة القراءة لمرة واحدة

في الرياضيات، الدالة التي تُقرأ مرة واحدة هي نوع خاص من الدوال المنطقية التي يمكن وصفها بتعبير منطقي يظهر فيه كل متغير مرة واحدة فقط.

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

على سبيل المثال، بالنسبة لثلاثة متغيرات a و b و c ، فإن التعبيرات

${\displaystyle a\wedge b\wedge c}$

${\displaystyle a\wedge (b\vee c)}$

${\displaystyle (a\wedge b)\vee c}$، و

${\displaystyle a\vee b\vee c}$

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

${\displaystyle (a\vee b)\wedge (a\vee c)\wedge (b\vee c)}$

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

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

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

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