طرق حل أنظمة المعادلات المنطقية. طرق حل أنظمة المعادلات المنطقية

طرق حل أنظمة المعادلات المنطقية

يمكنك حل نظام من المعادلات المنطقية، على سبيل المثال، باستخدام جدول الحقيقة (إذا لم يكن عدد المتغيرات كبيرًا جدًا) أو باستخدام شجرة القرار، بعد تبسيط كل معادلة أولاً.

1. طريقة الاستبدال المتغيرة.

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

دعونا نفكر في تطبيق هذه الطريقة باستخدام مثال محدد.

مثال.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

حل:

لنقدم متغيرات جديدة: A=(X1≡ X2)؛ ب=(X3 ≡ X4); С=(X5 ≡ X6); د=(X7 ≡ X8); ه=(X9 ≡X10).

(انتبه! يجب تضمين كل من المتغيرات x1، x2، ...، x10 في واحد فقط من المتغيرات الجديدة A، B، C، D، E، أي أن المتغيرات الجديدة مستقلة عن بعضها البعض).

ثم سيبدو نظام المعادلات كما يلي:

(أ ∧ ب) ∨ (¬أ ∧ ¬ب)=0

(ب ∧ ج) ∨ (¬ ب ∧ ¬ج)=0

(ج ∧ د) ∨ (¬C ∧ ¬D)=0

(د ∧ ه) ∨ (¬د ∧ ¬ه)=0

لنقم ببناء شجرة قرارات للنظام الناتج:

النظر في المعادلة A=0، أي. (X1≡ ×2)=0. له جذوران:

		×1 ≡ ×2

من نفس الجدول يمكن ملاحظة أن المعادلة A=1 لها أيضًا جذران. دعونا نرتب عدد الجذور في شجرة القرار:

للعثور على عدد الحلول لفرع واحد، تحتاج إلى مضاعفة عدد الحلول في كل مستوى. الفرع الأيسر لديه 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 حلاً؛ يحتوي الفرع الأيمن أيضًا على 32 حلًا. أولئك. النظام بأكمله لديه 32+32=64 حل.

الجواب: 64.

2. طريقة الاستدلال.

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

مثال 1. كم عدد مجموعات قيم المتغيرات المنطقية x1، x2، x3، x4، x5، y1، y2، y3، y4، y5 الموجودة والتي تستوفي جميع الشروط المذكورة أدناه؟

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

لا تحتاج الإجابة إلى سرد كافة مجموعات القيم المختلفة للمتغيرات x1، x2، x3، x4، x5، y1، y2، y3، y4، y5 التي يفي بها نظام المساواة هذا. كإجابة، تحتاج إلى الإشارة إلى عدد هذه المجموعات.

حل :

تحتوي المعادلتان الأولى والثانية على متغيرات مستقلة مرتبطة بالشرط الثالث. لنقم ببناء شجرة حلول للمعادلتين الأولى والثانية.

لتمثيل شجرة حلول لنظام المعادلتين الأولى والثانية، يجب أن يستمر كل فرع من فروع الشجرة الأولى بشجرة للمتغيراتفي . الشجرة التي تم بناؤها بهذه الطريقة سوف تحتوي على 36 فرعا. بعض هذه الفروع لا تحقق المعادلة الثالثة للنظام. دعونا نحدد عدد فروع الشجرة على الشجرة الأولى"ذ" والتي تحقق المعادلة الثالثة :

دعونا نوضح: لتحقيق الشرط الثالث، عندما يكون x1=0 يجب أن يكون هناك y1=1، أي جميع فروع الشجرة"X" ، حيث x1=0 يمكن الاستمرار بفرع واحد فقط من الشجرة"ذ" . ولفرع واحد فقط من الشجرة"X" (يمين) جميع فروع الشجرة تناسب"ذ". وبالتالي فإن الشجرة الكاملة للنظام بأكمله تحتوي على 11 فرعا. يمثل كل فرع حلاً واحدًا لنظام المعادلات الأصلي. وهذا يعني أن النظام بأكمله لديه 11 حلا.

الجواب: 11.

مثال 2. ما عدد الحلول المختلفة التي يمتلكها نظام المعادلات؟

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

حيث x1، x2، ...، x10 هي متغيرات منطقية؟ لا تحتاج الإجابة إلى سرد جميع المجموعات المختلفة من القيم المتغيرة التي تنطبق عليها هذه المساواة. كإجابة، تحتاج إلى الإشارة إلى عدد هذه المجموعات.

حل : دعونا تبسيط النظام. دعونا نبني جدول الحقيقة لجزء من المعادلة الأولى:

X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

انتبه إلى العمود الأخير، فهو يطابق نتيجة الإجراء×1 ≡ ×10.

×1 ≡ ×10

وبعد التبسيط نحصل على:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

خذ بعين الاعتبار المعادلة الأخيرة:(X1 ≡ X10) = 0، أي. يجب ألا يتزامن x1 مع x10. لكي تكون المعادلة الأولى تساوي 1، يجب أن تكون المساواة صحيحة(X1 ≡ X2)=1، أي. يجب أن يتطابق x1 مع x2.

دعونا نبني شجرة حل للمعادلة الأولى:

خذ بعين الاعتبار المعادلة الثانية: من أجل x10=1 و x2=0 القوسيجب أن يكون مساويًا لـ 1 (أي أن x2 يتطابق مع x3)؛ لـ x10=0 و لـ x2=1 قوس(X2 ≡ X10)=0، وهو ما يعني القوس (X2 ≡ X3) يجب أن يكون مساويًا لـ 1 (أي أن x2 يتطابق مع x3):

وبالاستدلال بهذه الطريقة، فإننا نبني شجرة قرارات لجميع المعادلات:

وبالتالي، فإن نظام المعادلات لديه حلين فقط.

الجواب: 2.

مثال 3.

كم عدد مجموعات قيم المتغيرات المنطقية x1، x2، x3، x4، y1، y2، y3، y4، z1، z2، z3، z4 الموجودة والتي تستوفي جميع الشروط المذكورة أدناه؟

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

حل:

دعونا نبني شجرة حل للمعادلة الأولى:

خذ المعادلة الثانية:

عندما x1=0 : القوسين الثاني والثالث يساوي 0؛ أن تكون القوس الأول مساوية لـ 1، y1=1، z1=1 (أي في هذه الحالة - حل واحد)
عندما x1=1 : القوس الأول سيكون مساوياً لـ 0؛ ثانيةأو القوس الثالث يجب أن يساوي 1؛ القوس الثاني سيكون مساوياً لـ 1 عندما تكون y1=0 وz1=1؛ القوس الثالث سيكون مساويًا لـ 1 عندما تكون y1=1 وz1=0 (أي في هذه الحالة - حلان).

وبالمثل بالنسبة للمعادلات المتبقية. دعونا نلاحظ عدد الحلول الناتج لكل عقدة شجرة:

لمعرفة عدد الحلول لكل فرع، اضرب الأرقام الناتجة لكل فرع على حدة (من اليسار إلى اليمين).

فرع واحد: 1 ⋅ 1 ⋅ 1 ⋅ 1 = حل واحد

الفرع الثاني: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 حل

الفرع الثالث: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 حلول

الفرع الرابع: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 حلول

الفرع الخامس: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 حل

لنجمع الأرقام الناتجة: هناك 31 حلًا في المجمل.

الجواب: 31.

3. الزيادة الطبيعية في عدد الجذور

في بعض الأنظمة، يعتمد عدد جذور المعادلة التالية على عدد جذور المعادلة السابقة.

مثال 1. كم عدد مجموعات قيم المتغيرات المنطقية x1، x2، x3، x4، x5، x6، x7، x8، x9، x10 التي تستوفي جميع الشروط المذكورة أدناه؟

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

دعونا نبسط المعادلة الأولى:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ ×3). ثم سيأخذ النظام النموذج:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

إلخ.

كل معادلة تالية لها جذران أكثر من المعادلة السابقة.

4 معادلة لها 12 جذرًا؛

المعادلة 5 لها 14 جذرًا

المعادلة 8 لها 20 جذرًا.

الجواب: 20 جذور.

في بعض الأحيان ينمو عدد الجذور وفقًا لقانون فيبوناتشي.

يتطلب حل نظام المعادلات المنطقية أسلوبًا إبداعيًا.

تحتوي هذه المادة على عرض تقديمي يقدم طرق حل المعادلات المنطقية وأنظمة المعادلات المنطقية في المهمة B15 (رقم 23، 2015) من امتحان الدولة الموحدة في علوم الكمبيوتر. ومن المعروف أن هذه المهمة من أصعب المهام ضمن مهام امتحان الدولة الموحدة. يمكن أن يكون العرض التقديمي مفيدًا عند تدريس الدروس حول موضوع "المنطق" في الفصول المتخصصة، وكذلك عند التحضير لامتحان الدولة الموحدة.

تحميل:

معاينة:

لاستخدام معاينات العرض التقديمي، قم بإنشاء حساب Google وقم بتسجيل الدخول إليه: https://accounts.google.com

