Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων. Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων

Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων

Μπορείτε να λύσετε ένα σύστημα λογικών εξισώσεων, για παράδειγμα, χρησιμοποιώντας έναν πίνακα αλήθειας (αν ο αριθμός των μεταβλητών δεν είναι πολύ μεγάλος) ή χρησιμοποιώντας ένα δέντρο αποφάσεων, έχοντας πρώτα απλοποιήσει κάθε εξίσωση.

1. Μέθοδος αντικατάστασης μεταβλητής.

Η εισαγωγή νέων μεταβλητών σάς επιτρέπει να απλοποιήσετε το σύστημα εξισώσεων, μειώνοντας τον αριθμό των αγνώστων.Οι νέες μεταβλητές πρέπει να είναι ανεξάρτητες η μία από την άλλη. Αφού λύσουμε το απλοποιημένο σύστημα, πρέπει να επιστρέψουμε στις αρχικές μεταβλητές.

Ας εξετάσουμε την εφαρμογή αυτής της μεθόδου χρησιμοποιώντας ένα συγκεκριμένο παράδειγμα.

Παράδειγμα.

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

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

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

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

Λύση:

Ας εισάγουμε νέες μεταβλητές: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); Ε=(Χ9 ≡ Χ10).

(Προσοχή! Κάθε μία από τις μεταβλητές x1, x2, ..., x10 πρέπει να περιλαμβάνεται μόνο σε μία από τις νέες μεταβλητές A, B, C, D, E, δηλαδή οι νέες μεταβλητές είναι ανεξάρτητες μεταξύ τους).

Τότε το σύστημα των εξισώσεων θα μοιάζει με αυτό:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

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

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Ας δημιουργήσουμε ένα δέντρο αποφάσεων για το σύστημα που προκύπτει:

Θεωρούμε την εξίσωση A=0, δηλ. (Χ1≡ X2)=0. Έχει 2 ρίζες:

		X1 ≡ X2

Από τον ίδιο πίνακα φαίνεται ότι η εξίσωση Α=1 έχει επίσης 2 ρίζες. Ας τακτοποιήσουμε τον αριθμό των ριζών στο δέντρο αποφάσεων:

Για να βρείτε τον αριθμό των λύσεων ενός κλάδου, πρέπει να πολλαπλασιάσετε τον αριθμό των λύσεων σε κάθε επίπεδο. Ο αριστερός κλάδος έχει 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 λύσεις; ο δεξιός κλάδος έχει επίσης 32 λύσεις. Εκείνοι. όλο το σύστημα έχει 32+32=64 λύσεις.

Απάντηση: 64.

2. Μέθοδος συλλογισμού.

Η δυσκολία επίλυσης συστημάτων λογικών εξισώσεων έγκειται στη δυσκινησία ενός πλήρους δέντρου αποφάσεων. Η συλλογιστική μέθοδος σας επιτρέπει να μην χτίσετε ολόκληρο το δέντρο, αλλά να καταλάβετε πόσα κλαδιά θα έχει. Ας δούμε αυτή τη μέθοδο χρησιμοποιώντας συγκεκριμένα παραδείγματα.

Παράδειγμα 1. Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;

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

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

x1\/y1 =1

Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 για τις οποίες ικανοποιείται αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.

Λύση :

Η πρώτη και η δεύτερη εξίσωση περιέχουν ανεξάρτητες μεταβλητές που σχετίζονται με την τρίτη συνθήκη. Ας φτιάξουμε ένα δέντρο λύσης για την πρώτη και τη δεύτερη εξίσωση.

Για να αναπαραστήσουμε ένα δέντρο λύσης για ένα σύστημα της πρώτης και της δεύτερης εξισώσεων, κάθε κλάδος του πρώτου δέντρου πρέπει να συνεχιστεί με ένα δέντρο για μεταβλητέςστο . Το δέντρο που κατασκευάζεται με αυτόν τον τρόπο θα περιέχει 36 κλαδιά. Ορισμένοι από αυτούς τους κλάδους δεν ικανοποιούν την τρίτη εξίσωση του συστήματος. Ας σημειώσουμε τον αριθμό των κλαδιών του δέντρου στο πρώτο δέντρο"υ" , που ικανοποιούν την τρίτη εξίσωση:

Ας εξηγήσουμε: για να ικανοποιηθεί η τρίτη συνθήκη, όταν x1=0 πρέπει να υπάρχουν y1=1, δηλαδή όλα τα κλαδιά του δέντρου"Χ" , όπου x1=0 μπορεί να συνεχιστεί με ένα μόνο κλαδί από το δέντρο"υ" . Και μόνο για ένα κλαδί του δέντρου"Χ" (δεξιά) όλα τα κλαδιά του δέντρου ταιριάζουν"υ". Έτσι, το πλήρες δέντρο ολόκληρου του συστήματος περιέχει 11 κλάδους. Κάθε κλάδος αντιπροσωπεύει μία λύση στο αρχικό σύστημα εξισώσεων. Αυτό σημαίνει ότι ολόκληρο το σύστημα έχει 11 λύσεις.

Απάντηση: 11.

Παράδειγμα 2. Πόσες διαφορετικές λύσεις έχει το σύστημα εξισώσεων;

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

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

………………

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

(X1 ≡ X10) = 0

όπου x1, x2, …, x10 είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα μεταβλητών τιμών για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.

Λύση : Ας απλοποιήσουμε το σύστημα. Ας φτιάξουμε έναν πίνακα αλήθειας για μέρος της πρώτης εξίσωσης:

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

Προσοχή στην τελευταία στήλη, ταιριάζει με το αποτέλεσμα της ενέργειας X1 ≡ X10.

X1 ≡ X10

Μετά την απλοποίηση παίρνουμε:

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

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

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

