Dessine le schéma logique de l'expression suivante. Construction de circuits logiques fonctionnels pour des fonctions données. Mission pour effectuer des travaux de contrôle
Travail de laboratoire n ° 2. Algèbre de la logique
but du travail
Apprenez les bases de l'algèbre booléenne.
Tâches travail de laboratoire
A l'issue de la leçon, l'étudiant doit :
- définitions de concepts de base (énoncés simples et complexes, opérations logiques, expressions logiques, fonction logique);
- l'ordre d'exécution des opérations logiques ;
- algorithme de construction de tables de vérité ;
- schémas de portes logiques de base ;
- lois de la logique et règles de transformation des expressions logiques ;
- appliquer des plumes logiques pour simplifier les expressions logiques ;
- construire des tables de vérité ;
- construire des diagrammes logiques d'expressions complexes.
Informations théoriques générales
Concepts de base de l'algèbre logique
La base logique de l'ordinateur est l'algèbre de la logique, qui considère les opérations logiques sur les déclarations.
Algèbre de la logique- C'est une branche des mathématiques qui étudie les énoncés, considérés du côté de leurs valeurs logiques (vérité ou fausseté) et des opérations logiques sur eux.
Énoncé logique Est-ce toute phrase déclarative pour laquelle il est possible de dire sans ambiguïté si elle est vraie ou fausse.
Exemple.« 3 est un nombre premier » est une affirmation parce qu'elle est vraie.
Toutes les phrases ne sont pas des affirmations logiques.
Exemple. la phrase "Allons au cinéma" n'est pas un dicton. Les phrases interrogatives et motivantes ne sont pas des déclarations.
Forme expressive Est une phrase déclarative qui contient directement ou indirectement au moins une variable et devient une déclaration lorsque toutes les variables sont remplacées par leurs valeurs.
Exemple."X + 2> 5" est une forme de déclaration qui est vraie pour x> 3, sinon elle est fausse.
L'algèbre de la logique considère tout énoncé d'un seul point de vue - qu'il soit vrai ou faux. Les mots et expressions "pas", "et", "ou", "si ..., alors", "alors et seulement alors" et d'autres permettent de construire de nouvelles déclarations à partir des déclarations déjà données. De tels mots et expressions sont appelés connecteurs logiques.
Les instructions formées à partir d'autres instructions utilisant des connecteurs logiques sont appelées constituant(difficile). Les instructions qui ne sont pas composées sont appelées élémentaire(Facile).
Exemple. dire "Le nombre 6 est divisible par 2" est une affirmation simple. L'énoncé « Le nombre 6 est divisible par 2 et le nombre 6 est divisible par 3 » est un énoncé composé formé de deux simples en utilisant le conjonctif logique « et ».
La vérité ou la fausseté des énoncés composés dépend de la vérité ou de la fausseté des énoncés élémentaires qui les composent.
Pour faire référence à des instructions logiques, des noms leur sont attribués.
Exemple. Notons par A l'énoncé simple « le nombre 6 est divisible par 2 », et par B l'énoncé simple « le nombre 6 est divisible par 3 ». Ensuite, l'énoncé composé « Le nombre 6 est divisible par 2 et le nombre 6 est divisé par 3 » peut être écrit comme « A et B ». Ici "et" est une connexion logique, A, B sont des variables logiques qui ne peuvent prendre que deux valeurs - "vrai" ou "faux", notées respectivement "1" et "0".
Chaque connecteur logique est considéré comme une opération sur des instructions logiques et possède son propre nom et sa propre désignation (tableau 1).
Tableau 1. Opérations logiques de base
NE PAS L'opération exprimée par le mot "pas" s'appelle le déni et est indiqué par une ligne au-dessus de la déclaration (ou du signe). L'énoncé A est vrai lorsque A est faux et faux lorsque A est vrai.
Exemple. Soit A = "Aujourd'hui est nuageux", alors A = "Aujourd'hui n'est pas nuageux."
ET L'opération exprimée par la conjonction "et" s'appelle conjonction(lat. conjonctio - connexion) ou multiplication logique et est désigné par le point "" (peut également être désigné par les signes ou &). L'énoncé A B est vrai si et seulement si les deux énoncés A et B sont vrais.
Exemple. L'énoncé « Le nombre 6 est divisible par 2 et le nombre 6 est divisé par 3 » est vrai, mais l'énoncé « Le nombre 6 est divisible par 2 et le nombre 6 est supérieur à 10 » est faux.
OU ALORS L'opération exprimée par le lien "ou" (au sens non exclusif de ce mot) est appelée disjonction(latin disjonctio - division) ou addition logique et est indiqué par le signe
(ou plus). L'énoncé A B est faux si et seulement si les deux énoncés A et B sont faux.
Exemple: L'énoncé « Le nombre 6 est divisible par 2 ou le nombre 6 est supérieur à 10 » est vrai, et l'énoncé « Le nombre 6 est divisible par 5 ou le nombre 6 est supérieur à 10 » est faux.
SI DONC Une opération exprimée par les ligaments "si ... alors", "de ... suit", "... entraîne ..." est appelée implication(latin implico - étroitement lié) et est désigné par le signe →. L'énoncé A → B est faux si et seulement si A est vrai et B est faux.
Exemple. La déclaration "si un étudiant a réussi tous les examens avec d'excellentes notes, alors il recevra une bourse". Évidemment, cette implication ne devrait être reconnue comme fausse que dans le cas où l'étudiant a réussi tous les examens avec d'excellentes notes, mais n'a pas reçu de bourse. Dans d'autres cas, lorsque tous les examens ne sont pas réussis avec d'excellentes notes et que la bourse est reçue (par exemple, en raison du fait que l'étudiant vit dans une famille à faible revenu) ou lorsque les examens n'ont pas du tout été réussis et qu'il peut pas question d'une bourse, l'implication peut être reconnue comme vraie.
ÉGALEMENT L'opération exprimée par les ligaments "alors et seulement alors", "nécessaire et suffisant", "... équivaut à..." s'appelle équivalent ou alors double implication et est noté ou ~. L'énoncé A↔B est vrai si et seulement si les valeurs de A et B coïncident.
Exemple: L'énoncé « Un nombre est pair si et seulement s'il est divisible par 2 » est vrai, et l'énoncé « Un nombre est impair si et seulement s'il est divisible par 2 » est faux.
OU SOIT L'opération exprimée par les ligaments "Soit... soit" s'appelle OU exclusif ou alors ajout mod 2 et est désigné par XOR ou. L'affirmation A B est vraie si et seulement si les valeurs de A et B ne coïncident pas.
Exemple. L'énoncé « Le nombre 6 est soit impair, soit divisible par 2 sans reste » est vrai, et l'énoncé « Le nombre 6 est pair ou le nombre 6 est divisible par 3 » est faux, car les deux affirmations qu'il contient sont vraies.
Commenter. L'implication peut s'exprimer en termes de disjonction et de négation :
L'équivalence peut s'exprimer en termes de négation, de disjonction et de conjonction :
Le OU exclusif peut être exprimé en termes de négation, de disjonction et de conjonction :
Production. Les opérations de négation, de disjonction et de conjonction sont suffisantes pour décrire et traiter des énoncés logiques.
L'ordre d'exécution des opérations logiques est spécifié par des parenthèses. Mais pour réduire le nombre de parenthèses, nous avons convenu de supposer que d'abord l'opération de négation (« non ») est effectuée, puis la conjonction (« et »), après la conjonction - la disjonction (« ou ») et le ou exclusif, enfin, l'implication et l'équivalence.
À l'aide de variables logiques et de symboles d'opérations logiques, toute déclaration peut être formalisée, c'est-à-dire remplacée par une formule logique (expression logique).
Formule logique est un enregistrement symbolique d'une instruction, constitué de valeurs logiques (constantes ou variables), unies par des opérations logiques (liens).
Fonction logique est une fonction de variables logiques qui ne peut prendre que deux valeurs : 0 ou 1. À son tour, la variable logique elle-même (l'argument d'une fonction logique) ne peut également prendre que deux valeurs : 0 ou 1.
Exemple... - fonction logique de deux variables A et B.
Les valeurs d'une fonction logique pour différentes combinaisons de valeurs de variables d'entrée - ou, comme on l'appelle autrement, des ensembles de variables d'entrée - sont généralement données par un tableau spécial. Un tel tableau s'appelle table de vérité.
Nous donnons une table de vérité des principales opérations logiques (Tableau 2)
Tableau 2
| UNE | B | ||||||
Sur la base des données de la table de vérité des principales opérations logiques, il est possible de compiler des tables de vérité pour des formules plus complexes.
Algorithme de construction de tables de vérité pour des expressions complexes :
- nombre de lignes = 2 n + ligne de cap,
- n est le nombre d'instructions simples.
- nombre de colonnes = nombre de variables + nombre d'opérations logiques ;
- déterminer le nombre de variables (expressions simples) ;
- déterminer le nombre d'opérations logiques et la séquence de leur exécution.
Exemple 1. Créez une table de vérité pour la formule AND-NOT, qui peut être écrite comme suit :.
1. Déterminez le nombre de lignes :
Il y a deux déclarations simples en entrée : A et B, donc n = 2 et le nombre de lignes = 2 2 + 1 = 5.
2. Déterminez le nombre de colonnes :
Une expression se compose de deux expressions simples (A et B) et de deux opérations logiques (1 inversion, 1 conjonction), c'est-à-dire nombre de colonnes de la table de vérité = 4.
3. Remplissez les colonnes en tenant compte des tables de vérité des opérations logiques (Tableau 3).
Tableau 3. Table de vérité pour l'opération logique
Remarque : NON ET NON aussi appelé "Le coup de Schaeffer"(noter |) ou "Anti-conjonction"; OU PAS aussi appelé "La flèche de Pierce"(indique ) ou "Antidisjonction".
Exemple 2. Créez une table de vérité pour une expression logique.
Décision:
1. Déterminez le nombre de lignes :
Il y a deux déclarations simples en entrée : A et B, donc n = 2 et le nombre de lignes = 2 2 + 1 = 5.
2. Déterminez le nombre de colonnes :
Une expression se compose de deux expressions simples (A et B) et de cinq opérations logiques (2 inversions, 2 conjonctions, 1 disjonction), c'est-à-dire nombre de colonnes de la table de vérité = 7.
On effectue d'abord les opérations d'inversion, puis de conjonction et enfin l'opération de disjonction.
3. Remplissez les colonnes en tenant compte des tables de vérité des opérations logiques (Tableau 5).
Tableau 5. Table de vérité pour l'opération logique
Étant donné que toute opération logique peut être représentée comme une combinaison de trois principales, tout dispositif informatique qui traite ou stocke des informations peut être assemblé à partir d'éléments logiques de base, comme à partir de « blocs de construction ».
Les éléments logiques de l'ordinateur fonctionnent avec des signaux qui sont des impulsions électriques. Il y a une impulsion - la signification logique du signal - 1, il n'y a pas d'impulsion - 0. Les signaux-valeurs des arguments arrivent aux entrées de l'élément logique, la valeur du signal de la fonction apparaît à la sortie.
La transformation d'un signal par un élément logique est spécifiée par une table d'état, qui est en fait une table de vérité correspondant à une fonction logique, uniquement présentée sous forme de circuits logiques. Sous cette forme, il est pratique de représenter des chaînes d'opérations logiques et d'effectuer leurs calculs.
Algorithme de construction de circuits logiques.
- Déterminer le nombre de variables booléennes.
- Déterminer le nombre d'opérations logiques et leur ordre.
- Dessinez l'élément logique correspondant pour chaque opération logique.
- Connectez les portes logiques dans l'ordre dans lequel les opérations logiques sont effectuées.
Exemple. Construire un circuit logique pour une fonction logique donnée.
Décision.
- Nombre de variables booléennes = 2 (A et B).
- Nombre d'opérations = 5 (2 inversions, 2 conjonctions, 1 disjonction). On effectue d'abord les opérations d'inversion, puis de conjonction et enfin l'opération de disjonction.
- Le circuit contiendra 2 onduleurs, 2 conjoncteurs et 1 disjoncteur.
- La construction doit commencer par une opération logique, qui doit être effectuée en dernier. Dans ce cas, une telle opération est une addition logique, par conséquent, la sortie doit être un disjoncteur. Des signaux lui sont transmis par deux conjoncteurs auxquels, à leur tour, un signal d'entrée normal et un inversé (des onduleurs).
Informations similaires.
Apprenons à les connaître un par un.
Construire un circuit logique pour une fonction logique donnée.
Une tâche:
Une fonction logique est donnée :Faites un schéma logique pour cela.
Décision:
Organisons l'ordre d'exécution des opérations logiques, guidés par les règles :- négation
- multiplication
- une addition
On a:
Nous construisons le circuit dans l'ordre spécifié.
Enregistrement de fonction logique selon un schéma logique donné.
Une tâche:
Un schéma logique est donné :
Composez-lui une fonction logique.
Décision:
Nous considérons le circuit à partir de la fin et notons les opérations logiques correspondantes, en tenant compte du fait que la fonction en cours d'écriture a trois opérandes A, B, CVous pouvez d'abord signer sur le schéma les fonctions intermédiaires obtenues à la sortie de chaque bloc, puis les enchaîner avec des opérations logiques.
Détermination du signal à la sortie du circuit logique par les valeurs spécifiées des signaux à toutes les entrées de ce circuit.
Une tâche:
Un schéma logique et des valeurs de signal à toutes les entrées sont donnés :
Déterminer la valeur de la fonction F à la sortie du circuit.
Décision:
En utilisant les tables de vérité pour les éléments logiques correspondants du circuit, nous organisons les valeurs des signaux aux sorties et, par conséquent, aux entrées de chaque élément logique jusqu'à ce que nous atteignions la fin du circuit. On a:
Répondre:
La valeur de la fonction F en sortie du circuit = 1.Construire une table de vérité pour un circuit logique donné.
Une tâche:
Un schéma logique est donné :
Construisez une table de vérité pour cela.
Décision:
Nous vérifions le nombre d'entrées sur le schéma. Le nombre de combinaisons de signaux à 2 entrées est de 4, pour 3 entrées c'est 8, pour 4 entrées c'est 16, etc. On fait une table de vérité dans laquelle les premières colonnes sont les entrées du circuit, désignées par des lettres, la suivante les colonnes sont les fonctions obtenues aux sorties de chaque élément du circuit, et les lignes reflètent différentes combinaisons de signaux aux entrées. Le nombre de lignes est le même que le nombre de combinaisons de signaux. En utilisant les tables de vérité pour les éléments logiques correspondants du circuit, nous organisons les valeurs des signaux aux sorties de chaque élément logique, c'est-à-dire pour chaque colonne jusqu'à ce que nous arrivions à la fin du circuit. On a:Répondre:
4) Répondre: l v 0 & l = 1.
Exemple 2
Construire un circuit logique qui correspond à une expression booléenne
F = X & Y v (Y v X).
Calculez les valeurs de l'expression pour X = 1, Y = 0.
1) Il y a deux variables : X et Y ;
2) Il y a trois opérations logiques : conjonction et deux disjonctions : 14 3 2 X & Y v (Y v X).
3) On construit le circuit de gauche à droite selon l'ordre des opérations logiques :
 |
