Méthode de cartographie pour résoudre des systèmes d'équations logiques. Logiques

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.

Méthodes de résolution de 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, de raisonner de manière convaincante, de formuler des hypothèses et 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 permettant d'établir la vérité ou la fausseté de certaines affirmations sur la base de la vérité ou de la fausseté d'autres affirmations.

Maîtriser les bases de cette science est impossible sans résoudre des problèmes logiques. Tester le développement des compétences pour appliquer ses connaissances dans une situation nouvelle s'effectue par le biais du passage. Il s'agit notamment de la capacité de résoudre des problèmes logiques. Les tâches B15 de l'examen d'État unifié 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. Il s'agit de réduction à une équation, de construction d'une table de vérité, de décomposition, de solution séquentielle d'équations, etc.

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

Considérons méthode de réduction à une équation . Cette méthode consiste à transformer des équations logiques afin 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, si les équations contiennent des opérations logiques complexes, nous les remplaçons par des opérations basiques : « 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 transformer l'équation résultante en vous basant sur les lois de l'algèbre logique et obtenir une solution spécifique au système.

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

Imaginons l'implication à travers les opérations de base « OU » et « NON » :

Puisque les côtés gauches des équations sont égaux à 1, nous pouvons les combiner en utilisant l’opération « ET » en une seule équation équivalente au système d’origine :

On ouvre la première parenthèse selon la loi de De Morgan et on transforme le résultat obtenu :

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

La méthode suivante est construire des tables de vérité . Puisque les quantités logiques n'ont que deux valeurs, vous pouvez simplement parcourir toutes les options et trouver parmi elles celles pour lesquelles un 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 droite avec les valeurs requises.

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

La ligne pour laquelle les conditions de la tâche sont remplies est mise en évidence en gras. Donc A =0, B =0 et C =1.

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

Solution 3 : Laisser A = 0, alors :

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

Vous pouvez également utiliser la méthode solution séquentielle d'équations , à chaque étape en ajoutant une variable à l'ensemble considéré. Pour ce faire, il faut transformer les équations pour 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 dépend uniquement de A et B, et la deuxième équation de A et C. La variable A peut prendre 2 valeurs 0 et 1 :

De la première équation il résulte que , donc quand A = 0 et 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.

Décrivons la deuxième équation, à partir de laquelle nous déterminons les valeurs de C pour chaque option. Lorsque 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. À UNE= 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'examen d'État unifié en informatique, il est très souvent nécessaire de déterminer le nombre de solutions d'un système d'équations logiques, sans trouver les solutions elles-mêmes ; La principale façon de trouver le nombre de solutions d’un système d’équations logiques est remplacement de variables. Tout d'abord, vous devez simplifier autant que possible chacune des équations en vous basant sur les lois de l'algèbre logique, puis remplacer les parties complexes des équations par de nouvelles variables et déterminer le nombre de solutions au nouveau système. Ensuite, revenez au remplacement et déterminez le nombre de solutions pour celui-ci.

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

Solution:Introduisons de nouvelles variables : X = A → B et Y = C → D . En tenant compte des nouvelles variables, l'équation s'écrira comme suit : X + Oui = 1.

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

La façon suivante de déterminer le nombre de solutions d'un système d'équations logiques est arbre binaire. Examinons cette méthode à l'aide d'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 de la première équation on obtient queX 2 c'est aussi vrai, à partir du deuxième -X 3 =1, et ainsi de suite jusqu'à xm= 1. Donc l’ensemble (1 ; 1 ; … ; 1) de m les unités sont la solution du système. Laisse-le maintenantX 1 =0, alors à partir de la première équation nous avonsX 2 =0 ou X 2 =1.

Quand X 2 vrai, nous obtenons que les variables restantes sont également vraies, c'est-à-dire que l'ensemble (0 ; 1 ; ... ; 1) est une solution du système. ÀX 2 =0 on obtient ça X 3 =0 ou X 3 =, et ainsi de suite. En passant à 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 des 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 égal m +1.

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

Réécrivons le système d'équations sous la forme :

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

Créons 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). Un 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 à la fois, 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 correcte.

Pour résumer tout ce qui précède, je voudrais attirer votre attention sur le fait que toutes les méthodes évoquées ne sont pas universelles. Lors de la résolution de chaque système d'équations logiques, il convient de prendre en compte ses caractéristiques, sur la base desquelles la méthode de solution doit être choisie.

Littérature:

1. Problèmes logiques / O.B. Bogomolov – 2e éd. – M. : BINOM. Laboratoire de la Connaissance, 2006. – 271 p. : ill.

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

Noskin Andreï Nikolaïevitch,
Professeur d'informatique
catégorie de qualification la plus élevée,
Candidat en sciences militaires, professeur agrégé
Lycée GBOU n° 1575, Moscou

Méthode de cartographie optimisée pour résoudre le problème 23 de l'examen d'État unifié KIM en informatique et TIC