……

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

(X1 ≡ X10) = 0

Εξετάστε την τελευταία εξίσωση:(X1 ≡ X10) = 0, δηλ. Το x1 δεν πρέπει να συμπίπτει με το x10. Για να είναι η πρώτη εξίσωση ίση με 1, η ισότητα πρέπει να είναι αληθής(X1 ≡ X2)=1, δηλ. Το x1 πρέπει να ταιριάζει με το x2.

Ας φτιάξουμε ένα δέντρο λύσης για την πρώτη εξίσωση:

Θεωρούμε τη δεύτερη εξίσωση: για x10=1 και για x2=0 την αγκύληπρέπει να είναι ίσο με 1 (δηλαδή το x2 συμπίπτει με το x3). για x10=0 και για x2=1 παρένθεση(X2 ≡ X10)=0, που σημαίνει το στήριγμα (X2 ≡ X3) πρέπει να είναι ίσο με 1 (δηλαδή το x2 συμπίπτει με το x3):

Συλλογιζόμενοι με αυτόν τον τρόπο, χτίζουμε ένα δέντρο αποφάσεων για όλες τις εξισώσεις:

Έτσι, το σύστημα των εξισώσεων έχει μόνο 2 λύσεις.

Απάντηση: 2.

Παράδειγμα 3.

Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;

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

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

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

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

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

Λύση:

Ας φτιάξουμε ένα δέντρο λύσης για την 1η εξίσωση:

Θεωρήστε τη δεύτερη εξίσωση:

Όταν x1=0 : η δεύτερη και η τρίτη παρένθεση θα είναι ίσες με 0. για την πρώτη αγκύλη να είναι ίση με 1, y1=1, z1=1 (δηλαδή σε αυτήν την περίπτωση - 1 λύση)
Όταν x1=1 : η πρώτη αγκύλη θα είναι ίση με 0. δεύτεροςή η τρίτη παρένθεση πρέπει να είναι ίση με 1. η δεύτερη αγκύλη θα είναι ίση με 1 όταν y1=0 και z1=1. η τρίτη αγκύλη θα είναι ίση με 1 όταν y1=1 και z1=0 (δηλαδή σε αυτή την περίπτωση - 2 λύσεις).

Ομοίως για τις υπόλοιπες εξισώσεις. Ας σημειώσουμε τον αριθμό των λύσεων που προκύπτει για κάθε κόμβο δέντρου:

Για να μάθετε τον αριθμό των λύσεων για κάθε κλάδο, πολλαπλασιάστε τους αριθμούς που προκύπτουν χωριστά για κάθε κλάδο (από αριστερά προς τα δεξιά).

1 κλάδος: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 διάλυμα

Κλάδος 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 διαλύματα

3ος κλάδος: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 λύσεις

4ος κλάδος: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 λύσεις

5ος κλάδος: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 λύσεις

Ας αθροίσουμε τους αριθμούς που προκύπτουν: υπάρχουν 31 λύσεις συνολικά.

Απάντηση: 31.

3. Φυσική αύξηση του αριθμού των ριζών

Σε ορισμένα συστήματα, ο αριθμός των ριζών της επόμενης εξίσωσης εξαρτάται από τον αριθμό των ριζών της προηγούμενης εξίσωσης.

Παράδειγμα 1. Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;

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

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

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

Ας απλοποιήσουμε πρώτη εξίσωση:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Τότε το σύστημα θα πάρει τη μορφή:

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

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

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

Και τα λοιπά.

Κάθε επόμενη εξίσωση έχει 2 περισσότερες ρίζες από την προηγούμενη.

Η 4 εξίσωση έχει 12 ρίζες.

Η εξίσωση 5 έχει 14 ρίζες

Η εξίσωση 8 έχει 20 ρίζες.

Απάντηση: 20 ρίζες.

Μερικές φορές ο αριθμός των ριζών αυξάνεται σύμφωνα με τον νόμο Fibonacci.

Η επίλυση ενός συστήματος λογικών εξισώσεων απαιτεί δημιουργική προσέγγιση.

Αυτό το υλικό περιέχει μια παρουσίαση που παρουσιάζει μεθόδους επίλυσης λογικών εξισώσεων και συστημάτων λογικών εξισώσεων στην εργασία Β15 (Αρ. 23, 2015) της Ενιαίας Κρατικής Εξέτασης στην επιστήμη των υπολογιστών. Είναι γνωστό ότι αυτό το έργο είναι ένα από τα πιο δύσκολα μεταξύ των εργασιών της Ενιαίας Κρατικής Εξέτασης. Η παρουσίαση μπορεί να είναι χρήσιμη κατά τη διδασκαλία μαθημάτων σχετικά με το θέμα «Λογική» σε εξειδικευμένες τάξεις, καθώς και κατά την προετοιμασία για την Ενιαία Κρατική Εξέταση.

Κατεβάστε:

Προεπισκόπηση:

Για να χρησιμοποιήσετε προεπισκοπήσεις παρουσίασης, δημιουργήστε έναν λογαριασμό Google και συνδεθείτε σε αυτόν: https://accounts.google.com

Λεζάντες διαφάνειας:

Λύση της εργασίας Β15 (συστήματα λογικών εξισώσεων) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18 Νοεμβρίου 2013, Saratov

Η εργασία Β15 είναι από τις πιο δύσκολες στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών!!! Δοκιμάζονται οι ακόλουθες δεξιότητες: μετατροπή εκφράσεων που περιέχουν λογικές μεταβλητές. περιγράψτε σε φυσική γλώσσα το σύνολο των τιμών των λογικών μεταβλητών για τις οποίες ισχύει ένα δεδομένο σύνολο λογικών μεταβλητών· μετρήστε τον αριθμό των δυαδικών συνόλων που ικανοποιούν δεδομένες συνθήκες. Το πιο δύσκολο είναι γιατί... δεν υπάρχουν επίσημοι κανόνες για το πώς να το κάνετε αυτό, απαιτεί εικασίες.