التسميات التوضيحية للشرائح:

حل المهمة B15 (أنظمة المعادلات المنطقية) Vishnevskaya M.P.، MAOU "Gymnasium No. 3" 18 نوفمبر 2013، ساراتوف

المهمة B15 هي من أصعب المهام في امتحان الدولة الموحدة في علوم الكمبيوتر !!! يتم اختبار المهارات التالية: تحويل التعبيرات التي تحتوي على متغيرات منطقية؛ وصف باللغة الطبيعية مجموعة قيم المتغيرات المنطقية التي تكون مجموعة معينة من المتغيرات المنطقية صحيحة فيها؛ حساب عدد المجموعات الثنائية التي تستوفي الشروط المحددة. أصعب شيء هو لأنه... لا توجد قواعد رسمية حول كيفية القيام بذلك، فهو يتطلب التخمين.

ما لا يمكنك الاستغناء عنه!

اقتران الرموز: A /\ B , A  B , AB , A &B , A و B انفصال: A \ / B , A + B , A | نفي B أو A أو B:  A أو A وليس تكافؤ A: A  B أو A  B أو A  B حصريًا "أو": A  B أو A xor B

طريقة الاستبدال المتغير كم عدد مجموعات قيم المتغيرات المنطقية x1، x2، ...، x9، x10 الموجودة والتي تستوفي جميع الشروط المذكورة أدناه: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 الإجابة لا تحتاج إلى سرد كافة المجموعات المختلفة x1, x2, …, x9, x10 التي لها هذا النظام من المساواة يحمل. كإجابة يجب الإشارة إلى عدد هذه المجموعات (الإصدار التجريبي 2012)

خطوة الحل 1. التبسيط عن طريق تغيير المتغيرات t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 بعد التبسيط: (t1\/ t2) /\ (¬t1\/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 فكر في إحدى المعادلات: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 من الواضح أنها =1 فقط إذا كان أحد المتغيرين 0 والآخر 1 لنستخدم الصيغة للتعبير عن عملية XOR من خلال الربط والانفصال: (t1\/ t2) /\ (¬t1\/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

الخطوة 2. تحليل النظام ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .ل. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….)، فإن كل قيمة tk تقابل زوجين من القيمتين x2k-1 وx2k، على سبيل المثال: tk =0 تقابل زوجين - (0) ,1) و (1, 0) و tk =1 – أزواج (0,0) و (1,1).

الخطوه 3. حساب عدد الحلول لكل t حلان، عدد ts هو 5. وهكذا. للمتغيرات t هناك 2 5 = 32 حل. ولكن لكل t هناك زوج من الحلول x، أي. النظام الأصلي لديه 2*32=64 حل. الجواب: 64

طريقة حذف جزء من الحلول كم عدد مجموعات قيم المتغيرات المنطقية x1, x2, ..., x5, y1,y2,..., y5 الموجودة والتي تحقق جميع الشروط المذكورة أدناه: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; ص5 → س5 =1. لا تحتاج الإجابة إلى سرد كافة المجموعات المختلفة x1, x2, ..., x5, y 1 , y2, ... , y5 التي ينطبق عليها نظام المساواة هذا. يجب أن تشير الإجابة إلى عدد هذه المجموعات.

حل. الخطوة 1. الحل التسلسلي للمعادلات x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 المعادلة الأولى هي اقتران عدة عمليات ضمنية تساوي 1، أي. كل من الآثار صحيحة. المعنى الضمني خاطئ في حالة واحدة فقط، عندما تكون 1  0، في جميع الحالات الأخرى (0  0، 0  1، 1  1) ترجع العملية 1. لنكتب هذا في شكل جدول:

الخطوة 1. الحل المتسلسل للمعادلات T.o. تم الحصول على 6 مجموعات من الحلول لـ x1، x2، x3، x4، x5: (00000)، (00001)، (00011)، (00111)، (01111)، (11111). بالاستدلال بالمثل، توصلنا إلى استنتاج مفاده أنه بالنسبة لـ y1، y2، y3، y4، y5 هناك نفس مجموعة الحلول. لأن هذه المعادلات مستقلة، أي. ليس لديهم متغيرات مشتركة، فإن حل نظام المعادلات هذا (دون مراعاة المعادلة الثالثة) سيكون 6 * 6 = 36 زوجًا من "X's" و"Y's". خذ بعين الاعتبار المعادلة الثالثة: y5→ x5 =1 الحل هو الأزواج: 0 0 0 1 1 1 الزوج ليس حلاً: 1 0