L'une des tâches les plus difficiles de l'examen d'État unifié KIM est le problème 23, dans lequel vous devez trouver le nombre d'ensembles différents de valeurs de variables logiques qui satisfont à la condition spécifiée.
Cette tâche est peut-être la tâche la plus difficile de l'examen d'État unifié KIM en informatique et TIC. En règle générale, pas plus de 5 % des candidats y parviennent (1).
Un si faible pourcentage d’élèves ayant accompli cette tâche s’explique par les éléments suivants :
- les élèves peuvent confondre (oublier) les signes des opérations logiques ;
- des erreurs mathématiques lors de l'exécution des calculs ;
- des erreurs de raisonnement lors de la recherche d'une solution ;
- des erreurs dans le processus de simplification des expressions logiques ;
- les enseignants recommandent de résoudre ce problème après avoir terminé tout le travail, car la probabilité de
les erreurs sont très importantes et le « poids » de la tâche n’est qu’un point primordial.
De plus, certains enseignants eux-mêmes ont du mal à résoudre ce type de problèmes et tentent donc de résoudre des problèmes plus simples avec les enfants.
Ce qui complique également la situation, c'est que dans ce bloc, il existe un grand nombre de tâches différentes et qu'il est impossible de choisir un modèle de solution.
Pour corriger cette situation, la communauté pédagogique finalise les deux principales méthodes de résolution de problèmes de ce type : la résolution par chaînes de bits (2) et la méthode du mappage (3).
La nécessité d'affiner (optimiser) ces méthodes est due au fait que les tâches changent constamment tant en structure qu'en nombre de variables (un seul type de variables X, deux types de variables X et Y, trois types : X, Y ,Z).
La difficulté de maîtriser ces méthodes de résolution de problèmes est confirmée par le fait que sur le site de K.Yu. Polyakov, il existe 38 analyses de ce type de problème (4). Certaines analyses proposent plusieurs types de solutions à un problème.
Récemment, lors de l'examen d'État unifié KIM en informatique, des problèmes sont survenus avec deux types de variables X et Y.
J'ai optimisé la méthode d'affichage et j'encourage mes élèves à utiliser la méthode améliorée.
Cela donne des résultats. Le pourcentage de mes étudiants qui réussissent à faire cette tâche varie jusqu'à 43% de ceux qui réussissent. En règle générale, chaque année, de 25 à 33 personnes de toutes les 11e années passent l'examen d'État unifié en informatique.
Avant l'apparition de problèmes avec deux types de variables, les élèves utilisaient la méthode de cartographie avec beaucoup de succès, mais après l'apparition de Y dans l'expression logique, j'ai commencé à remarquer que les réponses des enfants ne coïncidaient plus avec les tests. Il s'est avéré qu'ils ne savaient pas très bien comment créer un tableau de mappages avec un nouveau type de variable. Puis l'idée m'est venue que pour plus de commodité, l'expression entière devrait être réduite à un seul type de variable, comme cela convient aux enfants.
Je vais donner cette technique plus en détail. Pour plus de commodité, je le considérerai en utilisant l'exemple du système d'expressions logiques donné en (4).
Combien de solutions différentes possède un système d’équations logiques ?

(x1 ^ oui 1)=(¬x 2 V ¬ oui 2 )
(x2 ^ et 2)= (¬ X 3 V ¬ oui 3 )
...
(x5 ^ et 5) = (¬ X 6 V ¬ oui 6 )

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

5. Remplissez le tableau en calculant le nombre de paires de variables pour lesquelles le système a une solution.

6. Additionnez tous les résultats : 9 + 9 + 9 + 27 = 54
7. Réponse : 54.
La méthode optimisée ci-dessus pour résoudre le problème 23 de l'examen d'État unifié KIM a permis aux étudiants de reprendre confiance et de résoudre avec succès ce type de problème.

Littérature:

1. FIPI. Recommandations méthodologiques pour les enseignants, préparées sur la base d'une analyse des erreurs typiques des participants à l'examen d'État unifié 2015 en SCIENCES DE L'INFORMATION et TIC. Mode d'accès : http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

Comment résoudre certains problèmes des sections A et B de l'examen d'informatique

Lecon 3. Logiques. Fonctions logiques. Résoudre des équations

Un grand nombre de problèmes de l'examen d'État unifié sont consacrés à la logique propositionnelle. Pour résoudre la plupart d'entre eux, il suffit de connaître les lois fondamentales de la logique propositionnelle, la connaissance des tables de vérité des fonctions logiques à une et deux variables. Je vais donner les lois fondamentales de la logique propositionnelle.

1. Commutativité de la disjonction et de la conjonction :
   une ˅ b ≡ b ˅ une
   une^b ≡ b^une
2. Loi distributive concernant la disjonction et la conjonction :
   une ˅ (b^с) ≡ (une ˅ b) ^(une ˅ с)
   une ^ (b ˅ c) ≡ (une ^ b) ˅ (une ^ c)
3. Négation de négation :
   ¬(¬a) ≡ une
4. Cohérence:
   un ^ ¬а ≡ faux
5. Tiers exclusif :
   a ˅ ¬а ≡ vrai
6. Les lois de De Morgan :
   ¬(une ˅ b) ≡ ¬une ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Simplification:
   une ˄ une ≡ une
   une ˅ une ≡ une
   une ˄ vrai ≡ une
   a ˄ faux ≡ faux
8. Absorption:
   une ˄ (une ˅ b) ≡ une
   une ˅ (une ˄ b) ≡ une
9. Remplacement de l'implication
   une → b ≡ ¬une ˅ b
10. Remplacement d'identité
    une ≡ b ≡(une ˄ b) ˅ (¬une ˄ ¬b)

Représentation des fonctions logiques

Toute fonction logique de n variables - F(x 1, x 2, ... x n) peut être spécifiée par une table de vérité. Un tel tableau contient 2n ensembles de variables, pour chacun desquels est spécifiée la valeur d'une fonction sur cet ensemble. Cette méthode est efficace lorsque le nombre de variables est relativement faible. Déjà pour n > 5 la représentation devient peu visible.

Une autre façon consiste à définir la fonction par une formule utilisant des fonctions connues assez simples. Un système de fonctions (f 1, f 2, ... f k) est dit complet si une fonction logique peut être exprimée par une formule contenant uniquement des fonctions f i.

Le système de fonctions (¬, ˄, ˅) est complet. Les lois 9 et 10 sont des exemples démontrant comment l'implication et l'identité s'expriment à travers la négation, la conjonction et la disjonction.

En fait, un système de deux fonctions – négation et conjonction ou négation et disjonction – est également complet. Des lois de De Morgan découlent des idées qui permettent d'exprimer une conjonction par négation et disjonction et, par conséquent, d'exprimer une disjonction par négation et conjonction :

(une ˅ b) ≡ ¬(¬une ˄ ¬b)
(une ˄ b) ≡ ¬(¬une ˅ ¬b)

Paradoxalement, un système constitué d’une seule fonction est complet. Il existe deux fonctions binaires : l'anticonjonction et l'antidisjonction, appelées flèche de Peirce et trait de Schaeffer, représentant un système creux.

Les fonctions de base des langages de programmation incluent généralement l'identité, la négation, la conjonction et la disjonction. Dans les problèmes liés à l'examen d'État unifié, outre ces fonctions, des implications sont souvent trouvées.

