Il existe différentes manières de résoudre des systèmes d'équations logiques. Il s'agit d'une réduction à une équation, de la construction d'une table de vérité et d'une décomposition.

Tâche: Résoudre un système d'équations logiques :

Considérer méthode de réduction à une équation . Cette méthode implique la transformation d'équations logiques, de sorte que leurs membres droits soient égaux à la valeur de vérité (c'est-à-dire 1). Pour ce faire, utilisez l'opération de négation logique. Ensuite, s'il y a des opérations logiques complexes dans les équations, nous les remplaçons par des opérations de base : "ET", "OU", "NON". L'étape suivante consiste à combiner les équations en une seule, équivalente au système, en utilisant l'opération logique "ET". Après cela, vous devez effectuer des transformations de l'équation résultante sur la base des lois de l'algèbre de la logique et obtenir une solution spécifique au système.

Solution 1 : Appliquez l'inversion des deux côtés de la première équation :

Représentons l'implication par les opérations de base "OU", "NON":

Étant donné que les côtés gauches des équations sont égaux à 1, vous pouvez les combiner à l'aide de l'opération "ET" en une seule équation équivalente au système d'origine :

Nous ouvrons la première parenthèse selon la loi de Morgan et transformons le résultat :

L'équation résultante a une solution : A=0, B=0 et C=1.

La prochaine façon est construction de tables de vérité . Puisque les valeurs logiques n'ont que deux valeurs, vous pouvez simplement parcourir toutes les options et trouver parmi elles celles pour lesquelles le système d'équations donné est satisfait. Autrement dit, nous construisons une table de vérité commune pour toutes les équations du système et trouvons une ligne avec les valeurs souhaitées.

Solution 2 : Faisons une table de vérité pour le système :

En gras, la ligne pour laquelle les conditions du problème sont remplies. Donc A=0, B=0 et C=1.

Chemin décomposition . L'idée est de fixer la valeur d'une des variables (la mettre égale à 0 ou 1) et ainsi de simplifier les équations. Ensuite, vous pouvez fixer la valeur de la deuxième variable, et ainsi de suite.

Solution 3 : Soit A = 0, alors :

De la première équation, nous obtenons B = 0, et de la seconde - С=1. Solution système : A = 0, B = 0 et C = 1.

Dans l'USE en informatique, il est très souvent nécessaire de déterminer le nombre de solutions à un système d'équations logiques, sans trouver les solutions elles-mêmes, il existe aussi certaines méthodes pour cela. La principale façon de trouver le nombre de solutions à un système d'équations logiques estchangement de variable. Tout d'abord, il est nécessaire de simplifier autant que possible chacune des équations en fonction des lois de l'algèbre de la logique, puis de remplacer les parties complexes des équations par de nouvelles variables et de déterminer le nombre de solutions au nouveau système. Revenez ensuite au remplacement et déterminez le nombre de solutions pour celui-ci.

Tâche: Combien de solutions l'équation (A → B ) + (C → D ) = 1 a-t-elle ? Où A, B, C, D sont des variables booléennes.

Décision: Introduisons de nouvelles variables : X = A → B et Y = C → D . Compte tenu des nouvelles variables, l'équation s'écrira sous la forme : X + Y = 1.

La disjonction est vraie dans trois cas : (0;1), (1;0) et (1;1), tandis que X et Y sont une implication, c'est-à-dire qu'elle est vraie dans trois cas et fausse dans un. Ainsi, le cas (0;1) correspondra à trois combinaisons possibles de paramètres. Cas (1;1) - correspondra à neuf combinaisons possibles des paramètres de l'équation d'origine. Il y a donc 3+9=15 solutions possibles de cette équation.

La façon suivante de déterminer le nombre de solutions à un système d'équations logiques est - arbre binaire. Considérons cette méthode avec un exemple.

Tâche: Combien de solutions différentes le système d'équations logiques a-t-il :

Le système d'équations donné est équivalent à l'équation :

(X 1 → X 2 )*(X 2 → X 3 )*…*(xm -1 → xm) = 1.

Faisons comme si X 1 est vrai, alors à partir de la première équation, nous obtenons que X 2 également vrai, à partir de la seconde - X 3 =1, et ainsi de suite jusqu'à xm= 1. Cela signifie que l'ensemble (1 ; 1 ; … ; 1) de m unités est la solution du système. Laisse maintenant X 1 =0, alors à partir de la première équation on a X 2 =0 ou X 2 =1.

Lorsque X 2 vrai, on obtient que les autres variables sont également vraies, c'est-à-dire que l'ensemble (0; 1; ...; 1) est la solution du système. À X 2 =0 on obtient ça X 3 =0 ou X 3 =, et ainsi de suite. En continuant jusqu'à la dernière variable, on obtient que les solutions de l'équation sont les ensembles de variables suivants (m + 1 solution, chaque solution a m valeurs de variables) :

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Cette approche est bien illustrée par la construction d'un arbre binaire. Le nombre de solutions possibles est le nombre de branches différentes de l'arbre construit. Il est facile de voir qu'il est égal à m + 1.

En cas de difficultés de raisonnement niyah et construction derugissement de solutions, vous pouvez rechercher une solution avec en utilisant tables de vérité, pour une ou deux équations.

On réécrit le système d'équations sous la forme :

Et faisons une table de vérité séparément pour une équation :

Faisons une table de vérité pour deux équations :