دعونا نقارن الحلول التي تم الحصول عليها، حيث y5 =1، x5=0 غير مناسب. هناك 5 أزواج من هذه الأزواج، عدد حلول النظام: 36-5=31. الإجابة: كانت هناك حاجة إلى 31 مجموعة من التوافقيات!!!

طريقة البرمجة الديناميكية كم عدد الحلول المختلفة للمعادلة المنطقية x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1، حيث x 1, x 2, …, x 6 هي متغيرات منطقية؟ لا تحتاج الإجابة إلى سرد جميع المجموعات المختلفة من القيم المتغيرة التي تنطبق عليها هذه المساواة. كإجابة، تحتاج إلى الإشارة إلى كميات هذه المجموعات.

خطوة الحل1. تحليل الشرط على يسار المعادلة تكتب عمليات التضمين بشكل تسلسلي، الأولوية هي نفسها. لنعيد الكتابة: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 ملحوظة! وكل متغير لاحق لا يعتمد على السابق، بل على نتيجة التضمين السابق!

الخطوة 2. الكشف عن النمط لنفكر في التضمين الأول، X 1 → X 2. جدول الحقيقة: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 من واحد 0 حصلنا على وحدتين، ومن 1 لقد حصلنا على 0 واحد وواحد 1. لا يوجد سوى 0 واحد وثلاثة 1، وهذه نتيجة العملية الأولى.

الخطوة 2. الكشف عن النمط بربط x 3 بنتيجة العملية الأولى نحصل على: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 من اثنين 0 – اثنان 1، من كل 1 (يوجد 3) واحد 0 وواحد 1 (3+3)

الخطوة 3. اشتقاق الصيغة T.o. يمكنك إنشاء صيغ لحساب عدد الأصفار N i وعدد الآحاد E i لمعادلة ذات متغيرات i: ,

الخطوة 4. ملء الجدول دعونا نملأ الجدول من اليسار إلى اليمين لـ i = 6، ونحسب عدد الأصفار والآحاد باستخدام الصيغ المذكورة أعلاه؛ يوضح الجدول كيفية إنشاء العمود التالي من العمود السابق: عدد المتغيرات 1 2 3 4 5 6 عدد الأصفار N i 1 1 3 5 11 21 عدد الآحاد E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 الجواب: 43

طريقة استخدام تبسيط التعبيرات المنطقية كم عدد الحلول المختلفة للمعادلة ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 حيث J، K، L، M، N هي متغيرات منطقية؟ لا تحتاج الإجابة إلى سرد جميع مجموعات القيم المختلفة J وK وL وM وN التي تنطبق عليها هذه المساواة. كإجابة، تحتاج إلى الإشارة إلى عدد هذه المجموعات.

الحل لاحظ أن J → K = ¬ J  K لندخل تغيير المتغيرات: J → K=A, M  N  L =B لنعيد كتابة المعادلة مع مراعاة التغيير: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. من الواضح أن A  B لنفس قيم A وB 6. ضع في اعتبارك التأثير الأخير M → J =1 هذا ممكن إذا: M= J=0 M=0، J=1 M=J=1

الحل لأن A  B، ثم عندما M=J=0 نحصل على 1 + K=0. لا توجد حلول. عندما M=0، J=1 نحصل على 0 + K=0، K=0، وN وL موجودة، 4 حلول: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

الحل 10. عندما M=J=1 نحصل على 0+K=1 *N * L، أو K=N*L، 4 حلول: 11. المجموع لديه 4+4=8 حلول الإجابة: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

مصادر المعلومات: أو.ب. بوغومولوفا، د. أوسينكوف. ب15: مهام جديدة وحلول جديدة // المعلوماتية، العدد 6، 2012، ص. 35 - 39. ك.يو. بولياكوف. المعادلات المنطقية // المعلوماتية، العدد 14، 2011، ص. 30-35. http://ege-go.ru/zadania/grb/b15/، [المورد الإلكتروني]. http://kpolyakov.narod.ru/school/ege.htm، [المصدر الإلكتروني].

الغرض من الخدمة. تم تصميم الآلة الحاسبة عبر الإنترنت من أجل بناء جدول الحقيقة للتعبير المنطقي.
جدول الحقيقة – جدول يحتوي على جميع المجموعات الممكنة لمتغيرات الإدخال وقيم المخرجات المقابلة لها.
يحتوي جدول الحقيقة على صفين، حيث n هو عدد متغيرات الإدخال، وn+m عبارة عن أعمدة، حيث m هي متغيرات الإخراج.