Examinons quelques problèmes simples impliquant des fonctions logiques.

Problème 15 :

Un fragment de la table de vérité est donné. Laquelle des trois fonctions données correspond à ce fragment ?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Fonction numéro 3.

Pour résoudre le problème, vous devez connaître les tables de vérité des fonctions de base et vous rappeler les priorités des opérations. Permettez-moi de vous rappeler que la conjonction (multiplication logique) a une priorité plus élevée et est exécutée plus tôt que la disjonction (addition logique). Lors des calculs, il est facile de remarquer que les fonctions avec les nombres 1 et 2 dans le troisième ensemble ont la valeur 1 et pour cette raison ne correspondent pas au fragment.

Problème 16 :

Lequel des nombres donnés satisfait à la condition :

(les chiffres, en commençant par le chiffre le plus significatif, sont classés par ordre décroissant) → (nombre - pair) ˄ (chiffre faible - pair) ˄ (chiffre supérieur - impair)

S'il y en a plusieurs, indiquez le plus grand.

1. 13579
2. 97531
3. 24678
4. 15386

La condition est satisfaite par le chiffre 4.

Les deux premiers nombres ne satisfont pas à la condition car le chiffre le plus bas est impair. Une conjonction de conditions est fausse si l’un des termes de la conjonction est faux. Pour le troisième nombre, la condition du chiffre le plus élevé n’est pas remplie. Pour le quatrième numéro, les conditions imposées sur les chiffres bas et hauts du numéro sont remplies. Le premier terme de la conjonction est également vrai, puisque l’implication est vraie si sa prémisse est fausse, ce qui est le cas dans ce cas.

Problème 17 : Deux témoins ont donné le témoignage suivant :

Premier témoin : Si A est coupable, alors B est encore plus coupable et C est innocent.

Deuxième témoin : Deux sont coupables. Et l’un des autres est définitivement coupable, mais je ne peux pas dire qui exactement.

Quelles conclusions sur la culpabilité de A, B et C peut-on tirer du témoignage ?

Réponse : Il ressort du témoignage que A et B sont coupables et C est innocent.

Solution : Bien entendu, la réponse peut être donnée en fonction du bon sens. Mais regardons comment cela peut être fait de manière stricte et formelle.

La première chose à faire est de formaliser les déclarations. Introduisons trois variables logiques - A, B et C, dont chacune a la valeur vrai (1) si le suspect correspondant est coupable. Alors le témoignage du premier témoin est donné par la formule :

A → (B ˄ ¬C)

Le témoignage du deuxième témoin est donné par la formule :

UNE ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Le témoignage des deux témoins est présumé vrai et représente la conjonction des formules correspondantes.

Construisons une table de vérité pour ces lectures :

La preuve sommaire est vraie dans un seul cas, conduisant à une réponse claire : A et B sont coupables et C est innocent.

De l'analyse de ce tableau, il résulte également que le témoignage du deuxième témoin est plus informatif. De la véracité de son témoignage, seules deux options possibles découlent : A et B sont coupables et C est innocent, ou A et C sont coupables et B est innocent. Le témoignage du premier témoin est moins informatif - il existe 5 options différentes correspondant à son témoignage. Ensemble, les témoignages des deux témoins donnent une réponse claire sur la culpabilité des suspects.

Équations logiques et systèmes d'équations

Soit F(x 1, x 2, …x n) une fonction logique de n variables. L'équation logique ressemble à :

F(x 1, x 2, …x n) = C,

La constante C vaut 1 ou 0.

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

F(x 1 , x 2 , …x n) = 1

En effet, donnons l'équation :

F(x 1, x 2, …x n) = 0

Dans ce cas, on peut passer à l’équation équivalente :

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

Fk (x 1 , x 2 , …x n) = 1

La solution d'un 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 à un système d'équations logiques, il faut trouver un ensemble sur lequel la fonction logique Ф est vraie, représentant la conjonction des fonctions originales F :

Ф = F 1 ˄ F 2 ˄ … F k

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

Dans certains problèmes USE visant à trouver des solutions à un système d'équations logiques, le nombre de variables atteint 10. La construction d'une table de vérité devient alors une tâche presque impossible. Résoudre le problème nécessite une approche différente. Pour un système arbitraire d’équations, il n’existe pas de méthode générale autre que l’énumération permettant de résoudre de tels problèmes.

Dans les problèmes proposés à l'examen, la solution repose généralement sur la prise en compte des spécificités du système d'équations. Je le répète, à part essayer toutes les options pour un ensemble de variables, il n’existe aucun moyen général 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 en utilisant des 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 construirons son analogue - un arbre de décision binaire. Chaque branche de cet arbre correspond à une solution et spécifie un ensemble sur lequel la fonction Ф vaut 1. Le nombre de branches dans l'arbre de décision coïncide avec le nombre de solutions du système d'équations.

J'expliquerai ce qu'est un arbre de décision binaire et comment il est construit à l'aide d'exemples de plusieurs problèmes.

Problème 18

Combien d'ensembles différents de valeurs des variables logiques x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existent-ils qui satisfont au 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 - x 1, x 2, ... x 5. La première équation peut quant à elle être considérée comme un système de 5 équations. Comme nous l'avons montré, le système d'équations représente en réalité la conjonction de fonctions logiques. L’inverse est également vrai : une conjonction de conditions peut être considérée comme un système d’équations.

Construisons un arbre de décision pour l'implication (x1→ x2) - le premier terme de la conjonction, qui peut être considéré comme la première équation. Voici à quoi ressemble une représentation 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 X 1 . 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 reflètent uniquement les valeurs possibles de la variable X 2 pour lesquelles l'équation est vraie. Puisque l'équation spécifie une implication, une branche sur laquelle X 1 a la valeur 1 nécessite que sur cette branche X 2 ait la valeur 1. Une branche sur laquelle X 1 a la valeur 0 produit deux branches avec les valeurs de X 2 égal à 0 et 1 L'arbre construit définit trois solutions, sur lesquelles l'implication X 1 → X 2 prend la valeur 1. Sur chaque branche, un ensemble correspondant de valeurs variables est écrit, donnant 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 X 2 → X 3 . 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 X 2 a déjà des valeurs dans l'arbre, alors sur toutes les branches où la variable X 2 a une valeur de 1, la variable X 3 aura également une valeur de 1. Pour de telles branches, la construction de l'arbre continue au niveau suivant, mais de nouvelles branches n'apparaissent pas. La branche unique où la variable X 2 a la valeur 0 se ramifiera en deux branches où la variable X 3 recevra les valeurs 0 et 1. Ainsi, chaque ajout d'une nouvelle équation, compte tenu de ses spécificités, ajoute une solution. Première équation originale :

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
a 6 solutions. Voici à quoi ressemble l’arbre de décision complet pour cette équation :

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

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

