Logique en informatique résolvant des équations. fondements logiques des ordinateurs personnels

Établissement d'enseignement budgétaire municipal

"École secondaire n°18"

district urbain de la ville de Salavat de la République du Bachkortostan

Systèmes d'équations logiques

dans les problèmes d'examen d'État unifié en informatique

La section « Fondements de l'algèbre de la logique » dans les tâches de l'examen d'État unifié est considérée comme l'une des plus difficiles et des plus difficiles à résoudre. Le pourcentage moyen de tâches réalisées sur ce sujet est le plus bas et est de 43,2.

Basé sur la spécification KIM 2018, ce bloc comprend quatre tâches de différents niveaux de difficulté.

La tâche 23 a un niveau de difficulté élevé, elle a donc le pourcentage d'achèvement le plus faible. Parmi les diplômés préparés (81-100 points) 49,8 % ont terminé la tâche, moyennement préparés (61-80 points) 13,7 %, le groupe d'étudiants restant n'a pas terminé cette tâche.

Le succès de la résolution d'un système d'équations logiques dépend de la connaissance des lois de la logique et de l'application précise des méthodes de résolution du système.

Considérons la résolution d'un système d'équations logiques à l'aide de la méthode de cartographie.

(23.154 Polyakov K.Yu.) Combien de solutions différentes le système d'équations a-t-il ?

((X1  oui1 )  (X2  oui2 ))  (X1  X2 )  (oui1  oui2 ) =1

((X2  oui2 )  (X3  oui3 ))  (X2  X3 )  (oui2  oui3 ) =1

((X7  oui7 )  (X8  oui8 ))  (X7  X8 )  (oui7  oui8 ) =1

Où X1 , X2 ,…, X8, à1 ,oui2 ,…,oui8 - des variables logiques ? La réponse n'a pas besoin de lister tous les différents ensembles de valeurs de variables pour lesquels cette égalité est valable. En réponse, vous devez indiquer le nombre de ces ensembles.

Solution. Toutes les équations incluses dans le système sont du même type et chaque équation comprend quatre variables. Connaissant x1 et y1, nous pouvons trouver toutes les valeurs possibles de x2 et y2 qui satisfont la première équation. En raisonnant de la même manière, à partir des x2 et y2 connus, nous pouvons trouver x3, y3 qui satisfont la deuxième équation. C'est-à-dire qu'en connaissant la paire (x1, y1) et en déterminant la valeur de la paire (x2, y2), nous trouverons la paire (x3, y3), qui, à son tour, mènera à la paire (x4, y4) et ainsi de suite.

Trouvons toutes les solutions à la première équation. Cela peut se faire de deux manières : construire une table de vérité, par le raisonnement et l'application des lois de la logique.

Table de vérité:

Construire une table de vérité demande beaucoup de travail et de temps, c'est pourquoi nous utilisons la deuxième méthode : le raisonnement logique. Le produit est égal à 1 si et seulement si chaque facteur est égal à 1.

(X1  oui1 )  (X2  oui2 ))=1

(X1  X2 ) =1

(oui1  oui2 ) =1

Regardons la première équation. La conséquence est égale à 1 lorsque 0 0, 0 1, 1 1, ce qui signifie (x1 y1)=0 pour (01), (10), alors le couple (X2  oui2 ) peut être n'importe lequel (00), (01), (10), (11), et lorsque (x1 y1) = 1, c'est-à-dire (00) et (11), la paire (x2 y2) = 1 prend le mêmes valeurs (00) et (11). Excluons de cette solution les couples pour lesquels les deuxième et troisième équations sont fausses, c'est-à-dire x1=1, x2=0, y1=1, y2=0.

Nombre total de paires 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Combien de solutions différentes le système d'équations logiques a-t-il ?

(X 1  (X 2  oui 2 ))  (oui 1  oui 2 ) = 1

(X 2  (X 3  oui 3 ))  (oui 2  oui 3 ) = 1

...

( X 6  ( X 7  oui 7 ))  ( oui 6  oui 7 ) = 1

X 7  oui 7 = 1

Solution. 1) Les équations sont du même type, donc en raisonnant nous trouverons toutes les paires possibles (x1,y1), (x2,y2) de la première équation.

(X1  (X2  oui2 ))=1

(oui1  oui2 ) = 1

La solution de la deuxième équation est constituée des paires (00), (01), (11).

Trouvons des solutions à la première équation. Si x1=0, alors x2, y2 - n'importe lequel, si x1=1, alors x2, y2 prend la valeur (11).

Faisons des liens entre les paires (x1, y1) et (x2, y2).