تعليمات. عند الدخول من لوحة المفاتيح، استخدم الاصطلاحات التالية:

على سبيل المثال، يجب إدخال التعبير المنطقي abc+ab~c+a~bc على النحو التالي: a*b*c+a*b=c+a=b*c
لإدخال البيانات على شكل رسم تخطيطي منطقي، استخدم هذه الخدمة.

قواعد لإدخال وظيفة منطقية

بدلاً من رمز v (الانفصال، OR)، استخدم علامة +.
ليست هناك حاجة لتحديد تعيين وظيفة قبل وظيفة منطقية. على سبيل المثال، بدلاً من F(x,y)=(x|y)=(x^y) تحتاج ببساطة إلى إدخال (x|y)=(x^y) .
الحد الأقصى لعدد المتغيرات هو 10.

يتم تصميم وتحليل الدوائر المنطقية للكمبيوتر باستخدام فرع خاص من الرياضيات - الجبر المنطقي. في جبر المنطق، يمكن التمييز بين ثلاث وظائف منطقية رئيسية: "NOT" (النفي)، "AND" (الربط)، "OR" (الانفصال).
لإنشاء أي جهاز منطقي، من الضروري تحديد اعتماد كل من متغيرات الإخراج على متغيرات الإدخال الموجودة؛ ويسمى هذا الاعتماد وظيفة التبديل أو وظيفة الجبر المنطقي.
تسمى دالة الجبر المنطقي معرفة كاملة إذا تم إعطاء جميع قيمها 2n، حيث n هو عدد متغيرات الإخراج.
إذا لم يتم تعريف كافة القيم، تسمى الوظيفة محددة جزئيا.
يُسمى الجهاز منطقيًا إذا تم وصف حالته باستخدام دالة الجبر المنطقي.
يتم استخدام الطرق التالية لتمثيل دالة الجبر المنطقي:
في الصورة الجبرية، يمكنك بناء دائرة لجهاز منطقي باستخدام عناصر منطقية.

الشكل 1 - مخطط الجهاز المنطقي

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

العملية NOT - النفي المنطقي (الانعكاس)

لا يتم تطبيق العملية المنطقية على وسيطة واحدة، والتي يمكن أن تكون تعبيرًا منطقيًا بسيطًا أو معقدًا. نتيجة العملية ليست كما يلي:

فإذا كان التعبير الأصلي صحيحاً، كانت نتيجة نفيه كاذبة؛
فإذا كان التعبير الأصلي خطأ كانت نتيجة نفيه صحيحة.

لا يتم قبول الاتفاقيات التالية لعملية النفي:
ليس أ، Ā، وليس أ، ¬أ، !أ
لا يتم تحديد نتيجة عملية النفي من خلال جدول الحقيقة التالي:

أ	ليس أ
0	1
1	0

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

عملية OR - إضافة منطقية (انفصال، اتحاد)

تؤدي العملية المنطقية OR وظيفة الجمع بين عبارتين، والتي يمكن أن تكون تعبيرًا منطقيًا بسيطًا أو معقدًا. تسمى البيانات التي تمثل نقطة البداية لعملية منطقية بالوسائط. نتيجة العملية OR هي تعبير سيكون صحيحًا فقط إذا كان أحد التعبيرات الأصلية على الأقل صحيحًا.
التسميات المستخدمة: A أو B، A V B، A أو B، A||B.
يتم تحديد نتيجة العملية OR من خلال جدول الحقيقة التالي:
تكون نتيجة العملية OR صحيحة عندما يكون A صحيحًا، أو B صحيحًا، أو يكون كل من A وB صحيحًا، وخطأ عندما تكون الوسيطتان A وB خطأ.

العملية AND - الضرب المنطقي (الارتباط)

العملية المنطقية AND تؤدي وظيفة تقاطع عبارتين (وسائط)، والتي يمكن أن تكون إما تعبيرًا منطقيًا بسيطًا أو معقدًا. نتيجة العملية AND هي تعبير سيكون صحيحًا فقط إذا كان كلا التعبيرين الأصليين صحيحين.
التسميات المستخدمة: A وB، A Λ B، A & B، A وB.
يتم تحديد نتيجة العملية AND من خلال جدول الحقيقة التالي:

أ	ب	أ و ب
0	0	0
0	1	0
1	0	0
1	1	1

تكون نتيجة العملية AND صحيحة إذا وفقط إذا كانت العبارتان A وB صحيحتين وكاذبتين في جميع الحالات الأخرى.

عملية "IF-THEN" - النتيجة المنطقية (ضمنا)