À la fin de l'année, il s'est avéré qu'une seule des trois hypothèses était vraie. Quels départements ont réalisé des bénéfices à la fin de l'année ?

Décision. Écrivons les hypothèses de l'état du problème sous la forme d'énoncés logiques : « Recevoir des bénéfices par le département B n'est pas une condition nécessaire pour obtenir

bénéfices par unité A ":F 1 (A , B , C ) = A → B

"Recevoir un bénéfice par au moins un département B et C n'est pas suffisant pour réaliser un bénéfice par département A" : F 2 (A , B , C ) = (B + C ) → A

"Les divisions A et B ne bénéficieront pas en même temps": F 3 (A , B , C ) = A B

On sait à partir de la condition qu'une seule des trois hypothèses est vraie. Cela signifie que nous devons trouver laquelle des trois expressions logiques suivantes n'est pas identiquement fausse :

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (UNE→ B) ((B+ C) → UNE) (A↔ B) = UNE B(B C+ UNE) (UNE B+ UNE B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Par conséquent, à la fin de l'année, la deuxième hypothèse s'est avérée vraie, et la première et la troisième étaient fausses.

Par conséquent, cette division C recevra un profit, mais les divisions A et B ne recevront pas de profit.

Résolution d'équations logiques

Dans les textes des tests centralisés par l'État, il existe une tâche (A8), dans laquelle il est proposé de trouver la racine d'une équation logique. Regardons comment résoudre de telles tâches avec un exemple.

Trouvez la racine de l'équation logique : (A + B )(X AB ) = B + X → A .

La première solution est de construire une table de vérité. Construisons les tables de vérité des côtés droit et gauche de l'équation et voyons pour quoi X , les valeurs des dernières colonnes de ces tables correspondront.

F1 (A, B, X) = (A+ B)(X AB)

F2 (A, B, X) = B + X → UNE

Comparons les tables de vérité obtenues et sélectionnons les lignes dans lesquelles les valeurs F 1 (A , B , X ) et F 2 (A , B , X ) correspondent.

Nous réécrivons uniquement les lignes sélectionnées, ne laissant que les colonnes d'arguments. Regardons la variable X en fonction de A et B .

Il est évident que X = B → A .

La deuxième solution consiste à remplacer le signe égal dans l'équation par un signe équivalent, puis à simplifier l'équation logique résultante.

Pour faciliter le travail ultérieur, nous simplifions d'abord les côtés droit et gauche de l'équation logique et trouvons leurs négations :

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X UNE B) = X UNE B+ X UNE B+ X UNE B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Remplaçons le signe égal dans notre équation logique par un signe d'équivalence :

F1 ↔ F2 = F1 F2 + F1 F2 = (UNE B+ X UNE B+ X A+ X B) (X B+ UNE B) +

+ (X UNE B+ X UNE B+ X UNE B) (B+ X UNE) =

= (X UNE B+ X B+ X UNE B) + (X UNE B+ X UNE B) =

Regroupons les termes logiques de cette expression, en retirant les facteurs X et X de la parenthèse.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Notons T = A B , alors

X T+ X T= X↔ T.

Donc, pour qu'une équation logique ait une solution : X = A B = B + A = B → A .

Éléments logiques de l'ordinateur. Construction de schémas fonctionnels

La logique mathématique avec le développement de la technologie informatique était en relation étroite avec la conception et la programmation de la technologie informatique. L'algèbre de la logique a trouvé une large application initialement dans le développement de contact-relais régimes. La première recherche fondamentale qui attira l'attention des ingénieurs impliqués dans la conception d'ordinateurs sur la possibilité d'analyser des circuits électriques à l'aide de l'algèbre booléenne fut publiée en décembre 1938 par l'article de l'Américain Claude Shannon "Symbolic Analysis of Relay-Contact Circuits". Après cet article, la conception des ordinateurs n'était pas complète sans l'utilisation de l'algèbre booléenne.

Élément logique est un circuit qui implémente les opérations logiques de disjonction, conjonction et inversion. Envisagez la mise en œuvre d'éléments logiques via des circuits de contact à relais électriques, que vous connaissez depuis le cours de physique de l'école.

Connexion en série des contacts

Connexion parallèle des contacts

Faisons un tableau des dépendances de l'état des circuits sur tous les états possibles des contacts. Introduisons la notation : 1 - le contact est fermé, il y a un courant dans le circuit ; 0 - le contact est ouvert, il n'y a pas de courant dans le circuit.

Comme vous pouvez le voir, un circuit avec une connexion série correspond au fonctionnement logique de la conjonction, puisque le courant dans le circuit n'apparaît que lorsque les contacts A et B sont fermés simultanément. Un circuit avec connexion en parallèle correspond à l'opération logique disjonction, puisqu'il n'y a pas de courant dans le circuit uniquement au moment où les deux contacts sont ouverts.

L'opération logique d'inversion est mise en œuvre par le circuit de contact d'un relais électromagnétique dont le principe est étudié dans un cours de physique scolaire. Le contact x est ouvert quand x est fermé et vice versa.

L'utilisation d'éléments de contact de relais pour construire des circuits logiques d'ordinateurs ne s'est pas justifiée en raison d'une faible fiabilité, de grandes dimensions, d'une consommation d'énergie élevée et d'une faible vitesse. L'avènement des dispositifs électroniques (vide et semi-conducteur) a permis de construire des éléments logiques avec une vitesse de 1 million de commutations par seconde et plus. Les éléments logiques sur les semi-conducteurs fonctionnent en mode clé, similaire à un relais électromagnétique. Toute la théorie énoncée pour les circuits de contact est transférée aux éléments semi-conducteurs. Les éléments logiques sur semi-conducteurs ne sont pas caractérisés par l'état des contacts, mais par la présence de signaux à l'entrée et à la sortie.

