Logique

Définition

On appelle fonction booléenne toute application qui, à un n-uplet de variables booléennes, associe un unique booléen.

Une fonction booléenne est une expression booléenne à laquelle on a donné un nom. Exemple :

Il existe deux façons principales de définir une fonction booléenne :

1. Par une expression ou équation algébrique ;
2. Par une table de vérité.

Calculer une table de vérité à partir d'une expression est direct, l'opération inverse est plus délicate.

Définition

Une fonction booléenne est en forme normale disjonctive si elle est écrite comme une disjonction de monômes.

Une fonction booléenne est en forme normale conjonctive si elle est écrite comme une conjonction de clauses.

Théorème de Shannon

Soit une fonction booléenne à variables. Pour tout on a :

Cette décomposition permet d'obtenir itérativement les formes normales.

Mise en forme normale

À partir d'une table de vérité :

1. Pour la forme disjonctive, prendre les lignes où la fonction vaut 1 et former la disjonction des monômes correspondants.
2. Pour la forme conjonctive, prendre les lignes où la fonction vaut 0 et former la conjonction des clauses correspondantes.

À partir d'une expression :

1. Remplacer les équivalences par des opérations binaires, appliquer les lois de De Morgan et distribuer pour obtenir une forme normale.
2. Le théorème de Shannon peut aussi aider à construire ces formes.

• une diode bloquante/passante ;
• une proposition vraie/fausse.

Une variable logique représente l'un de ces états ; par convention on note souvent ces deux états 0 et 1.

Il existe plusieurs représentations d'un booléen :

Vrai	Faux
✅	❌
True	False

L'algèbre booléenne a été initiée par George Boole au XIXe siècle (1854).

Opérateurs de base (corrigé)

On possède deux opérateurs binaires et un unaire. Ces opérateurs sont définis par leurs tables de vérité.

Définition

Une table de vérité contient toutes les valeurs (l'évaluation) d'une expression booléenne pour toutes les combinaisons possibles des variables d'entrée.

Opérateur NOT

0	1
1	0

Opérateur ET

0	0	0
0	1	0
1	0	0
1	1	1

Opérateur OU

0	0	0
0	1	1
1	0	1
1	1	1

Règles de calcul

Règles de priorité

Circuits Logiques

Formes normales

Définitions

Défintion

On appelle fonction booléenne toute application qui à un n-uplet de variable booléenne associe un unique booléen.

C'est une expression booléenne à qui on a donné un nom. Exemple :

Il y a deux façons de définir une fonction booléenne :

1. Par une équation (comme si dessus)
2. Par une table de vérité

Calculer une table de vérité à partir d'une équation est simple. La manipulation inverse est plus complexe.

Défintion

Une fonction booléenne est sous forme normale disjonctive ssi elle est écrit comme une disjonction de monômes.

Une fonction booléenne est sous forme normale conjonctive ssi elle est écrit comme une conjonction de clauses.

Théorèmes

Toute fonction booléenne peut s'écrire dans les 2 formes. Il suffit d'appliquer itérativement le théorème de Shanon.

Théorème de Shanon: Soit une fonction booléenne à variables. Alors, ,

• ou

Mise en forme normale

À partir d'une table de vérité,

1. Pour une mise en forme disjonctive, on lie ou il y a des 1 et on les additionne
2. Pour une mise en forme conjonctive, on lie là où il y a des zéros dans la table de vérité puis passer à la négation

À partir d'une formule algébrique,

1. Remplacer les équivalences par les formules binaires puis remplacer par xx puis loi de Morgan
2. Shanon