Αυτό που δεν μπορείτε να κάνετε χωρίς!

Σύνδεσμος συμβόλων: 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 έχει 2 λύσεις, ο αριθμός των 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; y5→ x5 =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. Διαδοχική λύση εξισώσεων Τ.ο. Λήφθηκαν 6 σετ διαλυμάτων για x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Συλλογίζοντας παρόμοια, καταλήγουμε στο συμπέρασμα ότι για τα y1, y2, y3, y4, y5 υπάρχει το ίδιο σύνολο λύσεων. Επειδή αυτές οι εξισώσεις είναι ανεξάρτητες, δηλ. δεν έχουν κοινές μεταβλητές, τότε η λύση σε αυτό το σύστημα εξισώσεων (χωρίς να λαμβάνεται υπόψη η τρίτη εξίσωση) θα είναι 6 * 6 = 36 ζεύγη "X" και "Y". Θεωρήστε την τρίτη εξίσωση: 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 NB! Κάθε επόμενη μεταβλητή δεν εξαρτάται από την προηγούμενη, αλλά από το αποτέλεσμα της προηγούμενης συνεπαγωγής!

Βήμα 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 πήραμε 2 μονάδες και από 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. Παραγωγή του τύπου Τ.ο. μπορείτε να δημιουργήσετε τύπους για τον υπολογισμό του αριθμού των μηδενικών N i και του αριθμού των μονάδων E i για μια εξίσωση με μεταβλητές i:

Βήμα 4. Συμπλήρωση του πίνακα Ας συμπληρώσουμε τον πίνακα από αριστερά προς τα δεξιά για i = 6, υπολογίζοντας τον αριθμό των μηδενικών και των μονάδων χρησιμοποιώντας τους παραπάνω τύπους. ο πίνακας δείχνει πώς χτίζεται η επόμενη στήλη από την προηγούμενη: αριθμός μεταβλητών 1 2 3 4 5 6 Αριθμός μηδενικών N i 1 1 3 5 11 21 Αριθμός μονάδων E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Απάντηση: 43

Μέθοδος που χρησιμοποιεί απλοποιήσεις λογικών παραστάσεων Πόσες διαφορετικές λύσεις έχει η εξίσωση ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 όπου J, K, L, M, N είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των J, K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.

Λύση Σημειώστε ότι J → K = ¬ J  K Ας εισάγουμε μια αλλαγή μεταβλητών: J → K=A, M  N  L =B Ας ξαναγράψουμε την εξίσωση λαμβάνοντας υπόψη την αλλαγή: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Προφανώς, A  B για τις ίδιες τιμές των A και B 6. Θεωρήστε την τελευταία συνέπεια M → J =1 Αυτό είναι δυνατό εάν: M= J=0 M=0, J=1 M=J=1

Λύση Διότι A  B, τότε όταν M=J=0 παίρνουμε 1 + K=0. Δεν υπάρχουν λύσεις. Όταν M=0, J=1 παίρνουμε 0 + K=0, K=0, και N και L είναι οποιαδήποτε, 4 λύσεις: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Λύση 10. Όταν M=J=1 παίρνουμε 0+K=1 *N * L, ή K=N*L, 4 λύσεις: 11. Το σύνολο έχει 4+4=8 λύσεις Απάντηση: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Πηγές πληροφοριών: Ο.Β. Bogomolova, D.Yu. Ουσένκοφ. B15: νέες εργασίες και νέες λύσεις // Πληροφορική, Αρ. 6, 2012, σελ. 35 – 39. K.Yu. Πολιάκοφ. Λογικές εξισώσεις // Πληροφορική, Αρ. 14, 2011, σελ. 30-35. http://ege-go.ru/zadania/grb/b15/, [Ηλεκτρονικός πόρος]. http://kpolyakov.narod.ru/school/ege.htm, [Ηλεκτρονικός πόρος].

Σκοπός της υπηρεσίας. Η ηλεκτρονική αριθμομηχανή έχει σχεδιαστεί για κατασκευάζοντας έναν πίνακα αλήθειας για μια λογική έκφραση.
Πίνακας αλήθειας – ένας πίνακας που περιέχει όλους τους πιθανούς συνδυασμούς μεταβλητών εισόδου και τις αντίστοιχες τιμές εξόδου τους.
Ο πίνακας αλήθειας περιέχει 2n σειρές, όπου n είναι ο αριθμός των μεταβλητών εισόδου και n+m είναι στήλες, όπου m είναι μεταβλητές εξόδου.

Οδηγίες. Κατά την είσοδο από το πληκτρολόγιο, χρησιμοποιήστε τις ακόλουθες συμβάσεις:

Για παράδειγμα, η λογική έκφραση abc+ab~c+a~bc πρέπει να εισαχθεί ως εξής: a*b*c+a*b=c+a=b*c
Για να εισαγάγετε δεδομένα με τη μορφή λογικού διαγράμματος, χρησιμοποιήστε αυτήν την υπηρεσία.

Κανόνες εισαγωγής λογικής συνάρτησης

Αντί για το σύμβολο v (διάσπαση, OR), χρησιμοποιήστε το σύμβολο +.
Δεν χρειάζεται να προσδιορίσετε έναν προσδιορισμό συνάρτησης πριν από μια λογική συνάρτηση. Για παράδειγμα, αντί για F(x,y)=(x|y)=(x^y) πρέπει απλώς να εισαγάγετε (x|y)=(x^y) .
Ο μέγιστος αριθμός μεταβλητών είναι 10.

