المعادلات المنطقية في علوم الحاسوب. المنطق. وظائف المنطق. حل المعادلات. حل معادلة منطقية

UDC 004.023.004

سيمينوف سيرجي ماكسيموفيتش

جامعة ولاية فلاديفوستوك للاقتصاد والخدمة في روسيا. فلاديفوستوك

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

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

الكلمات والعبارات الأساسية: أنظمة المعادلات المنطقية ، شجرة القرار ، علاقات التكرار ، B15 ، الاستخدام.

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

نظم المعادلات المنطقية. دعنا نلتزم التدوين التالي: فصل (+) ، اقتران () ، حصري OR (©) ، ضمني (-> ■) ، التكافؤ (=) ، النفي (- ■). في الأشكال ، تشير الدائرة المظلمة إلى 1 ودائرة الضوء تشير إلى 0. Fl هو عدد الحلول لـ X1 يساوي 1. Fo هو عدد حلول X1 يساوي 0. N هو عدد المتغيرات في نظام المعادلات. F (N) = F1 (N) + F0 (N) هو العدد الإجمالي للحلول.

المهمة 1. تحتاج إلى إيجاد عدد الحلول لنظام المعادلات (اختبار رقم 2)

أولاً قمنا بتعيين X1 = 1. ثم بالنسبة للمعادلة الأولى ، يمكن أن تكون قيم X2 و X3 عشوائية. وهكذا ، تم بناء الشجرة حتى المستوى الثالث. علاوة على ذلك ، مع مراعاة X2 و Xs ، نختار X4. بعد ذلك ، تتكرر الخوارزمية لكل ثلاثة متغيرات (الشكل 1). بدءًا من المستوى الرابع ، يمكنك أن ترى أن Fl (4) = Fl (3) + Fl (1) ، Fl (5) = Fl (4) + Fl (2). وبالتالي ، نحصل على Fl (N) = Fl (N-1) + Fl (N-3) (1)

أرز. 1. المهمة 1

المعادلة (1) تعني:

ب س (8) = 16 + 7 = 23 ،

م (9) = 23 + 11 = 34.

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

إذن ، F (9) = Fl (9) + Fo (9) = 34 + 16 = 50.

عند بناء شجرة قرار ، يمكنك إنشاء علاقات تكرار بصريًا لتحديد عدد القرارات على المستوى N.

يقول مبدأ الاستقراء الرياضي: يجب أن يكون هناك تسلسل من العبارات Fl ، F2 ، F3 ودع العبارة الأولى Fl تكون صحيحة. يمكننا إثبات أن صحة FN تعني أن FN + l صحيح. ثم كل العبارات في هذا التسلسل صحيحة.

النظر في الشكل. 2 للمهمة 1.

d2> 3 x5 xb x7

أرز. 2. تحليل شجرة القرار

يوضح الشكل 2 الأرقام التي لها رأس مشترك (مجموعات من القيم المتغيرة) للمعادلات الخمس الأولى من النظام. هناك ثلاثة متغيرات متضمنة في كل معادلة ، لذلك تتكون الأشكال من قيم المتغيرات الثلاثة (ثلاثة مستويات للشجرة). من أجل تحديد الأرقام ، سيكون من الممكن إدخال التدوين. ومع ذلك ، سنمضي على النحو التالي: سيتم تعيين عدد الدوائر المكونة لكل رقم (قيم متغيرة). ثم نحصل على المعادلات التالية للتسلسل:

4. 7, 4, 4, 1, 7

5. 7, 4, 4, 1, 7, 7, 4.

من المعادلة 4 ، يمكن ملاحظة أن أشكال المعادلة N تتكون من أشكال المعادلة N-1 وأشكال المعادلة N-3. من المهم عدم وجود أرقام أخرى ولا يمكن أن تكون لهذا النوع من المعادلات ، أي أن الانتقال من معادلة إلى أخرى يتم عن طريق زيادة عدد الأرقام من مجموعة محدودة وفقًا لقواعد محددة بدقة. هذه الحقيقة هي الحقيقة الرئيسية من أجل التأكيد عن طريق الاستقراء أنه بالنسبة للمعادلة N + 1 ، ستتألف مجموعة الأرقام من أرقام المعادلة N وأرقام المعادلة N-2.

هناك طريقة أخرى لتحديد الأرقام وهي تحديد عدد القيم المتغيرة في المستوى الأخير لمعادلة معينة ، أي أننا نحتاج إلى الانتقال من رقم المعادلة إلى رقم مستوى الشجرة ، حيث نحتاج إلى تحديد الرقم من الحلول لنظام المعادلات ، ثم بالنسبة للشجرة المركبة نحصل على التسلسل: 1 ، 2 ، 4 ، 5 ، 7 ، 11 ، 16. بالنسبة لهذا التسلسل ، الصيغة صحيحة: FN = FN-1 + FN-3 .

وفقًا لاستدلالنا ، ستكون هذه الصيغة صحيحة لـ N + 1 ، وبتحريض أي N.

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

المهمة 2. من الضروري إيجاد عدد الحلول لنظام المعادلات (، 4.16)

(X1 = X2) + (X1 = X3) = 1 (X2 = X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4 = X5) + (X4 = X6) = 1 (X5 = X6) + (X5 = X7) = 1

XI X2 X3>: 1 X5 Xb X7

أرز. 3. المهمة 2

للحصول على عدد الحلول للمهمة 2 ، كان من الممكن عدم بناء شجرة القرار بالكامل (الشكل 3) ، لأنه من الواضح أن Fl (N) = N وبالمثل ، Fo (N) = N. إجمالي F ( 7) = 7 + 7 = 14.

المهمة 3. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (اختبار رقم 1)

(X1 ^ X2) ■ (X2 ^ X3) ■ (X3 ^ X4) ■ (X4 ^ X5) = 1

(Yl ^ Y2) ■ (Y2 ^ Yz) ■ (Yz ^ Y4) ■ (Y4 ^ Y5) = 1

(Yl ^ X1) ■ (Y2 ^ X2) ■ (Y3 ^ X3) ■ (Y4 ^ X4) ■ (Y5 ^ X5) = 1

يوضح الشكل 4 أشجار القرار لـ X و Y وجداول الحقيقة المقابلة.

أرز. 4. المهمة 3

من المعادلتين الأوليين ، بما أن X و Y مستقلتان ، فإن العدد الإجمالي للحلول F (5) = 6 * 6 = 36. من أجل مراعاة المعادلة الثالثة ، من الضروري لكل متغير Y احسب عدد المجموعات من الجدول X التي لا تفي بالمعادلة. المعنى الضمني Yi ^ Xi = 0 إذا كان Yi = 1 و Xi = 0. وبعبارة أخرى ، بالنسبة لـ Yl = 1 ، فإن المعادلة الثالثة لا تفي بجميع الصفوف من الجدول X ، حيث X1 = 0. عدد هذه الصفوف هو 5 . بالنسبة إلى Y2 = 1 مثل هذه الخطوط - 4 ، إلخ. إجمالي عدد الصفوف التي لا تحقق المعادلة الثالثة هو 5 + 4 + 3 + 2 + 1 = 15.

وبالتالي ، فإن العدد الإجمالي للحلول الممكنة هو 36 - 15 = 21. المهمة 4. من الضروري إيجاد عدد الحلول لنظام المعادلات (، 4.17.a)

(X1 = X2) + (X1 = X3) = (X2 = X3) + (X2 = X4) = (X4 = X5) + (X4 = X6) = (X5 = X6) + (X5 = X7) = (Xb \ u003d X7) + (Xb \ u003d X8) \ u003d (X5 \ u003d X6) \ u003d 0

أرز. 5. المهمة 4

في هذا المثال ، من الصعب تحديد الصيغة النهائية F (N) ، فمن الأسهل بناء شجرة قرار حتى النهاية (أو على الأقل إلى X6). يوضح الشكل 5 شجرة القرار المنشأة. نتيجة لذلك ، نحصل على F (8) = Fl (8) + Fo (8) = 5 + 5 = 10.

المهمة 5. من الضروري إيجاد عدد الحلول لنظام المعادلات (، 4.17.b)

(X1 = X2) + (X1 = X3) = 1 (X2 = X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4 = X5) + (X4 = X6) = 1 (X5 = X6) + (X5 = X7) = 1 (X6 = X8) = 1

في هذا المثال ، بالإضافة إلى المثال السابق ، من الأسهل بناء شجرة قرار حتى النهاية (الشكل 6). نتيجة لذلك ، نحصل على F (8) = Fl (8) + Fo (8) = 7 + 7 = 14.

المهمة 6. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات ([!]> 4.17.c)

(X! 8 "X2) + (X2EXz) \ u003d 1 (X2fXz) + (Xs \ u003d X4) \ u003d 1 (Xs8" X4) + (X4 \ u003d X5) \ u003d 1 (X4 © X5) + (X5 \ u003d Xb) \ u003d 1 (X5fXb) + (Xb = X7) = 1 (Xb © X7) + (X7 = X8) = 1 شجرة القرار موضحة في الشكل. 7.

XI X2 X3 X4 X5 X6 X7 X8 XI X2 X3 X4 X5 X6 X7 X8

أرز. 6. المهمة 5 الشكل. 7. المهمة 6

