Les lois de l'absorption et du collage de l'exclusion. Lois de l'algèbre d'absorption de la logique
Les ordinateurs modernes basés sur des ordinateurs électroniques "anciens" sont basés sur certains postulats comme principes de fonctionnement de base. On les appelle les lois de l'algèbre de la logique. Pour la première fois, une telle discipline a été décrite (bien sûr, pas avec autant de détails que dans sa forme moderne) par l'ancien scientifique grec Aristote.
Représentant une branche distincte des mathématiques, au sein de laquelle le calcul propositionnel est étudié, l'algèbre de la logique a un certain nombre de conclusions et de conclusions bien définies.
Afin de mieux comprendre le sujet, nous analyserons les concepts qui aideront à l'avenir à apprendre les lois de l'algèbre de la logique.
Peut-être que le terme principal dans la discipline à l'étude est une déclaration. C'est une affirmation qui ne peut pas être à la fois fausse et vraie. Il a toujours une seule de ces caractéristiques. En même temps, il est conventionnellement accepté de donner la valeur 1 à la vérité, 0 à la fausseté, et d'appeler l'énoncé lui-même une sorte de A, B, C. En d'autres termes, la formule A=1 signifie que l'énoncé A est vrai. Les expressions peuvent être manipulées de différentes manières. Considérons brièvement les actions qui peuvent être effectuées avec eux. Notez également que les lois de l'algèbre de la logique ne peuvent être maîtrisées sans connaître ces règles.
1. Disjonction deux déclarations - le résultat de l'opération "ou". Il peut être faux ou vrai. Le caractère "v" est utilisé.
2. Conjonction. Le résultat d'une telle action, effectuée avec deux propositions, ne sera nouveau que si les deux propositions originales sont vraies. L'opération "et", le symbole "^" est utilisé.
3. Implication. Opération "Si A, alors B". Le résultat est une déclaration qui n'est fausse que si A est vrai et B est faux. Le symbole "->" est utilisé.
4. Équivalence. Opération "A si et seulement si B quand". Cette affirmation est vraie si les deux variables ont la même valeur. Le symbole "<->».
Il existe également un certain nombre d'opérations proches de l'implication, mais elles ne seront pas considérées dans cet article.
Examinons maintenant de plus près les lois fondamentales de l'algèbre de la logique :
1. Les états commutatifs ou commutatifs que le changement de place des termes logiques dans les opérations de conjonction ou de disjonction n'affecte pas le résultat.
2. Associatif ou associatif. Selon cette loi, les variables dans les opérations de conjonction ou de disjonction peuvent être combinées en groupes.
3. Répartition ou distribution. L'essence de la loi est que les mêmes variables dans les équations peuvent être retirées des parenthèses sans changer la logique.
4. Loi de De Morgan (inversion ou négation). La négation de l'opération de conjonction équivaut à la disjonction de la négation des variables d'origine. La négation de la disjonction, à son tour, est égale à la conjonction de la négation des mêmes variables.
5. Double négation. La négation d'une certaine déclaration aboutit deux fois à la déclaration originale, trois fois - sa négation.
6. La loi d'idempotence ressemble à ceci pour l'addition logique : x v x v x v x = x ; pour la multiplication : x^x^x^=x.
7. La loi de non-contradiction dit : deux affirmations, si elles sont contradictoires, ne peuvent pas être vraies en même temps.
8. La loi de l'exclusion du tiers. Entre deux affirmations contradictoires, l'une est toujours vraie, l'autre est fausse, la troisième n'est pas donnée.
9. La loi d'absorption peut s'écrire ainsi pour l'addition logique : x v (x ^ y) = x, pour la multiplication : x ^ (x v y) = x.
10. La loi du collage. Deux conjonctions adjacentes peuvent se coller pour former une conjonction de rang inférieur. Dans ce cas, la variable par laquelle les conjonctions d'origine ont été collées disparaît. Exemple d'addition logique :
(x^y) v (-x^y)=y.
Nous n'avons considéré que les lois les plus utilisées de l'algèbre de la logique, qui peuvent en fait être bien plus nombreuses, car souvent les équations logiques prennent une forme longue et ornée, qui peut être réduite en appliquant un certain nombre de lois similaires.
En règle générale, des tableaux spéciaux sont utilisés pour faciliter le comptage et l'identification des résultats. Toutes les lois existantes de l'algèbre de la logique, dont le tableau a la structure générale d'un rectangle de grille, sont peintes, distribuant chaque variable dans une cellule séparée. Plus l'équation est grande, plus il est facile de la gérer à l'aide de tableaux.
Mathématiques discrètes : logique mathématique
Conférence 8
Minimisation des fonctions booléennes. Méthode Quine-McCluskey
Lois de l'algèbre booléenne
En logique mathématique, une algèbre spéciale, l'algèbre booléenne, est définie, contenant les opérations de multiplication logique, d'addition logique et de négation ( ,+, - ), qui permettent des transformations identiques d'expressions logiques. Ces lois comprennentLoi d'idempotence (identité)
Loi de commutativité
une b = b une
Loi d'associativité
une + (b + c) = (a + b) + c
une (b c) = (une b) c
Lois de distributivité
Distributivité de la conjonction par rapport à la disjonction
UNE (b + c) = une b + une c
Distributivité de la disjonction par rapport à la conjonction
UNE + b c = (a + b) (a + c)
Loi double négative
Les lois de De Morgan
Lois d'absorption
une + une b = une
une (a + b) = une
Lois définissant les actions avec des constantes logiques 0 et 1
| un + 0 = un un 0 = 0 | un + 1 = 1 une 1 = une |
| 1 = 0 |
|
La légitimité de toutes les lois évoquées ci-dessus peut être facilement prouvée, par exemple à l'aide de tables de vérité.
Lois supplémentaires
Les lois supplémentaires de l'algèbre de Boole sont des corollaires des lois de base et sont très utiles pour simplifier l'écriture des fonctions logiques.
La loi du lien
La preuve de cette identité s'effectue à l'aide de la première loi de distributivité :
La preuve de cette identité s'effectue à l'aide de la seconde loi distributive :
Loi de Blake-Poretsky
En appliquant les lois d'action avec les constantes logiques, l'idempotence et le collage, cette identité peut être prouvée comme suit :
La loi de convolution d'une expression logique
Cette identité peut être prouvée en utilisant successivement les lois de travail avec les constantes logiques, la distributivité, l'idempotence et le recollage :
Simplifier les fonctions logiques
Pour les formes normales de représentation des fonctions, le concept de complexité d'une fonction est défini comme le nombre de termes primaires dans une telle représentation. Les transformations de forme normale pour réduire la complexité d'une fonction sont appelées simplification . Pour simplifier les fonctions logiques, toutes les lois de l'algèbre de la logique sont utilisées.Tâches.
Simplifiez SDNF avec les fonctions suivantes :
1. (un b) c
2. (un b) c
Nous représentons la fonction sous une forme disjonctive parfaite et la simplifions en utilisant les lois de l'algèbre de la logique :
3.
Nous représentons la fonction sous une forme disjonctive parfaite et la simplifions en utilisant les lois de l'algèbre de la logique :
SDNF = 
Aucune autre simplification n'est possible.
4. 
Nous représentons la fonction sous une forme disjonctive parfaite et la simplifions en utilisant les lois de l'algèbre de la logique :
SDNF =
5. 
Nous représentons la fonction sous une forme disjonctive parfaite et la simplifions en utilisant les lois de l'algèbre de la logique :
Méthode Quine-McCluskey
La minimisation des fonctions logiques peut être effectuée à l'aide de la méthode Quine-McClussky, qui comprend quatre étapes :
Représentons les ensembles (constituants) sur lesquels la fonction est vraie sous forme d'équivalents binaires.
Nous classons les équivalents binaires par niveaux (selon le nombre d'unités d'équivalents binaires) et collons (appliquons la règle de collage aux constituants correspondants) des ensembles dans des niveaux voisins, en obtenant les intervalles maximaux aussi longs que possible ; nous marquons chaque ensemble qui a participé au collage. Seuls ces ensembles ou intervalles sont collés ensemble, dont la différence ne réside que dans la valeur d'un chiffre : 001 et 000, 001- et 101-, etc.
Construisons un tableau de Quine dont les colonnes correspondent aux ensembles de vérités binaires de la fonction, et les lignes correspondent aux intervalles maximaux. Si le i-ième ensemble est couvert par le j-ième intervalle, alors mettez 1 à l'intersection de la ligne et de la colonne correspondantes, sinon mettez 0 ou rien.
Nous trouvons la couverture minimale du tableau de Quine, constituée du nombre minimal d'intervalles maximaux qui incluent (couvrent) tous les ensembles sur lesquels la fonction est vraie.
Les équivalents binaires des ensembles vrais sont les suivants :
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Organisons les ensembles binaires par niveaux et effectuons le collage, tant que cela est possible
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Puis on construit une table de Quine :
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
Dans notre tableau, les ensembles 0001 et 1011 sont couverts de la seule manière possible, par conséquent, les intervalles minimaux les couvrant sont appelés obligatoire et forme noyau de revêtement, car doit être inclus dans toute couverture. Dans le tableau, les unités correspondantes sont soulignées, les intervalles (0- -1, -11) forment non seulement le cœur de la couverture, mais couvrent également l'ensemble du tableau Quine.
Ainsi, nous avons obtenu la forme minimale de la fonction étudiée sous la forme :
MDNF = (0 - - 1, - - 1 1) = 
Regardons quelques exemples.
Tâches.
1. Trouver des fonctions MDNFF1 =
f1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
Le DNF parfait de la fonction étudiée a la forme :
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
La première colonne contient un ensemble qui n'a participé à aucun collage - c'est l'intervalle maximum lui-même 0100. Dans la troisième colonne, quatre autres intervalles maximum lui sont ajoutés : (-0-1, -01-, --11, 1--1 ).
On construit une table de Quine :
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Définissons le cœur de la couverture, qui comprendra les intervalles obligatoires :
(0100, -0-1, -01-, --11). Dans ce cas, le noyau de couverture couvre l'ensemble de la table dans son ensemble.
La forme normale disjonctive minimale f1 a la forme :
2. Trouver les fonctions MDNF F 2( X 1, X 2, X 3), qui prend des valeurs uniques sur les ensembles 0,2,3,6 et 7.
Construisons une table de vérité pour F2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
SDNF =
Organisons les ensembles binaires par niveaux et effectuons le collage :
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
À la suite du collage, nous n'avons obtenu que deux intervalles maximum : (11-, --0). Sans construire un tableau de Quine, il est évident qu'ils forment une couverture minimale, puisque supprimer l'un de ces intervalles entraînera la perte d'ensembles sur lesquels la fonction f2(x1, x2, x3 ) vrai. MDNF = x1 x2 +x3.
LITTÉRATURE
Guseva A.I. Apprentissage de l'informatique : tâches et méthodes pour leur résolution - M. : DIALOGUE-MEPhI, 2003.
Gorbatov V. A. Fondamentaux des mathématiques discrètes. - M. : Sciences. Fizmatlit, 1999.-544s
Il y a cinq lois de l'algèbre de la logique :
1. La loi des éléments simples
1*X=X
0*X=0
1+X=1
0 + X = X
Cette loi de l'algèbre de la logique découle directement des expressions ci-dessus des axiomes de l'algèbre de la logique.
Les deux expressions supérieures peuvent être utiles lors de la construction de commutateurs, car en appliquant un zéro logique ou un à l'une des entrées de l'élément "2I", vous pouvez soit transmettre le signal à la sortie, soit former un potentiel zéro à la sortie.
La deuxième variante d'utilisation de ces expressions est la possibilité de mise à zéro sélective de certains chiffres d'un nombre à plusieurs chiffres. Avec l'application au niveau du bit de l'opération "ET", vous pouvez soit laisser la valeur précédente du chiffre, soit la réinitialiser en appliquant une unité ou un potentiel zéro aux chiffres correspondants. Par exemple, il est nécessaire de réinitialiser les chiffres 6, 3 et 1. Alors:
Dans l'exemple ci-dessus d'utilisation des lois de l'algèbre de la logique, on voit clairement que pour mettre à zéro les chiffres nécessaires dans le masque (nombre inférieur), des zéros sont écrits à la place des chiffres correspondants et des uns sont écrits dans le reste chiffres. Dans le nombre d'origine (nombre supérieur), il y a des unités à la place des chiffres 6 et 1. Après avoir effectué l'opération "ET", des zéros apparaissent à ces endroits. À la place du troisième chiffre du nombre original est zéro. Dans le nombre résultant, zéro est également présent à cet endroit. Les chiffres restants, tels que requis par l'état du problème, ne sont pas modifiés.
De la même manière, à l'aide de la loi des éléments simples, l'une des lois fondamentales de l'algèbre de la logique, nous pouvons écrire des unités dans les chiffres dont nous avons besoin. Dans ce cas, il faut utiliser les deux expressions inférieures de la loi des éléments simples. Avec l'application au niveau du bit de l'opération "OU", vous pouvez soit laisser la valeur précédente du chiffre, soit la réinitialiser en appliquant zéro ou un potentiel unitaire aux chiffres correspondants. Supposons qu'il soit nécessaire d'écrire les unités en 7 et 6 bits d'un nombre. Alors:
Ici, dans le masque (nombre inférieur), nous en avons écrit des dans les septième et sixième bits. Les bits restants contiennent des zéros et, par conséquent, ne peuvent pas modifier l'état initial du nombre d'origine, que nous voyons dans le nombre résultant sous la ligne.
Les première et dernière expressions de la loi des éléments simples permettent d'utiliser avec plus d'entrées comme éléments logiques avec moins d'entrées. Pour ce faire, les entrées inutilisées du circuit "ET" doivent être connectées à une source d'alimentation, comme illustré à la figure 1 :
Figure 1. Schéma "2I-NOT" implémenté sur l'élément logique "3I-NOT"
Dans le même temps, les entrées inutilisées du circuit "OU", conformément à la loi des éléments simples, doivent être connectées au fil commun du circuit, comme indiqué sur la figure 2.
Figure 2. Circuit "NOT" implémenté sur l'élément "2I-NOT"
Les lois suivantes de l'algèbre de la logique, découlant des axiomes de l'algèbre de la logique, sont les lois de la négation.
2. Lois de négation
un. Loi des éléments complémentaires
Les expressions de cette loi de l'algèbre de la logique sont largement utilisées pour minimiser les circuits logiques. S'il est possible d'isoler de telles sous-expressions de l'expression générale d'une fonction logique, il est alors possible de réduire le nombre requis d'entrées d'éléments de circuit numérique, et parfois même de réduire l'expression entière à une constante logique.
Une autre loi largement utilisée de l'algèbre de la logique est la loi de la double négation.
b. Deux fois non
La loi de la double négation est utilisée à la fois pour simplifier les expressions logiques (et à la suite de la simplification et de la réduction du coût des circuits combinatoires numériques), et pour éliminer l'inversion des signaux après des éléments logiques tels que "2I-NOT" et "2OR- NE PAS". Dans ce cas, les lois de l'algèbre de la logique permettent de réaliser des circuits numériques donnés utilisant un ensemble limité d'éléments logiques.
c. Loi de la logique négative
La loi de la logique négative est valable pour n'importe quel nombre de variables. Cette loi de l'algèbre de la logique vous permet d'implémenter en utilisant les éléments logiques "OU" et vice versa : d'implémenter la fonction logique "OU" en utilisant les éléments logiques "ET". Ceci est particulièrement utile dans les circuits TTL, car il est facile d'implémenter des portes ET, mais il est plutôt difficile d'implémenter des portes OU. Grâce à la loi de la logique négative, il est possible d'implémenter les éléments "OU" sur les éléments logiques "ET". La figure 3 montre l'implémentation de l'élément logique « 2OR » sur l'élément « » et deux inverseurs.
Figure 3. Elément logique "2OR" implémenté sur l'élément "2I-NOT" et deux inverseurs
La même chose peut être dite à propos du schéma de montage "OU". Si nécessaire, il peut être transformé en un montage "ET" en utilisant des inverseurs à l'entrée et à la sortie de ce circuit.
3. Lois de combinaison
Les lois combinatoires de l'algèbre de la logique correspondent largement aux lois combinatoires de l'algèbre ordinaire, mais il existe aussi des différences.
un. loi de tautologie (répétition multiple)
X + X + X + X = XX * X * X * X = X
Cette loi de l'algèbre de la logique permet d'utiliser des portes logiques avec plus d'entrées comme des portes avec moins d'entrées. Par exemple, vous pouvez implémenter un circuit "2I" à deux entrées sur un élément logique "3I", comme illustré à la Figure 4 :
Figure 4. Schéma "2I-NOT" implémenté sur l'élément logique "3I-NOT"
ou utilisez le circuit "2NAND-NOT" comme un onduleur normal, comme illustré à la figure 5 :
Figure 5. Circuit "NOT" implémenté sur l'élément logique "2I-NOT"
Cependant, il convient d'être averti que la combinaison de plusieurs entrées augmente les courants d'entrée de l'élément logique et sa capacité, ce qui augmente la consommation de courant des éléments précédents et nuit à la vitesse du circuit numérique dans son ensemble.
Pour réduire le nombre d'entrées dans un élément logique, il est préférable d'utiliser une autre loi de l'algèbre de la logique - la loi des éléments simples, comme indiqué ci-dessus.
Nous continuons notre examen des lois de l'algèbre de la logique :
b. loi de mobilité
UNE + B + C + D = UNE + C + B + Dc. loi de combinaison
UNE + B + C + D = UNE + (B + C) + D = UNE + B + (C + D)ré. droit de la distribution
X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /prouvons-le en développant les parenthèses/ == X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3
4. Règle d'absorption (une variable absorbe les autres)
X1 + X1X2X3 =X1(1 + X2X3) = X15. Règle de collage (effectuée par une seule variable)
Tout comme dans les mathématiques ordinaires, dans l'algèbre de la logique, il y a une priorité des opérations. Ceci est fait en premier:
- Action entre parenthèses
- Opération avec un opérande (opération simple) - "NON"
- Conjonction - "et"
- Disjonction - "OU"
- Somme modulo deux.
Les opérations de même rang sont effectuées de gauche à droite dans l'ordre d'écriture de l'expression logique. L'algèbre de la logique est linéaire et le principe de superposition est valable pour elle.
Littérature:
Avec l'article "Lois de l'algèbre de la logique", ils lisent:
Tout circuit logique sans mémoire est complètement décrit par une table de vérité... Pour implémenter une table de vérité, il suffit de ne considérer que ces lignes...
http://siteweb/digital/SintSxem.php
Les décodeurs (décodeurs) vous permettent de convertir un type de code binaire en un autre. Par exemple...
http://site/numérique/DC.php
Bien souvent, les développeurs d'équipements numériques sont confrontés au problème inverse. Vous souhaitez convertir un code de ligne octal ou décimal en...
http://site/numérique/codeur.php
Les multiplexeurs sont des appareils qui permettent de connecter plusieurs entrées à une sortie...
http://site/numérique/MS.php
Les appareils sont appelés démultiplexeurs ... Une différence significative par rapport à un multiplexeur est ...
http://site/numérique/DMS.php
Pour transformer des fonctions, simplifier les formules obtenues en formalisant les conditions de problèmes logiques, des transformations équivalentes sont effectuées dans l'algèbre de la logique, sur la base des lois logiques de base. Certaines de ces lois sont formulées et écrites de la même manière que des lois similaires en arithmétique et en algèbre, d'autres semblent inhabituelles.
Les lois de l'algèbre de la logique sont parfois appelées théorèmes.
En algèbre propositionnelle, les lois logiques sont exprimées sous forme d'égalité de formules équivalentes.
La validité de toutes les lois peut être vérifiée en construisant des tables de vérité pour les parties gauche et droite de la loi écrite. Après avoir simplifié l'expression en utilisant les lois de l'algèbre de la logique, les tables de vérité sont les mêmes.
La validité de certaines lois peut être prouvée à l'aide des outils des tables de vérité.
Image 1.
Exemples
figure 3
Simplifions l'expression originale en utilisant les lois de base de l'algèbre de la logique :
Figure 4
(loi de De Morgan, loi distributive pour ET, loi d'idempotence, opération d'une variable avec son inversion).
Le tableau montre que pour tous les ensembles de valeurs des variables $x$ et $y$, la formule de la Fig. 2 prend la valeur $1$, c'est-à-dire qu'elle est identiquement vraie.
Figure 6
On peut voir dans le tableau que l'expression source prend les mêmes valeurs que l'expression simplifiée sur les valeurs correspondantes des variables $x$ et $y$.
Simplifions l'expression de la Fig. 5 en appliquant les lois fondamentales de l'algèbre de la logique.
Figure 7
(loi de De Morgan, loi d'absorption, loi distributive pour I).
Figure 9
Le tableau montre que pour tous les ensembles de valeurs des variables $x$ et $y$, la formule de la Fig. 8 prend la valeur $0$, c'est-à-dire qu'elle est identiquement fausse.
Simplifions l'expression en appliquant les lois de l'algèbre de la logique :
Figure 10.
Figure 12.
(loi de De Mogrgan, distributive).
Faisons une table de vérité pour l'expression de la Fig. 11 :
Figure 13.
On peut voir à partir du tableau que l'expression de la figure 11 prend dans certains cas la valeur $1$, et dans certains cas - $0$, c'est-à-dire qu'elle est réalisable.
(règle de Morgan, on enlève le facteur commun, la règle des opérations d'une variable avec son inversion).
(le deuxième facteur est répété, ce qui est possible en utilisant la loi de l'idempotent, puis les deux premiers et les deux derniers facteurs sont combinés et la loi de collage est utilisée).
(on introduit un facteur logique auxiliaire
Lois de l'algèbre propositionnelle
L'algèbre des propositions (algèbre de la logique) est une section de la logique mathématique qui étudie les opérations logiques sur les propositions et les règles de transformation des propositions complexes.
Lors de la résolution de nombreux problèmes logiques, il est souvent nécessaire de simplifier les formules obtenues en formalisant leurs conditions. La simplification des formules dans l'algèbre des propositions est effectuée sur la base de transformations équivalentes basées sur les lois logiques de base.
Lois de l'algèbre propositionnelle (algèbre de la logique) sont des tautologies.
Ces lois sont parfois appelées théorèmes.
En algèbre propositionnelle, les lois logiques sont exprimées sous forme d'égalité de formules équivalentes. Parmi les lois, celles qui contiennent une variable sont particulièrement distinguées.
Les quatre premières des lois suivantes sont les lois de base de l'algèbre propositionnelle.
Loi sur l'identité :
Un=Un
Chaque concept et jugement est identique à lui-même.
La loi d'identité signifie que dans le processus de raisonnement on ne peut pas remplacer une pensée par une autre, un concept par un autre. Si cette loi est violée, des erreurs logiques sont possibles.
Par exemple, le raisonnement indique correctement que la langue vous amènera à Kyiv, mais j'ai acheté une langue fumée hier, ce qui signifie que je peux maintenant aller à Kyiv en toute sécurité de manière incorrecte, car les premier et deuxième mots "langue" désignent des concepts différents.
En raisonnement : Le mouvement est éternel. Aller à l'école, c'est bouger. Par conséquent, aller à l'école pour toujours, le mot "mouvement" est utilisé dans deux sens différents (le premier - au sens philosophique - comme attribut de la matière, le second - au sens ordinaire - comme action de se déplacer dans l'espace), ce qui conduit à une fausse conclusion.
Loi de non-contradiction :
Au même moment, l'énoncé peut être vrai ou faux, il n'y a pas de tiers. Soit A est vrai, soit non A. Exemples d'application de la loi du tiers exclu :
1. Le nombre 12345 est soit pair soit impair, le tiers n'est pas donné.
2. L'entreprise fonctionne à perte ou à l'équilibre.
3. Ce liquide peut ou non être un acide.
La loi du tiers exclu n'est pas une loi reconnue par tous les logiciens comme une loi universelle de la logique. Cette loi s'applique là où la cognition traite d'une situation rigide : « soit-ou », « vrai-faux ». Lorsqu'il y a incertitude (par exemple, dans le raisonnement sur l'avenir), la loi du tiers exclu ne peut souvent pas être appliquée.
Considérez l'énoncé suivant : Cette phrase est fausse. Cela ne peut pas être vrai parce qu'il prétend être faux. Mais cela ne peut pas non plus être faux, car alors ce serait vrai. Cette affirmation n'est ni vraie ni fausse, et donc la loi du tiers exclu est violée.
Le paradoxe (paradoxos grec - inattendu, étrange) dans cet exemple provient du fait que la phrase se réfère à elle-même. Un autre paradoxe bien connu est le problème du barbier : dans une ville, le barbier coupe les cheveux de tous les habitants, à l'exception de ceux qui se coupent les cheveux eux-mêmes. Qui coupe les cheveux du coiffeur ? En logique, à cause de sa formalité, il n'est pas possible d'obtenir la forme d'un tel énoncé autoréférentiel. Cela confirme une fois de plus l'idée qu'avec l'aide de l'algèbre de la logique, il est impossible d'exprimer toutes les pensées et tous les arguments possibles. Montrons comment, à partir de la définition de l'équivalence propositionnelle, le reste des lois de l'algèbre propositionnelle peut être obtenu.
Par exemple, déterminons ce qui est équivalent (équivalent) A (double négation A, c'est-à-dire négation de la négation A). Pour cela, nous allons construire une table de vérité :
Par définition d'équivalence, il faut trouver la colonne dont les valeurs correspondent aux valeurs de la colonne A. Ce sera la colonne A.
Ainsi, on peut formuler la loi de double négation :
Si nous nions une déclaration deux fois, alors le résultat est la déclaration originale. Par exemple, la déclaration A = Matroskin - chat est équivalent à A = Ce n'est pas vrai que Matroskin n'est pas un chat.
De même, les lois suivantes peuvent être dérivées et vérifiées :
Propriétés constantes :
Lois d'idempotence :
Peu importe combien de fois nous répétons : la télé est allumée ou la télé est allumée ou la télé est allumée... le sens de l'énoncé ne changera pas. De même, à partir de la répétition, il fait chaud dehors, il fait chaud dehors, ... il ne deviendra pas plus chaud d'un degré.
Les lois de la commutativité :
UNE contre B = B contre UNE
A & B = B & A
Les opérandes A et B dans les opérations de disjonction et de conjonction peuvent être interchangés.
Lois d'associativité :
A v(B v C) = (A v B) v C;
A & (B & C) = (A & B) & C.
Si l'expression utilise uniquement l'opération de disjonction ou uniquement l'opération de conjonction, vous pouvez négliger les crochets ou les disposer arbitrairement.
Lois de distributivité :
A v (B & C) = (A v B) &(A v C)
(disjonction distributive
concernant la conjonction)
A & (B contre C) = (A & B) contre (A & C)
(distributivité de la conjonction
concernant la disjonction)
La loi distributive de conjonction par rapport à la disjonction est similaire à la loi distributive en algèbre, mais la loi de disjonction distributive par rapport à la conjonction n'a pas d'analogue, elle n'est valable qu'en logique. Il faut donc le prouver. La preuve est mieux faite en utilisant une table de vérité :
Lois d'absorption :
A v (A & B) = A
UNE & (A contre B) = UNE
Effectuez vous-même la preuve des lois d'absorption.
Les lois de De Morgan :
Formulation verbale des lois de Morgan :
Règle mnémotechnique : sur le côté gauche de l'identité, l'opération de négation est au-dessus de l'énoncé entier. Du côté droit, il semble rompu et la négation se dresse au-dessus de chacun des énoncés simples, mais en même temps l'opération change : de la disjonction à la conjonction et inversement.
Exemples d'application de la loi de Morgan :
1) L'énoncé Ce n'est pas vrai que je connais l'arabe ou le chinois est identique à l'énoncé Je ne connais pas l'arabe et je ne connais pas le chinois.
2) L'énoncé Il n'est pas vrai que j'ai appris la leçon et obtenu un deux car il est identique à l'énoncé Soit je n'ai pas appris la leçon, soit je n'ai pas obtenu un deux pour cela.
Remplacement des opérations d'implication et d'équivalence
Les opérations d'implication et d'équivalence ne font parfois pas partie des opérations logiques d'un ordinateur ou d'un compilateur particulier à partir d'un langage de programmation. Cependant, ces opérations sont nécessaires pour résoudre de nombreux problèmes. Il existe des règles pour remplacer ces opérations par des séquences d'opérations de négation, de disjonction et de conjonction.
Ainsi, vous pouvez remplacer l'opération d'implication conformément à la règle suivante :
Il existe deux règles pour remplacer l'opération d'équivalence :
Il est facile de vérifier la validité de ces formules en construisant des tables de vérité pour les côtés droit et gauche des deux identités.
La connaissance des règles de remplacement des opérations d'implication et d'équivalence aide, par exemple, à construire correctement la négation d'une implication.
Prenons l'exemple suivant.
Donnons l'énoncé :
E = Ce n'est pas vrai que si je gagne le concours, je recevrai un prix.
Laisser A = je vais gagner le concours,
B = Je recevrai un prix.
Alors
D'ici, E = Je vais gagner le concours, mais je ne recevrai pas de prix.