La seule différence est que l'équation utilise des variables Y. Cette équation comporte également 6 solutions. Puisque chaque solution pour les variables X i peut être combinée avec chaque solution pour les variables Y j , le nombre total de solutions est de 36.

A noter que l'arbre de décision construit donne non seulement le nombre de solutions (en fonction du 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 des variables logiques x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 qui satisfont à toutes les conditions énumérées ci-dessous ?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1 → y1) = 1

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.

De l'équation X 1 → Y 1, il s'ensuit que lorsque X 1 a la valeur 1 (une telle solution existe), alors Y 1 a également la valeur 1. Ainsi, il existe un ensemble sur lequel X 1 et Y 1 ont les valeurs ​​1. Lorsque X 1 est égal à 0, Y 1 peut avoir n'importe quelle valeur, à la fois 0 et 1. Par conséquent, chaque ensemble avec X 1 égal à 0, et il existe 5 de ces ensembles, correspond aux 6 ensembles avec Y variables. Le nombre total de solutions est donc de 31.

Problème 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Solution : En nous rappelant les équivalences de base, nous écrivons notre équation sous la forme :

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

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

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Cette équation a deux solutions lorsque tous les X i valent 1 ou 0.

Problème 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Solution : Tout comme dans le problème 20, nous passons des implications cycliques aux identités, en réécrivant l'équation sous la forme :

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

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

Problème 22

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

((X1 ≡X 2) ˄ (X3 ≡X 4)) ˅(¬(X1 ≡X 2) ˄ ¬(X3 ≡X4)) = 0

((X3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X3 ≡X 4) ˄ ¬(X5 ≡X6)) = 0

((X5 ≡X 6) ˄ (X7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X7 ≡X8)) = 0

