كيفية حل بعض المسائل في القسمين (أ) و(ب) من امتحان علوم الحاسوب
الدرس 3. المنطق. وظائف المنطق. حل المعادلات
تم تخصيص عدد كبير من مشكلات امتحان الدولة الموحدة للمنطق الافتراضي. لحل معظمها، يكفي معرفة القوانين الأساسية للمنطق الافتراضي، ومعرفة جداول الحقيقة للوظائف المنطقية لمتغير واحد ومتغيرين. سأقدم القوانين الأساسية للمنطق المقترح.
- إبدال الانفصال والوصل:
أ ˅ ب ≡ ب ˅ أ
أ ^ ب ≡ ب ^ أ - قانون التوزيع فيما يتعلق بالانفصال والوصل:
أ˅ (ب^س) ≡ (أ˅ب) ^(أ˅س)
أ ^ (ب˅ج) ≡ (أ ^ ب)˅ (أ ^ ج) - نفي النفي:
¬(¬أ) ≡ أ - تناسق:
أ ^ ¬ أ ≡ خطأ - الحصري الثالث:
أ ˅ ¬а ≡ صحيح - قوانين دي مورغان:
¬(أ˅ب) ≡¬أ˄¬ب
¬(أ˄ب) ≡¬أ˅¬ب - تبسيط:
أ ˄ أ ≡ أ
أ ˅ أ ≡ أ
أ ˄ صحيح ≡ أ
أ ˄ خطأ ≡ خطأ - استيعاب:
أ˄ (أ˅ب) ≡ أ
أ ˅ (أ ˄ ب) ≡ أ - استبدال التضمين
أ → ب ≡ ¬أ ˅ ب - استبدال الهوية
أ ≡ ب ≡ (أ ˄ ب) ˅ (¬أ ˄ ¬ب)
تمثيل الوظائف المنطقية
يمكن تحديد أي دالة منطقية لمتغيرات n - F(x 1, x 2, ... x n) بواسطة جدول الحقيقة. يحتوي هذا الجدول على مجموعتين من المتغيرات، يتم تحديد قيمة دالة في هذه المجموعة لكل منها. هذه الطريقة جيدة عندما يكون عدد المتغيرات صغيرًا نسبيًا. بالفعل بالنسبة لـ n > 5، يصبح التمثيل ضعيفًا.
هناك طريقة أخرى وهي تحديد الدالة من خلال بعض الصيغ باستخدام وظائف بسيطة معروفة إلى حد ما. يُطلق على نظام الوظائف (f 1، f 2، ... f k) اسم كامل إذا كان من الممكن التعبير عن أي دالة منطقية بصيغة تحتوي على وظائف f i فقط.
نظام الوظائف (¬، ˄، ˅) مكتمل. القانونان 9 و10 هما أمثلة توضح كيفية التعبير عن التضمين والهوية من خلال النفي والاقتران والانفصال.
في الواقع، فإن النظام المكون من وظيفتين – النفي والاقتران أو النفي والانفصال – مكتمل أيضًا. من قوانين دي مورغان تتبع الأفكار التي تسمح للشخص بالتعبير عن الارتباط من خلال النفي والانفصال، وبالتالي، التعبير عن الانفصال من خلال النفي والربط:
(أ ˅ ب) ≡ ¬ (¬أ ˄ ¬ب)
(أ ˄ ب) ≡ ¬ (¬أ ˅ ¬ب)
ومن المفارقات أن النظام الذي يتكون من وظيفة واحدة فقط قد اكتمل. هناك وظيفتان ثنائيتان - الالتصاق المضاد والانفصال، ويطلق عليهما سهم بيرس وضربة شيفر، التي تمثل نظامًا مجوفًا.
تتضمن الوظائف الأساسية للغات البرمجة عادةً الهوية والنفي والاقتران والانفصال. في مشاكل امتحانات الدولة الموحدة، إلى جانب هذه الوظائف، غالبًا ما يتم العثور على التضمين.
دعونا نلقي نظرة على بعض المسائل البسيطة التي تتضمن وظائف منطقية.
المشكلة 15:
يتم إعطاء جزء من جدول الحقيقة. أي من الوظائف الثلاث المعطاة تتوافق مع هذا الجزء؟
| × 1 | × 2 | × 3 | × 4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
الوظيفة رقم 3.
لحل المشكلة، تحتاج إلى معرفة جداول الحقيقة للوظائف الأساسية وتذكر أولويات العمليات. اسمحوا لي أن أذكرك أن الاقتران (الضرب المنطقي) له أولوية أعلى ويتم تنفيذه قبل الانفصال (الإضافة المنطقية). أثناء العمليات الحسابية، من السهل ملاحظة أن الوظائف ذات الأرقام 1 و 2 في المجموعة الثالثة لها القيمة 1 ولهذا السبب لا تتوافق مع الجزء.
المشكلة 16:
أي من الأرقام المعطاة يحقق الشرط:
(الأرقام، بدءًا من الرقم الأكثر أهمية، مرتبة تنازليًا) → (رقم - زوجي) ˄ (رقم منخفض - زوجي) ˄ (رقم مرتفع - فردي)
إذا كان هناك العديد من هذه الأرقام، قم بالإشارة إلى الأكبر.
- 13579
- 97531
- 24678
- 15386
الشرط مستوفي بالرقم 4.
أول رقمين لا يستوفيان الشرط لأن الرقم الأدنى فردي. ويكون ربط الشروط خطأ إذا كان أحد شروط الربط خطأ. بالنسبة للرقم الثالث، لم يتم استيفاء شرط أعلى رقم. بالنسبة للرقم الرابع، يتم استيفاء الشروط المفروضة على الأرقام المنخفضة والمرتفعة للرقم. والحد الأول من الاقتران صحيح أيضاً، إذ يكون الضمن صحيحاً إذا كانت مقدمته خاطئة، وهذا هو الحال هنا.
مسألة 17: شهد شاهدان ما يلي:
الشاهد الأول: إذا كان (أ) مذنباً، فإن (ب) مذنب أكثر، و(ج) بريء.
الشاهد الثاني: اثنان مذنبان. وأحد الباقين مذنب ومذنب بالتأكيد، لكن لا أستطيع أن أقول من هو بالضبط.
ما هي الاستنتاجات حول ذنب "أ" و"ب" و"ج" التي يمكن استخلاصها من الشهادة؟
الجواب: يتبين من الشهادة أن A وB مذنبان، وC بريء.
الحل: بالطبع يمكن الإجابة على المنطق السليم. ولكن دعونا ننظر في كيفية القيام بذلك بشكل صارم ورسمي.
أول شيء يجب فعله هو إضفاء الطابع الرسمي على البيانات. دعونا نقدم ثلاثة متغيرات منطقية - A وB وC، كل منها له القيمة الحقيقية (1) إذا كان المشتبه به المقابل مذنبًا. ثم يتم إعطاء شهادة الشاهد الأول بالصيغة:
أ → (ب ˄ ¬ج)
وشهادة الشاهد الثاني تكون بالصيغة التالية:
أ˄ ((ب˄¬ج)˅ (¬ب˄ج))
يُفترض أن شهادة كلا الشاهدين صحيحة وتمثل ارتباط الصيغ المقابلة.
دعونا نبني جدول الحقيقة لهذه القراءات:
| أ | ب | ج | ف 1 | ف 2 | ف 1˄ ف 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
الأدلة الموجزة صحيحة في حالة واحدة فقط، مما يؤدي إلى إجابة واضحة - A وB مذنبان، وC بريء.
ويترتب على تحليل هذا الجدول أيضًا أن شهادة الشاهد الثاني أكثر إفادة. من حقيقة شهادته، يتبع ذلك خياران محتملان فقط - A وB مذنبان، وC بريء، أو A وC مذنبان، وB بريء. شهادة الشاهد الأول أقل إفادة - هناك 5 خيارات مختلفة تتوافق مع شهادته. تعطي شهادة كلا الشاهدين معًا إجابة واضحة حول ذنب المشتبه بهم.
المعادلات المنطقية وأنظمة المعادلات
اجعل F(x 1, x 2, …x n) دالة منطقية للمتغيرات n. تبدو المعادلة المنطقية كما يلي:
و(× 1، × 2، … × ن) = ج،
الثابت C له القيمة 1 أو 0.
يمكن أن تحتوي المعادلة المنطقية على حلول مختلفة من 0 إلى 2 n. إذا كانت C تساوي 1، فإن الحلول هي كل مجموعات المتغيرات من جدول الحقيقة التي تأخذ الدالة F لها القيمة true (1). المجموعات المتبقية هي حلول المعادلة مع C يساوي الصفر. يمكنك دائمًا النظر في معادلات النموذج فقط:
و(x 1 , x 2 , …x n) = 1
في الواقع، دعونا نعطي المعادلة:
و(× 1، × 2، … × ن) = 0
وفي هذه الحالة يمكننا الذهاب إلى المعادلة المكافئة:
¬F(x 1 , x 2 , …x n) = 1
خذ بعين الاعتبار نظام المعادلات المنطقية k :
ف 1 (× 1، × 2، … × ن) = 1
ف 2 (س 1، س 2، … س ن) = 1
F ك (x 1 , x 2 , …x n) = 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
(×1 → ص1) = 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
سلسلة التبعات الدورية تعني أن المتغيرات متطابقة، لذا فإن معادلتنا تعادل المعادلة:
× 1 ≡ × 2 ≡ × 3 ≡ × 4 ≡ × 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
ما عدد حلول نظام المعادلات التالي؟
((× 1 ≡× 2) ˄ (× 3 ≡× 4))˅(¬(× 1 ≡× 2) ˄ ¬(× 3 ≡× 4)) = 0
((× 3 ≡× 4) ˄ (× 5 ≡× 6))˅(¬(× 3 ≡× 4) ˄ ¬(× 5 ≡× 6)) = 0
((× 5 ≡× 6) ˄ (× 7 ≡× 8))˅(¬(× 5 ≡× 6) ˄ ¬(× 7 ≡× 8)) = 0
((× 7 ≡× 8) ˄ (× 9 ≡× 10))˅(¬(× 7 ≡× 8) ˄ ¬(× 9 ≡× 10)) = 0
الجواب: 64
الحل: دعنا ننتقل من 10 متغيرات إلى 5 متغيرات عن طريق إدخال التغيير التالي للمتغيرات:
ص 1 = (X 1 ≡ X 2)؛ ص 2 = (X 3 ≡ X 4)؛ ص 3 = (س 5 ≡ × 6)؛ ص 4 = (X 7 ≡ X 8)؛ ص 5 = (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 يوجد 2 قيم في متغيرات 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); // عدد المجموعات
كثافة العمليات = 0، س = 0، ك = 0؛
// أكمل البحث حسب عدد المجموعات
ل(int i = 0; i< m; i++)
// تشكيل المجموعة التالية - المجموعة،
// محدد بالتمثيل الثنائي للرقم i
ل(int j = 0; j< n; j++)
ك = (int)Math.Pow(2, j);
// احسب قيمة الوظيفة في المجموعة
لفهم البرنامج أتمنى أن تكون شروحات فكرة البرنامج والتعليقات الواردة في نصه كافية. سأركز فقط على شرح عنوان الوظيفة المحددة. تحتوي الدالة SolveEquations على معلمتين للإدخال. تحدد المعلمة fun دالة منطقية تتوافق مع المعادلة أو نظام المعادلات التي يتم حلها. تحدد المعلمة n عدد المتغيرات الممتعة. ونتيجة لذلك، تقوم الدالة SolveEquations بإرجاع عدد حلول الدالة المنطقية، أي عدد تلك المجموعات التي يتم تقييم الدالة عليها على أنها صحيحة.
من الشائع بالنسبة لأطفال المدارس أن تحتوي بعض الدالات F(x) على معلمة إدخال x وهي متغير من النوع الحسابي أو السلسلة أو المنطقي. في حالتنا، يتم استخدام تصميم أكثر قوة. تشير الدالة SolveEquations إلى دوال ذات ترتيب أعلى - دوال من النوع F(f)، والتي لا يمكن أن تكون معلماتها متغيرات بسيطة فحسب، بل دوال أيضًا.
يتم تحديد فئة الوظائف التي يمكن تمريرها كمعلمة إلى وظيفة SolveEquations على النحو التالي:
مندوب منطقي DF(bool vars);
تمتلك هذه الفئة جميع الوظائف التي يتم تمريرها كمعلمة لمجموعة من قيم المتغيرات المنطقية المحددة بواسطة صفيف vars. والنتيجة هي قيمة منطقية تمثل قيمة الدالة في هذه المجموعة.
وأخيرا، إليك برنامج يستخدم الدالة SolveEquations لحل عدة أنظمة من المعادلات المنطقية. تعد وظيفة SolveEquations جزءًا من فئة ProgramCommon أدناه:
برنامج الطبقة المشتركة
مندوب منطقي DF(bool vars);
الفراغ الثابت الرئيسي (وسائط السلسلة)
Console.WriteLine("والوظائف -" +
SolveEquations(FunAnd, 2));
Console.WriteLine("الوظيفة بها 51 حلًا -" +
SolveEquations(Fun51, 5));
Console.WriteLine("الوظيفة بها 53 حلًا -" +
SolveEquations(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 مهام للعمل المستقل
- أي الوظائف الثلاث متكافئة:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X˄Y
- المعطى هو جزء من جدول الحقيقة:
| × 1 | × 2 | × 3 | × 4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
أي من الوظائف الثلاث تتوافق معها هذه القطعة:
- (X 1˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 ← X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- تتكون لجنة التحكيم من ثلاثة أشخاص. يتم اتخاذ القرار إذا صوت له رئيس لجنة التحكيم، بدعم من واحد على الأقل من أعضاء لجنة التحكيم. وبخلاف ذلك، لا يتم اتخاذ أي قرار. بناء وظيفة منطقية تضفي الطابع الرسمي على عملية اتخاذ القرار.
- يفوز X على Y إذا أدت أربع رميات للعملات المعدنية إلى ظهور الرأس ثلاث مرات. حدد دالة منطقية تصف مردود X.
- يتم ترقيم الكلمات في الجملة بدءًا من واحد. تعتبر الجملة مبنية بشكل صحيح إذا تم استيفاء القواعد التالية:
- إذا انتهت الكلمة الزوجية بحرف متحرك، فإن الكلمة التالية، إن وجدت، يجب أن تبدأ بحرف متحرك.
- إذا انتهت الكلمة الفردية بحرف ساكن، فإن الكلمة التالية، إن وجدت، يجب أن تبدأ بحرف ساكن وتنتهي بحرف متحرك.
أي الجمل التالية مبنية بشكل صحيح: - غسلت أمي ماشا بالصابون.
- القائد هو دائما نموذج.
- الحقيقة جيدة، لكن السعادة أفضل.
- كم عدد الحلول التي تحتوي عليها المعادلة:
(أ ˄ ¬ ب) ˅ (¬أ ˄ ب) → (ج ˄ د) = 1 - قائمة جميع الحلول للمعادلة:
(أ → ب) → ج = 0 - ما عدد حلول نظام المعادلات التالي:
X 0 → X 1˄ X 1 → X 2 = 1
× 2 → × 3˄ × 3 → × 4 = 1
× 5 → × 6˄ × 6 → × 7 = 1
× 7 → × 8˄ × 8 → × 9 = 1
× 0 → × 5 = 1 - كم عدد الحلول التي تحتوي عليها المعادلة:
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1
أجوبة للمشاكل:
- الدالتان b وc متساويتان.
- الجزء يتوافق مع الوظيفة ب.
- دع المتغير المنطقي P يأخذ القيمة 1 عندما يصوت رئيس لجنة التحكيم بـ "لصالح" القرار. يمثل المتغيران M 1 و M 2 آراء أعضاء لجنة التحكيم. يمكن كتابة الوظيفة المنطقية التي تحدد اتخاذ قرار إيجابي على النحو التالي:
ف˄ (م 1˅ م 2) - دع المتغير المنطقي P i يأخذ القيمة 1 عندما تهبط العملة i على الرؤوس. يمكن كتابة الدالة المنطقية التي تحدد المردود X على النحو التالي:
¬((¬ص1˄ (¬ص2˅ ¬ص3˅ ¬ص4))˅
(¬ص2˄ (¬ص3˅ ¬ص4))˅
(¬ص3˄¬ص4)) - الجملة ب.
- للمعادلة 3 حلول: (أ = 1؛ ب = 1؛ ج = 0)؛ (أ = 0؛ ب = 0؛ ج = 0)؛ (أ = 0؛ ب = 1؛ ج = 0)
وفي نهاية العام، تبين أن افتراضًا واحدًا فقط من الافتراضات الثلاثة كان صحيحًا. ما هي الأقسام التي حققت ربحا في نهاية العام؟
حل. دعونا نكتب الافتراضات من شروط المشكلة في شكل عبارات منطقية: "إن الحصول على الربح عن طريق القسم ب ليس شرطًا ضروريًا للحصول على
الربح حسب القسمة A ":F 1 (A، B، C) = A → B
"الحصول على ربح من قسم واحد على الأقل B وC لا يكفي لكي يحقق القسم A ربحًا": F 2 (A, B, C) = (B + C) → A
"القسمان A وB لن يحققا ربحًا في نفس الوقت": F 3 (A، B، C) = A B
ومن الشرط يعلم أن واحدة فقط من الفرضيات الثلاثة صحيحة. وهذا يعني أنه يجب علينا العثور على أي من التعبيرات المنطقية الثلاثة التالية ليس خطأً متطابقًا:
1) ف 1 ف 2 ف 3
2) ف 1 ف 2 ف 3
3) ف 1 ف 2 ف 3
1) (أ→ ب) ((ب+ ج) → أ) (أ↔ ب) = أ ب(ب ج+ أ) (أ ب+ أ ب) = 0
2) (أ→ ب) ((ب+ ج) → أ) (أ↔ ب) = (أ+ ب) (أ ب+ أ ج) (أ ب+ أ ب) = أ ب ج
3) (أ→ ب) ((ب+ ج) → أ) (أ ب) = (أ+ ب) (ب ج+ أ) (أ ب+ أ ب) = 0
وبالتالي، في نهاية العام، تبين صحة الفرضية الثانية، وكذب الفرضية الأولى والثالثة.
أ = 0 |
|||||||||
F1 F2 F3 = أ ب ج = 1 |
|||||||||
إذا وفقط إذا كانت B = 0. |
|||||||||
ج = 1 |
|||||||||
لذلك، سيحصل القسم C على ربح، لكن القسمين A وB لن يحصلا على ربح.
حل المعادلات المنطقية
في نصوص الاختبار المركزي للدولة هناك مهمة (A8)، والتي تطلب العثور على جذر المعادلة المنطقية. دعونا نلقي نظرة على طرق حل مثل هذه المهام باستخدام مثال.
أوجد جذر المعادلة المنطقية: (A + B)(X AB) = B + X → A.
الحل الأول هو بناء جدول الحقيقة. دعونا نبني جداول الحقيقة للجانبين الأيمن والأيسر من المعادلة ونرى عند أي قيمة X تتطابق القيم الموجودة في الأعمدة الأخيرة من هذه الجداول.
F1 (أ، ب، X) = (أ+ ب)(X AB)
أ+ب | (أ+ب)(× أ ب) | ف 1 (أ،ب،X) |
|||||
F2 (أ، ب، X) = ب+ X→ أ
X → أ | ف 2 (أ،ب،X) |
|||||||||
X → أ | X → أ |
|||||||||
دعونا نقارن جداول الحقيقة الناتجة ونختار تلك الصفوف التي تتطابق فيها قيم F 1 (A، B، X) و F 2 (A، B، X).
ف 1 (أ،ب،X) | ف 2 (أ،ب،X) |
|||
دعونا نعيد كتابة الصفوف المحددة فقط، مع ترك أعمدة الوسيطات فقط. دعونا ننظر إلى المتغير X كدالة لـ A وB.
من الواضح أن X = B → A.
الحل الثاني هو استبدال علامة المساواة في المعادلة بعلامة مكافئة، ومن ثم تبسيط المعادلة المنطقية الناتجة.
لتسهيل المزيد من العمل، دعونا أولا نبسط الجانبين الأيمن والأيسر من المعادلة المنطقية ونجد سالبيهما:
F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B
F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B
F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A
لنستبدل علامة المساواة في معادلتنا المنطقية بعلامة التكافؤ:
F1 ↔ F2 = F1 F2 + F1 F2 = (أ ب+ X أ ب+ X أ+ X ب) (X ب+ أ ب) +
+ (X أ ب+ X أ ب+ X أ ب) (ب+ X أ) =
= (X أ ب+ X ب+ X أ ب) + (X أ ب+ X أ ب) =
دعونا نعيد ترتيب المصطلحات المنطقية لهذا التعبير، مع إخراج العوامل X و X من الأقواس.
X(أ ب) + X(ب+ AB) = X(أ ب) + X(ب+ أ) =
دعونا نشير إلى T = A B إذن
X T+ X T= X↔ T.
لذلك، لكي يكون للمعادلة المنطقية حل: X = A B = B + A = B → A.
عناصر المنطق الحاسوبي بناء المخططات الوظيفية
مع تطور تكنولوجيا الكمبيوتر، أصبح المنطق الرياضي وثيق الصلة بقضايا تصميم وبرمجة تكنولوجيا الكمبيوتر. وجد الجبر المنطقي تطبيقًا واسعًا في البداية في التطوير تتابع الاتصالالمخططات أول بحث أساسي لفت انتباه المهندسين العاملين في مجال تصميم الكمبيوتر إلى إمكانية تحليل الدوائر الكهربائية باستخدام الجبر البوليني، نُشر في ديسمبر 1938 من قبل الأمريكي كلود شانون بعنوان “التحليل الرمزي لدوائر السلم”. بعد هذه المقالة، لم يكن من الممكن أن يتم تصميم الكمبيوتر دون استخدام الجبر البوليني.
عنصر المنطقهي دائرة تنفذ العمليات المنطقية للانفصال والاقتران والانعكاس. دعونا نفكر في تنفيذ العناصر المنطقية من خلال دوائر الاتصال والترحيل الكهربائية، المألوفة لك من دورة الفيزياء المدرسية.
الاتصال التسلسلي للاتصالات
الاتصال الموازي للاتصالات
لنقم بتجميع جدول اعتمادات حالة الدوائر على جميع الحالات المحتملة لجهات الاتصال. دعونا نقدم الملاحظات التالية: 1 – جهة الاتصال مغلقة، ويوجد تيار في الدائرة؛ 0 – الاتصال مفتوح ولا يوجد تيار في الدائرة .
حالة الدائرة | حالة الدائرة بالتوازي |
||
اتصال تسلسلي | اتصال |
||
كما ترون، فإن الدائرة ذات الاتصال التسلسلي تتوافق مع التشغيل المنطقي للاقتران، حيث أن التيار في الدائرة يظهر فقط عندما تكون جهات الاتصال A و B مغلقة في نفس الوقت. تتوافق الدائرة ذات الاتصال المتوازي مع التشغيل المنطقي للفصل، حيث لا يوجد تيار في الدائرة إلا في اللحظة التي يكون فيها كلا الاتصالين مفتوحين.
يتم تنفيذ العملية المنطقية للانعكاس من خلال دائرة الاتصال للمرحل الكهرومغناطيسي، والذي يتم دراسة مبدأه في دورة الفيزياء المدرسية. جهة الاتصال x تكون مفتوحة عندما تكون x مغلقة والعكس صحيح.
إن استخدام عناصر اتصال الترحيل لإنشاء دوائر منطقية لأجهزة الكمبيوتر لم يبرر نفسه بسبب الموثوقية المنخفضة والأبعاد الكبيرة والاستهلاك العالي للطاقة والأداء المنخفض. أدى ظهور الأجهزة الإلكترونية (الفراغ وأشباه الموصلات) إلى خلق إمكانية بناء عناصر منطقية بسرعات تصل إلى مليون مفتاح في الثانية وما فوق. تعمل العناصر المنطقية لأشباه الموصلات في وضع التبديل المماثل للمرحل الكهرومغناطيسي. يتم نقل النظرية الكاملة المقدمة لدوائر الاتصال إلى عناصر أشباه الموصلات. لا تتميز العناصر المنطقية في أشباه الموصلات بحالة جهات الاتصال، بل بوجود الإشارات عند الإدخال والإخراج.
دعونا نفكر في العناصر المنطقية التي تنفذ العمليات المنطقية الأساسية:
العاكس - ينفذ عملية النفي أو الانقلاب. ش | |||||||||||||
العاكس لديه مدخل واحد ومخرج واحد. تظهر إشارة الإخراج | |||||||||||||
عندما لا يكون هناك شيء عند الإدخال، والعكس بالعكس. | |||||||||||||
الملتحمة - | |||||||||||||
X1 X2 ... Xn | ينفذ عملية الاقتران. | عند الملتحمة |
|||||||||||
مخرج واحد ومدخلين على الأقل. تشغيل الإشارة |
|||||||||||||
يظهر في الإخراج إذا وفقط إذا |
|||||||||||||
تتم الإشارة إلى كافة المدخلات. | |||||||||||||
X2 + ... Xn |
|||||||||||||
Disjunctor - ينفذ عملية الانفصال. ش | |||||||||||||
يحتوي المفكك على مخرج واحد واثنين على الأقل | |||||||||||||
لا تظهر إشارة الخرج إذا وفقط إذا | |||||||||||||
عندما لا يتم توفير إشارات لجميع المدخلات. | |||||||||||||
يبني | وظيفي |
||
F(X، Y، Z) = X(Y+ Z) | |||
X+Z |
|||
الرسم البياني المقابل للوظيفة:
&F(X، Y، Z)
حل المشاكل باستخدام العادية الملتحمة
و انفصالي عادينماذج
في غالبًا ما تحتوي كتب المشكلات المنطقية على مشكلات قياسية حيث تحتاج إلى كتابة دالة يمكن تنفيذهامخطط السلم، قم بتبسيطه وإنشاء جدول الحقيقة لهذه الوظيفة. كيفية حل المشكلة العكسية؟ بالنظر إلى جدول الحقيقة التعسفي، تحتاج إلى إنشاء مخطط وظيفي أو تتابعي. سنتعامل مع هذه القضية اليوم.
يمكن تمثيل أي دالة جبرية منطقية من خلال مجموعة من ثلاث عمليات: الاقتران والانفصال والانعكاس. دعونا معرفة كيف يتم ذلك. للقيام بذلك، دعونا نكتب بعض التعريفات.
Minterm هي دالة تتكون من اقتران عدد معين من المتغيرات أو نفيها. يأخذ Minterm القيمة 1 للمجموعة الوحيدة من جميع المجموعات الممكنة
الوسائط، والقيمة هي 0 لجميع الآخرين. مثال: × 1 × 2 × 3 × 4 .
الحد الأقصى هو دالة تتكون من انفصال عدد معين من المتغيرات أو نفيها. يأخذ Maxterm القيمة 0 في إحدى المجموعات الممكنة، و1 في جميع المجموعات الأخرى.
مثال: س 1 + س 2 + س 3.
وظيفة في الشكل العادي المنفصل(DNF) هو المجموع المنطقي للمينتريم.
مثال: × 1x 2+ × 1x 2+ × 1x 2x 3.
الشكل العادي المقترن(CNF) هو منتج منطقي للانفصالات الأولية (maxterms).
مثال: (x 1+ x 2+ x 3) (x 1+ x 2) .
الشكل الطبيعي المنفصل المثالي يسمى DNF، في كل دقيقة توجد جميع المتغيرات أو سلبياتها.
مثال: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3
الشكل الطبيعي المقترن المثالي يسمى CNF، في كل الحد الأقصى الذي توجد فيه جميع المتغيرات أو سلبياتها.
مثال: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)
كتابة دالة منطقية من جدول
يمكن التعبير عن أي وظيفة منطقية كـ SDNF أو SCNF. على سبيل المثال، النظر في الدالة f المعروضة في الجدول.
و(x1، x2، x3) | ||||||||
الوظائف G0، G1، G4، G5، G7 هي وظائف minterms (انظر التعريف). كل من هذه الوظائف هي نتاج ثلاثة متغيرات أو معكوساتها وتأخذ القيمة 1 في حالة واحدة فقط. يمكن أن نرى أنه من أجل الحصول على 1 في قيمة الدالة f، هناك حاجة إلى minterm واحد. وبالتالي، فإن عدد minterms التي تشكل SDNF لهذه الوظيفة يساوي عدد الوحدات في قيمة الدالة: f= G0+G1+G4+G5+G7. وبالتالي، فإن SDNF له الشكل:
و (x 1، x 2، x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.
وبالمثل، يمكنك بناء SKNF. عدد العوامل يساوي عدد الأصفار في قيم الدالة:
و (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .
وبالتالي، فإن أي دالة منطقية معطاة في شكل جدول يمكن كتابتها كصيغة.
خوارزمية لبناء SDNF باستخدام جدول الحقيقة
يتم إعطاء جدول الحقيقة لبعض الوظائف. لإنشاء SDNF، يجب عليك تنفيذ التسلسل التالي من الخطوات:
1. حدد جميع صفوف الجدول التي تأخذ فيها الدالة القيمة 1.
2. لكل سطر من هذا القبيل، قم بتعيين اقتران لجميع الوسائط أو انقلاباتها (مينترم). في هذه الحالة، يتم تضمين الوسيطة التي تأخذ القيمة 0 في Minterm بالنفي، ويتم تضمين القيمة 1 بدون نفي.
3. أخيرًا، نقوم بتشكيل انفصال جميع النعناع الذي تم الحصول عليه. يجب أن يتطابق عدد minterms مع عدد وحدات الدالة المنطقية.
خوارزمية لبناء SCNF باستخدام جدول الحقيقة
يتم إعطاء جدول الحقيقة لبعض الوظائف. لإنشاء SKNF، تحتاج إلى تنفيذ التسلسل التالي من الخطوات:
1. حدد كافة صفوف الجدول الذي تأخذ فيه الدالة القيمة 0.
2. لكل سطر من هذا القبيل، قم بتعيين انفصال لجميع الوسائط أو انقلاباتها (maxterm). في هذه الحالة، يتم تضمين وسيطة تأخذ القيمة 1 في الحد الأقصى مع النفي، ويتم تضمين القيمة 1 دون النفي.
3. أخيرًا، نقوم بتكوين رابط لجميع المصطلحات القصوى التي تم الحصول عليها. يجب أن يتطابق عدد الحدود القصوى مع عدد أصفار الدالة المنطقية.
إذا اتفقنا من النموذجين (SDNF أو SKNF) على إعطاء الأفضلية للذي يحتوي على عدد أقل من الحروف، فإن SDNF هو الأفضل إذا كان هناك عدد أقل من بين قيم دالة جدول الحقيقة، SKNF - إذا كان هناك عدد أقل من الأصفار.
مثال. يتم إعطاء جدول الحقيقة للدالة المنطقية لثلاثة متغيرات. قم ببناء صيغة منطقية تنفذ هذه الوظيفة.
و(أ، ب، ج) |
|||
دعونا نحدد تلك الصفوف في جدول الحقيقة هذا الذي تكون قيمة الدالة فيه 0.
و(أ، ب، ج) = (أ+ ب+ ج) (أ+ ب+ ج)
دعونا نتحقق من الوظيفة المشتقة عن طريق إنشاء جدول الحقيقة.
من خلال مقارنة جداول الحقيقة الأولية والنهائية، يمكننا أن نستنتج أن الدالة المنطقية مبنية بشكل صحيح.
حل المشاكل
1. ثلاثة معلمين يختارون مشاكل للأولمبياد. هناك العديد من المهام للاختيار من بينها. في كل مهمة يعبر كل معلم عن رأيه: مهمة سهلة (0) أو صعبة (1). يتم تضمين المهمة في مهمة الأولمبياد إذا حددها مدرسان على الأقل على أنها صعبة، ولكن إذا اعتبرها المعلمون الثلاثة جميعًا صعبة، فلن يتم تضمين هذه المهمة في مهمة الأولمبياد على أنها صعبة للغاية. أنشئ مخططًا منطقيًا لجهاز سيخرج 1 إذا كانت المهمة مضمنة في مهمة الأولمبياد، و0 إذا لم تكن متضمنة.
دعونا نبني جدول الحقيقة للوظيفة المطلوبة. لدينا ثلاثة متغيرات الإدخال (ثلاثة معلمين). وبالتالي فإن الدالة المطلوبة ستكون دالة لثلاثة متغيرات.
وبتحليل حالة المشكلة نحصل على جدول الحقيقة التالي:
نحن نبني SDNF. F(أ، ب، ج) = ABC+ ABC+ ABC
الآن نقوم ببناء مخطط منطقي لهذه الوظيفة.
ب&1و(أ،ب،ج)
2. أولمبياد المدينة في الدورة الأساسية لعلوم الحاسوب 2007.أنشئ مخططًا لدائرة كهربائية لمدخل منزل مكون من ثلاثة طوابق بحيث يمكن لمفتاح في أي طابق تشغيل أو إطفاء الأضواء في المنزل بأكمله.
إذن، لدينا ثلاثة مفاتيح يجب علينا استخدامها لتشغيل الضوء وإطفائه. يحتوي كل مفتاح على حالتين: أعلى (0) وأسفل (1). لنفترض أنه إذا كانت المفاتيح الثلاثة جميعها في الموضع 0، فسيتم إطفاء الأضواء الموجودة في المدخل. بعد ذلك، عند تحريك أي من المفاتيح الثلاثة إلى الموضع 1، يجب أن يضيء الضوء الموجود في المدخل. من الواضح أنه عند تحريك أي مفتاح آخر إلى الموضع 1، سينطفئ الضوء الموجود في المدخل. إذا تم تحويل المفتاح الثالث إلى الوضع 1، فسيتم تشغيل الضوء الموجود في المدخل. نحن نبني جدول الحقيقة.
إذن F(أ، ب، ج) = ABC+ ABC+ ABC+ ABC.
3. تغيير الحالة | قيم الوظائف المنطقية | F(أ، ب، ج) = ج→ | أ+ب | ||||||||
تغيير الوسيطتين B وC في نفس الوقت يساوي: | |||||||||||
أ → (ب ج) | (ب ج) → أ |
||||||||||
أ(ب ج) |
|||||||||||
4) (ب ج) → أ | أ → (ب ج) | ||||||||||
ملحوظة. لحل هذه المشكلة بنجاح، تذكر الصيغ المنطقية التالية:
x → y= x+ y x y= x y+ x y
س ↔ ص= س ص+ س ص
لقد حصلنا على دالة منطقية مكونة من ثلاثة متغيرات F 1 (A, B, C) = C → A + B = C + A B.
لنغير المتغيرين B وC في وقت واحد: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. دعونا نبني جداول الحقيقة لهاتين الوظيفتين:
دعونا نحلل الجدول الناتج. من بين صفوف الجدول الثمانية، فقط في صفين (الثاني والثالث) لا تغير الوظيفة قيمتها. لاحظ أنه في هذه السطور، المتغير A لا يعكس قيمته، لكن المتغيرين B وC يفعلان ذلك.
نقوم ببناء وظائف SKNF باستخدام هذه السطور:
F3 (أ، ب، ج) = (أ+ ب+ ج) (أ+ ب ج) = أ+ AB+ AC+ AB+ BC+ AC+ B C= .
أ+ (ب↔ ج) = أ+ ب ج= (ب ج) → أ
وبالتالي فإن الإجابة المطلوبة هي 4.
4. شرط تغيير قيمة الدالة المنطقية F (A، B، C) = C + AB مع تغيير الوسيطتين A و B في نفس الوقت يساوي:
1) ج+ (أ ب) | ||||||||||||||||||||||||||||||||||
ج+(أ ب) | سيارة أجرة) |
|||||||||||||||||||||||||||||||||
4) ج(أ ب) | ||||||||||||||||||||||||||||||||||
ج → (أ ب) | ||||||||||||||||||||||||||||||||||
ف 1 (أ،ب،ج)= | ||||||||||||||||||||||||||||||||||
ج + أب | ||||||||||||||||||||||||||||||||||
ف 2 ( أ , ب , ج )= ف 1 ( | ج)= أ | |||||||||||||||||||||||||||||||||
نحن نبني جدول الحقيقة. | ||||||||||||||||||||||||||||||||||
دعونا نحلل الجدول الناتج. من بين صفوف الجدول الثمانية، فقط في صفين (الأول والسابع) تغير الدالة قيمتها. يرجى ملاحظة أنه في هذه السطور، لا يغير المتغير C قيمته، ولكن المتغيرين A وB يفعلان ذلك.
نقوم ببناء وظائف SDNF باستخدام هذه السطور:
F3 (أ، ب، ج) = أ ب ج + أ ب ج = ج (أ ب + أ ب) = ج (أ ↔ ب) = ج + (أ ب)
ولذلك فإن الإجابة المطلوبة هي 2.
مراجع
1. شابيرو إس. حل المشاكل المنطقية والألعاب(دراسات منطقية ونفسية). – م: الإذاعة والاتصالات، 1984. – 152 ص.
2. شولوموف إل. أساسيات نظرية الأجهزة المنطقية والحاسوبية المنفصلة. - م: العلم. الفصل. إد. بدني - حصيرة. مضاءة، 1980. - 400 ص.
3. Pukhalsky G.I.، Novoseltseva T.Ya. تصميم الأجهزة المنفصلة على الدوائر المتكاملة: كتيب. - م: الإذاعة والاتصالات، 1990.
تحتوي هذه المادة على عرض تقديمي يقدم طرق حل المعادلات المنطقية وأنظمة المعادلات المنطقية في المهمة 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 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، [المصدر الإلكتروني].
موضوع الدرس: حل المعادلات المنطقية
تعليمية – دراسة طرق حل المعادلات المنطقية، وتطوير المهارات في حل المعادلات المنطقية وبناء تعبير منطقي باستخدام جدول الحقيقة؛التنموية - تهيئة الظروف لتنمية الاهتمام المعرفي لدى الطلاب، وتعزيز تنمية الذاكرة والانتباه والتفكير المنطقي؛
التعليمية : تعزيز القدرة على الاستماع لآراء الآخرين،تعزيز الإرادة والمثابرة لتحقيق النتائج النهائية.
نوع الدرس: درس مشترك
معدات: الكمبيوتر، جهاز عرض الوسائط المتعددة، العرض 6.
خلال الفصول الدراسية
تكرار وتحديث المعرفة الأساسية. التحقق من الواجبات المنزلية (10 دقائق)
تعرفنا في الدروس السابقة على القوانين الأساسية للجبر المنطقي وتعلمنا كيفية استخدام هذه القوانين لتبسيط التعبيرات المنطقية.
دعونا نتحقق من واجبنا المنزلي حول تبسيط التعبيرات المنطقية:
1. أي الكلمات التالية تحقق الشرط المنطقي:
(الحرف الأول ساكن → الحرف الثاني ساكن)٨ (حرف العلة الأخير → حرف العلة قبل الأخير)؟ إذا كان هناك العديد من هذه الكلمات، فحدد أصغرها.
1) آنا 2) ماريا 3) أوليغ 4) ستيبان
دعونا نقدم التدوين التالي:
أ- الحرف الأول الساكن
ب – الحرف الثاني الساكن
س - حرف العلة الأخير
د – حرف العلة قبل الأخير
دعونا نجعل التعبير:
لنقم بعمل جدول:
2. حدد التعبير المنطقي الذي يعادل التعبير
دعونا نبسط تسجيل التعبير الأصلي والخيارات المقترحة:
3. بالنظر إلى جزء من جدول الحقيقة للتعبير F:
ما التعبير الذي يطابق F؟
دعونا نحدد قيم هذه التعبيرات لقيم الوسائط المحددة:
مقدمة لموضوع الدرس وعرض مادة جديدة (30 دقيقة)
نواصل دراسة أساسيات المنطق وموضوع درسنا اليوم هو "حل المعادلات المنطقية". بعد دراسة هذا الموضوع ستتعلم الطرق الأساسية لحل المعادلات المنطقية، وتكتسب مهارات حل هذه المعادلات باستخدام لغة الجبر المنطقي والقدرة على تكوين تعبير منطقي باستخدام جدول الحقيقة.
1. حل معادلة منطقية
(¬ك م) → (¬L م ن) =0
اكتب إجابتك كسلسلة من أربعة أحرف: قيم المتغيرات K وL وM وN (بهذا الترتيب). لذلك، على سبيل المثال، السطر 1101 يتوافق مع حقيقة أن K=1، L=1، M=0، N=1.
حل:
دعونا تحويل التعبير(¬ك م) → (¬L م ن)
يكون التعبير خاطئًا عندما يكون كلا المصطلحين خاطئين. الحد الثاني يساوي 0 إذا كان M = 0، N = 0، L = 1. في الفصل الأول K = 0، حيث أن M = 0، و 
.
الجواب: 0100
2. كم عدد الحلول التي تحتوي عليها المعادلة (أشر فقط إلى الرقم في إجابتك)؟
الحل: تحويل التعبير
(أ +ب)*(ج +د)=1
أ + ب = 1 و ج + د = 1
الطريقة الثانية: رسم جدول الحقيقة
3 طريقة: بناء SDNF - الشكل الطبيعي المنفصل المثالي لوظيفة - انفصال عن أدوات الاقتران الأولية المنتظمة الكاملة.دعونا نحول التعبير الأصلي، ونفتح الأقواس للحصول على انفصال أدوات العطف:
(أ+ب)*(ج+د)=أ*ج+ب*ج+أ*د+ب*د=
دعونا نكمل أدوات العطف لإكمال أدوات العطف (منتج جميع الوسائط)، افتح الأقواس:
لنأخذ بعين الاعتبار نفس الاقترانات:
ونتيجة لذلك، حصلنا على SDNF يحتوي على 9 اقترانات. ولذلك، فإن جدول الحقيقة لهذه الوظيفة له القيمة 1 في 9 صفوف من 2 4 = 16 مجموعة من القيم المتغيرة.
3. كم عدد الحلول التي تحتوي عليها المعادلة (أشر فقط إلى الرقم في إجابتك)؟
دعونا نبسط التعبير:
,
3 طريقة: بناء SDNF
لنأخذ بعين الاعتبار نفس الاقترانات:
ونتيجة لذلك، نحصل على SDNF يحتوي على 5 اقترانات. ولذلك، فإن جدول الحقيقة لهذه الدالة له القيمة 1 على 5 صفوف من 2 4 = 16 مجموعة من القيم المتغيرة.
بناء تعبير منطقي باستخدام جدول الحقيقة:
لكل صف من جدول الحقيقة يحتوي على 1، نقوم بتكوين منتج من الوسائط، ويتم تضمين المتغيرات التي تساوي 0 في المنتج مع النفي، ويتم تضمين المتغيرات التي تساوي 1 بدون نفي. سيتكون التعبير المطلوب F من مجموع المنتجات الناتجة. ثم، إذا كان ذلك ممكنا، ينبغي تبسيط هذا التعبير.
مثال: يتم إعطاء جدول الحقيقة للتعبير. بناء تعبير منطقي.
حل:3. الواجب المنزلي (5 دقائق)
حل المعادلة:
كم عدد الحلول التي تحتوي عليها المعادلة (أشر فقط إلى الرقم في إجابتك)؟
باستخدام جدول الحقيقة المحدد، قم ببناء تعبير منطقي و
تبسيطها.