Créons un tableau pour calculer le nombre de paires à chaque étape.

Prise en compte des solutions de la dernière équation X 7  oui 7 = 1, excluons la paire (10). Trouver le nombre total de solutions 1+7+0+34=42

3)(23.180) Combien de solutions différentes possède un système d’équations logiques ?

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Solution. 1) Les équations sont du même type, donc en raisonnant nous trouverons toutes les paires possibles (x1,x2), (x3,x4) de la première équation.

(X1  X2 )  (X3  X4 ) = 1

Excluons de la solution les couples qui dans la séquence donnent 0 (1 0), ce sont les couples (01, 00, 11) et (10).

Faisons des connexions entre les paires (x1,x2), (x3,x4)

L'utilisation d'équations est répandue dans nos vies. Ils sont utilisés dans de nombreux calculs, construction de structures et même dans le sport. L’homme utilisait des équations dans l’Antiquité et depuis lors, leur utilisation n’a fait que croître. En mathématiques, certains problèmes concernent la logique propositionnelle. Pour résoudre ce genre d'équation, il faut avoir un certain nombre de connaissances : connaissance des lois de la logique propositionnelle, connaissance des tables de vérité des fonctions logiques à 1 ou 2 variables, méthodes de conversion d'expressions logiques. De plus, vous devez connaître les propriétés suivantes des opérations logiques : conjonction, disjonction, inversion, implication et équivalence.

Toute fonction logique de \variables - \peut être spécifiée par une table de vérité.

Résolvons plusieurs équations logiques :

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Commençons la solution avec \[X1\] et déterminons quelles valeurs cette variable peut prendre : 0 et 1. Ensuite, nous considérerons chacune des valeurs ci-dessus et verrons ce que peut être \[X2.\].

Comme le montre le tableau, notre équation logique a 11 solutions.

Où puis-je résoudre une équation logique en ligne ?

Vous pouvez résoudre l’équation sur notre site https://site. Le solveur en ligne gratuit vous permettra de résoudre des équations en ligne de toute complexité en quelques secondes. Tout ce que vous avez à faire est simplement de saisir vos données dans le solveur. Vous pouvez également regarder des instructions vidéo et apprendre à résoudre l'équation sur notre site Web. Et si vous avez encore des questions, vous pouvez les poser dans notre groupe VKontakte http://vk.com/pocketteacher. Rejoignez notre groupe, nous sommes toujours heureux de vous aider.

Résoudre des systèmes d'équations logiques en changeant des variables

La méthode de substitution des variables est utilisée si certaines variables sont incluses dans les équations uniquement sous la forme d'une expression spécifique, et rien d'autre. Cette expression peut alors être désignée par une nouvelle variable.

Exemple 1.

Combien d'ensembles différents de valeurs des variables logiques x1, x2, x3, x4, x5, x6, x7, x8 existe-t-il qui satisfont à toutes les conditions énumérées ci-dessous ?

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

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

La réponse n'a pas besoin de lister tous les différents ensembles de valeurs des variables x1, x2, x3, x4, x5, x6, x7, x8 pour lesquels ce système d'égalités est satisfait. En réponse, vous devez indiquer le nombre de ces ensembles.

Solution:

(x1 → x2) = y1 ; (x3 → x4) = y2 ; (x5 → x6) = y3; (x7 → x8) = y4.

On peut alors écrire le système sous la forme d’une seule équation :

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. La conjonction est 1 (vrai) lorsque chaque opérande prend la valeur 1. Soit chacune des implications doit être vraie, et cela vaut pour toutes les valeurs sauf (1 → 0). Ceux. dans le tableau des valeurs des variables y1, y2, y3, y4, il ne faut pas être à gauche de zéro :

Ceux. les conditions sont satisfaites pour 5 ensembles y1-y4.

Parce que y1 = x1 → x2, alors la valeur y1 = 0 est obtenue sur un seul ensemble x1, x2 : (1, 0), et la valeur y1 = 1 – sur trois ensembles x1, x2 : (0,0) , (0 ,1), (1.1). De même pour y2, y3, y4.

Puisque chaque ensemble (x1,x2) pour la variable y1 est combiné avec chaque ensemble (x3,x4) pour la variable y2, etc., les nombres d'ensembles des variables x sont multipliés :

Additionnons le nombre d'ensembles : 1 + 3 + 9 + 27 + 81 = 121.

Répondre: 121

Exemple 2.

Combien d'ensembles différents de valeurs des variables logiques x1, x2, ... x9, y1, y2, ... y9 existe-t-il qui satisfont à toutes les conditions énumérées ci-dessous ?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

