NOMBRES – Curiosités, Théorie et Usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/05/2021

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths                      

          

LOGIQUE

 

Débutants

Logique

Domaines

 

Glossaire

Logique

 

 

INDEX

 

ET / OU / …

 

Logique

Dualité

Logique de Boole

Logique formelle

Logique floue

Raisonnement

Intelligence

Systèmes experts

Incomplétude

Logique des propositions

Cours de logique

 

Sommaire de cette page

>>> Principe de la logique de Boole

>>> Les 16 fonctions de deux variables

>>> Les noms

>>> Logique vrai - faux

>>> Satisfaisabilité booléenne (SAT)

 

 

 

 

LOGIQUE de BOOLE

 Logique combinatoire

Logique mathématique

Algèbre de Boole

Calcul booléen

 

Logique du vrai / faux

du 0 / 1,

utilisée dans les ordinateurs

 

Oups! Je suis débutant

Voir: détails des fonctions logiques

George Boole (1815-1864)

 

Britannique, mathématicien, logicien et philosophe des mathématiques.

 

De 1844 à 1854, Boole crée une algèbre binaire n'acceptant que deux valeurs numériques : 0 et 1.

Fondement de la logique mathématique calculable, de la logique électronique, matérialisée d'abord par des relais puis, aujourd'hui, sous la forme de circuits intégrés à transistors.

Base du fonctionnement de l'électronique numérique: ordinateurs, des téléphones, etc.

 

 

Énigme logique de Martin Gardner

Tous les animaux que je possède sont

-      Tous sont des chiens sauf deux;

-      Tous sont des chats sauf deux; et

-      Tous sont des perroquets sauf deux.

Solution

 

 

  

PRINCIPE DE LA LOGIQUE DE BOOLE

 

*      Outil de logique consistant à donner une conclusion à une combinaison de variables.

*      On codifie les combinaisons pour deux variables logiques.

*      On généralise en prenant les variables deux à deux.

 

*      Par exemple: si la conclusion (S) n'est vraie (1) que lorsque les deux variables (A, B) sont vraies (1), on note: S = A . B. Il s'agit de la fonction ET, dont la table de vérité s'écrit de la manière suivante

 

Table de vérité de la fonction ET

 

A

B

S = A . B

0

0

0

0

1

0

1

0

0

1

1

1

Voir Table en DicoMot Math

Exemples de propositions

La rose est une fleur, c'est vrai.

L'eau est un liquide, ce n'est pas toujours vrai.

L'eau à 20°C est liquide, c'est vrai.

S'il pleut, le sol est mouillé, c'est vrai.

Le nombre 10 est premier, c'est faux.

 

Si un quadrilatère a ses côtés de même longueur et si ses angles sont droits alors c'est un carré, c'est vrai.

Si un nombre est divisible par 2 et par 3, alors il est divisible par 6, c'est vrai.

 

 

 

Les 16 fonctions de deux variables

Les 16 connecteurs ou 16 opérateurs

Fonction

0

1

2

3

4

5

6

7

AB = 00

0

0

0

0

0

0

0

0

01

0

0

0

0

1

1

1

1

10

0

0

1

1

0

0

1

1

11

0

1

0

1

0

1

0

1

 

Fonction

8

9

10

11

12

13

14

15

AB = 00

1

1

1

1

1

1

1

1

01

0

0

0

0

1

1

1

1

10

0

0

1

1

0

0

1

1

11

0

1

0

1

0

1

0

1

 

*      Le tableau est antisymétrique: la colonne n et 15 – n sont de même configuration: il suffit de changer les 0 en 1 et réciproquement. Il n'existe donc que 8 véritables fonction; les 8 autres s'en déduisent pas négation.

 

 

Les noms des connecteurs (ou opérateurs)

                (TdV = table de vérité abrégée)

Français

Anglais

TdeV

Commentaires

0

Contradiction

Contradiction

0000

Fausse quelque soit les variables d'entrée

1

ET

Conjunction

0001

Vraie si les deux variables sont vraies à la fois.

2

Non implication

Non implication

0010

 

3

A

A

0011

 

4

Non implication

contraire

Converse non implication