تربط هذه العملية بين تعبيرين منطقيين بسيطين، الأول عبارة عن شرط، والثاني نتيجة لهذا الشرط.
التسميات المستخدمة:
إذا كان أ، ثم ب؛ أ يستلزم ب؛ إذا كان أ ثم ب؛ أ → ب.
جدول الحقيقة:

أ	ب	أ → ب
0	0	1
0	1	1
1	0	0
1	1	1

تكون نتيجة عملية التضمين خاطئة فقط إذا كانت الفرضية A صحيحة والاستنتاج B (النتيجة) خاطئًا.

العملية "أ إذا وفقط إذا ب" (التكافؤ، التكافؤ)

التسمية المستخدمة: A ↔ B، A ~ B.
جدول الحقيقة:

أ	ب	أ↔ب
0	0	1
0	1	0
1	0	0
1	1	1

عملية "وحدة الإضافة 2" (XOR، الانفصال الحصري أو الصارم)

الترميز المستخدم: A XOR B، A ⊕ B.
جدول الحقيقة:

أ	ب	أ⊕ب
0	0	0
0	1	1
1	0	1
1	1	0

تكون نتيجة عملية التكافؤ صحيحة فقط إذا كان A وB صحيحين أو خاطئين في نفس الوقت.

أولوية العمليات المنطقية

الإجراءات بين قوسين
الانقلاب
اِقتِران (&)
الانفصال (V)، الحصري أو (XOR)، مجموع الوحدة 2
التضمين (←)
التكافؤ (↔)

الشكل الطبيعي المنفصل المثالي

الشكل الطبيعي المنفصل المثالي للصيغة(SDNF) هي صيغة مكافئة، وهي عبارة عن انفصال عن أدوات العطف الأولية ولها الخصائص التالية:

يحتوي كل مصطلح منطقي للصيغة على كافة المتغيرات المضمنة في الدالة F(x 1,x 2,...x n).
جميع المصطلحات المنطقية للصيغة مختلفة.
لا يوجد مصطلح منطقي واحد يحتوي على متغير ونفيه.
لا يوجد مصطلح منطقي في صيغة يحتوي على نفس المتغير مرتين.

يمكن الحصول على SDNF إما باستخدام جداول الحقيقة أو باستخدام تحويلات مكافئة.
لكل وظيفة، يتم تعريف SDNF وSCNF بشكل فريد حتى التقليب.

الشكل الطبيعي المقترن المثالي

الصيغة العادية الملتصقة المثالية (SCNF)وهذه صيغة مكافئة لها، وهي عبارة عن اقتران للانفصالات الأولية وتفي بالخصائص:

تحتوي جميع الانفصالات الأولية على جميع المتغيرات المضمنة في الدالة F(x 1 ,x 2 ,...x n).
جميع الانفصالات الأولية مختلفة.
يحتوي كل انفصال أولي على متغير مرة واحدة.
لا يوجد انفصال أولي واحد يحتوي على متغير ونفيه.

طرق حل أنظمة المعادلات المنطقية

كيرجيزوفا إي.في.، نيمكوفا إيه.إي.

معهد ليسوسيبيرسك التربوي –

فرع جامعة سيبيريا الفيدرالية، روسيا

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

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

مهمة:حل نظام المعادلات المنطقية:

دعونا نفكر طريقة الاختزال إلى معادلة واحدة . تتضمن هذه الطريقة تحويل المعادلات المنطقية بحيث يكون طرفها الأيمن مساويًا لقيمة الحقيقة (أي 1). للقيام بذلك، استخدم عملية النفي المنطقية. ثم، إذا كانت المعادلات تحتوي على عمليات منطقية معقدة، فإننا نستبدلها بعمليات أساسية: "AND"، "OR"، "NOT". الخطوة التالية هي دمج المعادلات في واحدة مكافئة للنظام باستخدام العملية المنطقية "AND". بعد ذلك، يجب عليك تحويل المعادلة الناتجة بناءً على قوانين الجبر المنطقي والحصول على حل محدد للنظام.

الحل 1:قم بتطبيق الانقلاب على طرفي المعادلة الأولى:

دعونا نتخيل المعنى الضمني من خلال العمليتين الأساسيتين "OR" و"NOT":

بما أن الأطراف اليسرى للمعادلتين تساوي 1، يمكننا دمجهما باستخدام العملية "AND" في معادلة واحدة تعادل النظام الأصلي:

نفتح القوس الأول حسب قانون دي مورغان ونحول النتيجة التي تم الحصول عليها:

المعادلة الناتجة لها حل واحد:أ= 0، ب = 0 و ج = 1.

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

الحل 2:لنقم بإنشاء جدول الحقيقة للنظام:








0	0	1	1	0	1

يتم تمييز السطر الذي يتم استيفاء شروط المهمة له بالخط العريض. إذًا أ = 0، ب = 0، ج = 1.

طريق تقسيم . تتمثل الفكرة في تثبيت قيمة أحد المتغيرات (تسويتها بـ 0 أو 1) وبالتالي تبسيط المعادلات. ومن ثم يمكنك تثبيت قيمة المتغير الثاني، وهكذا.

الحل 3:يترك أ = 0، ثم:

من المعادلة الأولى نحصل عليهاب =0 ومن الثاني - C=1. حل النظام: A = 0، B = 0، C = 1.

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

المعادلة الأولى للنظام تعتمد فقط على A وB، والمعادلة الثانية على A وC. يمكن للمتغير A أن يأخذ قيمتين 0 و 1:

من المعادلة الأولى يتبع ذلك ، اذن متى A = 0 ونحصل على B = 0، وبالنسبة لـ A = 1 لدينا B = 1. إذن، المعادلة الأولى لها حلان بالنسبة للمتغيرين A وB.

دعونا نصور المعادلة الثانية والتي من خلالها نحدد قيم C لكل خيار. عندما يكون A = 1، لا يمكن أن يكون التضمين خاطئًا، أي أن الفرع الثاني من الشجرة ليس له حل. فيأ= 0 نحصل على الحل الوحيدج= 1 :

وبذلك حصلنا على حل النظام: A = 0، B = 0، C = 1.

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

مهمة:ما عدد حلول المعادلة (أ → ب ) + (ج → د ) = 1؟ حيث A، B، C، D هي متغيرات منطقية.

حل:دعونا نقدم متغيرات جديدة: X = أ → ب و ص = ج → د . وبأخذ المتغيرات الجديدة في الاعتبار سيتم كتابة المعادلة على النحو التالي:س + ص = 1.

ويصح الانفصال في ثلاث حالات: (1؛0)، (1؛0)، (1؛1)، بينما X وY استدلالاً، أي أنه صادق في ثلاث، وباطل في واحدة. ولذلك، فإن الحالة (0;1) ستتوافق مع ثلاث مجموعات محتملة من المعلمات. الحالة (1؛1) - ستتوافق مع تسع مجموعات محتملة من معلمات المعادلة الأصلية. هذا يعني أن مجموع الحلول الممكنة لهذه المعادلة هو 3+9=15.

الطريقة التالية لتحديد عدد الحلول لنظام من المعادلات المنطقية هي شجرة ثنائية. دعونا نلقي نظرة على هذه الطريقة باستخدام مثال.

مهمة:ما عدد الحلول المختلفة لنظام المعادلات المنطقية:

نظام المعادلات المعطى يعادل المعادلة:

( س 1 → س 2 )*( س 2 → س 3 )*…*( س م -1 → س م) = 1.

دعونا نتظاهر بذلكس 1 - صحيح، فمن المعادلة الأولى نحصل على ذلكس 2 صحيح أيضًا ، من الثاني -س 3 =1 وهكذا حتى س م= 1. إذن المجموعة (1؛ 1؛ …؛ 1) منم الوحدات هي حل النظام دعها الآنس 1 =0 ثم من المعادلة الأولى التي لديناس 2 =0 أو س 2 =1.

متى س 2 صحيح أننا حصلنا على أن المتغيرات المتبقية صحيحة أيضًا، أي أن المجموعة (0; 1; ...; 1) هي حل للنظام. فيس 2 =0 لقد حصلنا على ذلك س 3 =0 أو س 3 =، وهكذا. وبالاستمرار إلى المتغير الأخير نجد أن حلول المعادلة هي مجموعات المتغيرات التالية (م +1 حل، في كل حلم القيم المتغيرة):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

تم توضيح هذا النهج بشكل جيد من خلال بناء شجرة ثنائية. عدد الحلول الممكنة هو عدد الفروع المختلفة للشجرة المبنية. ومن السهل أن نرى أنها متساويةم +1.

المتغيرات	شجرة	عدد الحلول
× 1
× 2
× 3

في حالة وجود صعوبات في التفكير وبناء شجرة القرار، يمكنك البحث عن حل باستخدام جداول الحقيقةلمعادلة واحدة أو معادلتين.

دعنا نعيد كتابة نظام المعادلات بالشكل:

ولنقم بإنشاء جدول الحقيقة بشكل منفصل لمعادلة واحدة:

× 1	× 2	(× 1 → × 2)

لنقم بإنشاء جدول الحقيقة لمعادلتين:

× 1	× 2	× 3	× 1 → × 2	× 2 → × 3	(× 1 → × 2) (× 2 → × 3)*

بعد ذلك، يمكنك أن ترى أن معادلة واحدة صحيحة في الحالات الثلاث التالية: (0؛ 0)، (0؛ 1)، (1؛ 1). نظام من معادلتين يكون صحيحا في أربع حالات (0؛ 0؛ 0)، (0؛ 0؛ 1)، (0؛ 1؛ 1)، (1؛ 1؛ 1). وفي هذه الحالة يتضح على الفور أن هناك حلًا يتكون من أصفار فقط وأكثر مالحلول التي يتم فيها إضافة وحدة واحدة في كل مرة، بدءًا من الموضع الأخير حتى ملء جميع الأماكن الممكنة. يمكن الافتراض أن الحل العام سيكون له نفس الشكل، ولكن لكي يصبح هذا النهج حلاً، يلزم إثبات صحة الافتراض.

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

الأدب:

1. مشاكل منطقية / أو.ب. بوجومولوف – الطبعة الثانية. - م: بينوم. مختبر المعرفة، 2006. – 271 ص: مريض.

2. بولياكوف ك.يو. نظم المعادلات المنطقية / مجلة تربوية ومنهجية لمعلمي علوم الحاسوب : المعلوماتية العدد 14 ، 2011.

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

مهمة:حل نظام المعادلات المنطقية:

الحل 1:قم بتطبيق الانقلاب على طرفي المعادلة الأولى:

دعونا نتخيل المعنى الضمني من خلال العمليتين الأساسيتين "OR" و"NOT":

نفتح القوس الأول حسب قانون دي مورغان ونحول النتيجة التي تم الحصول عليها:

المعادلة الناتجة لها حل واحد: A = 0، B = 0، C = 1.

الحل 2:لنقم بإنشاء جدول الحقيقة للنظام:








0	0	1	1	0	1

يتم تمييز السطر الذي يتم استيفاء شروط المهمة له بالخط العريض. إذًا أ=0، ب=0، ج=1.

الحل 3:دع A = 0، ثم:

من المعادلة الأولى نحصل على B = 0، ومن الثانية - C = 1. حل النظام: A = 0، B = 0، C = 1.

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

مهمة:ما عدد حلول المعادلة (A →B) + (C →D) = 1؟ حيث A، B، C، D هي متغيرات منطقية.

حل:دعونا نقدم متغيرات جديدة: X = A →B وY = C →D. وبأخذ المتغيرات الجديدة في الاعتبار، سيتم كتابة المعادلة على النحو التالي: X + Y = 1.

ويكون الانفصال صحيحاً في ثلاث حالات: (0;1)، (1;0) و(1;1)، في حين أن X وY هما مضامين، أي أنه صحيح في ثلاث حالات، وكاذب في حالة واحدة. ولذلك، فإن الحالة (0;1) ستتوافق مع ثلاث مجموعات محتملة من المعلمات. الحالة (1؛1) - ستتوافق مع تسع مجموعات محتملة من معلمات المعادلة الأصلية. هذا يعني أن مجموع الحلول الممكنة لهذه المعادلة هو 3+9=15.

مهمة:ما عدد الحلول المختلفة لنظام المعادلات المنطقية:

نظام المعادلات المعطى يعادل المعادلة:

(س 1 → س 2 )*(س 2 → س 3 )*…*(س م -1 → س م) = 1.

دعونا نتظاهر بذلك س 1 - صحيح، فمن المعادلة الأولى نحصل على ذلك س 2 صحيح أيضًا ، من الثاني - س 3 =1 وهكذا حتى س م= 1. هذا يعني أن المجموعة (1؛ 1؛ …؛ 1) من وحدات m هي حل للنظام. دعها الآن س 1 =0 ثم من المعادلة الأولى التي لدينا س 2 =0 أو س 2 =1.

متى س 2 صحيح أننا حصلنا على أن المتغيرات المتبقية صحيحة أيضًا، أي أن المجموعة (0; 1; ...; 1) هي حل للنظام. في س 2 =0 لقد حصلنا على ذلك س 3 =0 أو س 3 =، وهكذا. وبالاستمرار إلى المتغير الأخير نجد أن حلول المعادلة هي مجموعات المتغيرات التالية (م +1 حل، كل حل يحتوي على قيم م للمتغيرات):