((X7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0

Réponse : 64

Solution : Passons de 10 variables à 5 variables en introduisant le changement de variables suivant :

Oui 1 = (X 1 ≡ X 2) ; Oui 2 = (X 3 ≡ X 4) ; Oui 3 = (X 5 ≡ X 6) ; Oui 4 = (X 7 ≡ X 8) ; Oui 5 = (X 9 ≡ X 10) ;

Alors la première équation prendra la forme :

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

L'équation peut être simplifiée en l'écrivant ainsi :

(Oui 1 ≡ Oui 2) = 0

Passant à la forme traditionnelle, nous écrivons le système après simplifications sous la forme :

¬(Oui 1 ≡ Oui 2) = 1

¬(Oui 2 ≡ Oui 3) = 1

¬(Oui 3 ≡ Oui 4) = 1

¬(Oui 4 ≡ Oui 5) = 1

L'arbre de décision de ce système est simple et se compose de deux branches avec des valeurs variables alternées :

En revenant aux variables X d'origine, notez que pour chaque valeur de la variable Y, il y a 2 valeurs dans les variables X, donc chaque solution dans les variables Y génère 2 5 solutions dans les variables X. Les deux branches génèrent 2 * 2. 5 solutions, donc le nombre total de solutions est de 64.

Comme vous pouvez le constater, chaque problème de résolution d'un système d'équations nécessite sa propre approche. Une technique courante consiste à effectuer des transformations équivalentes pour simplifier les équations. Une technique courante consiste à construire des arbres de décision. L'approche utilisée rappelle en partie la construction d'une table de vérité avec la particularité que tous les ensembles de valeurs possibles de variables ne sont pas construits, mais uniquement ceux sur lesquels la fonction prend la valeur 1 (vrai). Souvent, dans les problèmes proposés, il n'est pas nécessaire de construire un arbre de décision complet, car dès le stade initial, il est possible d'établir le modèle d'apparition de nouvelles branches à chaque niveau ultérieur, comme cela a été fait, par exemple, dans le problème 18. .

En général, les problèmes impliquant la recherche de solutions à un système d’équations logiques constituent de bons exercices mathématiques.

Si le problème est difficile à résoudre manuellement, vous pouvez alors confier la solution à l'ordinateur en écrivant un programme approprié pour résoudre des équations et des systèmes d'équations.

Il n'est pas difficile d'écrire un tel programme. Un tel programme s'acquittera facilement de toutes les tâches proposées lors de l'examen d'État unifié.

Curieusement, la tâche consistant à trouver des solutions à des systèmes d'équations logiques est difficile pour un ordinateur, et il s'avère qu'un ordinateur a ses limites. L'ordinateur peut assez facilement résoudre des problèmes dans lesquels le nombre de variables est de 20 à 30, mais il commencera à réfléchir longtemps à des problèmes de plus grande taille. Le fait est que la fonction 2 n, qui spécifie le nombre d'ensembles, est une exponentielle qui croît rapidement à mesure que n augmente. Si rapide qu'un ordinateur personnel ordinaire ne peut pas faire face à une tâche comportant 40 variables par jour.

Programme en langage C# pour résoudre des équations logiques

Écrire un programme pour résoudre des équations logiques est utile pour de nombreuses raisons, ne serait-ce que parce que vous pouvez l'utiliser pour vérifier l'exactitude de votre propre solution aux problèmes de test de l'examen d'État unifié. Une autre raison est qu'un tel programme est un excellent exemple de tâche de programmation qui répond aux exigences des tâches de catégorie C de l'examen d'État unifié.

L'idée de construire un programme est simple : elle est basée sur une recherche complète de tous les ensembles possibles de valeurs de variables. Puisque pour une équation logique ou un système d'équations donné, le nombre de variables n est connu, alors le nombre d'ensembles est également connu - 2 n qui doivent être triés. En utilisant les fonctions de base du langage C# - négation, disjonction, conjonction et identité, il n'est pas difficile d'écrire un programme qui, pour un ensemble de variables donné, calcule la valeur de la fonction logique correspondant à une équation logique ou un système d'équations. .

Dans un tel programme, vous devez construire une boucle basée sur le nombre d'ensembles, dans le corps de la boucle, en utilisant le numéro de l'ensemble, former l'ensemble lui-même, calculer la valeur de la fonction sur cet ensemble, et si cela la valeur est 1, alors l’ensemble donne une solution à l’équation.

La seule difficulté qui se pose lors de la mise en œuvre du programme est liée à la tâche de générer lui-même l'ensemble des valeurs variables en fonction du nombre défini. La beauté de ce problème est que cette tâche apparemment difficile se résume en réalité à un problème simple qui s’est déjà posé à plusieurs reprises. En effet, il suffit de comprendre que l'ensemble des valeurs variables correspondant au nombre i, constitué de zéros et de uns, représente la représentation binaire du nombre i. Ainsi, la tâche complexe d'obtention d'un ensemble de valeurs variables par nombre défini est réduite à la tâche familière de conversion d'un nombre en binaire.

Voici à quoi ressemble une fonction en C# qui résout notre problème :

///

///

/// fonction logique - méthode,

/// dont la signature est précisée par le délégué DF

///

/// nombre de variables

/// nombre de solutions

static int SolveEquations (DF fun, int n)

bool set = nouveau bool[n];

int m = (int)Math.Pow(2, n); //nombre d'ensembles

int p = 0, q = 0, k = 0 ;

//Recherche complète par nombre d'ensembles

pour (int je = 0; je< m; i++)

//Formation de l'ensemble suivant - ensemble,

//spécifié par la représentation binaire du nombre i

pour (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Calculer la valeur de la fonction sur l'ensemble

Pour comprendre le programme, j'espère que les explications données sur l'idée du programme et les commentaires dans son texte sont suffisants. Je me concentrerai uniquement sur l'explication du titre de la fonction donnée. La fonction SolveEquations a deux paramètres d'entrée. Le paramètre fun spécifie une fonction logique correspondant à l'équation ou au système d'équations à résoudre. Le paramètre n spécifie le nombre de variables amusantes. Par conséquent, la fonction SolveEquations renvoie le nombre de solutions de la fonction logique, c'est-à-dire le nombre d'ensembles sur lesquels la fonction est évaluée comme vraie.

Il est courant pour les écoliers qu'une fonction F(x) ait un paramètre d'entrée x qui est une variable de type arithmétique, chaîne ou logique. Dans notre cas, une conception plus puissante est utilisée. La fonction SolveEquations fait référence à des fonctions d'ordre supérieur - des fonctions de type F(f), dont les paramètres peuvent être non seulement des variables simples, mais également des fonctions.

La classe de fonctions pouvant être transmise en paramètre à la fonction SolveEquations est spécifiée comme suit :

délégué bool DF(bool vars);

Cette classe possède toutes les fonctions auxquelles est passé en paramètre un ensemble de valeurs de variables logiques spécifiées par le tableau vars. Le résultat est une valeur booléenne représentant la valeur de la fonction sur cet ensemble.

Enfin, voici un programme qui utilise la fonction SolveEquations pour résoudre plusieurs systèmes d'équations logiques. La fonction SolveEquations fait partie de la classe ProgramCommon ci-dessous :

classe ProgrammeCommon

délégué bool DF(bool vars);

static void Main (arguments de chaîne)

Console.WriteLine("Et fonctions - " +

Résoudre des équations (FunAnd, 2));

Console.WriteLine("La fonction a 51 solutions - " +

Résoudre des équations (Fun51, 5));

Console.WriteLine("La fonction a 53 solutions - " +

Résoudre des équations (Fun53, 10));

bool statique FunAnd (vars bool)

renvoyer les variables && vars;

bool statique Fun51 (vars booléens)

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

bool statique Fun53 ​​(vars booléens)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Voici à quoi ressemblent les résultats de la solution pour ce programme :

10 tâches pour un travail indépendant

1. Lesquelles des trois fonctions sont équivalentes :
   1. (X → Oui) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Voici un fragment de la table de vérité :

À laquelle des trois fonctions correspond ce fragment :

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Le jury est composé de trois personnes. La décision est prise si le président du jury vote en faveur, soutenu par au moins un des membres du jury. Sinon, aucune décision n'est prise. Construire une fonction logique qui formalise le processus de prise de décision.
5. X l'emporte sur Y si quatre lancers de pièces donnent trois fois face. Définissez une fonction logique qui décrit le gain de X.
6. Les mots d’une phrase sont numérotés à partir de un. Une phrase est considérée comme correctement construite si les règles suivantes sont respectées :
   1. Si un mot pair se termine par une voyelle, alors le mot suivant, s'il existe, doit commencer par une voyelle.
   2. Si un mot impair se termine par une consonne, alors le mot suivant, s'il existe, doit commencer par une consonne et se terminer par une voyelle.
      Parmi les phrases suivantes, lesquelles sont correctement construites :
   3. Maman a lavé Masha avec du savon.
   4. Un leader est toujours un modèle.
   5. La vérité est bonne, mais le bonheur est meilleur.
7. Combien de solutions l'équation a-t-elle :
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Énumérez toutes les solutions de l’équation :
   (une → b) → c = 0
9. Combien de solutions le système d’équations suivant a-t-il :
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X0 → X5 = 1
10. Combien de solutions l'équation a-t-elle :
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Réponses aux problèmes :

1. Les fonctions b et c sont équivalentes.
2. Le fragment correspond à la fonction b.
3. Soit la variable logique P prendre la valeur 1 lorsque le président du jury vote « pour » la décision. Les variables M 1 et M 2 représentent les avis des membres du jury. La fonction logique qui spécifie de prendre une décision positive peut s'écrire comme suit :
   P ˄ (M 1 ˅ M 2)
4. Laissez la variable logique P i prendre la valeur 1 lorsque le ième tirage au sort tombe sur face. La fonction logique qui spécifie le gain X peut s'écrire comme suit :
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Phrase b.
6. L'équation a 3 solutions : (a = 1 ; b = 1 ; c = 0) ; (une = 0 ; b = 0 ; c = 0) ; (une = 0 ; b = 1 ; c = 0)

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, où J, K, L, M, N sont des variables logiques ?

Explication.

L'expression (N ∨ ¬N) est vraie pour tout N, donc

J ∧ ¬K ∧ L ∧ ¬M = 0.

Appliquons la négation aux deux côtés de l'équation logique et utilisons la loi de De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Nous obtenons ¬J ∨ K ∨ ¬L ∨ M = 1.

Une somme logique est égale à 1 si au moins un de ses énoncés constitutifs est égal à 1. Par conséquent, l'équation résultante est satisfaite par toute combinaison de variables logiques, sauf le cas où toutes les quantités incluses dans l'équation sont égales à 0. Chacune des les 4 variables peuvent être égales à 1 ou à 0, donc toutes les combinaisons possibles sont 2·2·2·2 = 16. L'équation a donc 16 −1 = 15 solutions.

Reste à noter que les 15 solutions trouvées correspondent à l'une des deux valeurs possibles de la variable logique N, l'équation originale comporte donc 30 solutions.

Réponse : 30

Combien de solutions différentes l’équation a-t-elle ?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

où J, K, L, M, N sont des variables logiques ?

La réponse n'a pas besoin d'énumérer tous les différents ensembles de valeurs de J, K, L, M et N pour lesquels cette égalité est valable. En réponse, vous devez indiquer le nombre de ces ensembles.

Explication.

On utilise les formules A → B = ¬A ∨ B et ¬(A ∨ B) = ¬A ∧ ¬B

Considérons la première sous-formule :

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Considérons la deuxième sous-formule

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Considérons la troisième sous-formule

1) M → J = 1 donc,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L ;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L ;

Combinons :

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 donc 4 solutions.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K ;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Combinons :

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L donc 4 solutions.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Réponse : 4 + 4 = 8.

Réponse : 8

Combien de solutions différentes l’équation a-t-elle ?

((K ∨ L) → (L ∧ M ∧ N)) = 0

où K, L, M, N sont des variables logiques ? La réponse n'a pas besoin de lister tous les différents ensembles de valeurs de K, L, M et N pour lesquels cette égalité est valable. En guise de réponse, vous devez indiquer le nombre de ces ensembles.

Explication.

Réécrivons l'équation en utilisant une notation plus simple pour les opérations :

((K + L) → (L M N)) = 0

1) de la table de vérité de l'opération « implication » (voir le premier problème) il s'ensuit que cette égalité est vraie si et seulement si en même temps

K + L = 1 et L M N = 0

2) de la première équation il résulte qu'au moins une des variables, K ou L, est égale à 1 (ou les deux ensemble) ; alors considérons trois cas