3) Calculer la valeur de l'expression : F = l & 0 v (0 v 1) = 0
Faire l'exercice
Construisez le schéma logique correspondant à l'expression booléenne et trouvez la valeur de l'expression booléenne :
A) F = A v B & C si A = 1, B = 1, C = 1.
B) F = (A v B & C) si A = 0, B = 1, C = 1.
B) F = A v B & C si A = 1, B = 0, C = 1.
D) F = (A v B) & (C v B) si A = 0, B = 1, C = 0.
E) F = (A & B & C) si A = 0, B = 0, C = 1.
E) F = (A & B & C) v (B & C vA) si A = 1, B = 1, C = 0.
G) F = B & A v B & A si A = 0, B = 0.
Les lois de la logique
Si l'expression booléenne contient grand nombre opérations, alors il est assez difficile de composer une table de vérité pour cela, car vous devez itérer un grand nombre de option. Dans de tels cas, il est commode de réduire les formules à forme normale.
Une formule a une forme normale s'il n'y a pas de signes d'équivalence, d'implication, de double négation, alors que les signes de négation ne sont trouvés que pour les variables logiques.
Pour amener la formule à la forme normale, les lois de la logique et les règles des transformations logiques sont utilisées.
| A = A | Droit de l'identité | |
| A & A = 0 | La loi de la contradiction | |
| Av A = l | La troisième loi d'exclusion | |
| A = A | La loi de la double négation | |
| A & 0 = 0 A v 0 = A | Lois d'élimination constante | |
| A & 1 = A A v 1 = 1 | Lois d'élimination constante | |
| & = А A v A = A | La règle de l'idempotence | |
| AvA = l | ||
| (A → B) = A & B | ||
| A → B = A v B | ||
| A & (Av B) = A | Loi d'absorption | |
| A v (A & B) = A | Loi d'absorption | |
| A & (Av B) = A & B | ||
| AvA & B = A v B | ||
| (AvB) vC = Av (BvC) (A&B) & C = A & (B&C) | Règle d'associativité | |
| (A&B) v (A&C) = A & (BvC) (AvB) & (AvC) = Av (B&C) | Règle de répartition | |
| AvB = BvA A&B = B&A | Règle de commutabilité | |
| AóB = A & Bv (A&B) | ||
| (AvB) = A & B | Les lois de Morgan | |
| (A&B) = Av B | Les lois de Morgan | |
Exemple
Simplifier l'expression booléenne F= ((UNE v B) → (B v DE))... Cette expression logique doit être réduite à la forme normale, puisque il contient l'implication et la négation d'une opération logique.
1. Débarrassons-nous de l'implication et de la négation. Nous utiliserons (8). Il s'avère : ((AvB) → (BvC)) = (AvB) & (BvC).
2. Appliquer la loi de la double négation (4). On obtient : (AvB) & (BvC) = (AvB) & (BvC)
3. Nous appliquons la règle de distributivité (15). On a:
(AvB) & (BvC) = (AvB) & Bv (AvB) & C.
4. On applique les lois de commutativité (17) et de distributivité (15). On obtient : (AvB) & Bv (AvB) & C = A & BvB & BvA & CvB & C.
5. Postulez (16) et obtenez : A & BvB & BvA & CvB & C = A & BvBvA & CvB & C
6. Nous appliquons (15), c'est-à-dire que nous retirons B.
A & BvBv A & Cv B & C = B & (Av1) v A & Cv B & C
7. Appliquons (6). On obtient : B & (Avl) v A & Cv B & C = Bv A & Cv B & C.
8. Réorganisons les termes, regroupons-les et mettons B en dehors des crochets. On a:
BvA & CvB & C = B & (1vC) vA & C.
9. Postulez (6) et obtenez la réponse :
Réponse : F = ((A v B) → (B v C)) = B v A & C.
Simplifiez l'expression :
1) F = (A & B) v (B v C).
2) F = (A → B) v (B → A).
3) F = A & C vA & C.
4) F = A vB vC v A v B v C.
5) F = (X & Y v (X & Y)).
6) F = X & (Y v X).
7) F = (X v Z) & (X vZ) & (Y v Z).
10) F = B & C & (AvA).
11) F = A & B & CvAvB
12) F = (AvB) & (BvA) & (CvB)
Simplifiez l'expression :
1. F = A & C VA & C.
2. F = A B v A&C
3. F = A & (B↔C)
4. F = (X v Y) & (Y X).
5. F = A vB vC v A v B v C.
6.F = (AvB) → (AvC)
7.F = A (B contre C)
8.F = A & B → C & D.
9.F =(X & Y v (X & Y)).
10. F = (X contre Y) & (Y contre X).
11.F = A B & C
12. F = (A contre B) & (B contre A → B).
13. F = X & (Y contre X).
14.F = A → B contre A&C
15. F = X & Y v X.
16.F = ((X contre Y) & (Z → X)) & (Z contre Y).
17.F =(X contre Z) & (X contre Z) & (Y contre Z).
18.F = A → (B contre C)
19.F = A B v C
20. F = ((X v Y) & (Z v X)) & (Z → Y).
21. F = (B & (A → C))
22. F = A → B contre A&C
23. F = A (B contre C)
24. F = ((X contre Y) & (Z contre X)) & (Z contre Y).
25. F =(A → B) v (B → A).
26. F = A & B & C & D.
27. F = A (B contre C)
28. F = A & (B → C).
29. F = A & (AvB)
30. F = A (B contre C)
31. F = A → B contre A & C
32. F = (A contre B) & (B contre A contre B).
33. F = B&C & (AvA).
34. F = A & B contre A & C
35. F = X & Y X.
36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).
37. F = A & B & CvAvB
38. F = (X → Y) & (Y v X).
39. F = A → B & C
40. F = (A B) & (B contre A & B).
41. F =(AvB) & (BvA) & (CvB) .
42. F = A & B contre A & C
43. F = A & (BvC)
44. F = (X → Y) & (Y ↔ X).
45. F = Moyenne (A&B)
46. F = A & B C & D.
47. F = A (B contre C)
48. F = (X & Y) v (Y & X).
But du service... Le calculateur en ligne est conçu pour construire une table de vérité pour une expression booléenne.Table de vérité - une table contenant toutes les combinaisons possibles de variables d'entrée et leurs valeurs de sortie correspondantes.
La table de vérité contient 2 n lignes, où n est le nombre de variables d'entrée et n + m sont des colonnes, où m sont des variables de sortie.
Instruction. Lors de la saisie au clavier, utilisez la notation suivante : Par exemple, l'expression logique abc + ab ~ c + a ~ bc doit être saisie comme ceci : a * b * c + a * b = c + a = b * c
Utilisez ce service pour saisir des données sous forme de schéma logique.
Règles de saisie des fonctions logiques
- Utilisez + au lieu de v (disjonction, OU).
- Il n'est pas nécessaire de faire précéder une fonction logique d'un indicateur de fonction. Par exemple, au lieu de F (x, y) = (x | y) = (x ^ y), vous entrez simplement (x | y) = (x ^ y).
- Le nombre maximum de variables est de 10.
La conception et l'analyse des circuits logiques informatiques sont effectuées à l'aide d'une section spéciale des mathématiques - l'algèbre de la logique. Dans l'algèbre de la logique, trois fonctions logiques principales peuvent être distinguées : « NON » (négation), « ET » (conjonction), « OU » (disjonction).
Pour créer tout dispositif logique, il est nécessaire de déterminer la dépendance de chacune des variables de sortie sur les variables d'entrée de fonctionnement, une telle dépendance est appelée fonction de commutation ou fonction d'algèbre logique.
Une fonction d'algèbre logique est dite entièrement définie si toutes ses 2 n valeurs sont données, où n est le nombre de variables de sortie.
Si toutes les valeurs ne sont pas définies, la fonction est dite partiellement définie.
Un dispositif est dit logique si son état est décrit à l'aide d'une fonction d'algèbre logique.
Les méthodes suivantes sont utilisées pour représenter une fonction de l'algèbre de la logique :
- une description verbale est une forme qui est utilisée au stade de la conception initiale et a une représentation conditionnelle.
- description de la fonction de l'algèbre de la logique sous forme de table de vérité.
- description de la fonction de l'algèbre de la logique sous la forme d'une expression algébrique : deux formes algébriques de FAL sont utilisées :
mais) DNF - disjonctif forme normale Est une somme logique de produits logiques élémentaires. Le DNF est obtenu à partir de la table de vérité selon l'algorithme ou la règle suivante :
1) les lignes de variables pour lesquelles la fonction de sortie = 1 sont sélectionnées dans le tableau.
2) un produit logique est écrit pour chaque ligne de variables ; où les variables = 0 sont écrites avec inversion.
3) le produit résultant est logiquement résumé.
Fднф = X 1 * X 2 * X 3 X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
Un DNF est dit parfait si toutes les variables ont le même rang ou le même ordre, c'est-à-dire chaque œuvre doit comprendre toutes les variables sous forme directe ou inverse.
b) CNF - forme normale conjonctive Est un produit logique de sommes logiques élémentaires.
Le CNF peut être obtenu à partir de la table de vérité en utilisant l'algorithme suivant :
1) sélectionner des ensembles de variables pour lesquels la fonction de sortie = 0
2) pour chaque ensemble de variables, nous écrivons une somme logique élémentaire, et les variables = 1 sont écrites avec inversion.
3) les montants reçus sont logiquement multipliés.
Fscnf = (X 1 V X 2 V X 3) (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
CNF est appelé parfait si toutes les variables ont le même rang.
Figure 1 - Schéma du dispositif logique
Toutes les opérations booléennes sont définies tables de vérité valeurs. La table de vérité détermine le résultat de l'opération pour tout est possible x valeurs logiques des déclarations originales. Le nombre d'options reflétant le résultat des opérations d'application dépendra du nombre d'instructions dans une expression logique. Si le nombre d'instructions dans une expression logique est N, alors la table de vérité contiendra 2 N lignes, car il existe 2 N combinaisons différentes de valeurs possibles des arguments.
Opération NON - négation logique (inversion)
Une opération logique n'est PAS appliquée à un seul argument, qui peut être une expression logique simple ou complexe. Le résultat de l'opération n'est PAS le suivant :- si l'expression originale est vraie, alors le résultat de sa négation sera faux ;
- si l'expression originale est fausse, alors le résultat de sa négation sera vrai.
pas А, , pas A, ,!
Le résultat de l'opération de négation n'est PAS déterminé par la table de vérité suivante :
| UNE | pas un |
| 0 | 1 |
| 1 | 0 |
Le résultat de l'opération de négation est vrai lorsque la déclaration d'origine est fausse, et vice versa.
Opération OU - addition logique (disjonction, union)
L'opération OU logique remplit la fonction de combiner deux instructions, qui peuvent être une expression logique simple ou complexe. Les instructions qui sont la source d'une opération logique sont appelées arguments. Le résultat de l'opération OU est une expression qui sera vraie si et seulement si au moins une des expressions originales sera vraie.Désignations appliquées : A ou B, A V B, A ou B, A || B.
Le résultat de l'opération OU est déterminé par la table de vérité suivante :
Le résultat de l'opération OU est vrai lorsque A est vrai, ou B est vrai, ou A et B sont vrais en même temps, et faux lorsque les arguments A et B sont faux.
Opération ET - multiplication logique (conjonction)
L'opération logique AND remplit la fonction d'intersection de deux instructions (arguments), qui peuvent être une expression logique simple ou complexe. Le résultat de l'opération AND est une expression qui sera vraie si et seulement si les deux expressions d'origine sont vraies.Désignations appliquées : A et B, A Λ B, A & B, A et B.
Le résultat de l'opération AND est déterminé par la table de vérité suivante :
| UNE | B | A et B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Le résultat de l'opération AND est vrai si et seulement si les énoncés A et B sont vrais en même temps, et faux dans tous les autres cas.
Opération "SI-ALORS" - suite logique (implication)
Cette opération relie deux simples expressions logiques, dont le premier est une condition, et le second est une conséquence de cette condition.Désignations appliquées :
si A, alors B ; A entraîne B; si A alors B ; A → B.
Table de vérité:
| UNE | B | A → B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Le résultat de l'opération de succession (implication) n'est faux que lorsque la prémisse A est vraie, et la conclusion B (conséquence) est fausse.
Opération "A si et seulement si B" (équivalence, équivalence)
Désignation appliquée : A B, A ~ B.Table de vérité:
| UNE | B | B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Opération "Addition mod 2" (XOR, exclusif ou, disjonction stricte)
Désignation appliquée : A XOR B, A ⊕ B.Table de vérité:
| UNE | B | B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Le résultat de l'opération équivalence n'est vrai que si A et B sont tous les deux vrais ou faux en même temps.
Priorité booléenne
- Actions entre parenthèses
- Inversion
- Conjonction (&)
- Disjonction (V), OU Exclusif (XOR), somme mod 2
- Implication (→)
- Équivalence (↔)
Forme normale disjonctive parfaite
Forme normale disjonctive parfaite d'une formule(SDNF) est une formule qui lui est équivalente, qui est une disjonction de conjonctions élémentaires ayant les propriétés suivantes :- Chaque terme logique de la formule contient toutes les variables incluses dans la fonction F (x 1, x 2, ... x n).
- Tous les termes logiques de la formule sont différents.
- Pas un seul terme logique ne contient une variable et sa négation.
- Aucun terme logique dans une formule ne contient deux fois la même variable.
Pour chaque fonction, SDNF et SKNF sont définis de manière unique jusqu'à la permutation.
Forme normale conjonctive parfaite
Formule de forme normale conjonctive parfaite (SKNF) c'est une formule qui lui est équivalente, qui est une conjonction de disjonctions élémentaires, satisfaisant les propriétés :- Toutes les clauses élémentaires contiennent toutes les variables incluses dans la fonction F (x 1, x 2, ... x n).
- Toutes les disjonctions élémentaires sont différentes.
- Chaque disjonction élémentaire contient une variable une fois.
- Aucune disjonction élémentaire ne contient une variable et sa négation.
Lors de la construction de nœuds individuels d'un ordinateur, il est souvent nécessaire de résoudre le problème de la construction de circuits logiques fonctionnels pour des fonctions données. Pour ce faire, il suffit de convenir qu'une affirmation vraie correspond au fait que le circuit conduit du courant et une fausse - le circuit est rompu.
Opérations logiques les conjonctions, disjonctions, inversions sont mises en œuvre dans un ordinateur en utilisant les schémas élémentaires suivants.
La conjonction est un élément logique "et":
Cet élément effectue l'opération de multiplication logique (conjonction) : f = x 1 x 2 Ùx 3 Ù… Ùx n; et a n entrées et une sortie.
La disjonction est un élément logique "ou":
Cet élément effectue l'opération d'addition logique (disjonction) : f = x 1 x 2 Úx 3 Ú… Úx n ; et a n entrées et une sortie.
L'inversion est un élément logique "pas":
Cet élément effectue l'opération de négation logique (inversion) : f =; et a une entrée et une sortie.
Des circuits fonctionnels complexes peuvent être construits à partir de portes logiques de base en utilisant les lois de base de l'algèbre booléenne
Un exemple de tâche de contrôle
La tâche:
1. Faites un schéma logique fonctionnel pour cette fonction.
2. Simplifier la fonction logique (en utilisant les lois de l'algèbre booléenne) et vérifier la conversion avec la table de vérité.
3. Rédiger un schéma logique fonctionnel pour une fonction simplifiée.
Performance:
1. Composons une table de vérité pour une fonction donnée :
| X | oui | |||||||
2. Composons un schéma logique fonctionnel pour une fonction donnée :
3. Simplifions la fonction donnée en utilisant les lois de l'algèbre booléenne :
a) selon la loi de Morgan - 9
b) selon la loi de l'idempotence - 13
c) la loi de la négation de la négation - 1
d) la loi de distribution - 6
e) propriétés 1 et 0 - 19
f) propriétés 1 et 0 - 16
Ainsi, la fonction simplifiée ressemble à : 
4. Composons une table de vérité pour une fonction simplifiée :
| X | oui | |||
Ainsi, en comparant les tables de vérité pour les fonctions originales et simplifiées (leurs dernières colonnes), nous concluons que les transformations effectuées sont correctes.
5. Composons un schéma logique fonctionnel pour une fonction simplifiée :
Mission pour effectuer des travaux de contrôle
Une fonction f (x, y) est donnée, le numéro de la fonction dans le tableau correspond au numéro ordinal de l'élève dans la liste.
4. Faites un schéma logique fonctionnel pour cette fonction.
5. Simplifier la fonction logique (en utilisant les lois de l'algèbre booléenne) et vérifier la conversion avec la table de vérité.