Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων στην επιστήμη των υπολογιστών. Συστήματα λογικών εξισώσεων σε προβλήματα Ενιαίας Πολιτικής Εξετάσεων στην επιστήμη των υπολογιστών
Θέμα μαθήματος: Επίλυση Λογικών Εξισώσεων
Εκπαιδευτικός - μελέτη μεθόδων για την επίλυση λογικών εξισώσεων, ανάπτυξη δεξιοτήτων επίλυσης λογικών εξισώσεων και κατασκευή λογικής έκφρασης χρησιμοποιώντας έναν πίνακα αλήθειας.Αναπτυξιακή - δημιουργία συνθηκών για την ανάπτυξη του γνωστικού ενδιαφέροντος των μαθητών, προώθηση της ανάπτυξης της μνήμης, της προσοχής και της λογικής σκέψης.
Εκπαιδευτικός : προωθήστε την ικανότητα να ακούτε τις απόψεις των άλλων,καλλιεργώντας τη θέληση και την επιμονή για την επίτευξη τελικών αποτελεσμάτων.
Τύπος μαθήματος: συνδυασμένο μάθημα
Εξοπλισμός: υπολογιστής, προβολέας πολυμέσων, παρουσίαση 6.
Κατά τη διάρκεια των μαθημάτων
Επανάληψη και ενημέρωση βασικών γνώσεων. Έλεγχος της εργασίας (10 λεπτά)
Σε προηγούμενα μαθήματα, εξοικειωθήκαμε με τους βασικούς νόμους της λογικής άλγεβρας και μάθαμε να χρησιμοποιούμε αυτούς τους νόμους για να απλοποιήσουμε τις λογικές εκφράσεις.
Ας ελέγξουμε την εργασία μας για την απλοποίηση λογικών εκφράσεων:
1. Ποια από τις παρακάτω λέξεις ικανοποιεί τη λογική συνθήκη:
(σύμφωνο πρώτου γράμματος→ σύμφωνο δεύτερου γράμματος)٨ (φωνήεν τελευταίου γράμματος → φωνήεν προτελευταίο γράμμα); Εάν υπάρχουν πολλές τέτοιες λέξεις, υποδείξτε τη μικρότερη από αυτές.
1) ΑΝΝΑ 2) ΜΑΡΙΑ 3) ΟΛΕΓ 4) ΣΤΕΠΑΝ
Ας εισάγουμε τον ακόλουθο συμβολισμό:
Α – σύμφωνο πρώτου γράμματος
Β – σύμφωνο δεύτερου γράμματος
S – τελευταίο γράμμα φωνήεν
Δ – προτελευταίο φωνήεν
Ας κάνουμε μια έκφραση:
Ας κάνουμε έναν πίνακα:
2. Υποδείξτε ποια λογική έκφραση είναι ισοδύναμη με την παράσταση
Ας απλοποιήσουμε την εγγραφή της αρχικής έκφρασης και τις προτεινόμενες επιλογές:
3. Δίνεται ένα τμήμα του πίνακα αλήθειας της έκφρασης F:
Ποια έκφραση ταιριάζει με το F;
Ας προσδιορίσουμε τις τιμές αυτών των παραστάσεων για τις καθορισμένες τιμές των ορισμάτων:
Εισαγωγή στο θέμα του μαθήματος, παρουσίαση νέου υλικού (30 λεπτά)
Συνεχίζουμε να μελετάμε τα βασικά της λογικής και το θέμα του σημερινού μας μαθήματος είναι «Επίλυση Λογικών Εξισώσεων». Αφού μελετήσετε αυτό το θέμα, θα μάθετε τους βασικούς τρόπους επίλυσης λογικών εξισώσεων, θα αποκτήσετε τις δεξιότητες επίλυσης αυτών των εξισώσεων χρησιμοποιώντας τη γλώσσα της λογικής άλγεβρας και την ικανότητα να συνθέσετε μια λογική έκφραση χρησιμοποιώντας έναν πίνακα αλήθειας.
1. Λύστε μια λογική εξίσωση
(¬Κ M) → (¬L Μ Ν) =0
Γράψτε την απάντησή σας ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση:
Ας μεταμορφώσουμε την έκφραση(¬Κ M) → (¬L Μ Ν)
Μια έκφραση είναι ψευδής όταν και οι δύο όροι είναι ψευδείς. Ο δεύτερος όρος είναι ίσος με 0 εάν M =0, N =0, L =1. Στον πρώτο όρο K = 0, αφού M = 0, και 
.
Απάντηση: 0100
2. Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Λύση: μετασχηματίστε την έκφραση
(A +B)*(C +D)=1
A +B =1 και C +D =1
Μέθοδος 2: κατάρτιση πίνακα αληθείας
3 τρόπο: κατασκευή ενός SDNF - μια τέλεια διαζευκτική κανονική μορφή για μια συνάρτηση - μια διάσπαση πλήρων τακτικών στοιχειωδών συνδέσμων.Ας μετατρέψουμε την αρχική έκφραση, ανοίξτε τις αγκύλες για να λάβετε τον διαχωρισμό των συνδέσμων:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Ας συμπληρώσουμε τους συνδέσμους σε πλήρεις συνδέσμους (το γινόμενο όλων των ορισμάτων), ανοίξτε τις αγκύλες:
Ας λάβουμε υπόψη τους ίδιους συνδέσμους:
Ως αποτέλεσμα, λαμβάνουμε ένα SDNF που περιέχει 9 συνδέσμους. Επομένως, ο πίνακας αλήθειας για αυτήν τη συνάρτηση έχει την τιμή 1 σε 9 σειρές των 2 4 = 16 συνόλων τιμών μεταβλητών.
3. Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Ας απλοποιήσουμε την έκφραση:
,
3 τρόπο: κατασκευή SDNF
Ας λάβουμε υπόψη τους ίδιους συνδέσμους:
Ως αποτέλεσμα, λαμβάνουμε ένα SDNF που περιέχει 5 συνδέσμους. Επομένως, ο πίνακας αλήθειας για αυτήν τη συνάρτηση έχει την τιμή 1 σε 5 σειρές των 2 4 = 16 συνόλων τιμών μεταβλητών.
Κατασκευάζοντας μια λογική έκφραση χρησιμοποιώντας έναν πίνακα αλήθειας:
Για κάθε γραμμή του πίνακα αληθείας που περιέχει 1, συνθέτουμε ένα γινόμενο ορισμάτων και μεταβλητές ίσες με 0 περιλαμβάνονται στο γινόμενο με άρνηση και μεταβλητές ίσες με 1 περιλαμβάνονται χωρίς άρνηση. Η επιθυμητή έκφραση F θα αποτελείται από το άθροισμα των προϊόντων που προκύπτουν. Στη συνέχεια, εάν είναι δυνατόν, αυτή η έκφραση θα πρέπει να απλοποιηθεί.
Παράδειγμα: δίνεται ένας πίνακας αλήθειας μιας έκφρασης. Κατασκευάστε μια λογική έκφραση.
Λύση:3. Εργασία για το σπίτι (5 λεπτά)
Λύστε την εξίσωση:
Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Χρησιμοποιώντας έναν δεδομένο πίνακα αληθείας, κατασκευάστε μια λογική έκφραση και
απλοποιήστε το.
Η χρήση των εξισώσεων είναι ευρέως διαδεδομένη στη ζωή μας. Χρησιμοποιούνται σε πολλούς υπολογισμούς, κατασκευές κατασκευών ακόμα και σε αθλήματα. Ο άνθρωπος χρησιμοποιούσε εξισώσεις στην αρχαιότητα, και από τότε η χρήση τους έχει αυξηθεί. Στα μαθηματικά, υπάρχουν ορισμένα προβλήματα που ασχολούνται με την προτασιακή λογική. Για να λύσετε αυτό το είδος εξίσωσης, πρέπει να έχετε μια ορισμένη ποσότητα γνώσης: γνώση των νόμων της προτασιακής λογικής, γνώση πινάκων αλήθειας λογικών συναρτήσεων 1 ή 2 μεταβλητών, μέθοδοι μετατροπής λογικών εκφράσεων. Επιπλέον, πρέπει να γνωρίζετε τις ακόλουθες ιδιότητες των λογικών πράξεων: σύνδεσμος, διαχωρισμός, αντιστροφή, συνεπαγωγή και ισοδυναμία.
Οποιαδήποτε λογική συνάρτηση του \variables - \ μπορεί να καθοριστεί από έναν πίνακα αλήθειας.
Ας λύσουμε πολλές λογικές εξισώσεις:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Ας ξεκινήσουμε τη λύση με το \[X1\] και ας προσδιορίσουμε ποιες τιμές μπορεί να πάρει αυτή η μεταβλητή: 0 και 1. Στη συνέχεια, θα εξετάσουμε καθεμία από τις παραπάνω τιμές και θα δούμε τι μπορεί να είναι το \[X2.\].
Όπως φαίνεται από τον πίνακα, η λογική μας εξίσωση έχει 11 λύσεις.
Πού μπορώ να λύσω μια λογική εξίσωση στο διαδίκτυο;
Μπορείτε να λύσετε την εξίσωση στην ιστοσελίδα μας https://site. Ο δωρεάν διαδικτυακός λύτης θα σας επιτρέψει να λύσετε διαδικτυακές εξισώσεις οποιασδήποτε πολυπλοκότητας μέσα σε λίγα δευτερόλεπτα. Το μόνο που χρειάζεται να κάνετε είναι απλώς να εισαγάγετε τα δεδομένα σας στο πρόγραμμα επίλυσης. Μπορείτε επίσης να παρακολουθήσετε οδηγίες βίντεο και να μάθετε πώς να λύσετε την εξίσωση στον ιστότοπό μας. Και αν εξακολουθείτε να έχετε ερωτήσεις, μπορείτε να τις ρωτήσετε στην ομάδα VKontakte http://vk.com/pocketteacher. Γίνετε μέλος της ομάδας μας, είμαστε πάντα στην ευχάριστη θέση να σας βοηθήσουμε.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, όπου J, K, L, M, N είναι λογικές μεταβλητές;
Λύση.
Επομένως, η έκφραση (N ∨ ¬N) ισχύει για οποιοδήποτε N
J ∧ ¬K ∧ L ∧ ¬M = 0.
Ας εφαρμόσουμε άρνηση και στις δύο πλευρές της λογικής εξίσωσης και ας χρησιμοποιήσουμε τον νόμο του De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Παίρνουμε ¬J ∨ K ∨ ¬L ∨ M = 1.
Ένα λογικό άθροισμα είναι ίσο με 1 εάν τουλάχιστον μία από τις συστατικές προτάσεις του είναι ίση με 1. Επομένως, η εξίσωση που προκύπτει ικανοποιείται από οποιονδήποτε συνδυασμό λογικών μεταβλητών εκτός από την περίπτωση που όλες οι ποσότητες που περιλαμβάνονται στην εξίσωση είναι ίσες με 0. Κάθε μία από τις οι 4 μεταβλητές μπορεί να είναι ίσες με 1 ή 0, επομένως όλοι οι πιθανοί συνδυασμοί είναι 2·2·2·2 = 16. Επομένως, η εξίσωση έχει 16 −1 = 15 λύσεις.
Μένει να σημειωθεί ότι οι 15 λύσεις που βρέθηκαν αντιστοιχούν σε οποιαδήποτε από τις δύο πιθανές τιμές της λογικής μεταβλητής N, επομένως η αρχική εξίσωση έχει 30 λύσεις.
Απάντηση: 30
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
όπου J, K, L, M, N είναι λογικές μεταβλητές;
Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των J, K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Λύση.
Χρησιμοποιούμε τους τύπους A → B = ¬A ∨ B και ¬(A ∨ B) = ¬A ∧ ¬B
Ας εξετάσουμε τον πρώτο υποτύπο:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Ας εξετάσουμε τον δεύτερο υποτύπο
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Ας εξετάσουμε τον τρίτο υποτύπο
1) M → J = 1 επομένως,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Ας συνδυάσουμε:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 άρα 4 διαλύματα.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Ας συνδυάσουμε:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L άρα 4 λύσεις.
γ) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Απάντηση: 4 + 4 = 8.
Απάντηση: 8
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
((K ∨ L) → (L ∧ M ∧ N)) = 0
όπου K, L, M, N είναι λογικές μεταβλητές; Η Απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα τιμών των K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση πρέπει να υποδείξετε τον αριθμό τέτοιων σετ.
Λύση.
Ας ξαναγράψουμε την εξίσωση χρησιμοποιώντας απλούστερο συμβολισμό για πράξεις:
((K + L) → (L M N)) = 0
1) από τον πίνακα αληθείας της πράξης «υπόνοια» (δείτε το πρώτο πρόβλημα) προκύπτει ότι αυτή η ισότητα ισχύει εάν και μόνο εάν ταυτόχρονα
K + L = 1 και L M N = 0
2) από την πρώτη εξίσωση προκύπτει ότι τουλάχιστον μία από τις μεταβλητές, K ή L, είναι ίση με 1 (ή και οι δύο μαζί). ας εξετάσουμε λοιπόν τρεις περιπτώσεις
3) εάν K = 1 και L = 0, τότε η δεύτερη ισότητα ικανοποιείται για οποιαδήποτε M και N. αφού υπάρχουν 4 συνδυασμοί δύο μεταβλητών Boolean (00, 01, 10 και 11), έχουμε 4 διαφορετικές λύσεις
4) εάν K = 1 και L = 1, τότε η δεύτερη ισότητα ισχύει για M · N = 0; υπάρχουν 3 τέτοιοι συνδυασμοί (00, 01 και 10), έχουμε άλλες 3 λύσεις
5) εάν K = 0, τότε L = 1 (από την πρώτη εξίσωση). Σε αυτή την περίπτωση, η δεύτερη ισότητα ικανοποιείται όταν M · N = 0; υπάρχουν 3 τέτοιοι συνδυασμοί (00, 01 και 10), έχουμε άλλες 3 λύσεις
6) συνολικά παίρνουμε 4 + 3 + 3 = 10 λύσεις.
Απάντηση: 10
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
(K ∧ L) ∨ (M ∧ N) = 1
Λύση.
Η έκφραση είναι αληθής σε τρεις περιπτώσεις, όταν (K ∧ L) και (M ∧ N) είναι ίσα με 01, 11, 10, αντίστοιχα.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N είναι ίσα με 1, και K και L είναι οτιδήποτε εκτός από ταυτόχρονα 1. Επομένως, υπάρχουν 3 λύσεις.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 διάλυμα.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 διαλύματα.
Απάντηση: 7.
Απάντηση: 7
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
όπου τα X, Y, Z, P είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, χρειάζεται μόνο να υποδείξετε τον αριθμό τέτοιων σετ.
Λύση.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Το λογικό Ή είναι ψευδές μόνο σε μία περίπτωση: όταν και οι δύο εκφράσεις είναι ψευδείς.
Ως εκ τούτου,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Υ = 1.
Επομένως, υπάρχει μόνο μία λύση στην εξίσωση.
Απάντηση: 1
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
(K ∨ L) ∧ (M ∨ N) = 1
όπου K, L, M, N είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, χρειάζεται μόνο να υποδείξετε τον αριθμό τέτοιων σετ.
Λύση.
Λογικό Και ισχύει μόνο σε μία περίπτωση: όταν όλες οι εκφράσεις είναι αληθείς.
K ∨ L = 1, M ∨ N = 1.
Κάθε εξίσωση δίνει 3 λύσεις.
Θεωρήστε την εξίσωση A ∧ B = 1, αν και το A και το B λάβουν αληθινές τιμές σε τρεις περιπτώσεις το καθένα, τότε συνολικά η εξίσωση έχει 9 λύσεις.
Επομένως η απάντηση είναι 9.
Απάντηση: 9
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
όπου A, B, C, D είναι λογικές μεταβλητές;
Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα τιμών A, B, C, D για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Λύση.
Το λογικό "OR" είναι αληθές όταν τουλάχιστον μία από τις προτάσεις είναι αληθής.
(D ∧ ¬D)= 0 για οποιοδήποτε D.
Ως εκ τούτου,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, που μας δίνει 3 πιθανές λύσεις για κάθε D.
(D ∧ ¬ D)= 0 για οποιοδήποτε D, που μας δίνει δύο λύσεις (για D = 1, D = 0).
Επομένως: συνολικές λύσεις 2*3 = 6.
Σύνολο 6 λύσεις.
Απάντηση: 6
Πόσες διαφορετικές λύσεις έχει η εξίσωση;
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
όπου K, L, M, N είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, χρειάζεται μόνο να υποδείξετε τον αριθμό τέτοιων σετ.
Λύση.
Ας εφαρμόσουμε άρνηση και στις δύο πλευρές της εξίσωσης:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Το λογικό Ή ισχύει σε τρεις περιπτώσεις.
Επιλογή 1.
K ∧ L ∧ M = 1, μετά K, L, M = 1, και ¬L ∧ M ∧ N = 0. Το N είναι αυθαίρετο, δηλαδή 2 λύσεις.
Επιλογή 2.
¬L ∧ M ∧ N = 1, μετά N, M = 1; L = 0, K οποιαδήποτε, δηλαδή 2 λύσεις.
Επομένως η απάντηση είναι 4.
Απάντηση: 4
Τα Α, Β και Γ είναι ακέραιοι αριθμοί για τους οποίους η πρόταση είναι αληθής
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Τι ισούται με το B αν A = 45 και C = 43;
Λύση.
Σημειώστε ότι αυτή η σύνθετη δήλωση αποτελείται από τρεις απλές
1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);
2) αυτές οι απλές εντολές συνδέονται με την πράξη ∧ (AND, σύνδεσμος), δηλαδή πρέπει να εκτελούνται ταυτόχρονα.
3) από ¬(A = B)=1 αμέσως προκύπτει ότι A B;
4) ας υποθέσουμε ότι A > B, τότε από τη δεύτερη συνθήκη παίρνουμε 1→(B > C)=1; αυτή η έκφραση μπορεί να είναι αληθής εάν και μόνο εάν B > C = 1;
5) επομένως έχουμε A > B > C, μόνο ο αριθμός 44 αντιστοιχεί σε αυτήν την συνθήκη.
6) για παν ενδεχόμενο, ας τσεκάρουμε επίσης την επιλογή A 0 →(B > C)=1;
Αυτή η έκφραση ισχύει για οποιοδήποτε Β. Τώρα κοιτάμε την τρίτη συνθήκη και παίρνουμε
αυτή η έκφραση μπορεί να είναι αληθής αν και μόνο αν C > B, και εδώ έχουμε μια αντίφαση, επειδή δεν υπάρχει τέτοιος αριθμός B για τον οποίο C > B > A.
Απάντηση: 44.
Απάντηση: 44
Κατασκευάστε έναν πίνακα αλήθειας για μια λογική συνάρτηση
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
στην οποία η στήλη των τιμών του ορίσματος Α είναι η δυαδική αναπαράσταση του αριθμού 27, η στήλη των τιμών του ορίσματος Β είναι ο αριθμός 77, η στήλη των τιμών του ορίσματος C είναι ο αριθμός 120. Ο αριθμός στη στήλη γράφεται από πάνω προς τα κάτω από το πιο σημαντικό στο λιγότερο σημαντικό (συμπεριλαμβανομένου του μηδενικού συνόλου). Μετατρέψτε την προκύπτουσα δυαδική αναπαράσταση των τιμών της συνάρτησης X στο σύστημα δεκαδικών αριθμών.
Λύση.
Ας γράψουμε την εξίσωση χρησιμοποιώντας απλούστερο συμβολισμό για πράξεις:
1) αυτή είναι μια έκφραση με τρεις μεταβλητές, επομένως θα υπάρχουν γραμμές στον πίνακα αλήθειας. Επομένως, η δυαδική αναπαράσταση των αριθμών που χρησιμοποιούνται για την κατασκευή των στηλών του πίνακα A, B και C πρέπει να αποτελείται από 8 ψηφία
2) μετατρέψτε τους αριθμούς 27, 77 και 120 στο δυαδικό σύστημα, προσθέτοντας αμέσως έως και 8 ψηφία μηδενικών στην αρχή των αριθμών
3) είναι απίθανο να μπορείτε να γράψετε αμέσως τις τιμές της συνάρτησης X για κάθε συνδυασμό, επομένως είναι βολικό να προσθέσετε επιπλέον στήλες στον πίνακα για τον υπολογισμό των ενδιάμεσων αποτελεσμάτων (δείτε τον παρακάτω πίνακα)
| ΕΝΑ | ΣΕ | ΜΕ | Χ|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) Συμπληρώστε τις στήλες του πίνακα:
| ΕΝΑ | ΣΕ | ΜΕ | Χ | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
η τιμή είναι 1 μόνο σε εκείνες τις γραμμές όπου A = B
η τιμή είναι 1 σε εκείνες τις γραμμές όπου είτε B είτε C = 1
η τιμή είναι 0 μόνο σε εκείνες τις γραμμές όπου A = 1 και B + C = 0
η τιμή είναι το αντίστροφο της προηγούμενης στήλης (0 αντικαθίσταται από 1 και το 1 αντικαθίσταται από 0)
το αποτέλεσμα του X (τελευταία στήλη) είναι το λογικό άθροισμα των δύο στηλών και
5) για να λάβετε την απάντηση, γράψτε τα bits από τη στήλη Χ από πάνω προς τα κάτω:
6) μετατρέψτε αυτόν τον αριθμό στο δεκαδικό σύστημα:
Απάντηση: 171
Ποιος είναι ο μεγαλύτερος ακέραιος X για τον οποίο ισχύει η πρόταση (10 (X+1)·(X+2));
Λύση.
Μια εξίσωση είναι μια πράξη συνεπαγωγής μεταξύ δύο σχέσεων:
1) Φυσικά, εδώ μπορείτε να εφαρμόσετε την ίδια μέθοδο όπως στο παράδειγμα 2208, αλλά θα χρειαστεί να λύσετε τετραγωνικές εξισώσεις (δεν θέλω...).
2) Σημειώστε ότι κατά συνθήκη μας ενδιαφέρουν μόνο ακέραιοι αριθμοί, οπότε μπορούμε να προσπαθήσουμε με κάποιο τρόπο να μετατρέψουμε την αρχική έκφραση, λαμβάνοντας μια ισοδύναμη δήλωση (δεν μας ενδιαφέρουν καθόλου οι ακριβείς τιμές των ριζών!).
3) Εξετάστε την ανισότητα: προφανώς, μπορεί να είναι είτε θετικός είτε αρνητικός αριθμός.
4) Είναι εύκολο να ελέγξετε ότι στον τομέα η πρόταση είναι αληθής για όλους τους ακέραιους αριθμούς και στον τομέα - για όλους τους ακέραιους αριθμούς (για να μην μπερδευτείτε, είναι πιο βολικό να χρησιμοποιείτε μη αυστηρές ανισότητες και, αντί για και );
5) Επομένως, για ακέραιους αριθμούς μπορεί να αντικατασταθεί από μια ισοδύναμη έκφραση
6) το πεδίο της αλήθειας μιας έκφρασης είναι η ένωση δύο άπειρων διαστημάτων.
7) Τώρα εξετάστε τη δεύτερη ανισότητα: είναι προφανές ότι μπορεί επίσης να είναι είτε θετικός είτε αρνητικός αριθμός.
8) Στην περιοχή, η πρόταση ισχύει για όλους τους ακέραιους αριθμούς και στην περιοχή - για όλους τους ακέραιους αριθμούς, επομένως για τους ακέραιους μπορεί να αντικατασταθεί από μια ισοδύναμη έκφραση
9) ο τομέας της αλήθειας της έκφρασης είναι ένα κλειστό διάστημα.
10) Η δεδομένη έκφραση ισχύει παντού, εκτός από τις περιοχές όπου και ;
11) Λάβετε υπόψη ότι η τιμή δεν είναι πλέον κατάλληλη, γιατί εκεί και, δηλαδή, η συνεπαγωγή δίνει 0.
12) Κατά την αντικατάσταση 2, (10 (2+1) · (2+2)), ή 0 → 0 που ικανοποιεί τη συνθήκη.
Άρα η απάντηση είναι 2.
Απάντηση: 2
Ποιος είναι ο μεγαλύτερος ακέραιος Χ για τον οποίο ισχύει η πρόταση
(50 (Χ+1)·(Χ+1));
Λύση.
Ας εφαρμόσουμε τον μετασχηματισμό της έννοιας και ας μετατρέψουμε την έκφραση:
(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Το λογικό Ή είναι αληθές όταν τουλάχιστον μία λογική πρόταση είναι αληθής. Έχοντας λύσει και τις δύο ανισώσεις και λαμβάνοντας υπόψη ότι βλέπουμε ότι ο μεγαλύτερος ακέραιος για τον οποίο ικανοποιείται τουλάχιστον ένας από αυτούς είναι το 7 (στο σχήμα, η θετική λύση της δεύτερης ανισότητας φαίνεται με κίτρινο και η πρώτη με μπλε).
Απάντηση: 7
Υποδείξτε τις τιμές των μεταβλητών K, L, M, N, στις οποίες εμφανίζεται η λογική έκφραση
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
ψευδής. Γράψτε την απάντηση ως συμβολοσειρά 4 χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση.
Διπλότυπη εργασία 3584.
Απάντηση: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Λύση.
Ας εφαρμόσουμε τον μετασχηματισμό της έννοιας:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Ας εφαρμόσουμε άρνηση και στις δύο πλευρές της εξίσωσης:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Ας μετατρέψουμε:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Επομένως, M = 0, N = 0, τώρα θεωρήστε (¬K ∧ L ∨ M ∧ L):
από το γεγονός ότι M = 0, N = 0 προκύπτει ότι M ∧ L = 0, τότε ¬K ∧ L = 1, δηλαδή K = 0, L = 1.
Απάντηση: 0100
Καθορίστε τις τιμές των μεταβλητών K, L, M, N στις οποίες εμφανίζεται η λογική έκφραση
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
ψευδής. Γράψτε την απάντησή σας ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση.
Ας γράψουμε την εξίσωση χρησιμοποιώντας απλούστερο συμβολισμό πράξεων (η συνθήκη "η έκφραση είναι ψευδής" σημαίνει ότι είναι ίση με λογικό μηδέν):
1) από τη διατύπωση της συνθήκης προκύπτει ότι η έκφραση πρέπει να είναι ψευδής μόνο για ένα σύνολο μεταβλητών
2) από τον πίνακα αληθείας της πράξης «υπόνοια» προκύπτει ότι αυτή η έκφραση είναι ψευδής εάν και μόνο εάν ταυτόχρονα
3) η πρώτη ισότητα (το λογικό γινόμενο είναι ίσο με 1) ικανοποιείται αν και μόνο αν και ; Από αυτό προκύπτει (το λογικό άθροισμα είναι ίσο με μηδέν), το οποίο μπορεί να συμβεί μόνο όταν ; Έτσι, έχουμε ήδη ορίσει τρεις μεταβλητές
4) από τη δεύτερη συνθήκη, , για και λαμβάνουμε .
Αντιγράφει την εργασία
Απάντηση: 1000
Καθορίστε τις τιμές των λογικών μεταβλητών P, Q, S, T, στις οποίες η λογική έκφραση
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) είναι λάθος.
Γράψτε την απάντηση ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών P, Q, S, T (με αυτή τη σειρά).
Λύση.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ Т)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Ας εφαρμόσουμε τον μετασχηματισμό της έννοιας:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Απάντηση: 0100
Καθορίστε τις τιμές των μεταβλητών K, L, M, N στις οποίες εμφανίζεται η λογική έκφραση
(K → M) ∨ (L ∧ K) ∨ ¬N
ψευδής. Γράψτε την απάντησή σας ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση.
Το λογικό Ή είναι ψευδές εάν και μόνο εάν και οι δύο προτάσεις είναι ψευδείς.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Ας εφαρμόσουμε τον μετασχηματισμό υπονοούμενων για την πρώτη έκφραση:
¬K ∨ M = 0 => K = 1, M = 0.
Σκεφτείτε τη δεύτερη έκφραση:
(L ∧ K) ∨ ¬N = 0 (δείτε το αποτέλεσμα της πρώτης έκφρασης) => L ∨ ¬N = 0 => L = 0, N = 1.
Απάντηση: 1001.
Απάντηση: 1001
Καθορίστε τις τιμές των μεταβλητών K, L, M, N στις οποίες εμφανίζεται η λογική έκφραση
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
αληθής. Γράψτε την απάντησή σας ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση.
Το λογικό "AND" είναι αληθές εάν και μόνο εάν και οι δύο προτάσεις είναι αληθείς.
1) (K → M) = 1 Εφαρμόστε τον μετασχηματισμό της έννοιας: ¬K ∨ M = 1
2) (K → ¬M) = 1 Εφαρμόστε τον μετασχηματισμό της έννοιας: ¬K ∨ ¬M = 1
Από αυτό προκύπτει ότι Κ = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Ας εφαρμόσουμε τον μετασχηματισμό συνεπειών: K ∨ (M ∧ ¬L ∧ N) = 1 από το γεγονός ότι λαμβάνουμε K = 0.
Υπάρχουν διάφοροι τρόποι επίλυσης συστημάτων λογικών εξισώσεων. Αυτό είναι αναγωγή σε μία εξίσωση, κατασκευή πίνακα αλήθειας και αποσύνθεση.
Εργο:Λύστε ένα σύστημα λογικών εξισώσεων:
Ας σκεφτούμε μέθοδος αναγωγής σε μία εξίσωση . Αυτή η μέθοδος περιλαμβάνει μετασχηματισμό λογικών εξισώσεων έτσι ώστε οι δεξιές πλευρές τους να είναι ίσες με την τιμή αλήθειας (δηλαδή 1). Για να το κάνετε αυτό, χρησιμοποιήστε τη λειτουργία λογικής άρνησης. Στη συνέχεια, εάν οι εξισώσεις περιέχουν σύνθετες λογικές πράξεις, τις αντικαθιστούμε με βασικές: «ΚΑΙ», «Ή», «ΟΧΙ». Το επόμενο βήμα είναι να συνδυάσετε τις εξισώσεις σε μία, ισοδύναμη με το σύστημα, χρησιμοποιώντας τη λογική πράξη «AND». Μετά από αυτό, θα πρέπει να μετατρέψετε την εξίσωση που προκύπτει με βάση τους νόμους της λογικής άλγεβρας και να αποκτήσετε μια συγκεκριμένη λύση στο σύστημα.
Λύση 1:Εφαρμόστε αντιστροφή και στις δύο πλευρές της πρώτης εξίσωσης:
Ας φανταστούμε την επίπτωση μέσω των βασικών πράξεων "OR" και "NOT":
Δεδομένου ότι οι αριστερές πλευρές των εξισώσεων είναι ίσες με 1, μπορούμε να τις συνδυάσουμε χρησιμοποιώντας την πράξη "AND" σε μία εξίσωση που είναι ισοδύναμη με το αρχικό σύστημα:
Ανοίγουμε την πρώτη αγκύλη σύμφωνα με το νόμο του De Morgan και μετατρέπουμε το αποτέλεσμα που προκύπτει:
Η εξίσωση που προκύπτει έχει μία λύση: A =0, B=0 και C=1.
Η επόμενη μέθοδος είναι κατασκευή πινάκων αλήθειας . Δεδομένου ότι τα λογικά μεγέθη έχουν μόνο δύο τιμές, μπορείτε απλά να περάσετε από όλες τις επιλογές και να βρείτε μεταξύ τους εκείνες για τις οποίες ικανοποιείται ένα δεδομένο σύστημα εξισώσεων. Δηλαδή, χτίζουμε έναν κοινό πίνακα αλήθειας για όλες τις εξισώσεις του συστήματος και βρίσκουμε μια γραμμή με τις απαιτούμενες τιμές.
Λύση 2:Ας δημιουργήσουμε έναν πίνακα αλήθειας για το σύστημα:
|
0 |
0 |
1 |
1 |
0 |
1 |
Η γραμμή για την οποία πληρούνται οι συνθήκες εργασίας επισημαίνεται με έντονη γραφή. Άρα Α=0, Β=0 και Γ=1.
Τρόπος αποσύνθεση . Η ιδέα είναι να καθορίσουμε την τιμή μιας από τις μεταβλητές (να την ορίσουμε ίση με 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 τιμές των μεταβλητών):
(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) |
Πίνακας αλήθειας – ένας πίνακας που περιέχει όλους τους πιθανούς συνδυασμούς μεταβλητών εισόδου και τις αντίστοιχες τιμές εξόδου τους.
Ο πίνακας αλήθειας περιέχει 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 και SCNF ορίζονται μοναδικά μέχρι τη μετάθεση.
Τέλεια συνδετική κανονική μορφή
Τέλεια συνδετική κανονική μορφή τύπου (SCNF)Αυτός είναι ένας τύπος ισοδύναμος με αυτόν, ο οποίος είναι ένας συνδυασμός στοιχειωδών διαχωρισμών και ικανοποιεί τις ιδιότητες:- Όλοι οι στοιχειώδεις διαχωρισμοί περιέχουν όλες τις μεταβλητές που περιλαμβάνονται στη συνάρτηση F(x 1 ,x 2 ,...x n).
- Όλοι οι στοιχειώδεις διαχωρισμοί είναι διαφορετικοί.
- Κάθε στοιχειώδης διαχωρισμός περιέχει μια μεταβλητή μία φορά.
- Κανένας στοιχειώδης διαχωρισμός δεν περιέχει μια μεταβλητή και την άρνησή της.