بالنسبة لنظام المعادلات هذا ، لم يكن من الممكن بناء شجرة قرار كاملة ، لأنه بالفعل من الخطوة الثالثة - الرابعة يتضح أن F1 (N) = N. من السهل رؤية أنه يمكن الحصول على Fo (N) من شجرة تبدأ من المستوى الثاني من الصفر. ثم F (N) = N. لذا ، F (8) = Fl (8) + Fo (8) = 8 + 8 = 16.

المهمة 7. تحتاج إلى إيجاد عدد الحلول لنظام المعادلات

(X4EX5) + (X4 © X6) = 1 (X5 © Xb) + (X5 © X7) = 1

لاحظ أنه إذا كانت X! = X2 = 1 ، ثم يتم استيفاء المعادلة الأولى لـ Xz = 0. دعونا أولاً نبني شجرة لـ Xl = X2 = 1 (الشكل 8). ثم عدد الحلول Fl (N) = Fll (N) + Flo (N).

XI X2 X3 X4 X5 X6 X7 X8

أرز. 8. المهمة 7

يوضح الشكل 8 أن عدد الحلول هو F11 (N) = F11 (N-1) + F11 (N-2). بمعنى آخر ، يتم وصف عدد الحلول بواسطة أرقام فيبوناتشي. يمكن حذف الفرع الثاني من الشجرة لـ F10 ، حيث يتم الحصول عليه من الشكل. 1 ابتداء من المستوى الثاني. ثم F10 (N) = F11 (N + 1). أخيرًا ، نحصل على Fll (8) = 13 و Flo (8) = Fll (9) = 13 + 8 = 21. ثم Fll (8) = Fll (8) + Flo (8) = 13 + 21 = 34.

من أجل الحصول على F0 (N) ، ليس من الضروري أيضًا بناء شجرة قرار ، حيث يتم الحصول عليها من الشكل. 1 ابتداء من المستوى الثالث. ثم Fo (N) = Fll (N + 2). ومن ثم نحصل على ذلك Fo (8) = Fll (10) = Fll (9) + Fll (8) = 21 + 13 = 34. وبالتالي ، فإن العدد الإجمالي للحلول F (8) = F1 (8) + F0 (8) = s4 + s4 = 68.

المهمة 8. من الضروري إيجاد عدد الحلول لنظام المعادلات ([h] ، المهمة 2)

(X1 + X2) ^ (X3 + X4) = 1 (X3 + X4) ^ (X5 + X6) = 1 (X5 + X6) ^ (X7 + X8) = 1 (X7 + X8) ^ (X9 + X10) = 1

لنقم بالتعويض (X1 + X2) = Yl ، إلخ. واحصل على نظام المعادلات:

^ ^ Y2 = 1 Y2 ^ Yg = 1 Yg ^ Y4 = 1 Y4 ^ Y5 = 1

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

نظرًا لأن المتغيرات Y مستقلة ، بالنسبة للصف الأول من جدول الحقيقة الموضح في الشكل. 4 ، عدد التركيبات المختلفة 35 ، للصف الثاني 34 ، وهكذا. العدد الإجمالي للتركيبات المختلفة هو 35 + 34 + 33 + 32 + 31 + 30 = 364.

المهمة 9. من الضروري إيجاد عدد الحلول لنظام المعادلات (، المهمة 4)

(^ ^ b) ■ (-X ^ X3) ■ No ^ X) ■ (-X ^ K3) = 1 No ^ Y2) ■ (Y1 ^ Y3) ■ (-G1 ^ Y4) ■ (Y1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1

بالنسبة إلى X و Y لدينا بعد الأشجارقرارات

أرز. 9. المهمة 8

بالنظر إلى المعادلة الثالثة ، نحصل على المجموعات الأربع التالية من المجموعات:

أ - ج: 4 * 4 = 16 ((- 1 جنيه إسترليني + ص 1) ■ (-X + Y5) = (0 + 1) ■ (0 + 1) = 1) ب - ج: 4 * 4 = 16 ( (-X + Y 1) ■ (-X + Y5) = (1 + 1) ■ (1 + 1) = 1) A - D: = 0 (0 + 0) ■ (-X + Y5) = 0) ب - د: 4 * 4 = 16 (1 + 0) ■ (1 + Y5) = 1) هناك 48 مجموعة من الحلول في المجموع.

المهمة 10. من الضروري إيجاد عدد الحلول لنظام المعادلات (^ 1 = ب) + (Xz = X)) ■ = ب) + -fz = X4)) = 1 ((Xz = X4) + (X5 = X6)) ■ (- (X = X) + - (X = X6)) = 1 ((X5 = X6) + ^ 7 = X ")) ■ (- (X = X6) + - (^ 7 = X8)) = 1

((X7 = X8) + (X9 = Xlo)) ■ (- ^ 7 = X8) + = Xlo)) = 1

(X5 = X) = Yz (X7 = X8) = Y4 (X9 = X10) = Y5

(ص ^ 2) ■ (-b + ^) = 1

(Y2 + Yz) ■ № + -Тз) = 1

(Yz + Y4) ■ № + ^) = 1

(Y4 + Y5) ■ (^ 4 + ^) = 1

يوضح الشكل 10 شجرة القرار

U1 U2 UZ U4 U5

أرز. 10. المهمة 10

المهمة 11. تحتاج إلى إيجاد عدد الحلول لنظام المعادلات (مثال 2)

X1 + X2 = 1 -X2 + Xs = 1

يوضح الشكل 11 شجرة قرار. لقد حددنا أنفسنا بأربعة مستويات بدلاً من عشرة ، لأنه من الواضح أن F1 (N) = 1 و F0 (N) = N. ثم P (N) = P1 (N) + BoC) = 1 + N.) = 1 + 10 = 11.

أرز. 11. المهمة 11

المهمة 12. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (مثال ح)

(X1 = X2) + (X2 = Xs) = 1

(X1 = X3) + (X3 = X4) (X1 = X4) + (X4 = X5) (X1 = X5) + (X5 = X6) (X1 = X6) + (X6 = X7) (X1 = X7) + (X7 = X8) (X1 = X) + (X8 = X9) (X1 = X9) + (X9 = X10) (X1 = X10) = 0

أرز. 12. المهمة 12

بعد بناء شجرة قرار من "1" (نقصر أنفسنا على خمسة مستويات) ، نلاحظ أن Fl (N) = N. علاوة على ذلك ، تتكون قيم Xn من قيم N-1 "0" وواحد قيمة "1". ومع ذلك ، فإن المعادلة الأخيرة في نظامنا تمنع القيمة "1" لـ X10. لذلك ، فإن عدد الحلول Fl (10) = 10 - 1. من السهل أن ترى أن شجرة القرار من "0" ستكون متماثلة (سيكون هناك واحد بدلاً من الأصفار). لذلك F0 = 10 - 1. أخيرًا

F (N) = 2 × 9 = 18.

المهمة 13. تحتاج إلى إيجاد عدد الحلول لنظام المعادلات (مثال 4)

- (X1 = X2) + (X3 = X4) = 1

- (X3 = X4) + (X5 = X) = 1

- (X = X) + (X7 = X) = 1

- (X7 = X8) + (X9 = X10) = 1

لنستبدل:

(X1 = X2) = Yl

(X5 \ u003d X) \ u003d Yz

(X7 = X8) = Y4

(X9 = X10) = Y5

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

توضح المهمة 11 أن F (5) = 5 + 1 = 6. يظهر جدول الحقيقة في الشكل. 13.

U1 U2 UZ U4 U5

أرز. 13. المهمة 13

بالنظر إلى الاستبدال ، نلاحظ أن التعبير ^ = X2) يساوي واحدًا (أو صفرًا) في حالتين (عندما تتطابق قيم المتغيرات). مع الأخذ في الاعتبار استقلالية المتغيرات لكل صف من الجدول ، نحصل على أن عدد مجموعات الحلول هو 25 = 32. العدد الإجمالي لمجموعات الحلول هو 6 * 32 = 192.

المهمة 14. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 1)

((X = ب) ■ (X3 = X4)) + (4X1 = ب) ■ - (X = X)) = 0 ((X3 = X4) ■ (X5 = X6)) + (4X3 = X4) ■ - (X = X6)) = 0

((X5 = X) ■ (X7 = X8)) + (- (X = X6) ■ 4X7 = X8)) = 0 ((X7 = X8) ■ (X9 = X '،)) + (- (^ 7 = X8) ■ ^ 9 = Xlo)) = 0

ب) = Yl (X = ^ 4) = Y2

(X5 = X6) = Yz ^ 7 = X8) = Y4 ^ 9 = Xlo) = Y5

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

(UL) + (-U "■ -U2) \ u003d 0

(Y2 Yz) + (-Y2 ■ -Y3) \ u003d 0 (Y3-Y4) + (-Y3 ■ -Y4) \ u003d 0 (Y4-Y5) + (-Y4 ■ -Y5) \ u003d 0

(Y2 = Yz) = 0 (Uz = Y4) = 0 (Y4 = Y5) = 0

يوضح الشكل 14 شجرة قرار

U1 U2 UZ U4 U5

أرز. 14. المهمة 14

بالنظر إلى الاستبدال ، نلاحظ أن التعبير (X1 = X2) يساوي واحدًا (أو صفرًا) في حالتين (عندما تكون قيم المتغيرات هي نفسها). مع الأخذ في الاعتبار استقلالية المتغيرات لكل شجرة ، نحصل على أن عدد مجموعات القرار هو 25 = z2. العدد الإجمالي لمجموعات الحلول هو 64.

المهمة 15. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 2)

