Cours logique Combinatoire.pdf

MPSI/PCSI SI, cours sur la logique

1/8

LOGIQUE COMBINATOIRE

I. VARIABLE LOGIQUE. Rappel : structure dun systme automatis. Les ordres et les informations peuvent tre :

Analogique (par exemple une tension variable) Logique (0 ou 1, vrai ou faux) Numrique

Exemple de systme automatis : Le portail automatis. Pour simplifier, on sintresse aux lments suivants :

Les 2 portes Les 2 moteurs La tlcommande La cellule photo lectrique

Entres/sorties de la Partie commande (PC) du portail : (les entres sont les informations, les sorties sont les ordres) Les entres et les sorties sont sous la forme tout ou rien (1 ou 0) (vrai ou faux), on les appelle des variables logiques. Lobjet de ce chapitre est de modliser le fonctionnement des PC

PC

Partie Commande

Pr actionneurs PO

Partie

Oprative

Actionneur Transmetteur

Effecteur

Capteurs

Ordres Energie

Informations Grandeurs physiques

MO MO +VA

PC du portail

Appui sur la tlcommande Prsence devant capteur

Ouvrir portes Fermer portes


2/8

II. ALGEBRE DE BOOLE. Il permet de traiter des problmes de logique. 1. Oprateurs logiques de base. Oprateur galit Table de vrit a S 0 0 Equation logique : S = a 1 1 Oprateur ET Table de vrit a b S 0 0 0 Equation logique : S = a.b 0 1 0 1 1 1 1 0 0 Oprateur OU Table de vrit a b S 0 0 0 Equation logique : S = a + b 0 1 1 1 1 1 1 0 1 Oprateur NON Table de vrit a S 0 1 Equation logique : aS 1 0 2. Exemple de problme de logique. Etude dun monte charge. Un monte-charge doit permettre le levage de masses comprises entre 20 et 80 kg. Pour cela, il comporte une plate-forme reposant sur des ressorts. Selon l'importance des charges soulever, trois contacts rglables sont mis en circuit. Les contacts passent 1 lorsque quils sont en contact avec la cuve du monte-charge.

Cahier des charges

vide, aucun des contacts n'est activ. le monte-charge peut fonctionner.


3/8

Pour des charges comprises entre 5 et 20 kg, le monte-charge ne peut fonctionner. Le contact a est actionn.

Pour les charges comprises entre 20 et 80 kg, le monte-charge doit fonctionner. a et b sont actionns.

Pour des charges suprieures 80 kg, le monte-charge ne peut fonctionner. Les contacts a , b et c sont actionns.

Problme pos : Il faut modliser le comportement attendu en quations afin de raliser la partie commande. Question : Dterminer l'quation boolenne de la sortie S assurant lautorisation de

fonctionnement de ce monte-charge. Le monte-charge doit fonctionner (S passe 1) vide (cas a=0 et b=0 et c=0) ou pour les charges comprises entre 20 et 80 kg (cas a=1 et b=1 et c=0)

On peut crire lquation de la sortie cbacbaS .... 3. Proprits de lalgbre de BOOLE. Commutativit a.b = b.a a+b = b+a

Associativit a.(b.c) = (a.b).c

a+(b+c) = (a+b)+c

Distributivit a.(b+c) = a.b+a.c

a+(b.c) = (a+b).(a+c)

Elments neutres a.1 = a

a + 0 = a

Elment absorbant a.0 = 0

a + 1 = 1

Complment 0. aa

1 aa

Idempotence

a.a = a a + a = a

Thorme de De Morgan baba .

baba .

Exemples dutilisation de lalgbre de Boole pour simplifier des expressions logiques.