En réponse pas besoin lister tous les différents ensembles de valeurs des variables x1, x2, ... x9, y1, y2, ... y9 pour lesquels le système d'égalités donné est satisfait. En réponse, vous devez indiquer le nombre de ces ensembles.

Solution:

Faisons un changement de variables :

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Le système peut s'écrire sous la forme d'une seule équation :

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

L'équivalence n'est vraie que si les deux opérandes sont égaux. Il existe deux ensembles de solutions à cette équation :

Parce que zi = (xi ≡ yi), alors la valeur zi = 0 correspond à deux ensembles (xi,yi) : (0,1) et (1,0), et la valeur zi = 1 correspond à deux ensembles (xi,yi ) : (0,0) et (1,1).

Alors le premier ensemble z1, z2,…, z9 correspond à 2 9 ensembles (x1,y1), (x2,y2),…, (x9,y9).

Le même numéro correspond au deuxième ensemble z1, z2,…, z9. Il y a alors un total de 2 9 +2 9 = 1024 ensembles.

Répondre: 1024

Résoudre des systèmes d'équations logiques en déterminant visuellement la récursion.

Cette méthode est utilisée si le système d'équations est assez simple et que l'ordre d'augmentation du nombre d'ensembles lors de l'ajout de variables est évident.

Exemple 3.

Combien de solutions différentes le système d’équations a-t-il ?

¬x9 ∨ x10 = 1,

où x1, x2,… x10 sont des variables logiques ?

La réponse n'a pas besoin de lister tous les différents ensembles de valeurs x1, x2, ... x10 pour lesquels ce système d'égalités est satisfait. En réponse, vous devez indiquer le nombre de ces ensembles.

Solution:

Résolvons la première équation. Une disjonction est égale à 1 si au moins un de ses opérandes est égal à 1. Soit les solutions sont les ensembles :

Pour x1=0 il y a deux valeurs de x2 (0 et 1), et pour x1=1 il n'y a qu'une seule valeur de x2 (1), telle que l'ensemble (x1,x2) est une solution de l'équation. Il y a 3 ensembles au total.

Ajoutons la variable x3 et considérons la deuxième équation. Elle est similaire à la première, ce qui signifie que pour x2=0 il y a deux valeurs de x3 (0 et 1), et pour x2=1 il n'y a qu'une seule valeur x3 (1), telle que l'ensemble (x2 ,x3) est une solution de l’équation. Il y a 4 ensembles au total.

Il est facile de voir que lors de l’ajout d’une autre variable, un ensemble est ajouté. Ceux. formule récursive pour le nombre d'ensembles de (i+1) variables :

N i +1 = N i + 1. Ensuite, pour dix variables, nous obtenons 11 ensembles.

Répondre: 11

Résolution de systèmes d'équations logiques de différents types

Exemple 4.

Combien y a-t-il d'ensembles différents de valeurs des variables logiques x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 qui satisfont à toutes les conditions énumérées ci-dessous ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ oui 4 ∧ z 4 = 0

En réponse pas besoin lister tous les différents ensembles de valeurs des variables x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 pour lesquels le système d'égalités donné est satisfait .

En réponse, vous devez indiquer le nombre de ces ensembles.

Solution:

Notez que les trois équations du système sont les mêmes sur différents ensembles indépendants de variables.

Regardons la première équation. Une conjonction n'est vraie (égale à 1) que si tous ses opérandes sont vrais (égaux à 1). L'implication est 1 sur tous les tuples sauf (1,0). Cela signifie que la solution de la première équation sera les ensembles suivants x1, x2, x3, x4, dans lesquels 1 n'est pas situé à gauche de 0 (5 ensembles) :

De même, les solutions des deuxième et troisième équations seront absolument les mêmes ensembles y1,…,y4 et z1,…, z4.

Analysons maintenant la quatrième équation du système : x 4 ∧ y 4 ∧ z 4 = 0. La solution sera tous les ensembles x4, y4, z4 dans lesquels au moins une des variables est égale à 0.

Ceux. pour x4 = 0, tous les ensembles possibles (y4, z4) conviennent, et pour x4 = 1, les ensembles (y4, z4) conviennent, dans lesquels il y a au moins un zéro : (0, 0), (0,1 ) , (dix).

Le nombre total d'ensembles est de 25 + 4*9 = 25 + 36 = 61.

Répondre: 61

Résoudre des systèmes d'équations logiques en construisant des formules récurrentes

La méthode de construction de formules récurrentes est utilisée lors de la résolution de systèmes complexes dans lesquels l'ordre d'augmentation du nombre d'ensembles n'est pas évident et la construction d'un arbre est impossible en raison des volumes.