Considérez les éléments logiques qui implémentent les opérations logiques de base :

schéma correspondant à la fonction :

& F(X, Y, Z)

Résoudre des problèmes en utilisant la conjonctive-normale

et disjonctif-normal formes

À Dans les livres de problèmes logiques, il y a souvent des problèmes standard où vous devez écrire une fonction qui implémente schéma à contacts, simplifiez-le et construisez une table de vérité pour cette fonction. Comment résoudre le problème inverse ? Étant donné une table de vérité arbitraire, vous devez construire un circuit fonctionnel ou de contact de relais. Nous traiterons ce problème aujourd'hui.

Toute fonction de l'algèbre de la logique peut être représentée par une combinaison de trois opérations : conjonction, disjonction et inversion. Voyons comment c'est fait. Pour ce faire, nous écrivons plusieurs définitions.

Un minterme est une fonction formée par la conjonction d'un certain nombre de variables ou leurs négations. Minterm prend la valeur 1 pour le seul de tous les ensembles possibles

arguments, et la valeur 0 pour tous les autres. Exemple : x 1 x 2 x 3 x 4 .

Maksterm est une fonction formée par la disjonction d'un certain nombre de variables ou leurs négations. Maxterm prend la valeur 0 dans l'un des ensembles possibles, et 1 dans tous les autres.

Exemple : x 1 + x 2 + x 3 .

Fonction dans forme normale disjonctive(DNF) est la somme logique des minterms.

Exemple : x 1x 2+ x 1x 2+ x 1x 2x 3.

Forme normale conjonctive(CNF) est un produit logique de disjonctions élémentaires (maxterms).

Exemple : (x 1+ x 2+ x 3) (x 1+ x 2) .

Forme normale disjonctive parfaite est appelé un DNF, dont chaque minterme contient toutes les variables ou leurs négations.

Exemple : x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Forme normale conjonctive parfaite est appelé CNF, dans chaque maxterm dont il y a toutes les variables ou leurs négations.

Exemple : (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Enregistrer une fonction logique dans une table

Toute fonction logique peut être exprimée sous la forme SDNF ou SKNF. A titre d'exemple, considérons la fonction f présentée dans le tableau.

Les fonctions G0, G1, G4, G5, G7 sont des mintermes (voir la définition). Chacune de ces fonctions est le produit de trois variables ou de leurs inverses et prend la valeur 1 dans une seule situation. On peut voir que pour obtenir 1 dans la valeur de la fonction f, un minterm est nécessaire. Par conséquent, le nombre de mintermes qui composent le SDNF de cette fonction est égal au nombre de uns dans la valeur de la fonction : f= G0+G1+G4+G5+G7. Ainsi, le SDNF a la forme :

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

De même, on peut construire un SKNF. Le nombre de facteurs est égal au nombre de zéros dans les valeurs de la fonction :

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) .

Ainsi, toute fonction logique donnée sous forme de tableau peut s'écrire sous forme de formule.

Algorithme de construction de SDNF selon la table de vérité

La table de vérité de certaines fonctions est donnée. Pour créer un SDNF, vous devez effectuer la séquence d'étapes suivante :

1. Sélectionnez toutes les lignes du tableau où la fonction prend la valeur 1.

2. Chacune de ces lignes se voit attribuer une conjonction de tous les arguments ou leurs inversions (minterm). Dans ce cas, l'argument qui prend la valeur 0 entre dans le minterme avec négation, et la valeur 1 entre dans le minterme sans négation.

3. Enfin, nous formons une disjonction de tous les minterms obtenus. Le nombre de minterms doit correspondre au nombre d'unités de la fonction logique.

Algorithme de construction de SKNF selon la table de vérité

La table de vérité de certaines fonctions est donnée. Pour créer un SKNF, vous devez effectuer la séquence d'étapes suivante :

1. Sélectionnez toutes les lignes du tableau où la fonction prend la valeur 0.

2. Chacune de ces lignes se voit attribuer une disjonction de tous les arguments ou leurs inversions (maxterm). Dans ce cas, l'argument qui prend la valeur 1 est inclus dans le maxterm avec négation, et la valeur 1 est incluse sans négation.

3. Enfin, nous formons une conjonction de tous les maxterms obtenus. Le nombre de maxterms doit correspondre au nombre de zéros de la fonction logique.

Si l'on s'accorde à partir de deux formes (SDNF ou SKNF) pour privilégier celle qui contient le moins de lettres, alors SDNF est préférable s'il y en a moins parmi les valeurs de la fonction de table de vérité, SKNF - s'il y a moins de zéros.

Exemple. La table de vérité d'une fonction logique de trois variables est donnée. Construire une formule logique qui implémente cette fonction.

Nous sélectionnons les lignes de la table de vérité donnée dans lesquelles la valeur de la fonction est égale à 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Vérifions la fonction dérivée en compilant une table de vérité.

En comparant la table de vérité initiale et finale, nous pouvons conclure que la fonction logique est construite correctement.

Résolution de problème