3) si K = 1 et L = 0, alors la deuxième égalité est valable pour tout M et N ; puisqu'il y a 4 combinaisons de deux variables booléennes (00, 01, 10 et 11), on a 4 solutions différentes

4) si K = 1 et L = 1, alors la deuxième égalité est vraie pour M · N = 0 ; il y a 3 de ces combinaisons (00, 01 et 10), nous avons 3 autres solutions

5) si K = 0, alors L = 1 (d'après la première équation) ; dans ce cas, la deuxième égalité est satisfaite lorsque M · N = 0 ; il y a 3 de ces combinaisons (00, 01 et 10), nous avons 3 autres solutions

6) au total on obtient 4 + 3 + 3 = 10 solutions.

Réponse : 10

Combien de solutions différentes l’équation a-t-elle ?

(K ∧ L) ∨ (M ∧ N) = 1

Explication.

L'expression est vraie dans trois cas, lorsque (K ∧ L) et (M ∧ N) sont égaux à 01, 11, 10, respectivement.

1) "01" K ∧ L = 0 ; M ∧ N = 1, => M, N sont égaux à 1, et K et L valent n'importe quoi sauf simultanément 1. Il y a donc 3 solutions.

2) "11" K ∧ L = 1 ; M ∧ N = 1. => 1 solution.

3) "10" K ∧ L = 1 ; M ∧ N = 0. => 3 solutions.

Réponse : 7.

Réponse : 7

Combien de solutions différentes l’équation a-t-elle ?

(X ∧ Y ∨ Z) ​​​​​​→ (Z ∨ P) = 0

où X, Y, Z, P sont des variables logiques ? La réponse n'a pas besoin d'énumérer tous les différents ensembles de valeurs pour lesquels cette égalité est valable. En guise de réponse, il vous suffit d'indiquer le nombre de ces ensembles.

Explication.

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​​​​​∨ (Z ∨ P) = 0 ;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0 ;

Le OU logique n’est faux que dans un cas : lorsque les deux expressions sont fausses.

Ainsi,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1 ; Oui = 1.

Il n’y a donc qu’une seule solution à l’équation.

Réponse 1

Combien de solutions différentes l’équation a-t-elle ?

(K ∨ L) ∧ (M ∨ N) = 1

où K, L, M, N sont des variables logiques ? La réponse n'a pas besoin d'énumérer tous les différents ensembles de valeurs de K, L, M et N pour lesquels cette égalité est valable. En guise de réponse, il vous suffit d'indiquer le nombre de ces ensembles.

Explication.

Le Et logique n'est vrai que dans un cas : lorsque toutes les expressions sont vraies.

K ∨ L = 1, M ∨ N = 1.

Chacune des équations donne 3 solutions.

Considérons l'équation A ∧ B = 1, si A et B prennent tous deux de vraies valeurs dans trois cas chacun, alors au total l'équation a 9 solutions.

La réponse est donc 9.

Réponse : 9

Combien de solutions différentes l’équation a-t-elle ?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

où A, B, C, D sont des variables logiques ?

La réponse n'a pas besoin d'énumérer tous les différents ensembles de valeurs A, B, C, D pour lesquels cette égalité est vraie. En réponse, vous devez indiquer le nombre de ces ensembles.

Explication.