Exemple 5.

Combien d'ensembles différents de valeurs des variables logiques x1, x2, ... x7, y1, y2, ... y7 existe-t-il qui satisfont à toutes les conditions énumérées ci-dessous ?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

La réponse n'a pas besoin de lister tous les différents ensembles de valeurs des variables x1, x2, ..., x7, y1, y2, ..., y7 pour lesquels ce système d'égalités est satisfait. En réponse, vous devez indiquer le nombre de ces ensembles.

Solution:

Notez que les six premières équations du système sont identiques et ne diffèrent que par l’ensemble des variables. Regardons la première équation. Sa solution sera les ensembles de variables suivants :

Notons :

nombre de tuples (0,0) sur les variables (x1,y1) jusqu'à A 1,

nombre de tuples (0,1) sur les variables (x1,y1) jusqu'à B 1,

nombre de tuples (1,0) sur les variables (x1,y1) jusqu'à C 1,

le nombre de tuples (1,1) sur les variables (x1,y1) jusqu'à D 1 .

nombre de tuples (0,0) sur les variables (x2,y2) jusqu'à A 2 ,

nombre de tuples (0,1) sur les variables (x2,y2) jusqu'à B 2,

nombre de tuples (1,0) sur les variables (x2,y2) jusqu'à C 2,

le nombre de tuples (1,1) sur les variables (x2,y2) jusqu'à D 2 .

De l'arbre de décision, nous voyons que

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

A noter que l'ensemble (0,0) sur les variables (x2,y2) est obtenu à partir des ensembles (0,1), (1,0) et (1,1) sur les variables (x1,y1). Ceux. A 2 =B 1 +C 1 +D 1.

L'ensemble (0,1) sur les variables (x2,y2) est obtenu à partir des ensembles (0,1), (1,0) et (1,1) sur les variables (x1,y1). Ceux. B 2 =B 1 +C 1 +D 1.

En argumentant de la même manière, nous notons que C 2 =B 1 +C 1 +D 1. D2 = D1.

Ainsi, on obtient des formules récurrentes :

UNE je+1 = B je + C je + ré je

B je + 1 = B je + C je + ré je

C je + 1 = B je + C je + ré je

ré je+1 = UNE je +B je + C je + RÉ je

Faisons un tableau

La dernière équation (x7 ∨ y7) = 1 est satisfaite par tous les ensembles sauf ceux dans lesquels x7=0 et y7=0. Dans notre tableau, le nombre de ces ensembles est A 7.

Alors le nombre total d'ensembles est B 7 + C 7 + D 7 = 127+127+1 = 255

Répondre: 255

Instructions. Lors de la saisie au clavier, utilisez les notations suivantes : Par exemple, l'expression logique abc+ab~c+a~bc doit être saisie comme ceci : a*b*c+a*b=c+a=b*c
Pour saisir des données sous forme de diagramme logique, utilisez ce service.

Règles de saisie d'une fonction logique

1. Au lieu du symbole v (disjonction, OR), utilisez le signe +.
2. Il n'est pas nécessaire de spécifier une désignation de fonction avant une fonction logique. Par exemple, au lieu de F(x,y)=(x|y)=(x^y) vous devez simplement saisir (x|y)=(x^y) .
3. Le nombre maximum de variables est de 10.

La conception et l'analyse des circuits logiques informatiques sont réalisées à l'aide d'une branche spéciale des mathématiques - l'algèbre logique. En algèbre logique, on distingue trois fonctions logiques principales : « NON » (négation), « ET » (conjonction), « OU » (disjonction).
Pour créer un dispositif logique, il est nécessaire de déterminer la dépendance de chacune des variables de sortie par rapport aux variables d'entrée existantes ; cette 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 2n 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 appareil 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 d'algèbre logique :
Sous forme algébrique, vous pouvez construire un circuit d'un dispositif logique à l'aide d'éléments logiques.


Figure 1 - Schéma du dispositif logique

Toutes les opérations de l'algèbre de la logique sont définies tables de vérité valeurs. La table de vérité détermine le résultat de l'opération pour tout le monde est possible x valeurs logiques des instructions originales. Le nombre d'options reflétant le résultat des opérations appliquées dépendra du nombre d'instructions dans l'expression logique. Si le nombre d'énoncés dans une expression logique est N, alors la table de vérité contiendra 2 N lignes, puisqu'il existe 2 N combinaisons différentes de valeurs d'argument possibles.

Opération NON - négation logique (inversion)

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

Opération OU - addition logique (disjonction, union)