1. Trois enseignants sélectionnent des tâches pour l'Olympiade. Vous avez le choix entre plusieurs tâches. Pour chaque tâche, chacun des enseignants donne son avis : tâche facile (0) ou difficile (1). Une tâche est incluse dans la tâche Olympiade si au moins deux enseignants l'ont marquée comme difficile, mais si les trois enseignants la considèrent difficile, alors une telle tâche n'est pas incluse dans la tâche Olympiade comme trop difficile. Faites un schéma logique d'un appareil qui affichera 1 si le problème est inclus dans la tâche Olympiade et 0 s'il n'est pas inclus.

Construisons une table de vérité de la fonction recherchée. Nous avons trois variables d'entrée (trois enseignants). Par conséquent, la fonction recherchée sera une fonction de trois variables.

En analysant l'état du problème, on obtient la table de vérité suivante :

Nous construisons SDNF. F(A, B, C) = ABC + ABC + ABC

Construisons maintenant le circuit logique de cette fonction.

B & 1F(A,B,C)

2. City Olympiad dans le cours de base d'informatique, 2007.Construisez un schéma de circuit électrique pour l'entrée d'une maison à trois étages afin qu'un interrupteur à n'importe quel étage puisse allumer ou éteindre la lumière dans toute la maison.

Donc, nous avons trois interrupteurs avec lesquels nous devons allumer et éteindre la lumière. Chaque commutateur a deux états : haut (0) et bas (1). Supposons que si les trois interrupteurs sont en position 0, la lumière de l'entrée est éteinte. Ensuite, lorsque vous déplacez l'un des trois interrupteurs sur la position 1, la lumière de l'entrée doit s'allumer. Évidemment, lorsque vous déplacez n'importe quel autre interrupteur sur la position 1, la lumière de l'entrée s'éteint. Si le troisième interrupteur est déplacé en position 1, la lumière de l'entrée s'allumera. Nous construisons une table de vérité.

Alors, F(A, B, C) = ABC+ ABC+ ABC+ ABC.

Noter. Pour réussir à résoudre ce problème, souvenez-vous des formules logiques suivantes :

x → y= x+ y x y= x y+ x y

x ↔ y = x y + x y

On nous donne une fonction logique de trois variables F 1 (A , B , C ) = C → A + B = C + A B .

Modifions les variables B et C en même temps : F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Construisons les tables de vérité de ces deux fonctions :

Analysons le tableau résultant. Sur les huit lignes du tableau, seules deux (2ème et 3ème) la fonction ne change pas de valeur. Notez que dans ces lignes, la variable A n'inverse pas sa valeur, contrairement aux variables B et C.

Nous construisons des fonctions SKNF selon ces lignes :

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

UNE+ (B↔ C) = UNE+ B C= (B C) → UNE

La réponse demandée est donc 4.

4. Condition de modification de la valeur d'une fonction logique F (A , B , C ) = C + AB en changeant les arguments A et B est égal à :

Analysons le tableau obtenu. Sur les huit lignes du tableau, seules deux (1ère et 7ème) la fonction change de valeur. Notez que dans ces lignes, la variable C ne change pas de valeur, contrairement aux variables A et B.

Nous construisons des fonctions SDNF selon ces lignes :

F3 (UNE, B, C) = UNE B C+ UNE B C= C(UNE B+ UNE B) = C(A↔ B) = C+ (UNE B)

La réponse demandée est donc 2.

Références

1. Shapiro S.I. Résolution de problèmes de logique et de jeu(études logiques et psychologiques). - M. : Radio et communication, 1984. - 152 p.

2. Sholomov L.A. Principes fondamentaux de la théorie de la logique discrète et des dispositifs informatiques. – M. : Sciences. Ch. éd. physique - tapis. lit., 1980. - 400 p.

3. Pukhalsky G.I., Novoseltseva T.Ya. Conception de dispositifs discrets sur circuits intégrés.: A Handbook. - M. : Radio et communication, 1990.

Ce matériel contient une présentation qui présente des méthodes pour résoudre des équations logiques et des systèmes d'équations logiques dans la tâche B15 (n ° 23, 2015) de l'examen d'État unifié en informatique. On sait que cette tâche est l'une des plus difficiles parmi les tâches de l'examen. La présentation peut être utile lors de la conduite de cours sur le thème "Logique" dans des classes spécialisées, ainsi que pour préparer la réussite de l'examen.

Télécharger:

Aperçu:

Pour utiliser l'aperçu des présentations, créez un compte Google (account) et connectez-vous : https://accounts.google.com

Légendes des diapositives :