Ο σχεδιασμός και η ανάλυση των λογικών κυκλωμάτων υπολογιστών πραγματοποιείται χρησιμοποιώντας έναν ειδικό κλάδο των μαθηματικών - λογική άλγεβρα. Στην άλγεβρα της λογικής διακρίνονται τρεις κύριες λογικές συναρτήσεις: «ΟΧΙ» (άρνηση), «ΚΑΙ» (σύνδεση), «OR» (διάσπαση).
Για τη δημιουργία οποιασδήποτε λογικής συσκευής, είναι απαραίτητο να προσδιοριστεί η εξάρτηση καθεμιάς από τις μεταβλητές εξόδου από τις υπάρχουσες μεταβλητές εισόδου· αυτή η εξάρτηση ονομάζεται συνάρτηση μεταγωγής ή συνάρτηση λογικής άλγεβρας.
Μια συνάρτηση λογικής άλγεβρας ονομάζεται πλήρως καθορισμένη εάν δίνονται και τα 2n από τις τιμές της, όπου n είναι ο αριθμός των μεταβλητών εξόδου.
Εάν δεν έχουν καθοριστεί όλες οι τιμές, η συνάρτηση ονομάζεται μερικώς καθορισμένη.
Μια συσκευή ονομάζεται λογική εάν η κατάστασή της περιγράφεται χρησιμοποιώντας μια συνάρτηση λογικής άλγεβρας.
Οι ακόλουθες μέθοδοι χρησιμοποιούνται για την αναπαράσταση μιας συνάρτησης λογικής άλγεβρας:
Σε αλγεβρική μορφή, μπορείτε να δημιουργήσετε ένα κύκλωμα μιας λογικής συσκευής χρησιμοποιώντας λογικά στοιχεία.

Εικόνα 1 - Διάγραμμα λογικής συσκευής

Όλες οι πράξεις της άλγεβρας της λογικής ορίζονται πίνακες αλήθειαςαξίες. Ο πίνακας αλήθειας καθορίζει το αποτέλεσμα μιας πράξης για όλοι είναι δυνατοί x λογικές τιμές των αρχικών δηλώσεων. Ο αριθμός των επιλογών που αντικατοπτρίζουν το αποτέλεσμα της εφαρμογής πράξεων θα εξαρτηθεί από τον αριθμό των δηλώσεων στη λογική έκφραση. Εάν ο αριθμός των δηλώσεων σε μια λογική παράσταση είναι N, τότε ο πίνακας αλήθειας θα περιέχει 2 N σειρές, αφού υπάρχουν 2 N διαφορετικοί συνδυασμοί πιθανών τιμών ορίσματος.

Λειτουργία NOT - λογική άρνηση (αναστροφή)

Μια λογική πράξη ΔΕΝ εφαρμόζεται σε ένα μεμονωμένο όρισμα, το οποίο μπορεί να είναι μια απλή ή σύνθετη λογική έκφραση. Το αποτέλεσμα της επέμβασης ΔΕΝ είναι το εξής:

Εάν η αρχική έκφραση είναι αληθής, τότε το αποτέλεσμα της άρνησής της θα είναι ψευδές.
αν η αρχική έκφραση είναι ψευδής, τότε το αποτέλεσμα της άρνησής της θα είναι αληθές.

Οι ακόλουθες συμβάσεις ΔΕΝ γίνονται δεκτές για τη λειτουργία άρνησης:
όχι A, Ā, όχι A, ¬A, !A
Το αποτέλεσμα της πράξης άρνησης ΔΕΝ προσδιορίζεται από τον ακόλουθο πίνακα αληθείας:

ΕΝΑ	δεν είναι
0	1
1	0

Το αποτέλεσμα της πράξης άρνησης είναι αληθές όταν η αρχική πρόταση είναι ψευδής και το αντίστροφο.

Λειτουργία Ή - λογική προσθήκη (διάσπαση, ένωση)

Η λειτουργία λογικής OR εκτελεί τη λειτουργία του συνδυασμού δύο δηλώσεων, οι οποίες μπορεί να είναι είτε απλή είτε σύνθετη λογική έκφραση. Οι δηλώσεις που είναι τα σημεία εκκίνησης για μια λογική πράξη ονομάζονται ορίσματα. Το αποτέλεσμα της λειτουργίας OR είναι μια έκφραση που θα είναι αληθής εάν και μόνο εάν τουλάχιστον μία από τις αρχικές εκφράσεις είναι αληθής.
Χρησιμοποιούνται ονομασίες: A ή B, A V B, A ή B, A||B.
Το αποτέλεσμα της πράξης OR προσδιορίζεται από τον ακόλουθο πίνακα αληθείας:
Το αποτέλεσμα της πράξης OR είναι αληθές όταν το Α είναι αληθές, ή το Β είναι αληθές, ή και το Α και το Β είναι αληθές και ψευδές όταν τα ορίσματα Α και Β είναι ψευδή.

Πράξη ΚΑΙ - λογικός πολλαπλασιασμός (σύνδεση)

Η λογική πράξη ΚΑΙ εκτελεί τη συνάρτηση τομής δύο προτάσεων (επιχειρήματα), που μπορεί να είναι είτε απλή είτε σύνθετη λογική έκφραση. Το αποτέλεσμα της λειτουργίας AND είναι μια έκφραση που θα είναι αληθής εάν και μόνο εάν και οι δύο αρχικές εκφράσεις είναι αληθείς.
Χρησιμοποιούνται ονομασίες: Α και Β, Α Λ Β, Α & Β, Α και Β.
Το αποτέλεσμα της πράξης AND καθορίζεται από τον ακόλουθο πίνακα αληθείας:

ΕΝΑ	σι	Α και Β
0	0	0
0	1	0
1	0	0
1	1	1