Le « OU » logique est vrai lorsqu'au moins une des affirmations est vraie.

(D ∧ ¬D)= 0 pour tout D.

Ainsi,

(A → B)∧ C) = 1 => C = 1 ; A → B = 1 => ¬ A ∨ B = 1, ce qui nous donne 3 solutions possibles pour chaque D.

(D ∧ ¬ D)= 0 pour tout D, ce qui nous donne deux solutions (pour D = 1, D = 0).

Donc : solutions totales 2*3 = 6.

Total 6 solutions.

Réponse : 6

Combien de solutions différentes l’équation a-t-elle ?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

où K, L, M, N sont des variables logiques ? La réponse n'a pas besoin d'énumérer tous les différents ensembles de valeurs de K, L, M et N pour lesquels cette égalité est valable. En guise de réponse, il vous suffit d'indiquer le nombre de ces ensembles.

Explication.

Appliquons la négation aux deux côtés de l'équation :

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Le OU logique est vrai dans trois cas.

Option 1.

K ∧ L ∧ M = 1, alors K, L, M = 1 et ¬L ∧ M ∧ N = 0. N est arbitraire, c'est-à-dire 2 solutions.

Option 2.

¬L ∧ M ∧ N = 1, alors N, M = 1 ; L = 0, K quelconque, soit 2 solutions.

La réponse est donc 4.

Réponse : 4

A, B et C sont des entiers pour lesquels l'énoncé est vrai

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

À quoi B est égal si A = 45 et C = 43 ?

Explication.

1) ¬(A = B); (UNE> B) → (B> C); (B > A) → (C > B) ;

2) ces instructions simples sont reliées par l'opération ∧ (ET, conjonction), c'est-à-dire qu'elles doivent être exécutées simultanément ;

3) de ¬(A = B)=1 il s'ensuit immédiatement que A B ;

4) supposons que A > B, alors à partir de la deuxième condition on obtient 1 → (B > C) = 1 ; cette expression peut être vraie si et seulement si B > C = 1 ;

5) donc on a A > B > C, seul le nombre 44 correspond à cette condition ;

6) juste au cas où, vérifions également l'option A 0 →(B > C)=1 ;

cette expression est vraie pour tout B ; regardons maintenant la troisième condition que nous obtenons

cette expression peut être vraie si et seulement si C > B, et ici nous avons une contradiction, car il n'existe pas de nombre B pour lequel C > B > A.

Réponse : 44.

Réponse : 44

Construire une table de vérité pour une fonction logique

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

dans laquelle la colonne de valeurs de l'argument A est la représentation binaire du nombre 27, la colonne de valeurs de l'argument B est le nombre 77, la colonne de valeurs de l'argument C est le nombre 120. Le nombre dans la colonne est écrit de haut en bas du plus significatif au moins significatif (y compris l'ensemble des zéros). Convertissez la représentation binaire résultante des valeurs de la fonction X au système de nombres décimaux.

Explication.

Écrivons l'équation en utilisant une notation plus simple pour les opérations :

1) il s'agit d'une expression à trois variables, il y aura donc des lignes dans la table de vérité ; par conséquent, la représentation binaire des nombres utilisés pour construire les colonnes A, B et C du tableau doit être composée de 8 chiffres

2) convertir les nombres 27, 77 et 120 dans le système binaire, en ajoutant immédiatement jusqu'à 8 chiffres de zéros au début des nombres

3) il est peu probable que vous puissiez écrire immédiatement les valeurs de la fonction X pour chaque combinaison, il est donc pratique d'ajouter des colonnes supplémentaires au tableau pour calculer les résultats intermédiaires (voir tableau ci-dessous)

4) remplissez les colonnes du tableau :

la valeur est 1 uniquement dans les lignes où A = B

la valeur est 1 dans les lignes où B ou C = 1

la valeur est 0 uniquement dans les lignes où A = 1 et B + C = 0

la valeur est l'inverse de la colonne précédente (0 est remplacé par 1, et 1 est remplacé par 0)

le résultat de X (dernière colonne) est la somme logique des deux colonnes et

5) pour obtenir la réponse, écrivez les bits de la colonne X de haut en bas :

6) convertir ce nombre au système décimal :

Réponse : 171

Quel est le plus grand entier X pour lequel l'énoncé (10 (X+1)·(X+2)) est vrai ?

Explication.

Une équation est une opération d'implication entre deux relations :

1) Bien sûr, vous pouvez ici appliquer la même méthode que dans l'exemple 2208, mais vous devrez résoudre des équations quadratiques (je ne veux pas...) ;

2) Notez que par condition nous ne nous intéressons qu'aux nombres entiers, nous pouvons donc essayer de transformer d'une manière ou d'une autre l'expression originale, en obtenant un énoncé équivalent (nous ne sommes pas du tout intéressés par les valeurs exactes des racines !) ;

3) Considérons l'inégalité : évidemment, elle peut être soit un nombre positif, soit un nombre négatif ;

4) Il est facile de vérifier que dans le domaine l'énoncé est vrai pour tous les entiers , et dans le domaine - pour tous les entiers (afin de ne pas se tromper, il est plus pratique d'utiliser des inégalités non strictes, et , au lieu de et );

5) Par conséquent, pour les entiers, il peut être remplacé par une expression équivalente

6) le domaine de vérité d'une expression est l'union de deux intervalles infinis ;

7) Considérons maintenant la deuxième inégalité : il est évident qu'elle peut aussi être soit un nombre positif, soit un nombre négatif ;

8) Dans le domaine, la déclaration est vraie pour tous les entiers, et dans le domaine - pour tous les entiers, donc pour les entiers, elle peut être remplacée par une expression équivalente

9) le domaine de vérité de l'expression est un intervalle fermé ;

10) L'expression donnée est vraie partout, sauf pour les zones où et ;

11) Veuillez noter que la valeur ne convient plus, car là et , c'est-à-dire que l'implication donne 0 ;

12) Lors de la substitution de 2, (10 (2+1) · (2+2)), ou 0 → 0 qui satisfait à la condition.

La réponse est donc 2.

Réponse : 2

Quel est le plus grand entier X pour lequel l'énoncé est vrai