Solution de la tâche B15 (système d'équations logiques) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 18 novembre 2013, Saratov

La tâche B15 est l'une des plus difficiles de l'examen en informatique !!! Les compétences sont vérifiées : pour transformer des expressions contenant des variables logiques ; décrire en langage naturel l'ensemble des valeurs de variables logiques pour lesquelles un ensemble donné de variables logiques est vrai ; compter le nombre d'ensembles binaires qui satisfont les conditions données. Le plus difficile, car il n'y a pas de règles formelles sur la façon de procéder, il faut deviner.

De quoi ne pas se passer !

De quoi ne pas se passer !

Conventions conjonction : A /\ B , A  B , AB , А &B, A et B disjonction : A \ / B , A + B , A | B , A ou B négation :  A , A, non A équivalent : A  B, A  B, A  B XOR : A  B , A xor B

Méthode de substitution de variables Combien d'ensembles différents de valeurs de variables booléennes x1, x2, ..., x9, x10 existent qui satisfont toutes les conditions suivantes : ((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 La réponse n'a pas besoin d'énumérer tous les différents ensembles x1, x2, …, x9, x10 sous lesquels le système d'égalités donné est satisfait. En réponse, vous devez indiquer le nombre de ces ensembles (version de démonstration 2012)

Solution Étape 1. Simplifier en changeant les variables t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Après simplification : (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Considérons l'une des équations : (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Évidemment, it =1 uniquement si l'une des variables vaut 0 et l'autre vaut 1 Nous utilisons la formule pour exprimer l'opération XOR en termes de conjonction et de disjonction : (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Étape 2. Analyse du système .à. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), alors chaque valeur tk correspond à deux couples de valeurs x2k-1 et x2k , par exemple : tk =0 correspond à deux couples - (0, 1) et (1, 0) , et tk =1 sont les couples (0,0) et (1,1).

Étape 3. Compter le nombre de solutions. Chaque t a 2 solutions, le nombre de t est 5. Ainsi pour les variables t il y a 2 5 = 32 solutions. Mais chaque t correspond à un couple de solutions x, c'est-à-dire le système original a 2*32 = 64 solutions. Réponse : 64

Méthode d'élimination de solution partielle Combien d'ensembles différents de valeurs de variables logiques x1, x2, …, x5, y1,y2,…, y5 existent qui satisfont toutes les conditions suivantes : (x1→ x2)∧(x2→ x3)∧ (x3→ x4 )∧(x4→ x5) =1 ; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1 ; y5→ x5 =1. La réponse n'a pas besoin d'énumérer tous les différents ensembles x1, x2, ..., x5, y 1, y2, ..., y5, sous lesquels ce système d'égalités est satisfait. En guise de réponse, vous devez indiquer le nombre de ces ensembles.

Décision. Étape 1. Solution séquentielle des équations 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 chacune des implications est vraie. L'implication n'est fausse que dans un cas, quand 1  0, dans tous les autres cas (0  0, 0  1, 1  1) l'opération retourne 1. Écrivons ceci sous forme de tableau :

Étape 1. Solution séquentielle des équations Т.о. 6 ensembles de solutions pour х1,х2,х3,х4,х5 sont reçus : (00000), (00001), (00011), (00111), (01111), (11111). En arguant de la même manière, nous concluons que pour y1, y2, y3, y4, y5, il existe le même ensemble de solutions. Car ces équations sont indépendantes, c'est-à-dire il n'y a pas de variables communes en eux, alors la solution de ce système d'équations (sans tenir compte de la troisième équation) sera 6 * 6 = 36 paires de "x" et "oui". Considérons la troisième équation : y5→ x5 =1 Les paires sont la solution : 0 0 0 1 1 1 La paire n'est pas une solution : 1 0

Comparons les solutions obtenues, où y5 =1, x5=0 ne correspondent pas. ces paires sont au nombre de 5. Le nombre de solutions du système : 36-5 = 31. Réponse : 31 Il a fallu de la combinatoire !!!

Méthode de programmation dynamique Combien de solutions différentes l'équation logique x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 a-t-elle, où x 1, x 2, ..., x 6 sont des variables logiques ? La réponse n'a pas besoin de lister tous les différents ensembles de valeurs de variables pour lesquelles cette égalité est valable. En guise de réponse, vous devez indiquer le nombre de ces ensembles.

Solution Étape 1. Analyse de la condition A gauche de l'équation, les opérations d'implication sont écrites séquentiellement, la priorité est la même. Réécrire : ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB ! Chaque variable suivante ne dépend pas de la précédente, mais du résultat de l'implication précédente !

Étape 2. Révéler la régularité Considérons la première implication, X 1 → X 2. Table de vérité : X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 De un 0 nous avons obtenu 2 uns, et de 1 nous avons obtenu un 0 et un 1. Un seul 0 et trois 1, c'est le résultat de la première opération.

Étape 2. Révéler une régularité En reliant x 3 au résultat de la première opération, on obtient : 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 Sur deux 0 - deux 1, sur chaque 1 (il y en a 3) un 0 et un 1 (3 + 3)

Étape 3. Dérivation de la formule on peut faire des formules pour calculer le nombre de zéros N i et le nombre de uns E i pour une équation à i variables : ,

Étape 4. Remplir le tableau Remplissons le tableau pour i = 6 de gauche à droite, en calculant le nombre de zéros et de uns à l'aide des formules ci-dessus ; le tableau montre comment la colonne suivante est construite en fonction de la précédente : : nombre de variables 1 2 3 4 5 6 Nombre de zéros N i 1 1 3 5 11 21 Nombre de uns E i 1 2*1+1= 3 2 *1+3= 5 11 21 43 Réponse : 43

Méthode utilisant des simplifications d'expressions logiques Combien de solutions différentes l'équation a-t-elle ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 où J , K, L, M, N sont des variables logiques ? La réponse n'a pas besoin de lister tous les différents ensembles de valeurs J, K, L, M et N pour lesquels cette égalité est vraie. En guise de réponse, vous devez indiquer le nombre de ces ensembles.

Solution Remarquons que J → K = ¬ J  K On introduit un changement de variables : J → K=A, M  N  L =B On réécrit l'équation en tenant compte du changement : (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Évidemment, A  B pour les mêmes valeurs de A et B 6. Considérons la dernière implication M → J =1 Ceci est possible si : M= J=0 M=0, J=1 M=J=1

Solution A  B , alors Avec M=J=0 on obtient 1 + K=0. Il n'y a pas de solution. Avec M=0, J=1 on obtient 0 + K=0, K=0, et N et L - quelconque, 4 solutions : ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 un

Solution 10. Avec M=J=1 on obtient 0+K=1 *N * L , ou K=N*L, 4 solutions : 11. Le total a 4+4=8 solutions Réponse : 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Sources d'information : O.B. Bogomolova, D.Yu. Usenkov. B15 : nouvelles tâches et nouvelle solution // Informatique, n° 6, 2012, p. 35 – 39. K.Yu. Polyakov. Équations logiques // Informatique, n° 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [ressource électronique]. http://kpolyakov.narod.ru/school/ege.htm, [ressource électronique].

Soit une fonction logique de n variables. L'équation logique est :

La constante C vaut 1 ou 0.

Une équation logique peut avoir de 0 à différentes solutions. Si C est égal à 1, alors les solutions sont tous les ensembles de variables de la table de vérité sur lesquels la fonction F prend la valeur vrai (1). Les ensembles restants sont des solutions de l'équation pour C égal à zéro. On ne peut toujours considérer que des équations de la forme :

En effet, donnons l'équation :

Dans ce cas, vous pouvez passer à l'équation équivalente :

Considérons un système de k équations logiques :

La solution du système est un ensemble de variables sur lesquelles toutes les équations du système sont satisfaites. En termes de fonctions logiques, pour obtenir une solution au système d'équations logiques, il faut trouver un ensemble sur lequel la fonction logique Ф est vraie, représentant la conjonction des fonctions d'origine :

Si le nombre de variables est petit, par exemple inférieur à 5, il n'est pas difficile de construire une table de vérité pour la fonction , ce qui vous permet de dire combien de solutions le système a et quels sont les ensembles qui donnent des solutions.

Dans certaines tâches de l'examen d'État unifié sur la recherche de solutions à un système d'équations logiques, le nombre de variables atteint la valeur de 10. La construction d'une table de vérité devient alors une tâche presque insoluble. Résoudre le problème nécessite une approche différente. Pour un système arbitraire d'équations, il n'y a pas de voie générale, autre que l'énumération, qui permette de résoudre de tels problèmes.

Dans les problèmes proposés à l'examen, la solution est généralement basée sur la prise en compte des spécificités du système d'équations. Je le répète, à part l'énumération de toutes les variantes d'un ensemble de variables, il n'y a pas de manière générale de résoudre le problème. La solution doit être construite en fonction des spécificités du système. Il est souvent utile de procéder à une simplification préalable d'un système d'équations à l'aide de lois logiques connues. Une autre technique utile pour résoudre ce problème est la suivante. Nous ne nous intéressons pas à tous les ensembles, mais uniquement à ceux sur lesquels la fonction a la valeur 1. Au lieu de construire une table de vérité complète, nous allons construire son analogue - un arbre de décision binaire. Chaque branche de cet arbre correspond à une solution et précise l'ensemble sur lequel la fonction vaut 1. Le nombre de branches de l'arbre de décision coïncide avec le nombre de solutions au système d'équations.

Qu'est-ce qu'un arbre de décision binaire et comment il est construit, je vais vous expliquer avec des exemples de plusieurs tâches.

Problème 18

Combien y a-t-il d'ensembles différents de valeurs de variables booléennes x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 qui satisfont un système de deux équations ?

Réponse : Le système propose 36 solutions différentes.

Solution : Le système d'équations comprend deux équations. Trouvons le nombre de solutions pour la première équation en fonction de 5 variables - . La première équation peut à son tour être considérée comme un système de 5 équations. Comme on l'a montré, le système d'équations représente en fait une conjonction de fonctions logiques. L'énoncé inverse est également vrai - la conjonction de conditions peut être considérée comme un système d'équations.

Construisons un arbre de décision pour l'implication () - le premier terme de la conjonction, qui peut être considérée comme la première équation. Voici à quoi ressemble l'image graphique de cet arbre

L'arbre se compose de deux niveaux selon le nombre de variables dans l'équation. Le premier niveau décrit la première variable. Deux branches de ce niveau reflètent les valeurs possibles de cette variable - 1 et 0. Au deuxième niveau, les branches de l'arbre ne reflètent que les valeurs possibles de la variable pour laquelle l'équation prend la valeur vrai. Puisque l'équation définit une implication, la branche sur laquelle elle a une valeur de 1 nécessite qu'elle ait sur cette branche une valeur de 1. La branche sur laquelle elle a une valeur de 0 génère deux branches avec des valeurs égales à 0 et 1. L'arbre construit définit trois solutions, sur lesquelles l'implication prend la valeur 1. Sur chaque branche, l'ensemble correspondant de valeurs des variables est écrit, ce qui donne une solution à l'équation.

Ces ensembles sont : ((1, 1), (0, 1), (0, 0))

Continuons à construire l'arbre de décision en ajoutant l'équation suivante, l'implication suivante. La spécificité de notre système d'équations est que chaque nouvelle équation du système utilise une variable de l'équation précédente, en ajoutant une nouvelle variable. Puisque la variable a déjà des valeurs dans l'arbre, alors sur toutes les branches où la variable a une valeur de 1, la variable aura également une valeur de 1. Pour de telles branches, la construction de l'arbre se poursuit au niveau suivant, mais aucune nouvelle branche n'apparaît. La seule branche où la variable a la valeur 0 donnera une branche en deux branches, où la variable prendra les valeurs 0 et 1. Ainsi, chaque ajout d'une nouvelle équation, compte tenu de sa spécificité, ajoute une solution. Première équation originale :

a 6 solutions. Voici à quoi ressemble l'arbre de décision complet pour cette équation :

La seconde équation de notre système est similaire à la première :

La seule différence est que l'équation utilise des variables Y. Cette équation a également 6 solutions. Étant donné que chaque solution variable peut être combinée avec chaque solution variable, le nombre total de solutions est de 36.

A noter que l'arbre de décision construit donne non seulement le nombre de solutions (selon le nombre de branches), mais aussi les solutions elles-mêmes, inscrites sur chaque branche de l'arbre.

Problème 19

Combien y a-t-il d'ensembles différents de valeurs de variables booléennes x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 qui satisfont toutes les conditions suivantes ?

Cette tâche est une modification de la tâche précédente. La différence est qu'une autre équation est ajoutée qui relie les variables X et Y.

Il résulte de l'équation que lorsqu'elle a la valeur 1 (une telle solution existe), alors elle a la valeur 1. Ainsi, il y a un ensemble sur lequel et ont les valeurs 1. Lorsqu'il est égal à 0, il peut avoir n'importe quelle valeur, à la fois 0 et 1. Par conséquent, chaque ensemble égal à 0, et il y a 5 ensembles de ce type, correspond aux 6 ensembles avec les variables Y. Par conséquent, le nombre total de solutions est de 31.

Problème 20

Solution : En nous souvenant de l'équivalence de base, nous écrivons notre équation sous la forme :

La chaîne cyclique d'implications signifie que les variables sont identiques, donc notre équation est équivalente à :

Cette équation a deux solutions quand toutes sont soit 1 soit 0.

Problème 21

Combien de solutions l'équation a-t-elle :

Solution : Comme dans le problème 20, on passe des implications cycliques aux identités en réécrivant l'équation sous la forme :

Construisons un arbre de décision pour cette équation :

Problème 22

Combien de solutions le système d'équations suivant a-t-il ?

Façons de résoudre des systèmes d'équations logiques

Kirgizova E.V., Nemkova A.E.

Institut pédagogique de Lesosibirsk -

branche de l'Université fédérale de Sibérie, Russie

La capacité de penser de manière cohérente, d'argumenter de manière concluante, de construire des hypothèses, de réfuter des conclusions négatives, ne vient pas d'elle-même, cette compétence est développée par la science de la logique. La logique est une science qui étudie les méthodes d'établissement de la vérité ou de la fausseté de certains énoncés sur la base de la vérité ou de la fausseté d'autres énoncés.

Maîtriser les bases de cette science est impossible sans résoudre des problèmes logiques. La vérification de la formation des compétences pour appliquer leurs connaissances dans une nouvelle situation s'effectue par passage. En particulier, il s'agit de la capacité à résoudre des problèmes logiques. Les tâches B15 de l'examen sont des tâches d'une complexité accrue, car elles contiennent des systèmes d'équations logiques. Il existe différentes manières de résoudre des systèmes d'équations logiques. C'est la réduction à une équation, la construction d'une table de vérité, la décomposition, la résolution séquentielle d'équations, etc.

Tâche:Résoudre un système d'équations logiques :

Considérer méthode de réduction à une équation . Cette méthode implique la transformation d'équations logiques, de sorte que leurs membres droits soient égaux à la valeur de vérité (c'est-à-dire 1). Pour ce faire, utilisez l'opération de négation logique. Ensuite, s'il y a des opérations logiques complexes dans les équations, nous les remplaçons par des opérations de base : "ET", "OU", "NON". L'étape suivante consiste à combiner les équations en une seule, équivalente au système, en utilisant l'opération logique "ET". Après cela, vous devez effectuer des transformations de l'équation résultante sur la base des lois de l'algèbre de la logique et obtenir une solution spécifique au système.

Solution 1 :Appliquez l'inversion des deux côtés de la première équation :

Représentons l'implication par les opérations de base "OU", "NON":

Étant donné que les côtés gauches des équations sont égaux à 1, vous pouvez les combiner à l'aide de l'opération "ET" en une seule équation équivalente au système d'origine :

Nous ouvrons la première parenthèse selon la loi de Morgan et transformons le résultat :

L'équation résultante admet une solution : A= 0 , B=0 et C=1 .

La prochaine façon est construction de tables de vérité . Puisque les valeurs logiques n'ont que deux valeurs, vous pouvez simplement parcourir toutes les options et trouver parmi elles celles pour lesquelles le système d'équations donné est satisfait. Autrement dit, nous construisons une table de vérité commune pour toutes les équations du système et trouvons une ligne avec les valeurs souhaitées.

Solution 2 :Faisons une table de vérité pour le système :

En gras, la ligne pour laquelle les conditions du problème sont remplies. Donc A =0 , B =0 et C =1 .

Chemin décomposition . L'idée est de fixer la valeur d'une des variables (la mettre égale à 0 ou 1) et ainsi de simplifier les équations. Ensuite, vous pouvez fixer la valeur de la deuxième variable, et ainsi de suite.

Solution 3 : Laisser être A = 0, alors :

De la première équation on obtient B =0, et à partir de la seconde - С=1. Solution système : A = 0 , B = 0 et C = 1 .

Vous pouvez également utiliser la méthode solution séquentielle d'équations , en ajoutant une variable à l'ensemble considéré à chaque étape. Pour ce faire, il est nécessaire de transformer les équations de manière à ce que les variables soient saisies par ordre alphabétique. Ensuite, nous construisons un arbre de décision, en y ajoutant séquentiellement des variables.

La première équation du système ne dépend que de A et B, et la seconde équation de A et C. La variable A peut prendre 2 valeurs 0 et 1 :

Il résulte de la première équation que , donc quand A = 0 on obtient B = 0 , et pour A = 1 on a B = 1 . Ainsi, la première équation a deux solutions par rapport aux variables A et B .

Nous dessinons la deuxième équation, à partir de laquelle nous déterminons les valeurs de C pour chaque option. Pour A =1, l'implication ne peut pas être fausse, c'est-à-dire que la deuxième branche de l'arbre n'a pas de solution. À A= 0 nous obtenons la seule solution C= 1 :

Ainsi, nous avons obtenu la solution du système : A = 0 , B = 0 et C = 1 .

Dans l'USE en informatique, il est très souvent nécessaire de déterminer le nombre de solutions à un système d'équations logiques, sans trouver les solutions elles-mêmes, il existe aussi certaines méthodes pour cela. La principale façon de trouver le nombre de solutions à un système d'équations logiques est changement de variable. Tout d'abord, il est nécessaire de simplifier autant que possible chacune des équations en fonction des lois de l'algèbre de la logique, puis de remplacer les parties complexes des équations par de nouvelles variables et de déterminer le nombre de solutions au nouveau système. Revenez ensuite au remplacement et déterminez le nombre de solutions pour celui-ci.

Tâche:Combien de solutions l'équation ( A → B ) + (C → D ) = 1 ? Où A, B, C, D sont des variables booléennes.

Décision:Introduisons de nouvelles variables : X = A → B et Y = C → D . En tenant compte des nouvelles variables, l'équation peut s'écrire : X + Y = 1.

La disjonction est vraie dans trois cas : (0;1), (1;0) et (1;1), alors que X et Y est une implication, c'est-à-dire qu'elle est vraie dans trois cas et fausse dans un. Ainsi, le cas (0;1) correspondra à trois combinaisons possibles de paramètres. Cas (1;1) - correspondra à neuf combinaisons possibles des paramètres de l'équation d'origine. Il y a donc 3+9=15 solutions possibles de cette équation.

La façon suivante de déterminer le nombre de solutions à un système d'équations logiques est - arbre binaire. Considérons cette méthode avec un exemple.

Tâche:Combien de solutions différentes le système d'équations logiques a-t-il :

Le système d'équations donné est équivalent à l'équation :

( X 1 → X 2 )*( X 2 → X 3 )*…*( xm -1 → xm) = 1.

Faisons comme siX 1 est vrai, alors à partir de la première équation, nous obtenons queX 2 également vrai, à partir de la seconde -X 3 =1, et ainsi de suite jusqu'à xm= 1. D'où l'ensemble (1; 1; …; 1) de m unités est la solution du système. Laisse maintenantX 1 =0, alors à partir de la première équation on aX 2 =0 ou X 2 =1.

Lorsque X 2 vrai, on obtient que les autres variables sont également vraies, c'est-à-dire que l'ensemble (0; 1; ...; 1) est la solution du système. ÀX 2 =0 on obtient ça X 3 =0 ou X 3 =, et ainsi de suite. En continuant à la dernière variable, nous constatons que les solutions de l'équation sont les ensembles de variables suivants ( m +1 solution, dans chaque solution m valeurs variables):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Cette approche est bien illustrée par la construction d'un arbre binaire. Le nombre de solutions possibles est le nombre de branches différentes de l'arbre construit. Il est facile de voir que c'est m+1.

En cas de difficultés de raisonnement et de construction d'un arbre de décision, vous pouvez chercher une solution en utilisant tables de vérité, pour une ou deux équations.

On réécrit le système d'équations sous la forme :

Et faisons une table de vérité séparément pour une équation :

Faisons une table de vérité pour deux équations :

Ensuite, vous pouvez voir qu'une équation est vraie dans les trois cas suivants : (0 ; 0), (0 ; 1), (1 ; 1). Le système de deux équations est vrai dans quatre cas (0 ; 0 ; 0), (0 ; 0 ; 1), (0 ; 1 ; 1), (1 ; 1 ; 1). Dans ce cas, il est immédiatement clair qu'il existe une solution composée uniquement de zéros et plus m solutions dans lesquelles une unité est ajoutée, en commençant par la dernière position jusqu'à ce que toutes les places possibles soient remplies. On peut supposer que la solution générale aura la même forme, mais pour qu'une telle approche devienne une solution, il faut prouver que l'hypothèse est vraie.

En résumant tout ce qui précède, je voudrais attirer l'attention sur le fait que toutes les méthodes envisagées ne sont pas universelles. Lors de la résolution de chaque système d'équations logiques, ses caractéristiques doivent être prises en compte, sur la base desquelles la méthode de résolution doit être choisie.

Littérature:

1. Tâches logiques / O.B. Bogomolov - 2e éd. – M. : BINOM. Laboratoire des connaissances, 2006. - 271 p. : ill.

2. Polyakov K.Yu. Systèmes d'équations logiques / Journal pédagogique et méthodique pour les professeurs d'informatique : Informatique n°14, 2011