Το αποτέλεσμα της πράξης AND είναι αληθές αν και μόνο αν οι προτάσεις Α και Β είναι και αληθείς και ψευδείς σε όλες τις άλλες περιπτώσεις.

Λειτουργία «ΑΝ-ΤΟΤΕ» - λογική συνέπεια (υπόνοια)

Αυτή η λειτουργία συνδέει δύο απλές λογικές εκφράσεις, εκ των οποίων η πρώτη είναι συνθήκη και η δεύτερη είναι συνέπεια αυτής της συνθήκης.
Ονομασίες που χρησιμοποιούνται:
αν Α, τότε Β. Το Α συνεπάγεται το Β. αν Α τότε Β; Α→Β.
Πίνακας αλήθειας:

ΕΝΑ	σι	Α → Β
0	0	1
0	1	1
1	0	0
1	1	1

Το αποτέλεσμα της πράξης υπαινιγμού είναι ψευδές μόνο εάν η υπόθεση Α είναι αληθής και το συμπέρασμα Β (συνέπεια) είναι ψευδές.

Λειτουργία «Α εάν και μόνο εάν Β» (ισοδυναμία, ισοδυναμία)

Ονομασία που χρησιμοποιείται: A ↔ B, A ~ B.
Πίνακας αλήθειας:

ΕΝΑ	σι	Α↔Β
0	0	1
0	1	0
1	0	0
1	1	1

Λειτουργία "Addition modulo 2" (XOR, αποκλειστική ή αυστηρή διάσπαση)

Χρησιμοποιημένος συμβολισμός: A XOR B, A ⊕ B.
Πίνακας αλήθειας:

ΕΝΑ	σι	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Το αποτέλεσμα της πράξης ισοδυναμίας είναι αληθές μόνο εάν το Α και το Β είναι ταυτόχρονα αληθές ή ψευδές.

Προτεραιότητα λογικών πράξεων

Ενέργειες σε παρένθεση
Αναστροφή
Σύνδεσμος (&)
Disjunction (V), Exclusive OR (XOR), sum modulo 2
Υπονοούμενα (→)
Ισοδυναμία (↔)

Τέλεια διαχωριστική κανονική μορφή

Τέλεια διαχωριστική κανονική μορφή φόρμουλαςΤο (SDNF) είναι ένας ισοδύναμος τύπος, ο οποίος είναι ένας διαχωρισμός στοιχειωδών συνδέσμων και έχει τις ακόλουθες ιδιότητες:

Κάθε λογικός όρος του τύπου περιέχει όλες τις μεταβλητές που περιλαμβάνονται στη συνάρτηση F(x 1,x 2,...x n).
Όλοι οι λογικοί όροι του τύπου είναι διαφορετικοί.
Κανένας λογικός όρος δεν περιέχει μια μεταβλητή και την άρνησή της.
Κανένας λογικός όρος σε έναν τύπο δεν περιέχει την ίδια μεταβλητή δύο φορές.

Το SDNF μπορεί να ληφθεί είτε χρησιμοποιώντας πίνακες αλήθειας είτε χρησιμοποιώντας ισοδύναμους μετασχηματισμούς.
Για κάθε συνάρτηση, τα SDNF και SCNF ορίζονται μοναδικά μέχρι τη μετάθεση.

Τέλεια συνδετική κανονική μορφή

Τέλεια συνδετική κανονική μορφή τύπου (SCNF)Αυτός είναι ένας τύπος ισοδύναμος με αυτόν, ο οποίος είναι ένας συνδυασμός στοιχειωδών διαχωρισμών και ικανοποιεί τις ιδιότητες:

Όλοι οι στοιχειώδεις διαχωρισμοί περιέχουν όλες τις μεταβλητές που περιλαμβάνονται στη συνάρτηση F(x 1 ,x 2 ,...x n).
Όλοι οι στοιχειώδεις διαχωρισμοί είναι διαφορετικοί.
Κάθε στοιχειώδης διαχωρισμός περιέχει μια μεταβλητή μία φορά.
Κανένας στοιχειώδης διαχωρισμός δεν περιέχει μια μεταβλητή και την άρνησή της.

Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων

Kirgizova E.V., Nemkova A.E.

Παιδαγωγικό Ινστιτούτο Lesosibirsk -

παράρτημα του Ομοσπονδιακού Πανεπιστημίου της Σιβηρίας, Ρωσία

Η ικανότητα να σκέφτεστε με συνέπεια, να συλλογίζεστε πειστικά, να χτίζετε υποθέσεις και να αντικρούετε αρνητικά συμπεράσματα δεν προκύπτει από μόνη της· αυτή η ικανότητα αναπτύσσεται από την επιστήμη της λογικής. Η λογική είναι μια επιστήμη που μελετά μεθόδους για τον καθορισμό της αλήθειας ή της αναλήθειας ορισμένων δηλώσεων με βάση την αλήθεια ή το ψεύδος άλλων δηλώσεων.

Η κατοχή των βασικών στοιχείων αυτής της επιστήμης είναι αδύνατη χωρίς την επίλυση λογικών προβλημάτων. Ο έλεγχος της ανάπτυξης δεξιοτήτων για την εφαρμογή της γνώσης του ατόμου σε μια νέα κατάσταση πραγματοποιείται με επιτυχία. Συγκεκριμένα, αυτή είναι η ικανότητα επίλυσης λογικών προβλημάτων. Οι εργασίες Β15 στην Εξέταση Ενιαίου Κράτους είναι εργασίες αυξημένης πολυπλοκότητας, καθώς περιέχουν συστήματα λογικών εξισώσεων. Υπάρχουν διάφοροι τρόποι επίλυσης συστημάτων λογικών εξισώσεων. Αυτό είναι αναγωγή σε μία εξίσωση, κατασκευή πίνακα αλήθειας, αποσύνθεση, διαδοχική λύση εξισώσεων κ.λπ.