(X4 X5) + (-X4 -X5) + (X4 = X) = 1

(X5 X) + (-X -X6) + (X5 = X7) = 1

(X X7) + (-X -X7) + (X = X8) = 1

(X7 X) + (-X7 -X8) + (X7 = X9) = 1

(X8 X9) + (-X -X9) + (X8 = X10) = 1

(X1 = X2) + (X1 = Xs) = 1

(X = X3) + (X2 = X4) = 1

(Xs = X4) + (Xs = X5) = 1

(X4 = X5) + (X4 = X) = 1

(X5 = X6) + (X5 = X7) = 1

(X = X7) + (X6 = X8) = 1

(X7 = X8) + (X7 = X9) = 1

(X = X9) + (X8 = X10) = 1

لكن هذا النظام يكرر النظام من المهمة 5 ، فقط بدون شرط القيد وللحالة N = 10. ثم عدد الحلول هو F (N) = F1 (N) + F0 (N) = N + N لـ N = 10 نحصل على F (N) = 20.

المهمة 16. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 3)

(X1 X2) + (-X1 -X2) + (X1 \ u003d Xs) \ u003d 1

(X2 Xs) + (-X -Xs) + (X2 \ u003d X4) \ u003d 1

(Xs X4) + (-Xs -X4) + (Xs = X5) = 1

(X4 X5) + (-X -X5) + (X4 = Xb) = 1

(X5 Xb) + (-X -Xb) + (X5 \ u003d X7) \ u003d 1

(Xb X7) + (-Xb -X7) + (Xb \ u003d X8) \ u003d 1

(X7 X8) + (-X7 -X8) + (X7 = X9) = 1

(X8 X9) + (-X8 -X9) + (X8 = X10) = 0

يمكن إعادة كتابة نظام المعادلات هذا ، كما في المهمة السابقة ، على النحو التالي:

(XI = X2) + (XI = Xs) = 1 (X = Xs) + (X2 = X) = 1 (Xs = X) + (Xs = X5) = 1 (X = X5) + (X4 = Xb) = 1 (X5 = Xb) + (X5 = X7) = 1 (Xb = X7) + (Xb = X8) = 1 (X = X8) + (X7 = X9) = 1 (X = X9) + (X8 = Xxc) = 0

من السهل التحقق من المعادلة الأخيرة من أنه بعد N = 8 يتوقف عدد الحلول عن الزيادة. ثم F (10) = F (8) = 8 + 8 = 16.

المهمة 17. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 4)

(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 -Xs) = 1

(X2 Xs) + (-X2 -Xs) + (Xs X) + (-Xs ■ -X4) = 1

(Xz X) + (-Xz -X4) + (X4 X5) + (-X4 -X5) = 1

(X4 X) + (-X -X5) + (X5 Xb) + (-X5 -Xb) = 1

(X5 Xb) + (-X -Xb) + (Xb X7) + (-Xb ■ -X7) = 1

(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 -X8) = 1

(X7 X) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1

(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 1

لاحظ أنه يمكن إعادة كتابة نظام المعادلات على النحو التالي:

(X = X2) + (X = X3) = 1 (X = X3) + (X = X) = 1 (X3 = X4) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X5 = Xb) + (Xb = X7) = 1

(Xb = X7) + (X7 = X) = 1 (X7 = X8) + (X8 = X9) = 1 (Xv = X 9) + (X9 = X10) = 1

في الشكل 15 ، تم بناء الشجرة حتى المستوى الخامس ويمكن ملاحظة أن عدد الحلول موصوف بأرقام فيبوناتشي ، أي Fl (N) = Fl (N-1) + Fl (N-2 ). ثم Fl (10) = 89. من السهل التحقق من أن الشجرة متماثلة في F0 (N). إذن Fo (10) = 89. B (10) = p1 (10) + Po (10) = 89 + 89 = 178.

أرز. 15. المهمة 17

المهمة 18. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 5)

(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 ■ -Xs) = 1

(X2 Xs) + (-X -Xs) + (Xs X4) + (-Xs -X4) = 1

(Xs X4) + (-Xs -X4) + (X4 X5) + (-X4 ■ -X5) = 1

(X4 X5) + (-X4 -X5) + (X Xb) + (-X5 ■ -Xb) = 1

(X5 Xb) + (-X5 -Xb) + (Xb X7) + (-Xb ■ -X7) = 1

(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 ■ -X8) = 1

(X7 X8) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1

(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 0

لاحظ أنه يمكن إعادة كتابة نظام المعادلات على النحو التالي:

(X = X2) + (X2 = X3) = 1 (X2 = X3) + (X3 = X4) = 1

(Xz = X) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X = Xb) + (Xb = X7) = 1 (Xb = X7) + (X7 = X8) = 1 (X7 = X8) + (X8 = X9) = 1 (X8 = X 9) + (X = X10) = 0

المهمة 18 تشبه المهمة 17 ، ومع ذلك ، فإن المعادلة الأخيرة تؤدي إلى حقيقة أنه بدءًا من المستوى السابع ، لا يزيد عدد الحلول. نتيجة لذلك ، F (10) = Fl (10) + Fo (10) = Fl (7) + Fo (7) = 21 + 21 = 42.

المهمة 19. تحتاج إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة ب)

(X = X2) + (X = X10) = 1 (X = X3) + (X2 = X10) = 1 (X3 = X4) + (X = X10) = 1 (X = X5) + (X = X10) = 1 (X = Xb) + (X5 = X10) = 1 (Xb = X7) + (Xb = X10) = 1 (X7 = X) + (X = X10) = 1 (X8 = X9) + (X = X10) = 1 (X9 = X10) + (X9 = X10) = 1 (X = X10) = 0

- - - - * - - - - * - س

أرز. 1 ب. المهمة 19

تظهر أشجار القرار للحصول على F1 (N) و F0 (N) في الشكل. 1 ب. ومع ذلك ، لا يمكن تحقيق المعادلة (X9 = X10) = 1. لذلك ، نظام المعادلات ليس له حلول.

المهمة 20. أنت بحاجة إلى إيجاد عدد الحلول لنظام المعادلات (، المهمة 7)

(X ^ X2) + (X ^ X3) = 1 (X2 ^ X3) + (X2 * X4) = 1 (X3 ^ X4) + (X3 ^ X5) = 1 (X ^ X5) + (X4 ^ Xb) = 1 (X5 ^ Xb) + (X5 ^ X7) = 1 (Xb ^ X7) + (Xb ^ X8) = 1

(X7 ^ Xs) + (X7 ^ X9) = 1 (Xs ^ X9) + (Xs ^ X10) = 1

يوضح الشكل 17 شجرة قرار من "1".

أرز. 17. المهمة 20 18. المهمة 20

بدلاً من عشرة مستويات ، حددنا أنفسنا بخمسة ، لأن المهمة مشابهة للمهمة 17. ومع ذلك ، من "0" ستبدو الشجرة مختلفة (الشكل 18).

لاحظ أن F0 (N) = Fx (N + 1) - 1. ثم Fx (10) = 89 ، و F0 (10) = Fx (11) - 1 = 144-1. إذن ، F (10) = F1 ( 10) + F0 (10) = 89 + 143 = 232.

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

في البرنامج الموضح في الشكل. 19 ، المصفوفة m والمتغير c يحتويان على قيم المتغيرات التي ترضي نظام المعادلات من المهمة 7. يعطي البرنامج الإجابة 68. يستخدم البرنامج حقيقة أن عدد مجموعات القيم المختلفة n من المتغيرات المنطقية هي 2n. للحصول على كل المجموعات ، تحتاج إلى التكرار من 0 إلى 2n-1. يتم تحويل متغير الحلقة إلى النظام الثنائي في كل خطوة ، وتكتب النتيجة إلى المصفوفة m ، ثم يتم التحقق من الشروط من نظام المعادلات. لحل نظام آخر من المعادلات ، يكفي تغيير أبعاد المصفوفة m ، وتغيير قيمة المتغير vg (يساوي البعد) ، وتغيير شروط الاختبار.

Dim m (S) As Integer، k As Integer، j. كعدد صحيح. _ j كعدد صحيح. N كعدد صحيح ، vg As Integer Dim مع As String vg = S j-0

من 1 إلى 2 ■ "" ■ vg "حلقة من خلال ^ من 1 إلى 2n. حيث n = ،. g لـ k = 1 إلى vg

N =) .- 1: ثنائي

قم بترجمة "^ Tiils N> 0" e النظام الثنائي m (k) = N Mod 2 K = N ■ 2 k = k +! حلقة

Ifim (l) O m (2) or m (l) 0- ni (3)) and_ "شروط المعادلة (م (2)

c = "" "المتغير c في كل خطوة سيحتوي على حل النظام لـ k = 1 ثم vg