Opération ET - multiplication logique (conjonction)

Opération « IF-THEN » - conséquence logique (implication)

Opération « A si et seulement si B » (équivalence, équivalence)

Opération « Addition modulo 2 » (XOR, exclusif ou, disjonction stricte)

Priorité des opérations logiques

• Actions entre parenthèses
• Inversion
• Conjonction (&)
• Disjonction (V), OU exclusif (XOR), somme modulo 2
• Implications (→)
• Équivalence (↔)

Forme normale disjonctive parfaite

1. Chaque terme logique de la formule contient toutes les variables incluses dans la fonction F(x 1,x 2,...x n).
2. Tous les termes logiques de la formule sont différents.
3. Pas un seul terme logique ne contient une variable et sa négation.
4. Aucun terme logique dans une formule ne contient deux fois la même variable.

Forme normale conjonctive parfaite

1. Toutes les disjonctions élémentaires contiennent toutes les variables incluses dans la fonction F(x 1 ,x 2 ,...x n).
2. Toutes les disjonctions élémentaires sont différentes.
3. Chaque disjonction élémentaire contient une fois une variable.
4. Pas une seule disjonction élémentaire ne contient une variable et sa négation.

142. Trouvez la plus grande solution binaire sur un octet de l'équation
.

143. Trouver X, Si .

144. La séquence des énoncés est déterminée par la relation récurrente suivante : . Les déclarations sont données, à la fois vraies et fausses. La déclaration est-elle vraie ou fausse ? Comment s’exprime-t-il ?

145. Combien de solutions différentes une équation logique a-t-elle ?
?

146. Combien de solutions différentes une équation logique a-t-elle ?
?

147. Combien de solutions différentes une équation logique a-t-elle :
.

148. Combien de solutions différentes une équation logique a-t-elle : .

149. Combien de solutions différentes une équation logique a-t-elle : .

150. Combien de solutions différentes l'équation logique a-t-elle : .

151. Combien de solutions différentes une équation logique a-t-elle :
.

152. Résolvez l'équation :

153. Trouvez toutes les différentes solutions de l'équation : .

Trouvez les racines d'une équation logique :

Trouvez les racines des systèmes d'équations logiques :

Trouvez le nombre de solutions aux systèmes d’équations logiques suivants :

183. (Problème d'économie) Construisez un schéma de circuit électrique pour l'entrée d'un immeuble de trois étages, de sorte qu'un interrupteur à n'importe quel étage puisse allumer et éteindre les lumières dans toute l'entrée.

184. (Machine d'urgence) Il y a trois machines sur le site de l'atelier - deux en état de marche, la troisième d'urgence. Il est nécessaire de relier les machines par une ligne automatique afin que la troisième machine soit allumée alors, et seulement alors, lorsqu'au moins une des deux premières machines s'arrête.

185. Supposons que dans un certain concours, la question de l'admission d'un participant particulier au tour suivant soit décidée par trois membres du jury : A, B, C. La décision est positive si et seulement si au moins deux membres du jury sont favorables à l'admission, et parmi eux doit figurer le président du jury. AVEC. Il est nécessaire de développer un dispositif de vote dans lequel chaque membre du jury appuie sur l'un des deux boutons - "Pour" ou "Contre", et le résultat du vote des trois membres du jury est déterminé par l'allumage ou non du signal lumineux (la décision est prise ) ou pas (la décision n'est pas prise).

186. Trois enseignants sélectionnent des problèmes pour l'Olympiade. Vous avez le choix entre plusieurs tâches. Pour chaque tâche, chaque enseignant exprime son avis : une tâche facile (0) ou une tâche difficile (1). Une tâche est incluse dans la tâche de l'Olympiade si au moins deux enseignants la jugent difficile, mais si les trois enseignants la considèrent comme difficile, alors une telle tâche n'est pas incluse dans la tâche de l'Olympiade comme trop difficile. Établissez un schéma fonctionnel d'un appareil qui produira 1 si la tâche est incluse dans la tâche Olympiade, et 0 si elle n'est pas incluse.

187. Écrivez la formule développée du circuit logique suivant :

191. Il n'y a que deux connecteurs et un onduleur. Est-il possible à partir de ces trois éléments logiques (portes) de construire un circuit logique équivalent au circuit d'expression. A quoi ressemble ce schéma ?

192. Il n'y a qu'un conjoncteur, un disjoncteur et un onduleur. Est-il possible de construire à partir de ces éléments un circuit logique équivalent à un circuit d'expression logique ? Les trois vannes doivent être utilisées. A quoi ressemble ce schéma ?