(50 (X+1)·(X+1)) ?

Explication.

Appliquons la transformation d'implication et transformons l'expression :

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Le OU logique est vrai lorsqu'au moins une instruction logique est vraie. Après avoir résolu les deux inégalités et en tenant compte de cela, nous voyons que le plus grand entier pour lequel au moins l'une d'entre elles est satisfaite est 7 (sur la figure, la solution positive de la deuxième inégalité est représentée en jaune et la première en bleu).

Réponse : 7

Indiquer les valeurs des variables K, L, M, N, auxquelles l'expression logique

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

FAUX. Écrivez la réponse sous forme de chaîne de 4 caractères : les valeurs des variables K, L, M et N (dans cet ordre). Ainsi, par exemple, la ligne 1101 correspond au fait que K=1, L=1, M=0, N=1.

Explication.

Tâche 3584 en double.

Réponse : 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Explication.

Appliquons la transformation d'implication :

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Appliquons la négation aux deux côtés de l'équation :

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Transformons :

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Par conséquent, M = 0, N = 0, considérons maintenant (¬K ∧ L ∨ M ∧ L) :

du fait que M = 0, N = 0 il s'ensuit que M ∧ L = 0, alors ¬K ∧ L = 1, c'est-à-dire K = 0, L = 1.

Réponse : 0100

Préciser les valeurs des variables K, L, M, N pour lesquelles l'expression logique

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

FAUX. Écrivez votre réponse sous la forme d'une chaîne de quatre caractères : les valeurs des variables K, L, M et N (dans cet ordre). Ainsi, par exemple, la ligne 1101 correspond au fait que K=1, L=1, M=0, N=1.

Explication.

Écrivons l'équation en utilisant une notation d'opérations plus simple (la condition « l'expression est fausse » signifie qu'elle est égale au zéro logique) :

1) de la formulation de la condition, il s'ensuit que l'expression ne doit être fausse que pour un ensemble de variables

2) de la table de vérité de l'opération « implication » il résulte que cette expression est fausse si et seulement si en même temps

3) la première égalité (le produit logique est égal à 1) est satisfaite si et seulement si et ; il en résulte (la somme logique est égale à zéro), ce qui ne peut arriver que lorsque ; Ainsi, nous avons déjà défini trois variables

4) à partir de la deuxième condition, , pour et on obtient .

Duplique la tâche

Réponse : 1000

Spécifiez les valeurs des variables logiques P, Q, S, T, auxquelles l'expression logique

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) est faux.

Écrivez la réponse sous la forme d'une chaîne de quatre caractères : les valeurs des variables P, Q, S, T (dans cet ordre).

Explication.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ T)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Appliquons la transformation d'implication :

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Réponse : 0100

Préciser les valeurs des variables K, L, M, N pour lesquelles l'expression logique

(K → M) ∨ (L ∧ K) ∨ ¬N

FAUX. Écrivez votre réponse sous la forme d'une chaîne de quatre caractères : les valeurs des variables K, L, M et N (dans cet ordre). Ainsi, par exemple, la ligne 1101 correspond au fait que K=1, L=1, M=0, N=1.

Explication.

Le OU logique est faux si et seulement si les deux affirmations sont fausses.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Appliquons la transformation d'implication pour la première expression :

¬K ∨ M = 0 => K = 1, M = 0.

Considérons la deuxième expression :

(L ∧ K) ∨ ¬N = 0 (voir le résultat de la première expression) => L ∨ ¬N = 0 => L = 0, N = 1.

Réponse : 1001.

Réponse : 1001

Préciser les valeurs des variables K, L, M, N pour lesquelles l'expression logique

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

vrai. Écrivez votre réponse sous la forme d'une chaîne de quatre caractères : les valeurs des variables K, L, M et N (dans cet ordre). Ainsi, par exemple, la ligne 1101 correspond au fait que K=1, L=1, M=0, N=1.

Explication.

Le « ET » logique est vrai si et seulement si les deux affirmations sont vraies.

1) (K → M) = 1 Appliquer la transformation d'implication : ¬K ∨ M = 1

2) (K → ¬M) = 1 Appliquer la transformation d'implication : ¬K ∨ ¬M = 1

Il s’ensuit que K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Appliquer la transformation d'implication : K ∨ (M ∧ ¬L ∧ N) = 1 du fait que K = 0 on obtient :

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Réponse : 0011

On sait que pour les entiers X, Y et Z, l'énoncé suivant est vrai :

(Z Qu'est-ce que Z est égal si X=25 et Y=48 ?

Explication.

Après avoir remplacé les nombres, nous obtenons que Z = 47.

Veuillez noter que cette déclaration complexe se compose de trois simples

1) (Z 2) ces instructions simples sont reliées par l'opération ∧ (ET, conjonction), c'est-à-dire qu'elles doivent être exécutées simultanément.

3) de ¬(Z+1 24, et de ¬(Z+1 47.

4) de (Z Z Réponse : 47.

Réponse : 47

A, B et C sont des nombres entiers pour lesquels l'énoncé suivant est vrai :

(C Quelle est la valeur de C si A=45 et B=18 ?

Explication.

Le « ET » logique est vrai si et seulement si les deux affirmations sont vraies.

Remplaçons les nombres dans l'expression :

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

De 2) et 1) il résulte que C

Réponse : 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

Quelle est la valeur de A si C = 8 et B = 18 ?

Explication.

Le « ET » logique est vrai si et seulement si les deux affirmations sont vraies.

1) ¬(A = B) = 1, c'est-à-dire A ≠ 18 = 1.

2) ((B A)) Appliquer la transformation d'implication : (18 > A) ∨ (16 > A) = 1

3) (A 2C) Appliquer la transformation d'implication : (A > 18) ∨ (A > 16) = 1

De 2) et 3) il résulte que (18 > A) et (A > 16), sinon une contradiction surgit : A = 17.

Réponse : 17

A, B et C sont des entiers pour lesquels l'énoncé est vrai

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

Quelle est la valeur de B si A = 45 et C = 18 ?

Explication.

Le « ET » logique n’est vrai que si toutes les affirmations sont vraies.