0100

 

5

B

B

0101

 

6

OU Exclusif

Exclusive disjunction

0110

Vraie dès qu'une seule variable est vraie (une seule).

7

OU (Inclusif)

Disjunction

0111

Vraie dès qu'une des variables est vraie (même les deux).

8

NonET (NAND)

Joint denial

1000

Vraie si  A et B sont fausses

9

Équivalence

Biconditionnal

1001

Vraie si les deux variables sont identiques.

10

Non B

Negation of B

1010

 

11

Implication contraire

Converse implication

1011

 

12

Non A

Negation of A

1100

 

13

Implication

Implication

1101

Fausse que si la deuxième variable est fausse.

14

NonOU (NOR)

Alternative denial

1110

Vraie si A ou  B est fausse

15

Identité

Tautologie

Tautology

1111

Toujours vraie.

Voir Connecteurs

Anglais: binary logical connectives (voir Wikipedia à ces mots)

 Voir Raisonnement

 

 

Logique VRAI – FAUX

 

*      La logique est basée sur le fait de classer le monde en vrai / faux, appartient / n'appartient pas...

 

 

*      Cantor a mis au point la théorie des ensembles dont la base repose sur les notions suivantes:

 

Dénomination

Ensemble A

Complément

de l'ensemble A

Intersection des ensembles

 A et B

Union des ensembles

A et B

 

Illustration

 

*      Aristote: il chercha à établir les fondements de la logique.

" Vous devez commencez quelque part,

et vous partez de choses admises mais indémontrables. "

Ses deux axiomes, base de sa logique étaient:

 

 

Axiome

Loi de la contradiction

Loi d'exclusion mutuelle

En bref

*      A ne peut pas être à la fois B et non-B.

*      A est soit B soit non-B.

Énoncé

*      Le même objet ne peut pas à la fois appartenir à une entité et ne pas appartenir à cette entité.

*      De tout sujet, on peut l'affirmer ou le nier.

Explication

*      Vrai et pas vrai à la fois ne peuvent pas exister.

*      Il n'existe rien d'autre que vrai et pas vrai.

Moderne

*      L'intersection des ensembles " vrai " et " non-vrai " est vide.

*      L'union des ensembles " vrai " et " non-vrai " est complète.

Exemples

*      On considère toutes les personnes gentilles et toutes les personnes non–gentilles.

 

*      Intersection: personne.

*      Union: tout le monde.

  

 

*      La logique a vécu avec ces notions jusqu'à aujourd'hui.
 

*      Mais des questions se posaient tout de même!

Même si Aristote lui-même, et tous ses successeurs, admettaient les nuances: les personnes très gentilles, celles assez gentilles, etc. Ils s'en sortaient en définissant un seuil arbitraire passant d'une catégorie à l'autre.

*      À partir de quel grain de blé obtient-on un tas de blé ?

*      À partir de quelle taille les hommes sont-ils grands ?

*      Comment trouver la frontière entre les hommes gentils et ceux qui ne le sont pas ?

*      A partir de quand, un homme est-il chauve ?...

 

 

Devinette classique

Énigme

Parmi la population de bébés étudiée: 50% vont à la crèche, 80% sont propres et 80% savent dire maman. Quel est le pourcentage minimum de bébés propres qui vont à la crèche et disent maman?

 

Réponse en image

Explications

Schéma du centre: Parmi les bébés, au pire tous ceux qui ne vont pas à la crèche sont propres; au mieux seuls 30% sont propres à la crèche.

Schéma de droite: au pire, tous ceux qui ne vont pas à la crèche et qui vont à la crèche sans être propres disent maman. Soit 70% des bébés. Il en reste au mieux 10% qui vont à la crèche en étant propres et qui savent dire maman.

 

 

Énigme logique de Martin Gardner – Solution

 

Énigme

Tous les animaux que je possède sont

-      Tous sont des chiens sauf deux;

-      Tous sont des chats sauf deux; et

-      Tous sont des perroquets sauf deux.

 

Solution

 

1 chien

1 chat

1 perroquet

Retour

 

 

 

Satisfaisabilité booléenne (SAT)