Εργο:Λύστε ένα σύστημα λογικών εξισώσεων:

Ας σκεφτούμε μέθοδος αναγωγής σε μία εξίσωση . Αυτή η μέθοδος περιλαμβάνει μετασχηματισμό λογικών εξισώσεων έτσι ώστε οι δεξιές πλευρές τους να είναι ίσες με την τιμή αλήθειας (δηλαδή 1). Για να το κάνετε αυτό, χρησιμοποιήστε τη λειτουργία λογικής άρνησης. Στη συνέχεια, εάν οι εξισώσεις περιέχουν σύνθετες λογικές πράξεις, τις αντικαθιστούμε με βασικές: «ΚΑΙ», «Ή», «ΟΧΙ». Το επόμενο βήμα είναι να συνδυάσετε τις εξισώσεις σε μία, ισοδύναμη με το σύστημα, χρησιμοποιώντας τη λογική πράξη «AND». Μετά από αυτό, θα πρέπει να μετατρέψετε την εξίσωση που προκύπτει με βάση τους νόμους της λογικής άλγεβρας και να αποκτήσετε μια συγκεκριμένη λύση στο σύστημα.

Λύση 1:Εφαρμόστε αντιστροφή και στις δύο πλευρές της πρώτης εξίσωσης:

Ας φανταστούμε την επίπτωση μέσω των βασικών πράξεων "OR" και "NOT":

Δεδομένου ότι οι αριστερές πλευρές των εξισώσεων είναι ίσες με 1, μπορούμε να τις συνδυάσουμε χρησιμοποιώντας την πράξη "AND" σε μία εξίσωση που είναι ισοδύναμη με το αρχικό σύστημα:

Ανοίγουμε την πρώτη αγκύλη σύμφωνα με το νόμο του De Morgan και μετατρέπουμε το αποτέλεσμα που προκύπτει:

Η εξίσωση που προκύπτει έχει μία λύση:Α= 0, Β = 0 και Γ = 1.

Η επόμενη μέθοδος είναι κατασκευή πινάκων αλήθειας . Δεδομένου ότι τα λογικά μεγέθη έχουν μόνο δύο τιμές, μπορείτε απλά να περάσετε από όλες τις επιλογές και να βρείτε μεταξύ τους εκείνες για τις οποίες ικανοποιείται ένα δεδομένο σύστημα εξισώσεων. Δηλαδή, χτίζουμε έναν κοινό πίνακα αλήθειας για όλες τις εξισώσεις του συστήματος και βρίσκουμε μια γραμμή με τις απαιτούμενες τιμές.

Λύση 2:Ας δημιουργήσουμε έναν πίνακα αλήθειας για το σύστημα:








0	0	1	1	0	1

Η γραμμή για την οποία πληρούνται οι συνθήκες εργασίας επισημαίνεται με έντονη γραφή. Άρα Α =0, Β =0 και Γ =1.

Τρόπος αποσύνθεση . Η ιδέα είναι να καθορίσουμε την τιμή μιας από τις μεταβλητές (να την ορίσουμε ίση με 0 ή 1) και έτσι να απλοποιηθούν οι εξισώσεις. Στη συνέχεια, μπορείτε να διορθώσετε την τιμή της δεύτερης μεταβλητής και ούτω καθεξής.

Λύση 3:Αφήνω A = 0, τότε:

Από την πρώτη εξίσωση παίρνουμεσι =0, και από το δεύτερο – C=1. Λύση του συστήματος: Α = 0, Β = 0 και Γ = 1.

Μπορείτε επίσης να χρησιμοποιήσετε τη μέθοδο διαδοχική λύση εξισώσεων , σε κάθε βήμα προσθέτοντας μία μεταβλητή στο υπό εξέταση σύνολο. Για να γίνει αυτό, είναι απαραίτητο να μετασχηματιστούν οι εξισώσεις έτσι ώστε οι μεταβλητές να εισαχθούν με αλφαβητική σειρά. Στη συνέχεια, χτίζουμε ένα δέντρο αποφάσεων, προσθέτοντας διαδοχικά μεταβλητές σε αυτό.

Η πρώτη εξίσωση του συστήματος εξαρτάται μόνο από τα Α και Β και η δεύτερη εξίσωση από τα Α και Γ. Η μεταβλητή Α μπορεί να λάβει 2 τιμές 0 και 1:

Από την πρώτη εξίσωση προκύπτει ότι , οπότε πότε A = 0 και παίρνουμε B = 0, και για A = 1 έχουμε B = 1. Άρα, η πρώτη εξίσωση έχει δύο λύσεις ως προς τις μεταβλητές Α και Β.

Ας απεικονίσουμε τη δεύτερη εξίσωση, από την οποία προσδιορίζουμε τις τιμές του C για κάθε επιλογή. Όταν A =1, η συνεπαγωγή δεν μπορεί να είναι ψευδής, δηλαδή, ο δεύτερος κλάδος του δέντρου δεν έχει λύση. ΣτοΑ= 0 έχουμε τη μόνη λύση C= 1 :

Έτσι, πήραμε τη λύση του συστήματος: A = 0, B = 0 και C = 1.

Στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών, είναι πολύ συχνά απαραίτητο να προσδιοριστεί ο αριθμός των λύσεων σε ένα σύστημα λογικών εξισώσεων, χωρίς να βρεθούν οι ίδιες οι λύσεις· υπάρχουν επίσης ορισμένες μέθοδοι για αυτό. Ο κύριος τρόπος για να βρείτε τον αριθμό των λύσεων σε ένα σύστημα λογικών εξισώσεων είναι αντικατάσταση μεταβλητών. Πρώτα, πρέπει να απλοποιήσετε όσο το δυνατόν περισσότερο καθεμία από τις εξισώσεις με βάση τους νόμους της λογικής άλγεβρας και στη συνέχεια να αντικαταστήσετε τα σύνθετα μέρη των εξισώσεων με νέες μεταβλητές και να καθορίσετε τον αριθμό των λύσεων στο νέο σύστημα. Στη συνέχεια, επιστρέψτε στην αντικατάσταση και καθορίστε τον αριθμό των λύσεων για αυτό.

Εργο:Πόσες λύσεις έχει η εξίσωση ( A → B ) + (C → D ) = 1; Όπου Α, Β, Γ, Δ είναι λογικές μεταβλητές.

Λύση:Ας εισάγουμε νέες μεταβλητές: X = A → B και Y = C → D . Λαμβάνοντας υπόψη τις νέες μεταβλητές, η εξίσωση θα γραφτεί ως: X + Y = 1.

Ο διαχωρισμός ισχύει σε τρεις περιπτώσεις: (0;1), (1;0) και (1;1), ενώΧ και Υ είναι υπονοούμενο, δηλαδή είναι αληθές σε τρεις περιπτώσεις και ψευδές σε μία. Επομένως, η περίπτωση (0;1) θα αντιστοιχεί σε τρεις πιθανούς συνδυασμούς παραμέτρων. Περίπτωση (1;1) – θα αντιστοιχεί σε εννέα πιθανούς συνδυασμούς παραμέτρων της αρχικής εξίσωσης. Αυτό σημαίνει ότι οι συνολικές πιθανές λύσεις αυτής της εξίσωσης είναι 3+9=15.

Ο επόμενος τρόπος προσδιορισμού του αριθμού των λύσεων σε ένα σύστημα λογικών εξισώσεων είναι δυαδικό δέντρο. Ας δούμε αυτή τη μέθοδο χρησιμοποιώντας ένα παράδειγμα.

Εργο:Πόσες διαφορετικές λύσεις έχει το σύστημα των λογικών εξισώσεων:

Το δεδομένο σύστημα εξισώσεων είναι ισοδύναμο με την εξίσωση:

( Χ 1 → Χ 2 )*( Χ 2 → Χ 3 )*…*( x m -1 → x m) = 1.

Ας το προσποιηθούμεΧ 1 – είναι αλήθεια, τότε από την πρώτη εξίσωση προκύπτει ότιΧ 2 επίσης αλήθεια, από το δεύτερο -Χ 3 =1, και ούτω καθεξής μέχρι x m= 1. Άρα το σύνολο (1; 1; …; 1) τουΜ μονάδες είναι η λύση του συστήματος. Αφήστε το τώραΧ 1 =0, τότε από την πρώτη εξίσωση έχουμεΧ 2 =0 ή Χ 2 =1.

Οταν Χ 2 true, παίρνουμε ότι οι υπόλοιπες μεταβλητές είναι επίσης αληθείς, δηλαδή το σύνολο (0; 1; ...; 1) είναι μια λύση στο σύστημα. ΣτοΧ 2 =0 το καταλαβαίνουμε Χ 3 =0 ή Χ 3 =, και ούτω καθεξής. Συνεχίζοντας στην τελευταία μεταβλητή, βρίσκουμε ότι οι λύσεις της εξίσωσης είναι τα ακόλουθα σύνολα μεταβλητών (Μ +1 διάλυμα, σε κάθε διάλυμαΜ μεταβλητές τιμές):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Αυτή η προσέγγιση απεικονίζεται καλά με την κατασκευή ενός δυαδικού δέντρου. Ο αριθμός των πιθανών λύσεων είναι ο αριθμός των διαφορετικών κλάδων του κατασκευασμένου δέντρου. Είναι εύκολο να δεις ότι είναι ίσο m +1.

Μεταβλητές	Δέντρο	Αριθμός λύσεων
x 1
x 2
x 3

Σε περίπτωση δυσκολιών στη λογική και τη δημιουργία ενός δέντρου αποφάσεων, μπορείτε να αναζητήσετε μια λύση χρησιμοποιώντας πίνακες αλήθειας, για μία ή δύο εξισώσεις.

Ας ξαναγράψουμε το σύστημα των εξισώσεων με τη μορφή:

Και ας δημιουργήσουμε έναν πίνακα αλήθειας ξεχωριστά για μία εξίσωση:

x 1	x 2	(x 1 → x 2)