cbccbccbcccbc )1.(...).( babaaabaa ...).(

III. OPERATEURS LOGIQUES. 1. Oprateurs une variable.

f(a) a S


4/8

Reprsentons dans une table de vrit, tous les cas possibles dune fonction Boolenne une variable dentre. Variable a Fonction f(a) f1 f2 f3 f4 0 0 0 1 1 1 0 1 0 1 f1 = 0 mise 0 f2 = a identit

f3 = a complment (fonction non) f4 = 1 mise 1

2. Oprateurs deux variables. Etudions tous les cas possibles dune fonction Boolenne deux variables dentre.

Remarque : il y a 16 fonctions possibles (n.22 = 42 )

Fonctions dj vues :

f1 = 0 mise 0 f2 = 1 mise 1 f3 = a identit f4 = a complment

f5 = b identit f6 = b complment f7 = a + b ou f8 = a.b et

Autres fonctions : OU exclusif Table de vrit a b S 0 0 0

bababaf ..9 0 1 1 1 1 0

1 0 1

NOR (non ou) : babaf .10 (De Morgan)

NAND (non et) : babaf .11 Equivalence Table de vrit a b S 0 0 1

babaf ..12 0 1 0 1 1 1

1 0 0 Implication (a implique b) Table de vrit a b S

baf 13 0 0 1 0 1 1 1 1 1

Si a=1 alors S=b 1 0 0 Si a=0, b peut prendre les valeurs 0 ou 1

f(a,b) a b

S


5/8

Implication (b implique a) : baf 14

IV. SIMPLIFICATION DE FONCTION. Une expression combinatoire reprsente une fonction boolenne Pour n variables dentres, il existe :

n.22 fonctions diffrentes.

Une infinit dexpressions combinatoires (certaines sont quivalentes). On recherche la forme la plus simple possible dune expression combinatoire. Le but est de raliser une fonction en utilisant le moins doprateurs logiques possibles. Mthode algbrique : On crit les produits par ordre alphabtique afin de les comparer plus facilement et on utilise les proprits de lalgbre de Boole. Exemples : baabababaS )1.(.1

)..().).(.()....(2 cbbacbccbacbcbcbaS Remarque : Certaines simplifications napparaissent pas, par exemple babaabaaS ...3 (on rajoute ba. )(car a+a.b=a(1+b)=a)

babaaaS ).(3 On peut donc reprendre ).(2 cbaS Mthode graphique. Tableau de Karnaugh. Le tableau de Karnaugh est une table de vrit dispose de manire faire apparatre les possibilits de regroupement de termes. Exemple 1 Une fonction S4 trois entres est reprsente par une table de vrit. On va reprsenter cette fonction dans un tableau de Karnaugh et on va crire son quation simplifie.

a b c S4 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1

Tableau de Karnaugh

S4 a b

c

Equation simplifie : cbbaS ..4


6/8

Exemple de fonctions S5 et S6 4 variables reprsentes par des tableaux de Karnaugh S5 a S6 a b b

1

0

0

1

1

1

0

1

1

1

0

1

1

1

0

0

0

1

0

1

1

1

1

0

1

0

1

0

1

1

0

1

c d c d

dcbadbadbadbacbS ..........5 dcbdbaS ...6 Remarques :

On forme les groupes de 1 (ou de 0) adjacents les plus gros possibles (dun nombre de 2n de termes : 1, 2, 4, 8, 16,)

Les entres sont organises sous forme de code binaire rflchi appel aussi code Gray (2 cases adjacentes ne se distinguent que par le changement dune seule variable).

On utilise les nombreuses symtries.

V. REPRESENTATION DES FONCTIONS LOGIQUES On peut reprsenter une fonction logique avec :

Une phrase (S est vrai si a et b sont vrais) Une quation logique (S = a.b) Une table de vrit. Un tableau de Karnaugh. Un chronogramme.

1. Schmas lectriques. Ils sont raliss par des contacts lectriques commands manuellement (poussoir) ou lectriquement (relais). Exemple 1.


7/8

On distingue deux sortes de contacts : ouverture (Non) et fermeture (Oui). Si c = 1, le courant passe dans le contact. Si c = 0, le courant ne passe pas. Si a = 0, le courant passe dans le contact. Si a = 1, le courant ne passe pas.

La fonction reprsente est : ).( bacL La fonction et est ralise par des contacts en srie. La fonction ou est ralise par des contacts en parallles.

Exemple 2.

La fonction reprsente est : ).(.)..( cadbdacbL Remarque : Les contacts a et a lectriquement indpendants sont commands par

la mme action a . 2. Logigrammes. Un logigramme est une association doprateurs logiques dcrivant une quation logique. Liste (non exhaustive) des oprateurs logiques :

Symbole Equation Oprateur Symbole Equation Oprateur

S = a

Identit

aS

Non

S = a.b

ET

baS .

NAND

S = a + b

OU

baS

NOR

baS

OU exclusif

baS

a implique b


8/8

Le logigramme dune fonction logique nest pas unique. Il dpend des contraintes technologiques imposes.

Exemple : On veut raliser la fonction baS . Solution 1 : En utilisant toutes les fonctions logiques disponibles

Solution 2 : En utilisant uniquement les fonctions de base ET, OU, NON

Dans certains cas, on se voit imposer lutilisation unique des cellules NOR ou NAND En effet, toute fonction peut tre ralise en utilisant uniquement des cellules NOR ou NAND (cellules dites universelles). Cela permet de raliser une fonction logique en utilisant quun seul type de cellules. Il faut alors rorganiser la fonction (en utilisant le thorme de De Morgan) pour faire apparatre que des NOR ou que des NAND. Remarques. Pour avoir un NON avec un NAND

Pour avoir un NON avec un NOR

Solution 1 : En utilisant que des NAND.

)..(.. bbababaS

Solution 2 : En utilisant que des NOR.

bababaS ..

baaS )(

Documents

Cours logique Combinatoire.pdf