Boolean Satisfiability Problem or Propositional Satisfiability Problem

 

Calcul booléen et sa résolution

L'informatique utilise le calcul booléen:

 

Les valeurs sont (faux, vrai) ou (0, 1);

Les opérateurs logiques sont: (non, et, ou).

 

A ou B peut être satisfait par exemple avec A vrai alors A ou B est vrai.

Par contre A et non A, ne peut jamais l'être. Dans ces deux cas simples nous avons pu décider. Avec une cinquantaine de variables ou plus, on ne sait plus faire. La table de vérité est inimaginable et aucun algorithme ne permet de résoudre ce problème.

 

Calcul booléen, une nécessité du monde moderne

Le calcul booléen a été Introduit par George Boole au milieu du XIXe siècle. Avec lui:

 

Le raisonnement logique passe de discours philosophique à une véritable théorie mathématique. Surtout, il devient la base de la conception des ordinateurs.

 

 

Problème SAT

Le calcul booléen a constitué une révolution. Pourtant la recherche de la valeur (vrai-faux), en fonction de la quantité des variables, coûte exponentiellement cher en temps de calcul.

 

Prenons seulement 50 variables binaires. Elles conduisent à 250 = 1 125 899 906 842 624 combinaisons. Imaginez pour des centaines ou des milliers de variables …

 

C'est le problème de la satisfaisabilité booléenne.

 

Important pour la conception des circuits intégrés, la vérification des logiciels, et des centaines de problèmes combinatoires.

 

Situation

Le problème SAT est donc une interrogation pour savoir s'il existe une solution à une série d'équations logiques.

 

Problème de décision en logique propositionnelle: soit une formule de logique, il s'agit de déterminer s'il existe une valeur des variables qui rend la formule vraie. Pensez à la mise en équations du Sudoku comme exemple.

La résolution de ce genre de problème devient de plus en plus présente dans les systèmes modernes. Par exemple, la configuration intime d'un microprocesseur

 

Le théorème de Cook-Levin (1971) affirme que le problème SAT est NP-complet. Ce qui veut dire: problème d'une grande complexité, voire insoluble.

 

Problème NP-complet: on ne connaît aucun algorithme déterministe polynomial pour le résoudre

 

 

 

Perspective 2000

Depuis les années 2000 et faute de pouvoir attaquer ces problèmes de front, on a développé des algorithmes heuristiques plutôt que des algorithmes dédiés ou l'examen, cas par cas, de la table de vérité.

 

Table de vérité: tableau qui montre le résultat pour toutes les valeurs possibles des variables.

 

Algorithme dédié: qui suit une exécution "directe ou linéaire" et conduit vers la solution, comme la résolution d'une équation, par exemple.

 

Algorithme heuristique: qui cherche progressivement à converger vers la solution en pratiquante des essais-erreurs.

 

Exemple: il est plus facile de résoudre un Sudoku par heuristique qu'avec un algorithme classique.

 

Interrogation: les mathématiciens ne comprennent toujours pas pourquoi ces algorithmes marchent si bien sur autant de cas pratiques !

 

Voir Neuronique / Sept problèmes du siècle / 21 problèmes de Karp

 

 

 

Suite

*    Détails des fonctions logiques

*    Implication

*   Multi-variable – Diagramme de Karnaugh

*    LogiqueIndex

*    Logique des ascenseurs Junior Diaporama

*    Les 15 algorithmes les plus importants

*    Vocabulaire des maths et de la logique

Voir

*    Additionneur

*    De Morgan (théorème)

*    Énigmes et paradoxes

*    Fractales

*    Groupes sanguins

*    Intelligence artificielle

*    Logique

*    Outils de la logique

*    Raisonnement

*    Syllogismes

*    Tiers exclu

DicoNombre

*    Nombre 16

Site

*    Système digital: de l’algorithme au circuit – Jean Vuillemin – 2015 – pdf de 280 pages

Sites sur le problème SAT

*    Les mystères des 0 et des 1 -  Gérard Berry – Les Échos – 12/09/2016

*    Le problème SAT -  Le blog de Balise – 25/02/2013

*    Problème SAT – Wikipédia

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/LogBoole.htm