c = c - Foimat (m (k) j التالي k j-j-1 End If Next I.

Ms ^ Eox i "عدد الحلول

VvVvVlVvVvv- -1 ط

أرز. 19. برنامج للمهمة 7

1. كريلوف إس. استخدام 2014. المعلوماتية. مهام الاختبار المواضيعي / SS كريلوف ، د. أوشاكوف. - م: دار النشر "امتحان". - 245 ص.

2. موقع K.Yu. بولياكوف. وضع الوصول: http: //kpolyakov.namd.-ru/download/inf-2011-14.pdf

3. دورة منهجية معتمدة من شركة "1C" للتحضير لامتحان الدولة الموحد في المعلوماتية. وحدة 1". - م: دار النشر "1 ج". - 218 ص.

4. اجتياز الامتحان بنجاح في علوم الحاسب. وضع الوصول: http://infoegehelp.ru/index.php؟Itemid=77&id=103&option=com_con-

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

خوارزمية حل أنظمة المعادلات بهذه الطريقة:

قم بتحويل المعادلة المنطقية وتبسيطها.

تحديد تسلسل حل المعادلات في النظام ، لأنه في معظم الحالات يوجد حل متسلسل للمعادلات من أعلى إلى أسفل (كما هو الحال في النظام) ، ولكن هناك خيارات عندما يكون ذلك أكثر ملاءمة ، فمن الأسهل البدء حل من الأسفل إلى الأعلى.

قم ببناء جدول للمتغيرات ، حيث يتم تعيين القيم الأولية للمتغير الأول (أو الأخير).

اكتب بالتتابع المتغيرات المحتملة للمتغير التالي عندما الجميعمعنى الأول.

بعد حل المعادلة السابقة ، والانتقال إلى المعادلة التالية ، تأكد من الانتباه إلى المتغيرات المستخدمة في المعادلات السابقة واللاحقة ، حيث يتم نقل قيم المتغيرات التي تم الحصول عليها عند حل المعادلات السابقة كخيارات لـ المعادلات التالية.

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

مثال 1.

¬ X1 ˅ X2=1

¬ X2 ˅ X3=1

¬ X3 ˅ X4=1

¬ X9 ˅ X10=1

لنبدأ بـ X1 ونرى القيم التي يمكن أن يأخذها هذا المتغير: 0 و 1.

ثم سننظر في كل من هذه القيم ونرى ما يمكن أن تكونه X2.

الجواب: 11 حلا

مثال 2

( X1X2) ˅ (¬X1˄¬X2) ˅( X1↔ X3)=1

( X2˄X3) ˅ (¬X2˄¬X3) ˅( X2↔ X4)=1

(X8˄ X9) ˅ (¬X8˄¬X9)˅ (X8↔X10) = 0

دعنا نتحول وفقًا للصيغة (أ˄ ب)˅ (¬ أ ˄ ¬ ب)= أ↔ ب

نحن نحصل:

( X1↔ X2) ˅ (X1↔ X3) =1

( X2↔ X3) ˅ (X2↔ X4) =1

( X8↔ X9 (X8↔ X10) =0

بالنسبة إلى X1 = 0-8 حلول

لنأخذ X1 = 1 ونرى القيمة التي يمكن أن تأخذها X2. الآن ، لكل X2 ، ضع في اعتبارك القيم التي يمكن أن تأخذها X3 ، وما إلى ذلك.

ل Х1 = 1-8 حلول

مجموع 8 + 8 = 16 حلا

إجابة. 16 حلا

مثال 3 .

¬ ( X1↔ X2) ( X1X3) ˄ (¬X1˅¬X3 )=0

¬ ( X2↔ X3) ˄ (X2˅X4) ˄ (¬X2˅¬X4)=0

….

¬ ( X8↔ X9 (X8X10) ˄ (¬X8˅¬X10)=0

بعد التحولات (أ˅ ب) ˄(¬ أ ˅¬ ب)= ¬( أ ↔ ب)

نحن نحصل:

¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0

¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0

…..

¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0

لنأخذ X1 = 0 ونرى القيمة التي يمكن أن تأخذها X2. الآن لكل X2 ، ضع في اعتبارك القيم التي يمكن أن تأخذها X3 ، وما إلى ذلك.

اتضح 10 حلول لـ Х1 = 0

سنفعل نفس الشيء مع X1 = 1. نحصل أيضًا على 10 حلول

المجموع: 10 + 10 = 20

الجواب: 20 حلاً.

مثال 4

(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1

(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4) = 1

….

(X8 ˄ X9) ˅ (¬X8˄ ¬X9) ˅ (X9 ˄ X10) ˅ (¬X9 ˄¬ X10) = 0

دعنا نتحول وفقًا للصيغ. (أ˄ ب)˅ (¬ أ ˄ ¬ ب)= أ↔ ب. نحن نحصل:

(X1↔X2) ˅ (X2↔X3) = 1

(X2↔X3) ˅ (X3↔X4) = 1

(X3↔X4) ˅ (X4↔X5) = 1

(X4↔X5) ˅ (X5↔X6) = 1

(X5↔X6) ˅ (X6↔X7) = 1

(X6↔X7) ˅ (X7↔X8) = 1

(X7↔X8) ˅ (X8↔X9) = 1

(Х8↔ Х9) ˅ (9↔ Х10) = 0

لنبدأ من النهاية ، لأنه في المعادلة الأخيرة يتم تحديد المتغيرات بشكل فريد.

دع X10 = 0 ، ثم X9 = 1 ، X8 = 0 ، X7 = 0 ، X6 = 0 ، ويمكن أن تأخذ المتغيرات التالية قيمًا مختلفة. سننظر في كل منها.

إجمالي 21 حلًا لـ X10 = 0

فكر الآن في X10 = 1. نحصل أيضًا على 21 حلاً

المجموع: 21 + 21 = 42

الجواب: 42 حلاً

مثال 5

( X1X2) ˅ (¬X1˄¬X2) ˅ (¬X3˄X4 (X3˄¬X4)=1

( X3˄X4) ˅ (¬X3˄¬X4) ˅ (¬X5X6) ˅ (X5˄¬X6)=1

( X5X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8 (X7˄¬X8)=1

( X7˄X8) ˅ (¬X7˄¬X8) ˅ (¬ X9X10 (X9˄ ¬X10) =1

دعنا نتحول وفقًا للصيغ:(¬ أ ˄ ب) ˅ ( أ ˄ ¬ ب)= أ↔ ¬ ب

( أ˄ ب)˅ (¬ أ ˄ ¬ ب)= أ↔ ب

( X1↔ X2) ˅ (X3 ↔ ¬X4)=1

( X3↔ X4 (X5 ↔ ¬X6)=1

( X5↔ X6) ˅ (X7 ↔ ¬X8)=1

( X7↔ X8 (X9 ↔ ¬X10)=1

ضع في اعتبارك القيم التي يمكن أن تأخذها X1 و X2: (0.0) ، (0.1) ، (1.0) ، (1.1).

دعنا نفكر في كل خيار ونرى القيم في هذه الحالة X3 و X4 التي يمكن أن تتخذها

بدءًا من X7 و X8 ، سنقوم على الفور بتدوين عدد الحلول ، لأنه من الواضح على الفور أنه عندما تكون القيم هي نفسها (1.1) و (0.0) ، فإن المتغيرات التالية لها 4 حلول ، و عند الاختلاف (0.1) و (1 ، 0) - حلين.

المجموع: 80 + 80 + 32 = 192

الجواب: 192 حلا

مثال 6

(X1↔X2) ˅ (X2 ↔X3) = 1

(X2↔X3) ˅ (X3↔X4) = 1

(X3↔X4) ˅ (X4 ↔X5) = 1

….

(X8↔X9) ˅ (X9 ↔X10) = 1

لنأخذ X1 = 0 ونرى القيمة التي يمكن أن تأخذها X2. الآن ، لكل X2 ، ضع في اعتبارك القيم التي يمكن أن تأخذها X3 ، وما إلى ذلك.

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

نفس الشيء بالنسبة لـ X1 = 1 نحصل على 89 حلاً

المجموع: 89 + 89 = 178 حلاً

الجواب: 178 حلاً

دعونا نحلها بطريقة أخرى

(X1↔X2) ˅ (X2 ↔X3) = 1

(X2↔X3) ˅ (X3↔X4) = 1

(X3↔X4) ˅ (X4 ↔X5) = 1

….

(X8↔X9) ˅ (X9 ↔X10) = 1

دعنا نقدم بديلاً:

تي 1 =(X1↔X2)

تي 2 =(X2↔X3)

تي 3 =(X3↔X4)

تي 4 =(X4↔X5)

تي 5 =(X5↔X6)

تي 6 =(X6↔X7)

تي 7 =(X7↔X8)

تي 8 =(X8↔X9)

تي 9 =(X9↔ X10)

نحن نحصل:

تي1تي2=1

تي2˅تي3=1

تي3˅تي4=1

تي4تي5=1

تي5تي6=1

تي6˅تي7=1

تي7˅تي8=1

تي8تي9=1

تي9تي10=1

لنأخذتي1 = 1 واستخدم خصائص الانفصال:

لكن تذكر ذلك

تي 1 =(X1↔X2)

تي 2 =(X2↔X3) ، إلخ.

دعنا نستخدم خاصية التكافؤ ونتأكد من ذلك ، بالنظر إلى الجدول

عندما يكون T = 1 ، يتم الحصول على حلين. وعندما = 0 - حل واحد.

لذلك ، يمكنك حساب عدد الآحاد وضربها في 2 + عدد الأصفار. العد ، أيضًا باستخدام النمط.

اتضح أن عدد الآحاد = العدد الإجمالي السابق للحلول T ، وعدد الأصفار يساوي عدد الآحاد السابق

لذا. سوف نتلقى. بما أن واحد يعطي حلين ، فإن 34 * 2 = 68 حلاً من واحد + 21 حلاً من 0.

إجمالي 89 حلًا لـ T = 1. بطريقة مماثلة ، نحصل على 89 حلاً لـ T = 0

المجموع 89 + 89 = 178

الجواب: 178 حلاً

مثال 7

(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬ (X1 ↔ X2) ˅ ¬ (X3↔ X4)=1

(X3 ↔ X4 (X5↔ X6) ˄ ¬ (X3 ↔ X4) ˅ ¬ (X5↔ X6)=1

(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬ (X5 ↔ X6) ˅ ¬ (X7↔ X8)=1

(X7 ↔ X8 (X9↔ X10) ˄ ¬ (X7 ↔ X8) ˅ ¬ (X9↔ X10)=1

دعنا نقدم بديلاً:

تي1=(X1 ↔ X2)

تي2=(X3↔ X4)

تي3=(X5↔ X6)

تي4=(X7 ↔ X8)

تي5=(X9↔ X10)

نحن نحصل:

(Т1 ˅ Т2) ˄ ¬ (Т1 ˅¬ Т2) = 1

(Т2 ˅ Т3) ˄ ¬ (Т2˅¬ Т3) = 1

(Т3 ˅ Т4) ˄ ¬ (Т3 ˅¬ Т4) = 1

(Т4 ˅ Т5) ˄ ¬ (Т4˅¬ Т5) = 1

ضع في اعتبارك ما يمكن أن يكون T:

T1

T2

T3

T4

T5

المجموع

0

1

0

1

0

32

1

0

1

0

1

32

تي ك ≠ ت ك + 1 هو - هي ك = ت K + 2

نحصل على: 2 5 = 32 لـ T.

المجموع: 32 + 32 = 64

الجواب: 64 حلاً.

كيفية حل بعض المشكلات في القسمين "أ" و "ب" من اختبار علوم الكمبيوتر

الدرس رقم 3. المنطق. وظائف المنطق. حل المعادلات

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

1. تبادلية الانفصال والاقتران:
   أ ، ب ، ب ، أ
   أ ^ ب ≡ ب ^ أ
2. قانون التوزيع فيما يتعلق بالانفصال والاقتران:
   أ ˅ (ب ^ ج) ≡ (أ ˅ ب) ^ (أ ˅ ج)
   أ ^ (ب ˅ ج) ≡ (أ ^ ب) ˅ (أ ^ ج)
3. نفي سلبي:
   ¬ (أ) ≡ أ
4. تناسق:
   أ ^ ¬a ≡ خطأ
5. ثالث حصري:
   أ أ صحيح
6. قوانين دي مورغان:
   ¬ (أ ˅ ب) ≡ ¬ أ ب
   ¬ (أ ˄ ب) ≡ ¬ أ ب
7. تبسيط:
   أ ˄ أ ≡ أ
   أ ˅ أ ≡ أ
   أ ˄ صحيح أ
   أ ˄ خطأ ≡ خطأ
8. استيعاب:
   أ ˄ (أ ˅ ب) ≡ أ
   أ ˅ (أ ˄ ب) ≡ أ
9. استبدال التضمين
   أ → ب ≡ ¬a ˅ ب
10. تغيير الهوية
    أ ≡ ب ≡ (أ ˄ ب) ˅ (¬a ˄ ب)

تمثيل الوظائف المنطقية

يمكن تعريف أي دالة منطقية لمتغيرات n - F (x 1، x 2، ... x n) بواسطة جدول الحقيقة. يحتوي هذا الجدول على مجموعتين من المتغيرات ، يتم تحديد قيمة الوظيفة في هذه المجموعة لكل منها. هذه الطريقة جيدة عندما يكون عدد المتغيرات صغيرًا نسبيًا. حتى بالنسبة لـ n> 5 ، يصبح التمثيل ضعيفًا.

هناك طريقة أخرى لتعريف الوظيفة من خلال بعض الصيغ ، باستخدام دوال بسيطة إلى حد ما معروفة. يُطلق على نظام الوظائف (f 1، f 2،… f k) اسم كامل إذا كان من الممكن التعبير عن أي دالة منطقية بواسطة صيغة تحتوي فقط على الوظائف f i.

اكتمل نظام الوظائف (¬ ، ˄ ، ˅). القانونان 9 و 10 هما مثالان على كيفية التعبير عن التضمين والهوية من خلال النفي والاقتران والفصل.

في الواقع ، نظام وظيفتين كامل أيضًا - النفي والاقتران أو النفي والفصل. تأتي الإقرارات من قوانين De Morgan التي تسمح بالتعبير عن اقتران من خلال النفي والفصل ، وبالتالي التعبير عن الانفصال من خلال النفي والاقتران:

(أ ˅ ب) ≡ ¬ (¬a ˄ ¬b)
(أ ˄ ب) ≡ ¬ (¬a ˅ ¬b)

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

عادةً ما تتضمن الوظائف الأساسية للغات البرمجة الهوية والنفي والاقتران والفصل. في مهام الاستخدامجنبا إلى جنب مع هذه الوظائف غالبا ما يكون هناك ضمنا.

دعونا نلقي نظرة على بعض المهام البسيطة المتعلقة بالوظائف المنطقية.

المهمة 15:

يتم إعطاء جزء من جدول الحقيقة. أي من الوظائف الثلاث المعطاة يتوافق مع هذا الجزء؟

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬X 1 ˄ X 2) ˅ (X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

رقم الميزة 3.

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

المهمة 16:

أي من الأرقام التالية يستوفي الشرط:

(الأرقام ، بدءًا من الرقم الأكثر أهمية ، انتقل بترتيب تنازلي) → (رقم - زوجي) ˄ (أدنى رقم - زوجي) ˄ (أعلى رقم - فردي)

إذا كان هناك العديد من هذه الأرقام ، حدد أكبرها.

1. 13579
2. 97531
3. 24678
4. 15386

يتم استيفاء الشرط من خلال الرقم 4.

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

المشكلة 17: شهد شاهدان على النحو التالي:

الشاهد الأول: إذا كان "أ" مذنباً ، فإن "ب" مذنب بالتأكيد ، وج "بريء".

الشاهد الثاني: اثنان مذنبان. وواحد من المتبقين هو بالتأكيد مذنب ومذنب ، لكن لا يمكنني تحديد من بالضبط.

ما هي الاستنتاجات حول ذنب "أ" و "ب" و "ج" التي يمكن استخلاصها من الأدلة؟

الجواب: يستنتج من الشهادة أن (أ) و (ب) مذنبان و (ج) بريء.

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

أول شيء يجب القيام به هو إضفاء الطابع الرسمي على البيانات. دعنا نقدم ثلاثة متغيرات منطقية ، A و B و C ، كل منها صحيح (1) إذا كان المشتبه به المقابل مذنبًا. ثم تُعطى شهادة الشاهد الأول بالصيغة:

أ → (ب ، ¬ ج)

تُعطى شهادة الشاهد الثاني بالصيغة:

أ ˄ ((ب ˄ ¬ ج) ˅ (ب ج))

يُفترض أن شهادات كلا الشاهدين صحيحة وتمثل اقتران الصيغ المقابلة.

دعونا نبني جدول الحقيقة لهذه القراءات:

الأدلة الموجزة صحيحة في حالة واحدة فقط ، مما يؤدي إلى إجابة واضحة - A و B مذنبان و C بريء.

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

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

لنفترض أن F (x 1، x 2،… x n) دالة منطقية لمتغيرات n. المعادلة المنطقية هي:

F (x 1 ، x 2 ، ... x n) \ u003d C ،

الثابت C له القيمة 1 أو 0.

يمكن أن تحتوي المعادلة المنطقية على من 0 إلى 2 ن حلول مختلفة. إذا كانت C تساوي 1 ، فإن الحلول هي كل مجموعات المتغيرات من جدول الحقيقة التي تأخذ فيها الدالة F القيمة الحقيقية (1). المجموعات المتبقية هي حلول معادلة C تساوي صفرًا. يمكننا دائمًا اعتبار المعادلات من النموذج فقط:

F (x 1، x 2،… x n) = 1

في الواقع ، دع المعادلة تعطى:

F (x 1، x 2،… x n) = 0

في هذه الحالة ، يمكنك الانتقال إلى المعادلة المكافئة:

¬F (x 1، x 2،… x n) = 1

ضع في اعتبارك نظام من المعادلات المنطقية k:

F 1 (x 1، x 2، ... x n) \ u003d 1

F 2 (x 1، x 2، ... x n) \ u003d 1

و ك (س 1 ، س 2 ، ... س ن) = 1

حل النظام عبارة عن مجموعة من المتغيرات التي يتم استيفاء جميع معادلات النظام عليها. من حيث الوظائف المنطقية ، للحصول على حل لنظام المعادلات المنطقية ، يجب على المرء أن يجد مجموعة تكون فيها الوظيفة المنطقية Ф صحيحة ، والتي تمثل اقتران الوظائف الأصلية F:

Ф = F 1 ˄ F 2 ˄… F ك

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

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

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

ما هي شجرة القرار الثنائية وكيف يتم بناؤها ، سأشرح بأمثلة للعديد من المهام.

المشكلة 18

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 ، x2 ، x3 ، x4 ، x5 ، y1 ، y2 ، y3 ، y4 ، y5 التي تحقق نظامًا من معادلتين؟

الإجابة: يحتوي النظام على 36 حلاً مختلفًا.

الحل: يتضمن نظام المعادلات معادلتين. لنجد عدد الحلول للمعادلة الأولى ، اعتمادًا على 5 متغيرات - x 1 ، x 2 ، ... x 5. يمكن اعتبار المعادلة الأولى بدورها نظامًا من 5 معادلات. كما هو موضح ، يمثل نظام المعادلات في الواقع اقترانًا للوظائف المنطقية. العبارة العكسية صحيحة أيضًا - يمكن اعتبار اقتران الشروط كنظام معادلات.

لنقم ببناء شجرة قرار للتضمين (x1 → x2) ، المصطلح الأول للارتباط ، والذي يمكن اعتباره المعادلة الأولى. إليك ما يبدو عليه التمثيل الرسومي لهذه الشجرة:

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

هذه المجموعات هي: ((1 ، 1) ، (0 ، 1) ، (0 ، 0))

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

(x1 → x2) / \ (x2 → x3) / \ (x3 → x4) / \ (x4 → x5) = 1
لديه 6 حلول. إليك ما تبدو عليه شجرة القرار الكاملة لهذه المعادلة:

المعادلة الثانية لنظامنا تشبه الأولى:

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

الاختلاف الوحيد هو أن المعادلة تستخدم متغيرات Y. لهذه المعادلة أيضًا 6 حلول. نظرًا لأنه يمكن دمج كل حل متغير X i مع كل حل متغير Y j ، فإن إجمالي عدد الحلول هو 36.

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

المشكلة 19

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية 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

هذه المهمة هي تعديل للمهمة السابقة. الفرق هو أنه تمت إضافة معادلة أخرى تتعلق بمتغيري X و Y.

من المعادلة X 1 → Y 1 ، يترتب على ذلك أنه عندما يكون لدى X 1 القيمة 1 (يوجد أحد هذه الحلول) ، فإن Y 1 له القيمة 1. وبالتالي ، هناك مجموعة واحدة تحتوي على قيم X 1 و Y 1 1. عندما تكون X 1 تساوي 0 ، يمكن أن يكون لـ Y 1 أي قيمة ، كلاهما 0 و 1. لذلك ، كل مجموعة مع X 1 تساوي 0 ، وهناك 5 مجموعات من هذا القبيل ، تتوافق مع جميع المجموعات الست ذات المتغيرات Y. لذلك ، العدد الإجمالي للحلول هو 31.

المشكلة 20

(¬X 1 ˅ X 2) ˄ (X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 X 1) = 1

الحل: تذكر المعادلة الأساسية ، نكتب معادلتنا على النحو التالي:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

تعني سلسلة المضامين الدورية أن المتغيرات متطابقة ، لذا فإن معادلتنا تكافئ:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

تحتوي هذه المعادلة على حلين عندما تكون كل X i إما 1 أو 0.

المشكلة 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

الحل: كما هو الحال في المسألة 20 ، ننتقل من الآثار الدورية إلى الهويات بإعادة كتابة المعادلة بالصيغة:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

لنقم ببناء شجرة قرار لهذه المعادلة:

المشكلة 22

كم عدد الحلول الموجودة في نظام المعادلات التالي؟

((× 1X 2) ˄ (X 3 ≡X 4)) ˅ (¬ (× 1X 2) ˄ ¬ (X 3 ≡X4)) = 0

((X 3 ≡× 4) ˄ (X5 ≡X 6)) ˅ (¬ (X 3 ≡× 4) ˄ ¬ (X5 ≡X 6)) = 0

((X5 ≡× 6) ˄ (X 7X 8)) ˅ (¬ (X5 ≡X 6) ˄ ¬ (X 7X8)) = 0

((X 7X 8) ˄ (X9 ≡X 10)) ˅ (¬ (X 7× 8) ˄ ¬ (X9 ≡X10)) = 0

الجواب: 64

الحل: دعنا ننتقل من 10 متغيرات إلى 5 متغيرات عن طريق إدخال التغيير التالي في المتغيرات:

ص 1 = (س 1 ≡ × 2) ؛ ص 2 \ u003d (X 3 ≡ X 4) ؛ ص 3 = (س 5 × 6) ؛ ص 4 \ u003d (X 7 ≡ X 8) ؛ Y 5 \ u003d (X 9 ≡ X 10) ؛

ثم تأخذ المعادلة الأولى الشكل:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ¬Y 2) = 0

يمكن تبسيط المعادلة بكتابتها على النحو التالي:

(ص 1 ≡ ص 2) = 0

بالانتقال إلى النموذج التقليدي ، نكتب النظام بعد التبسيط بالشكل:

¬ (ص 1 ≡ ص 2) = 1

¬ (ص 2 ≡ ص 3) = 1

¬ (ص 3 ≡ ص 4) = 1

¬ (ص 4 ≡ ص 5) = 1

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

بالعودة إلى متغيرات X الأصلية ، لاحظ أن كل قيمة للمتغير Y تتوافق مع قيمتين من متغيرات X ، لذا فإن كل حل في المتغيرات Y يولد 2 5 حلاً في متغيرات X. ينتج عن فرعين 2 * 2 5 حلاً ، لذا فإن إجمالي عدد الحلول هو 64.

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

بشكل عام ، تعتبر مشاكل إيجاد حلول لنظام المعادلات المنطقية تمارين رياضية جيدة.

إذا كان من الصعب حل المشكلة يدويًا ، فيمكنك تكليف الكمبيوتر بحل المشكلة عن طريق كتابة برنامج مناسب لحل المعادلات وأنظمة المعادلات.

من السهل كتابة مثل هذا البرنامج. سوف يتعامل مثل هذا البرنامج بسهولة مع جميع المهام المعروضة في الاختبار.

من الغريب أن مهمة إيجاد حلول لأنظمة المعادلات المنطقية صعبة أيضًا على الكمبيوتر ، فقد اتضح أن الكمبيوتر له حدوده. يمكن للكمبيوتر التعامل بسهولة مع المهام التي يكون فيها عدد المتغيرات 20-30 ، لكنه سيبدأ في التفكير لفترة طويلة في المهام الأكبر. النقطة المهمة هي أن الدالة 2 n التي تحدد عدد المجموعات هي الأس الذي ينمو بسرعة مع n. سريع جدًا لدرجة أن الكمبيوتر الشخصي العادي لا يمكنه التعامل مع مهمة تحتوي على 40 متغيرًا في اليوم.

برنامج C # لحل المعادلات المنطقية

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

إن فكرة إنشاء برنامج بسيطة - فهي تستند إلى تعداد كامل لجميع المجموعات الممكنة من القيم المتغيرة. نظرًا لأن عدد المتغيرات n معروف بمعادلة منطقية معينة أو نظام معادلات ، فإن عدد المجموعات معروف أيضًا - 2 n ، والتي يجب فرزها. باستخدام الوظائف الأساسية للغة C # - النفي والفصل والاقتران والهوية ، من السهل كتابة برنامج يقوم ، لمجموعة معينة من المتغيرات ، بحساب قيمة دالة منطقية تقابل معادلة منطقية أو نظام معادلات.

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

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

هذه هي الطريقة التي تبدو بها وظيفة C # التي تحل مشكلتنا:

///

///

/// دالة منطقية - طريقة ،

/// الذي تم تعيين توقيعه بواسطة مفوض DF

///

/// عدد المتغيرات

/// عدد الحلول

ثابت int SolveEquations (DF fun، int n)

مجموعة منطقية = منطقية جديدة [n] ؛

int m = (int) Math.Pow (2، n) ؛ // عدد المجموعات

int p = 0 ، q = 0 ، k = 0 ؛

// العد الكامل بعدد المجموعات

لـ (int i = 0 ؛ i< m; i++)

// تشكيل المجموعة التالية - المجموعة ،

// معطى بالتمثيل الثنائي للرقم i

لـ (int j = 0 ؛ j< n; j++)

k = (int) Math.Pow (2، j) ؛

// حساب قيمة الوظيفة في المجموعة

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

بالنسبة لأطفال المدارس ، من المعتاد عندما تكون معلمة الإدخال x بالنسبة لبعض الوظائف F (x) متغيرًا من النوع الحسابي أو السلسلة أو النوع المنطقي. في حالتنا ، يتم استخدام تصميم أكثر قوة. تشير دالة SolveEquations إلى وظائف ذات ترتيب أعلى - وظائف من النوع F (f) ، والتي لا يمكن أن تكون معلماتها متغيرات بسيطة فحسب ، بل وظائف أيضًا.

يتم تعريف فئة الوظائف التي يمكن تمريرها كمعامل لوظيفة SolveEquations على النحو التالي:

مندوب منطقي DF (bool vars) ؛

تتضمن هذه الفئة جميع الوظائف التي تم تمريرها كمعامل ، ومجموعة من قيم المتغيرات المنطقية المحددة بواسطة مصفوفة vars. والنتيجة هي قيمة منطقية تمثل قيمة الوظيفة في هذه المجموعة.

في الختام ، سأقدم برنامجًا تُستخدم فيه وظيفة SolveEquations لحل العديد من أنظمة المعادلات المنطقية. دالة SolveEquations هي جزء من فئة ProgramCommon التالية:

برنامج الفصل شائع

مندوب منطقي DF (bool vars) ؛

ثابت الفراغ الرئيسي (سلسلة args)

Console.WriteLine ("الوظيفة والحلول -" +

حل المعادلات (FunAnd ، 2)) ؛

Console.WriteLine ("الوظيفة لها 51 حلًا -" +

حل المعادلات (Fun51، 5)) ؛

Console.WriteLine ("الوظيفة بها 53 حلًا -" +

حل المعادلات (Fun53 ​​، 10)) ؛

ثابت منطقي FunAnd (بول فارز)

عودة vars && vars؛

ثابت منطقي Fun51 (فارز منطقي)

f = f && (! vars || vars) ؛

f = f && (! vars || vars) ؛

f = f && (! vars || vars) ؛

f = f && (! vars || vars) ؛

f = f && (! vars || vars) ؛

ثابت منطقي Fun53 ​​(فارز منطقي)

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && ((vars == vars) || (vars == vars)) ؛

f = f && (! ((vars == vars) || (vars == vars))) ؛

إليك ما تبدو عليه نتائج الحل لهذا البرنامج:

10 مهام للعمل المستقل

1. أي من الوظائف الثلاث متكافئة:
   1. (X → Y) ˅ ¬Y
   2. ¬ (X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. تم تقديم جزء من جدول الحقيقة:

أي من الوظائف الثلاث تتوافق مع هذا الجزء:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. هيئة المحلفين تتكون من ثلاثة أشخاص. يتم اتخاذ القرار إذا صوت له رئيس لجنة التحكيم ، مدعومًا بواحد على الأقل من أعضاء لجنة التحكيم. خلاف ذلك ، لم يتم اتخاذ أي قرار. بناء وظيفة منطقية تضفي الطابع الرسمي على عملية صنع القرار.
5. يفوز X على Y إذا ظهرت أربع دفعات من العملات على الوجه ثلاث مرات. حدد دالة منطقية تصف العائد X.
6. يتم ترقيم الكلمات في الجملة بدءًا من واحد. تعتبر الجملة جيدة إذا تم استيفاء القواعد التالية:
   1. إذا انتهت الكلمة المرقمة الزوجية بحرف متحرك ، فيجب أن تبدأ الكلمة التالية ، إن وجدت ، بحرف متحرك.
   2. إذا انتهت الكلمة المرقمة الفردية بحرف ساكن ، فيجب أن تبدأ الكلمة التالية ، إن وجدت ، بحرف ساكن وتنتهي بحرف متحرك.
      أي الجمل التالية صحيحة:
   3. تغسل أمي ماشا بالصابون.
   4. القائد دائما نموذج.
   5. الحقيقة جيدة ، لكن السعادة أفضل.
7. كم عدد الحلول التي تحتوي عليها المعادلة:
   (أ ˄ ¬ ب) ˅ (¬a ˄ ب) → (ج ˄ د) = 1
8. ضع قائمة بجميع حلول المعادلة:
   (أ → ب) → ج = 0
9. كم عدد الحلول التي يمتلكها نظام المعادلات التالي:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 ← X 6 ˄ X 6 ← X 7 = 1
   X 7 ← X 8 ˄ X 8 ← X 9 = 1
   X 0 → X 5 = 1
10. كم عدد الحلول التي تحتوي عليها المعادلة:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

إجابات على المهام:

1. الوظائف b و c متكافئة.
2. الجزء يتوافق مع الوظيفة ب.
3. دع المتغير المنطقي P يأخذ القيمة 1 عندما يصوت رئيس لجنة التحكيم "لصالح" القرار. يمثل المتغيران M 1 و M 2 رأي أعضاء لجنة التحكيم. يمكن كتابة الوظيفة المنطقية التي تحدد اعتماد قرار إيجابي على النحو التالي:
   ف ˄ (م 1 ˅ م 2)
4. دع المتغير المنطقي P i يأخذ القيمة 1 عندما تظهر عملة i-th بشكل رأسي. يمكن كتابة الوظيفة المنطقية التي تحدد العائد X على النحو التالي:
   ¬ ((P 1 ˄ (P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (P 3 ˅ P 4)) ˅
   (¬P 3 ˄ P 4))
5. عرض ب.
6. تحتوي المعادلة على 3 حلول: (أ = 1 ؛ ب = 1 ؛ ج = 0) ؛ (أ = 0 ؛ ب = 0 ؛ ج = 0) ؛ (أ = 0 ؛ ب = 1 ؛ ج = 0)

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

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

مثال 1

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 و x2 و x3 و x4 و x5 و x6 و x7 و x8 التي تفي بجميع الشروط التالية؟

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

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

لا تحتاج الإجابة إلى سرد جميع مجموعات القيم المختلفة للمتغيرات x1 ، x2 ، x3 ، x4 ، x5 ، x6 ، x7 ، x8 ، والتي بموجبها يتم استيفاء نظام المساواة هذا. كإجابة ، تحتاج إلى تحديد عدد هذه المجموعات.

حل:

(x1 → x2) = y1 ؛ (x3 → x4) = y2 ؛ (x5 → x6) = y3 ؛ (x7 → x8) = y4.

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

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. يكون الارتباط 1 (صحيح) عندما يتم تقييم كل معامل إلى 1. أي ، يجب أن يكون كل من الدلالات صحيحًا ، وهذا صحيح بالنسبة لجميع القيم باستثناء (1 → 0). أولئك. في جدول قيم المتغيرات y1 و y2 و y3 و y4 ، يجب ألا تكون الوحدة على يسار الصفر:

أولئك. يتم استيفاء الشروط لـ 5 مجموعات من y1 إلى y4.

لأن y1 = x1 → x2 ، ثم يتم تحقيق القيمة y1 = 0 على مجموعة واحدة x1 ، x2: (1 ، 0) ، ويتم تحقيق القيمة y1 = 1 على ثلاث مجموعات x1 ، x2: (0،0) ، ( 0،1) ، (1.1). وبالمثل بالنسبة لـ y2 و y3 و y4.

نظرًا لأن كل مجموعة (x1 ، x2) للمتغير y1 يتم دمجها مع كل مجموعة (x3 ، x4) للمتغير y2 ، وهكذا ، يتم ضرب عدد مجموعات المتغيرات x:

لنجمع عدد المجموعات: 1 + 3 + 9 + 27 + 81 = 121.

إجابة: 121

مثال 2

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 ، x2 ، ... x9 ، y1 ، y2 ، ... y9 هناك والتي تفي بجميع الشروط التالية؟

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

كرد لا حاجةضع قائمة بجميع مجموعات القيم المختلفة للمتغيرات x1 ، x2 ، ... x9 ، y1 ، y2 ، ... y9 ، والتي بموجبها يتم استيفاء نظام المساواة المحدد. كإجابة ، تحتاج إلى تحديد عدد هذه المجموعات.

حل:

لنقم بتغيير المتغيرات:

(x1 ≡ y1) = z1، (x2 ≡ y2) = z2،…. ، (x9 ≡ y9) = z9

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

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧… ..∧ (¬z8 ≡ z9)

التكافؤ صحيح فقط إذا كان كلا المعاملين متساويين. ستكون حلول هذه المعادلة مجموعتين:

لأن zi = (xi ≡ yi) ، ثم القيمة zi = 0 تقابل مجموعتين (xi، yi): (0،1) و (1،0) ، والقيمة zi = 1 تقابل مجموعتين (xi، yi ): (0 ، 0) و (1،1).

ثم المجموعة الأولى z1، z2،…، z9 تقابل 2 9 مجموعات (x1، y1)، (x2، y2)،…، (x9، y9).

نفس الرقم يتوافق مع المجموعة الثانية z1 ، z2 ، ... ، z9. ثم هناك 2 9 +2 9 = 1024 مجموعة في المجموع.

إجابة: 1024

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

تُستخدم هذه الطريقة إذا كان نظام المعادلات بسيطًا بدرجة كافية وكان ترتيب زيادة عدد المجموعات عند إضافة المتغيرات واضحًا.

مثال 3

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

¬x9 ∨ x10 = 1 ،

أين x1، x2، ... x10 متغيرات منطقية؟

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

حل:

لنحل المعادلة الأولى. يساوي الانفصال 1 إذا كان أحد معاملاته على الأقل يساوي 1. أي ، الحلول هي المجموعات:

بالنسبة إلى x1 = 0 ، توجد قيمتان x2 (0 و 1) ، وبالنسبة إلى x1 = 1 ، توجد قيمة x2 واحدة فقط (1) ، بحيث تكون المجموعة (x1، x2) هي حل المعادلة. 3 مجموعات فقط.

دعونا نضيف المتغير x3 ونفكر في المعادلة الثانية. إنه مشابه للقيمة الأولى ، مما يعني أنه بالنسبة إلى x2 = 0 ، توجد قيمتان لـ x3 (0 و 1) ، وبالنسبة إلى x2 = 1 ، توجد قيمة واحدة فقط لـ x3 (1) ، بحيث تكون المجموعة ( x2، x3) حل المعادلة. هناك 4 مجموعات في المجموع.

من السهل ملاحظة أنه عند إضافة متغير آخر ، تتم إضافة مجموعة واحدة. أولئك. صيغة متكررة لعدد المجموعات على متغيرات (i + 1):

N i +1 = N i + 1. ثم بالنسبة لعشرة متغيرات نحصل على 11 مجموعة.

إجابة: 11

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

مثال 4

كم عدد مجموعات قيم المتغيرات المنطقية x 1، ...، x 4، y 1، ...، y 4، z 1، ...، z 4 التي تفي بجميع الشروط التالية؟

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

س ٤ ∧ ص ٤ ع ٤ = ٠

كرد لا حاجةضع قائمة بجميع مجموعات القيم المختلفة للمتغيرات x 1، ...، x 4، y 1، ...، y 4، z 1، ...، z 4 ، والتي بموجبها يتم استيفاء نظام المساواة المعطى .

كإجابة ، تحتاج إلى تحديد عدد هذه المجموعات.

حل:

لاحظ أن المعادلات الثلاث للنظام هي نفسها في مجموعات مختلفة من المتغيرات المستقلة.

تأمل المعادلة الأولى. يكون العطف صحيحًا (يساوي 1) فقط إذا كانت جميع معاملاته صحيحة (تساوي 1). المعنى الضمني هو 1 في كل المجموعات باستثناء (1،0). هذا يعني أن حل المعادلة الأولى سيكون مثل هذه المجموعات x1 ، x2 ، x3 ، x4 ، حيث 1 ليس على يسار 0 (5 مجموعات):

وبالمثل ، فإن حلول المعادلتين الثانية والثالثة ستكون بالضبط نفس مجموعات y1 ، ... ، y4 و z1 ، ... ، z4.

لنحلل الآن المعادلة الرابعة للنظام: x 4 ∧ y 4 ∧ z 4 = 0. سيكون الحل هو جميع المجموعات x4 و y4 و z4 التي يكون فيها أحد المتغيرات على الأقل يساوي 0.

أولئك. بالنسبة إلى x4 = 0 ، تكون جميع المجموعات الممكنة (y4، z4) مناسبة ، وبالنسبة إلى x4 = 1 ، تكون المجموعات (y4، z4) التي تحتوي على صفر واحد على الأقل مناسبة: (0 ، 0) ، (0،1) ، ( 1 ، 0).

إجمالي عدد المجموعات هو 25 + 4 * 9 = 25 + 36 = 61.

إجابة: 61

حل أنظمة المعادلات المنطقية من خلال بناء الصيغ المتكررة

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

مثال 5

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 ، x2 ، ... x7 ، y1 ، y2 ، ... y7 هناك والتي تفي بجميع الشروط التالية؟

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

لا تحتاج الإجابة إلى سرد جميع مجموعات القيم المختلفة للمتغيرات x1 ، x2 ، ... ، x7 ، y1 ، y2 ، ... ، y7 ، والتي بموجبها يظل نظام المساواة المعطى ثابتًا. كإجابة ، تحتاج إلى تحديد عدد هذه المجموعات.

حل:

لاحظ أن المعادلات الست الأولى للنظام هي نفسها وتختلف فقط في مجموعة المتغيرات. تأمل المعادلة الأولى. سيكون حلها هو مجموعات المتغيرات التالية:

دل:

عدد المجموعات (0،0) على المتغيرات (x1 ، y1) حتى A 1 ،

عدد المجموعات (0،1) على المتغيرات (x1 ، y1) حتى B 1 ،

عدد المجموعات (1،0) على المتغيرات (x1 ، y1) عبر C 1 ،

عدد المجموعات (1،1) على المتغيرات (x1، y1) عبر D 1.

عدد المجموعات (0،0) على المتغيرات (x2 ، y2) حتى A 2 ،

عدد المجموعات (0،1) على المتغيرات (x2 ، y2) عبر B 2 ،

عدد المجموعات (1،0) على المتغيرات (x2 ، y2) عبر C 2 ،

عدد المجموعات (1،1) على المتغيرات (x2، y2) عبر D 2.

من شجرة القرار ، نرى ذلك

أ 1 = 0 ، ب 1 = 1 ، ج 1 = 1 ، د 1 = 1.

لاحظ أن المجموعة (0،0) في المتغيرات (x2، y2) يتم الحصول عليها من المجموعات (0،1) و (1،0) و (1،1) في المتغيرات (x1، y1). أولئك. أ 2 \ u003d ب 1 + ج 1 + د 1.

يتم الحصول على المجموعة (0،1) الخاصة بالمتغيرات (x2، y2) من المجموعات (0،1) و (1،0) و (1،1) على المتغيرات (x1، y1). أولئك. ب 2 \ u003d ب 1 + ج 1 + د 1.

بالمثل ، نلاحظ أن C 2 \ u003d B 1 + C 1 + D 1. D2 = D1.

وبالتالي ، نحصل على صيغ متكررة:

أ i + 1 = B i + C i + D i

B i + 1 = B i + C i + D i

C i + 1 = B i + C i + D i

د i + 1 = A i + B i + C i + D i

دعونا نصنع طاولة

المعادلة الأخيرة (x7 ∨ y7) = 1 تتحقق من جميع المجموعات باستثناء تلك التي فيها x7 = 0 و y7 = 0. في جدولنا ، عدد هذه المجموعات هو A 7.

إذن ، إجمالي عدد المجموعات هو B 7 + C 7 + D 7 = 127 + 127 + 1 = 255

إجابة: 255

اسمحوا أن تكون وظيفة منطقية لمتغيرات n. المعادلة المنطقية هي:

الثابت C له القيمة 1 أو 0.

يمكن أن تحتوي المعادلة المنطقية على 0 إلى حلول مختلفة. إذا كانت C تساوي 1 ، فإن الحلول هي كل مجموعات المتغيرات من جدول الحقيقة التي تأخذ فيها الدالة F القيمة الحقيقية (1). المجموعات المتبقية هي حلول معادلة C تساوي صفرًا. يمكننا دائمًا اعتبار المعادلات من النموذج فقط:

في الواقع ، دع المعادلة تعطى:

في هذه الحالة ، يمكنك الانتقال إلى المعادلة المكافئة:

ضع في اعتبارك نظام من المعادلات المنطقية k:

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

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

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

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

ما هي شجرة القرار الثنائية وكيف يتم بناؤها ، سأشرح بأمثلة للعديد من المهام.

المشكلة 18

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 ، x2 ، x3 ، x4 ، x5 ، y1 ، y2 ، y3 ، y4 ، y5 التي تحقق نظامًا من معادلتين؟

الإجابة: يحتوي النظام على 36 حلاً مختلفًا.

الحل: يتضمن نظام المعادلات معادلتين. لنجد عدد الحلول للمعادلة الأولى اعتمادًا على 5 متغيرات -. يمكن اعتبار المعادلة الأولى بدورها نظامًا من 5 معادلات. كما هو موضح ، يمثل نظام المعادلات في الواقع اقترانًا للوظائف المنطقية. العبارة العكسية صحيحة أيضًا - يمكن اعتبار اقتران الشروط كنظام معادلات.

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

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

هذه المجموعات هي: ((1 ، 1) ، (0 ، 1) ، (0 ، 0))

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

لديه 6 حلول. إليك ما تبدو عليه شجرة القرار الكاملة لهذه المعادلة:

المعادلة الثانية لنظامنا تشبه الأولى:

الاختلاف الوحيد هو أن المعادلة تستخدم متغيرات Y. لهذه المعادلة أيضًا 6 حلول. نظرًا لأنه يمكن دمج كل حل متغير مع كل حل متغير ، فإن إجمالي عدد الحلول هو 36.

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

المشكلة 19

كم عدد مجموعات القيم المختلفة للمتغيرات المنطقية x1 ، x2 ، x3 ، x4 ، x5 ، y1 ، y2 ، y3 ، y4 ، y5 التي تفي بجميع الشروط التالية؟

هذه المهمة هي تعديل للمهمة السابقة. الفرق هو أنه تمت إضافة معادلة أخرى تتعلق بمتغيري X و Y.

ويترتب على المعادلة أنه عندما يكون لها القيمة 1 (يوجد أحد هذه الحلول) ، يكون لها القيمة 1. وبالتالي ، هناك مجموعة واحدة تحتوي على القيم 1. عندما تكون مساوية لـ 0 ، يمكن أن يكون لها أي قيمة ، كل من 0 و 1. لذلك ، كل مجموعة تساوي 0 ، وهناك 5 مجموعات من هذا القبيل ، تتوافق مع جميع المجموعات الست ذات المتغيرات Y. لذلك ، العدد الإجمالي للحلول هو 31.

المشكلة 20

الحل: تذكر المعادلة الأساسية ، نكتب معادلتنا على النحو التالي:

تعني سلسلة المضامين الدورية أن المتغيرات متطابقة ، لذا فإن معادلتنا تكافئ:

هذه المعادلة لها حلين عندما تكون جميعها إما 1 أو 0.

المشكلة 21

كم عدد الحلول التي تحتوي عليها المعادلة:

الحل: كما هو الحال في المسألة 20 ، ننتقل من الآثار الدورية إلى الهويات بإعادة كتابة المعادلة بالصيغة:

لنقم ببناء شجرة قرار لهذه المعادلة:

المشكلة 22

كم عدد الحلول الموجودة في نظام المعادلات التالي؟