Ας δημιουργήσουμε έναν πίνακα αλήθειας για δύο εξισώσεις:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Στη συνέχεια, μπορείτε να δείτε ότι μια εξίσωση είναι αληθής στις ακόλουθες τρεις περιπτώσεις: (0; 0), (0; 1), (1; 1). Ένα σύστημα δύο εξισώσεων ισχύει σε τέσσερις περιπτώσεις (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Σε αυτή την περίπτωση, είναι αμέσως σαφές ότι υπάρχει μια λύση που αποτελείται μόνο από μηδενικά και περισσότερα Μλύσεις στις οποίες προστίθεται μία μονάδα κάθε φορά, ξεκινώντας από την τελευταία θέση μέχρι να συμπληρωθούν όλες οι πιθανές θέσεις. Μπορεί να υποτεθεί ότι η γενική λύση θα έχει την ίδια μορφή, αλλά για να γίνει λύση μια τέτοια προσέγγιση, απαιτείται απόδειξη ότι η υπόθεση είναι σωστή.

Για να συνοψίσω όλα τα παραπάνω, θα ήθελα να επιστήσω την προσοχή σας στο γεγονός ότι δεν είναι όλες οι μέθοδοι που συζητήθηκαν καθολικές. Κατά την επίλυση κάθε συστήματος λογικών εξισώσεων, θα πρέπει να ληφθούν υπόψη τα χαρακτηριστικά του, βάσει των οποίων θα πρέπει να επιλεγεί η μέθοδος επίλυσης.

Βιβλιογραφία:

1. Λογικά προβλήματα / Ο.Β. Bogomolov – 2η έκδ. – Μ.: BINOM. Laboratory of Knowledge, 2006. – 271 σελ.: ill.

2. Polyakov K.Yu. Συστήματα λογικών εξισώσεων / Εκπαιδευτική και μεθοδολογική εφημερίδα για καθηγητές πληροφορικής: Πληροφορική Νο 14, 2011.

Υπάρχουν διάφοροι τρόποι επίλυσης συστημάτων λογικών εξισώσεων. Αυτό είναι αναγωγή σε μία εξίσωση, κατασκευή πίνακα αλήθειας και αποσύνθεση.

Εργο:Λύστε ένα σύστημα λογικών εξισώσεων:

Λύση 1:Εφαρμόστε αντιστροφή και στις δύο πλευρές της πρώτης εξίσωσης:

Ας φανταστούμε την επίπτωση μέσω των βασικών πράξεων "OR" και "NOT":

Ανοίγουμε την πρώτη αγκύλη σύμφωνα με το νόμο του De Morgan και μετατρέπουμε το αποτέλεσμα που προκύπτει:

Η εξίσωση που προκύπτει έχει μία λύση: A =0, B=0 και C=1.

Λύση 2:Ας δημιουργήσουμε έναν πίνακα αλήθειας για το σύστημα:








0	0	1	1	0	1

Η γραμμή για την οποία πληρούνται οι συνθήκες εργασίας επισημαίνεται με έντονη γραφή. Άρα Α=0, Β=0 και Γ=1.

Λύση 3:Έστω A = 0, τότε:

Από την πρώτη εξίσωση παίρνουμε B = 0, και από τη δεύτερη - C = 1. Λύση του συστήματος: Α = 0, Β = 0 και Γ = 1.

Στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών, είναι πολύ συχνά απαραίτητο να προσδιοριστεί ο αριθμός των λύσεων σε ένα σύστημα λογικών εξισώσεων, χωρίς να βρεθούν οι ίδιες οι λύσεις· υπάρχουν επίσης ορισμένες μέθοδοι για αυτό. Ο κύριος τρόπος για να βρείτε τον αριθμό των λύσεων σε ένα σύστημα λογικών εξισώσεων είναιαντικατάσταση μεταβλητών. Πρώτα, πρέπει να απλοποιήσετε όσο το δυνατόν περισσότερο καθεμία από τις εξισώσεις με βάση τους νόμους της λογικής άλγεβρας και στη συνέχεια να αντικαταστήσετε τα σύνθετα μέρη των εξισώσεων με νέες μεταβλητές και να καθορίσετε τον αριθμό των λύσεων στο νέο σύστημα. Στη συνέχεια, επιστρέψτε στην αντικατάσταση και καθορίστε τον αριθμό των λύσεων για αυτό.

Εργο:Πόσες λύσεις έχει η εξίσωση (A →B) + (C →D) = 1; Όπου Α, Β, Γ, Δ είναι λογικές μεταβλητές.

Λύση:Ας εισάγουμε νέες μεταβλητές: X = A →B και Y = C →D. Λαμβάνοντας υπόψη τις νέες μεταβλητές, η εξίσωση θα γραφεί ως εξής: X + Y = 1.

Ο διαχωρισμός είναι αληθής σε τρεις περιπτώσεις: (0;1), (1;0) και (1;1), ενώ τα Χ και Υ είναι συνεπακόλουθα, δηλαδή είναι αληθής σε τρεις περιπτώσεις και ψευδής σε μία. Επομένως, η περίπτωση (0;1) θα αντιστοιχεί σε τρεις πιθανούς συνδυασμούς παραμέτρων. Περίπτωση (1;1) – θα αντιστοιχεί σε εννέα πιθανούς συνδυασμούς παραμέτρων της αρχικής εξίσωσης. Αυτό σημαίνει ότι οι συνολικές πιθανές λύσεις αυτής της εξίσωσης είναι 3+9=15.

Εργο:Πόσες διαφορετικές λύσεις έχει το σύστημα των λογικών εξισώσεων:

Το δεδομένο σύστημα εξισώσεων είναι ισοδύναμο με την εξίσωση:

(Χ 1 → Χ 2 )*(Χ 2 → Χ 3 )*…*(x m -1 → x m) = 1.

Ας το προσποιηθούμε Χ 1 – είναι αλήθεια, τότε από την πρώτη εξίσωση προκύπτει ότι Χ 2 επίσης αλήθεια, από το δεύτερο - Χ 3 =1, και ούτω καθεξής μέχρι x m= 1. Αυτό σημαίνει ότι το σύνολο (1; 1; …; 1) των m μονάδων είναι μια λύση στο σύστημα. Αφήστε το τώρα Χ 1 =0, τότε από την πρώτη εξίσωση έχουμε Χ 2 =0 ή Χ 2 =1.

Οταν Χ 2 true, παίρνουμε ότι οι υπόλοιπες μεταβλητές είναι επίσης αληθείς, δηλαδή το σύνολο (0; 1; ...; 1) είναι μια λύση στο σύστημα. Στο Χ 2 =0 το καταλαβαίνουμε Χ 3 =0 ή Χ 3 =, και ούτω καθεξής. Συνεχίζοντας στην τελευταία μεταβλητή, βρίσκουμε ότι οι λύσεις της εξίσωσης είναι τα ακόλουθα σύνολα μεταβλητών (m +1 λύση, κάθε λύση περιέχει m τιμές των μεταβλητών):