Mathématiques appliquées à l’informatique 3 – Logique ...bliaudet.free.fr/IMG/pdf/Maths-03-Logique.pdf · LOGIQUE DES PREDICATS 43 1 : Logique des prédicat (logique d’ordre

Mathématiques appliquées à l’informatique – Logique - page 1/54

Mathématiques appliquées à l’informatique 3 – Logique

logique des propositions logique des prédicats

Bertrand LIAUDET

SOMMAIRE

SOMMAIRE 1

LOGIQUE DES PROPOSITIONS 3Références 3Contenu du cours 3

1 : Les propositions 4Présentation 4Proposition atomique et proposition complexe 6Tables de vérité : première approche 8Logique d’ordre 0 10Exercices 11

2 : Les opérateurs logiques 12Présentation 12La négation : ¬p 13La conjonction : p et q 14La disjonction : P ou Q 14Priorité des opérateurs 15Exercices et code Python – série 1 15Table de vérité et proposition complexe 17L’équivalence : P ⇔Q 18Le ou exclusif : P xor Q 19Exercices et code Python – série 2 19L’implication : => 21Généralisation : les 16 opérateurs binaires 24Priorité des opérateurs 24Exercices récapitulatifs 25

3 : Propriétés et démonstration 26Propriétés = tautologies 26


Table de vérité et démonstration des propriétés 28Exercices récapitulatifs 29

4 : Raisonnement (ou syllogisme) 30Le modus ponens : (p et p=>q) => q 30La contraposée (modus tollens) : (non q et p => q) => non p 30Exercices récapitulatifs 31

5 : Applications aux circuits booléens 32Forme normale disjonctive 32Tableaux de Karnaugh 35Circuit à relais 37Circuit électronique 39

LOGIQUE DES PREDICATS 431 : Logique des prédicat (logique d’ordre 1) 43

Présentation 43Variables et prédicats 43Quantificateurs 45Construction de proposition simple : 1 seule variable, 1 seul quantificateur 46Construction de propositions complexes : plusieurs variables, plusieurs quantificateurs 47Exercices 47

2 : Déduction immédiate 48Notion de déduction immédiate 48Négation des quantificateurs 48Contraposé 49Carré logique 50Exercices 51

3 : Raisonnement 52Rappel : la règle du détachement : (p+ p=>q) => q 52Application aux prédicats 52Exercices 54

Dernière édition : novembre 2017


LOGIQUE DES PROPOSITIONS

Références Mathématique pour l’informatique – BTS SIO – Dunod – 2015 : Chapitre 1, pp. 3-33. Méthodes mathématiques pour l’informatique – IUT-Licence-Ecole d’ingénieurs-CNAM – Dunond 2013. Notions de Logique – Philippe Thiry – De Boeeck Université – 1997 Site http://exo7.emath.fr/

Contenu du cours En jaune : là où sont les exercices Les propositions

• Théorie de la proposition • Proposition atomique et proposition complexe • Table de vérité • Logique d’ordre 0 • Exercices

Les opérateurs logiques • Présentation • La négation : non(p) • La conjonction : p et q • La disjonction : p ou q • Priorité des opérateurs • Exercices et code Python • Table de vérité et proposition complexe • L’équivalence • Le ou exclusif • Exercices et code Python • L’implication • Généralisation : les 16 opérateurs • Exercices récapitulatifs

Propriétés et démonstration • Propriétés = tautologies • Tables de vérité et démonstration • Exercices récapitulatifs

Raisonnement (ou syllogisme) • Le modus ponens • Le modus tollens • Exercices récapitulatifs

Applications aux circuits booléens • Forme normale disjonctive


• Tableaux de Karnaugh • Circuit à relais • Circuit électronique

1 : Les propositions

Présentation

Définition Une proposition est un énoncé ayant un sens et qui est vrai ou faux.

Exemples de propositions « Il fait beau » : proposition vraie en fonction du contexte « 8 = 4*2 » : proposition vraie « 10 = 5+6 » : proposition fausse

Subtilité : On note la proposition dont on parle entre guillemets pour la distinguer de ce qu’on en dit : qu’elle est vraie ou fausse. On a 2 langages en présence : celui de la proposition. C’est le langage « objet ». Celui qui parle de la proposition : c’est le métalangage.

Exemples d’expressions qui ne sont pas des propositions • « Bonjour » n’est pas une proposition. • « Le ciel bleu » n’est pas une proposition. • « 8 » n’est pas une proposition. • « Je vais gagner à la loterie » n’est pas une proposition. Ce n’est ni vrai ni faux. C’est un futur

et c’est peu prédictible même si c’est très probablement faux. • « x <- 3 » n’est pas une proposition : c’est une affectation (ou assignation), c’est-à-dire une

action. Une action n’est pas une proposition, elle n’a pas de valeur de vérité.

Subtilités • « x==3 » tel quel n’est pas une proposition car on ne sait pas ce qu’est x. Il n’est pas défini. En

mathématiques, il faudra le définir pour avoir une proposition. Par exemple : « il existe x E N tel que x=3 » est une proposition mathématique vraie. En informatique, ce sera une proposition si x est déclaré. Dans ce cas, x contient une valeur et on peut le comparer à 3. Selon sa valeur, la proposition sera vraie ou fausse.

• « 8 x + 5 » en tant qu’expression informatique, est une proposition. Si x est défini et est un entier positif, on peut évaluer l’expression. Si le résultat vaut 0, la proposition est fausse, sinon elle est vraie.

• « 8 x + 5 » en tant qu’expression mathématique n’est pas une proposition. Elle n’a pas de valeur de vérité.

Notation symbolique Les propositions se notent : p, q, P, Q

Ø Exemples


On peut écrire : p= « il fait beau » q = « il y a du vent »


Proposition atomique et proposition complexe

Définitions : première approche

Ø Proposition atomique Une proposition atomique ne comporte pas de parties. Elle ne contient pas d’autres propositions qu’elle-même.

Ø Proposition complexe Une proposition complexe est composée de plusieurs propositions atomiques ou complexes.

Ø Exemples « Il fait beau » : est une proposition atomique. « Le soleil brille et il y a du vent » est une proposition complexe constituée de 2 propositions atomiques : « le soleil brille » et « il y a du vent ».

Connecteurs logiques Les propositions complexes relient entre elles des propositions atomiques ou complexes par des connecteurs logiques. Les 2 principaux connecteurs sont « et » et « ou ».

Ø Exemples

« Le soleil brille et il y a du vent » : c’est un proposition complexe.

« Le soleil brille ou il y a du vent » : c’est un proposition complexe. Les deux propositions complexes peuvent être vraies ou fausses en fonction des valeurs de vérités des propositions atomiques. Si « le soleil brille » est vraie et si « il y a du vent » est fausse, alors la première proposition est fausse et la seconde est vraie.

Notation symbolique

P= « Le soleil brille et il y a du vent » On utilise plutôt les majuscules pour les propositions complexes et les minuscules pour les propositions atomiques. On peut écrire une proposition complexe sous forme symbolique en utilisant l’expression symbolique des propositions atomiques qui la constitue : p = « Le soleil brille » q = « Il y a du vent » P = p et q


Utilisation en informatique

Ø Expression booléenne En informatique, les expressions booléennes sont des propositions : Dans le code suivant :

a=-5; if(a<0): print("négatif");

L’expression « a<0 » est une expression booléenne : c’est une proposition qui est vraie ou fausse. Elle est évaluée : selon la valeur de a, elle est vraie ou fausse et on fera ou pas le travail. Soit le code suivant :

n=0; while n<10: n=n+1; print(n);

L’expression « n<10 » est une expression booléenne : c’est une proposition qui est vraie ou fausse. Elle est évaluée : selon la valeur de n, elle est vraie ou fausse et on fera ou pas le travail. A noter que « n=0 » n’est pas une proposition. Pas plus que « n=n+1 ». Pas plus que « n+1 ».


Tables de vérité : première approche

Table de vérité d’une proposition atomique

Ø Présentation Une table de vérité est un tableau dans lequel :

• on met en colonne des propositions • on met en ligne les valeurs de vérité possibles pour les propositions : vrai ou faux.

Ø Exemple

Il fait beau Vrai Faux

Table de vérité et algèbre booléenne Dans l’algèbre booléenne : 1 = vrai 0 = faux La table de vérité devient : Il fait beau 1 0

Par commodité d’écriture, on utilisera toujours la formulation booléenne.

Table de vérité d’une proposition complexe

Ø Présentation Dans le cas d’une proposition complexe, on met chaque proposition atomique en colonne et aussi la proposition complexe. En ligne, on met tout les cas possibles de valeurs de vérité pour l’ensemble des propositions atomiques.

Ø Exemple La proposition complexe contient 2 propositions atomiques : n=2. On a donc 4 cas possibles (4 lignes dans la table) selon les valeurs de vérité des 2 propositions atomiques. Le nombre de cas possibles vaut 22 et d’une façon générale : 2n. Il fait beau Il y a du vent Il fait beau et il y a du vent 1 1 1 1 0 0 0 1 0 0 0 0


Avec une proposition complexe à 3 propositions atomiques, le nombre de cas possibles vaut 23 =8. Il fait beau Il y a du vent Il y a des nauges Il fait beau et il y a du vent

et il y a des nuages 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0

Pour définir tous les cas possibles, dans la première colonne on met une première moitié de 1 puis une deuxième moitié de 0. Dans la deuxième colonne on met une moitié de 1 et une moitié de 0 dans la zone des 1 précédent, puis la même chose dans la zone des 0. Même logique pour la troisième colonne qui finalement alterne les 1 et les 0.


Logique d’ordre 0

Définition La logique d’ordre 0 c’est la logique des propositions. Une proposition peut être vraie ou fausse. La logique d’ordre 0 s’occupe à la vérité ou à la fausseté des propositions. Elle s’occupe aussi des opérations que l’on peut effectuer sur ces propositions.

Proposition scientifique

Subtilité : la falsifiabilité Certains philosophes disent qu’une proposition dont on dit qu’elle est vraie est scientifique si elle peut être réfutée, c’est-à-dire si on peut prouver sa négation. On dit qu’une proposition scientifique doit être « falsifiable ». Les propositions qui ne sont pas falsifiables sont des croyances. Par exemple : « Le Mont Blanc est la plus haute montagne de France » est une proposition scientifique. Pour prouver le contraire, il suffit de trouver une montagne plus haute. Autre exemple : « Les extraterrestres n’existent pas » est une proposition qui peut être vraie ou fausse. Si on considère qu’elle est vraie, alors son contraire est « les extraterrestres existent ». Cette proposition est « facilement » prouvable : il suffit d’en trouver un ! Comme on n’en a toujours pas trouvé, la proposition « les extraterrestres n’existent pas » est une proposition scientifique vraie jusqu’à preuve du contraire. Il en va de même pour les dragons et les fantômes ! Par contre, « les extraterrestres existent » est aussi une proposition qui peut être vraie ou fausse. Mais le contraire est : « les extraterrestres n’existent pas ». Comment le prouver ? Il faudrait parcourir l’univers tout entier dans tous ses recoins ! Impossible. Donc la proposition « les extraterrestres existent » n’est pas une affirmation scientifique : c’est une croyance. Il en va de même pour l’existence des dragons et des fantômes ! Donc la seule proposition scientifique possible est « les extraterrestres n’existent pas », au moins jusqu’à preuve du contraire. Ca n’empêche pas d’y croire !


Exercices

Ø Quels sont les énoncés qui sont des propositions : • Les bons élèves écoutent en classe. • 7+3 = 5x2 • Les forts en maths • Les bons élèves n’écoutent rien. • 7+3 = 6+5 • Faites les exercices ! • La lune est un morceau de gruyère • Je crois aux extraterrestres. • La plus vielle maison de Paris • Il a dit « à demain » et il est sorti • Il pleut et il ne pleut pas • Il fait beau ou il fait beau • Il pleut ou il fait beau • Il pleut et les nuages sont formés de coton • Il fait beau ou faites vos exercices. • Il fait des maths et elle fait de l’informatique et il pleut.

Ø Dans les énoncés précédents : • Quelles sont les propositions complexes ? • Ecrivez chaque proposition complexe avec une notation symbolique : P= « … », p=

«…», q=« … », P = p et q (par exemple).

Ø Quelles sont les valeurs de vérité des propositions suivantes : • 3 > 5 • 2 == 4 - 2 • 2 > 4 • 2 == 2+2


2 : Les opérateurs logiques

Présentation

Les opérateurs logiques Il existe de nombreux opérateurs logiques (opérateurs ou connecteurs).

Ø négation A partir de la proposition : p = « il fait beau » on peut construire sa négation : non(p) = « il ne fait pas beau ».

Ø conjonction A partir d’une deuxième proposition : q = « il y a du vent » on peut construire la conjonction des deux propositions : P = « il ne fait pas beau et il y a du vent » Cette dernière proposition pourra s’écrire en formalisme logique : P = non(p) et q « non » et « et » sont des opérateurs logiques (ou connecteurs logiques).

Ø On va étudier les opérateurs suivants : • Négation • Et • Ou • Equivalence • Ou exclusif • Implication.

Propositions atomiques et propositions complexes : définition finale

Ø Proposition atomique Une proposition atomique ne comporte pas de parties. Elle ne contient pas d’autres propositions qu’elle-même. Elle est toujours affirmative.

Ø Proposition complexe Toutes les propositions construites avec des connecteurs logiques sont des propositions complexes.

Ø Exemples « il pleut » est 1 proposition atomique. « il ne pleut pas » est 1 proposition atomique. « il pleut et il fait froid » est une proposition complexe.

Table de vérité Pour déterminer la valeur de vérité d’une proposition complexe, on utilise les tables de vérité. On présente des exemples et le principe général au fil du cours.


La négation : ¬p

Formalisme non(p), not(p), !p, ¬p,�p

Langage naturel p= « il fait beau » non(p) = « il ne fait pas beau » non(p), c’est la négation : « ne … pas »

Proposition atomique et proposition complexe Une proposition négative est toujours une proposition complexe. « Il ne fait pas beau » est une proposition complexe. « Il fait beau » est une proposition atomique.

Table de vérité La table de vérité permet de calculer la valeur de vérité pour une opération donnée (ici la négation) en partant des valeurs possibles pour la proposition de départ. Valeur de vérité Algèbre booléenne p non (p) p non (p) Vrai Faux 1 0 Faux Vrai 0 1

Exemples p : « PI est un entier » non(p) : « PI n’est pas un entier » q : 3 > 4 non(q) : 3 <= 4


La conjonction : p et q

Formalisme p et q, p and q, p∧q, pxq, p.q, pq, p ∩ q

Table de vérité Valeur de vérité Algèbre booléenne P Q P et Q P Q P et Q Vrai Vrai Vrai 1 1 1 Vrai Faux Faux 1 0 0 Faux Vrai Faux 0 1 0 Faux Faux Faux 0 0 0

Langage naturel P et Q veut dire les deux en même temps. Si P et Q sont des ensembles (les animaux marins et les mammifères), les deux en même temps veut dire l’intersection des deux ensembles : les dauphins et les baleines.

La disjonction : P ou Q

Formalisme P ou Q, P or Q, P∨Q, P+Q, P ∪ Q

Table de vérité

Valeur de vérité Algèbre booléenne P Q P ou Q P Q P ou Q Vrai Vrai Vrai 1 1 1 Vrai Faux Vrai 1 0 1 Faux Vrai Vrai 0 1 1 Faux Faux Faux 0 0 0

Langage naturel P ou Q veut dire l’un ou l’autre ou les deux en même temps. Si P et Q sont des ensembles (les animaux marins ou les mammifères), l’un ou l’autre veut dire l’union des deux ensembles : les lions, les thons, les dauphins.


Priorité des opérateurs 1. Les parenthèses sont prioritaires sur les opérateurs. 2. L’opérateur unaire de négation est prioritaire sur les opérateurs binaires 3. L’opérateur « et » est prioritaire sur l’opérateur « ou » 4. Les opérateurs de comparaison arithmétique (==, >, >, etc) sont prioritaires sur les opérateurs

de logique propositionnelle (et, ou, implique, etc.).

Exercices et code Python – série 1

################################################################### p=2>3 p # combien vaut p ? q=not(p) q # combien vaut q ? ################################################################### x=0 p= x>0 and x<10 p # combien vaut p ? x=5 p= x>0 and x<10 p # combien vaut p ? p= 3 >2 and 6>5 p # combien vaut p ? p= 2 >3 and 6>5 p # combien vaut p ? ################################################################### x=5 p= x<0 or x>10 p # combien vaut p ? x=20 p= x<0 or x>10 p # combien vaut p ? p= 3 >2 ou 7 >6 p # combien vaut p ? p= 3 >2 ou 5 >6 p # combien vaut p ? p= 3 >4 ou 5 >6 p # combien vaut p ?


################################################################### # Si un entier intervient dans une proposition booléeenne, on applique la règle

suivante : 0 vaut faux, !=0 vaut vrai. p= False and False or True p # combien vaut p ? p= False and (False or True) p # combien vaut p ? p= (4==4) and True p # combien vaut p ? p= 4== (4 and True) p # combien vaut p ? p= 4==4 and True p # combien vaut p ?


Table de vérité et proposition complexe

Présentation Une table de vérité permet d’analyser la valeur de vérité d’une proposition complexe en partant des différents cas possibles pour chaque proposition atomique. On part de proposition atomique affirmative.

Exemple 1 P = « Il fait beau et il ne pleut pas » q = « il fait beau » r = « il pleut » non(r) = « il ne pleut pas » P = q et non(r)

Ø Table de vérité On commence par mettre les propositions atomiques en colonnes. Ensuite met les négations qui interviennent dans la propositions complexes. Enfin, on met la proposition complexe.

Exercices – table de vérités de propositions complexes Construire la table de vérité des propositions suivantes : • p et non(q) ou r • non ((non p) ou q) et r

Valeur de vérité Algèbre booléenne q r non(r) P = q et non(r) q r non(r) P = q et non(r) Vrai Vrai Faux Faux 1 1 0 0 Vrai Faux Vrai Vrai 1 0 1 1 Faux Vrai Faux Faux 0 1 0 0 Faux Faux Vrai Faux 0 0 1 0


L’équivalence : P ⇔Q

Formalisme P ⇔ Q

Table de vérité

Valeur de vérité Algèbre booléenne P Q P ⇔ Q P Q P ⇔ Q Vrai Vrai Vrai 1 1 1 Vrai Faux Faux 1 0 0 Faux Vrai Faux 0 1 0 Faux Faux Vrai 0 0 1

Langage naturel P ⇔ Q veut dire que quand on a l’un, on à l’autre et quand on n’a pas l’un on n’a pas l’autre non plus. Les deux propositions vont ensemble. Ca peut se rapprocher de l’égalité : dire que deux proposition sont équivalentes, c’est comparer leur valeur de vérité et constater qu’elles sont identiques dans tous les cas.

Propriété : P <=> P P <=> P est toujours vraie. On peut le démontrer avec une table de vérité : Table de vérité P P P <=> P 1 1 1 0 0 1


Le ou exclusif : P xor Q

Formalisme P xor Q, P ⊕ Q

Table de vérité

Valeur de vérité Algèbre booléenne P Q P xor Q P Q P xor Q Vrai Vrai Faux 1 1 0 Vrai Faux Vrai 1 0 1 Faux Vrai Vrai 0 1 1 Faux Faux Faux O 0 0

Langage naturel P xor Q veut dire l’un ou l’autre mais pas les deux, comme dans l’option « dessert ou café » dans certains menus de restaurant.

Exercices et code Python – série 2 ################################################################### Quelle est la valeur de vérité des propositions suivantes : x=1 ; « 4x - 8 == 0 <=> x == 2 » x=2 ; « 4x - 8 == 0 <=> x == 2 » x=1 ; « 4x – 8 == 0 <=> x == 1 » x=2 ; « 4x – 8 == 0 <=> x == 1 » x=3 ; « 4x – 8 == 0 <=> x == 1 » « 4 + 4 == 8 <=> 1 < 2 » « 4 + 4 == 9 <=> 1 < 2 » « 4 + 4 == 9 <=> 2 < 1 » « La Terre est un cube <=> Les chats ont 6 pattes » A l’aide d’une table de vérité, démontrer le principe de la double négation : P <=>

non(non(P))


################################################################### # x > 0 xor x < 10 : quelle est la valeur de vérité x=5 p= (x<0) ^ (x>10) p # combien vaut p ? x=20 p= (x<0) ^ (x>10) p # combien vaut p ? # x >= 0 xor x< 0 : quelle est la valeur de vérité ? x=5 p= (x>= 0) ^ (x< 0) p # combien vaut p ? x=-5 p= (x>= 0) ^ (x< 0) p # combien vaut p ? # 3 >2 xor 6 >5 : quelle est la valeur de vérité ? p= (3 >2) ^ (6 >5) p # combien vaut p ? # 3 >2 xor 5>6 : quelle est la valeur de vérité ? p= (3 >2) ^ (5>6) p # combien vaut p ?


L’implication : =>

Formalisme p implique q, p donc q, si p alors q, p ⇒ q, p => q, p -> q

Antécédent et conséquent. Si on a p => q, on appelle « p » l’antécédent, « q » le conséquent.

Exemple Il pleut donc le sol est mouillé. p = il pleut q = le sol est mouillé p => q On peut aussi dire : s’il pleut alors le sol est mouillé.

Table de vérité Valeur de vérité Algèbre booléenne p q p ⇒ q p q p ⇒q Vrai Vrai Vrai 1 1 1 Vrai Faux Faux 1 0 0 Faux Vrai Vrai 0 1 1 Faux Faux Vrai 0 0 1

Condition suffisante et condition nécessaire Pour qu’il y ait implication, il faut : • que l’antécédent soit une condition suffisante du conséquent • que le conséquent soit une condition nécessaire de l’antécédent. C’est ce critère qui permet de savoir qui est l’antécédent et qui est le conséquent : pour que p il suffit que q.

Ø Exemple Il pleut donc le sol est mouillé. La pluie est une condition suffisante d’un sol mouillée. Il suffit qu’il pleuve pour que le sol soit mouillé. Le sol mouillé est une condition nécessaire de la pluie. Il faut (nécessité) que le sol soit mouillé pour qu’il pleuve. C’est nécessaire mais pas suffisant : si on a que cette information (le sol mouillé), il ne pleut pas forcément.


Propriété 1 : P => P P => P est toujours vrai. On peut le démontrer avec une table de vérité : Table de vérité P P P => P 1 1 1 0 0 1

P => P est toujours vrai.

Propriétés 2 : P => Q <=> non (P et nonQ) P => Q <=> on ne peut pas avoir P sans Q : non (p et non q). P => Q <=> non (P et nonQ)

Ø Par exemple : Il pleut donc le sol est mouillé. p = il pleut. q = le sol est mouillé. p => q <=> non (p et non q) Ce qu’on peut traduire par : on ne peut pas avoir de la pluie sans que le sol soit mouillé.

Propriétés 3 : La contraposée : P=>Q ó nonQ => nonP

Ø Par exemple : Il pleut donc le sol est mouillé. p = il pleut. q = le sol est mouillé. p => q <=> non q => non p Le sol n’est pas mouillé donc il ne pleut pas.

Ø Démonstration formelle : nonQ => nonP ó non (nonQ et non(non(P)) ó non (nonQ et P) ó non (P et nonQ) ó P=>Q

Bizarrerie : du faux, on peut tout déduire A partir d’une proposition fausse, on peut tout déduire, du faux et du vrai. Autrement dit : « la lune est un gruyère implique que les poules ont des dents » est vrai ! C’est étrange, mais on le comprend aisément si on sait que : non (A et B) ó nonA ou nonB (lois de Morgan : cf suite du cours) Donc P=>Q ó non (P et nonQ) ó nonP ou Q Donc, si nonP est vrai alors nonP ou Q est vrai et donc P=>Q est vrai. Donc si P est faut, P => Q est vrai


Exercices sur l’implication 1. A l’aide d’une table de vérité, démontrer que P => Q ⇔ non(P et non(Q)) 2. A l’aide d’une table de vérité, démontrer que P => Q ⇔ nonQ => nonP 3. Doit-on dire : « Le temps est sec donc il ne pleut pas » ou « Il ne pleut pas donc le temps est

sec » ? Traduisez en propositions symbolique les énoncés et justifier votre réponse. Donnez aussi la contraposé.

4. Traduisez en propositions et implications les phrases suivantes. Dans chaque cas, donnez

aussi la contraposé • Le cours a lieu si le professeur est arrivé. • Je cours beaucoup donc je suis fatigué • Si l’accusé est coupable il n’a pas d’alibi. • Pour que les étudiants réussissent, il faut qu’ils étudient. 5. Dans les deux derniers cas, faites le tableau de vérité et interpréter tous les cas.


Généralisation : les 16 opérateurs binaires Quand on fait la table de vérité d’une opération binaire, on obtient un résultat qu’on peut lire comme un nombre binaire à 4 chiffres : P et Q = 1 0 0 0. Valeur de vérité P Q P et Q 1 1 1 1 0 0 0 1 0 0 0 0 Ilyadoncautantderésultatspossiblesquedecodagespossiblessur4binaires=24=16Onpeutdoncfaireletableaudesrésultatspourles16caspossibles:

P Q et P xor ou ó Q =>

P Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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

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

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

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

Celanousmontrequ’ilya9autresopérateursqueceuxquisontintuitifspournous.Onpeutimaginerdesthéoriesaveccesopérateurs.

Priorité des opérateurs 1. Les parenthèses sont prioritaires sur les opérateurs. 2. L’opérateur unaire de négation est prioritaire sur les opérateurs binaires 3. L’opérateur « et » est prioritaire sur l’opérateur « ou » 4. Les opérateurs de comparaison arithmétique (==, >, >, etc) sont prioritaires sur les opérateurs

de logique propositionnelle (et, ou, implique, etc.). 5. L’opérateur <=> est le moins prioritaire : on commence toujours par évaluer les propositions

qui l’entoure avant lui (sauf s’il y a des parenthèses). 6. L’opérateur => est le moins prioritaire, juste derrière l’opérateur <=> : on commence toujours

par évaluer les propositions qui l’entoure avant lui (sauf s’il y a des parenthèses).


Exercices récapitulatifs

Écrire la négation des assertions suivantes sans parenthèses où P, Q, R, S sont des propositions 1. P⇒Q 2. P et nonQ

(Exercice 8 de exo7.emath.fr).

Traduire en langage symbolique les expressions suivantes Si on a une implication, donner la contraposée. Donner la formulation en français de la traduction symbolique. Donner la formulation en français de la contraposée, s’il y a lieu. 1. Le monde n’a ni commencement ni fin. 2. Un quadrilatère est un carré seulement si c’est un losange. 3. Pour que cette enveloppe soit ouverte il faut que Jean ait été informé à moins que Pierre ait

oublié de la coller. 4. On ne devient pas un musicien accompli sans apprendre à lire les notes et à jouer d’un

instrument. 5. Si le règlement est très strict mais est le même pour tout le monde alors les étudiants ont tort

de le contester.

Construire la table de vérité des expressions précédentes à partir de leur formule en langage symbolique

Faire la table de vérité des expressions suivantes 1. (p ou !q) et ( !p ou q) 2. !p => (p ou q) 3. p ou !q => !p ou r

La proposition suivante est-elle vraie ? 4. P ∧ Q ⇒ (¬P) ∨ Q

(Exercice 19 de exo7.emath.fr)


3 : Propriétés et démonstration

Propriétés = tautologies

Définition Les propriétés sont des expressions logiques qui sont toujours vraies. On les appelle des « tautologies »

Propriétés de base Les premières propriétés sont assez évidentes. 1 Principe d’identité P ⇔ P 2 Principe de non contradiction non (P ⇔ non(P)) 3 Principe du tiers exclu (P ou non(P)) 4 Double négation P ⇔ non(non(P)) 5 Commutativité du « et » P et Q ⇔ Q et P 6 Commutativité du « ou » P ou Q ⇔ Q ou P 7 Associativité du « et » (P et Q) et R ⇔ P et (Q et R) 8 Associativité du « ou » (P ou Q) ou R ⇔ P ou (Q ou R)

Distributivité On a une distributivité du « ou » sur le « et » et du « et » sur le « ou ». 9 Distributivité du « ou » sur le « et » P ou (Q et R) ⇔ (P ou Q) et (P ou R) 10 Distributivité du « et » sur le « ou » P et (Q ou R) ⇔ (P et Q) ou (P et R)

Lois de Morgan

11 Loi de Morgan - 1 non(P et Q) ⇔ non(P) ou non(Q) 12 Loi de Morgan - 2 non(P ou Q) ⇔ non(P) et non(Q)

Application des lois de Morgan : transformation de l’implication en disjonction On sait déjà que p = > q ó -(P et -Q) D’après les lois de Morgan : -(P et -Q) ó -P ou Q Donc : 13 Transformation de l’implication en disjonction ( P ⇒ Q ) ⇔ nonP ou Q


Propriétés utiles Ø p et !p <=> faux Ø p ou !p <=> vrai Ø p ou faux <=> p Ø p et faux <=> faux Ø p ou vrai <=> vrai Ø p et vrai <=> p Ø p ou pq <=> p


Table de vérité et démonstration des propriétés

Tautologie et table de vérité La table de vérité d’une tautologie ne contient que des 1 (que des Vrai).

Méthode de démonstration Pour démontrer les propriétés, on utilise un tableau de vérité et on calcule la valeur de vérité de la propriété à démontrer. Dans tous les cas pour les propositions de départ, la tautologie doit être vraie.

Double négation

Ø Démonstration :

P non (P) non(non(P)) P ⇔ non(non(P)) Vrai Faux Vrai Vrai Vrai Faux Vrai Vrai Faux Vrai Faux Vrai Faux Vrai Faux Vrai

On a que des vrais pour la tautologie quelles que soient les valeurs de départ de chacune des propositions atomiques.

Distributivité du « ou » sur le « et » P ou (Q et R) ⇔ (P ou Q) et (P ou R)

Ø Démonstration :

P Q R Q et R A = P ou (Q et R)

P ou Q P ou R B= (P ou Q) et (P ou R)

A<=>B

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

On a que des 1 (vrai) pour la tautologie T quelles que soient les valeurs de départ de chacune des propositions atomiques.



Démontrer les propriétés suivantes 1. Démontrez avec une table de vérité les lois de Morgan (tautologies 11 et 12). 2. Démontrer avec une table de vérité l’équivalence entre implication et disjonction (tautologie

13).

Donner la négation des phrases suivantes : 1. x >= 3 2. 0 < x <=2 3. p et q et r 4. p ou q ou r 5. p ou q et r 6. (p ou q) et r

Développez jusqu’à retirer les parenthèses et simplifiez 1. non(a et b) ou a 2. non(a ou b) et a

Développez jusqu’à écrire la proposition sous la forme de suites de disjonctions de conjonctions : 1. a et non(b et c)

Développez jusqu’à écrire la proposition sous la forme de suites de conjonctions de disjonctions :

1. a ou non(b ou c)

Sachant que P, Q, R, S sont des propositions, écrire à la négation des propositions suivantes sous la forme d’une disjonction de propositions atomiques ou de conjonctions.

1. P et (Q et R) 2. P ou (Q et R) 3. (P et Q) ⇒ (R ⇒S)

(Exercice 8 de exo7.emath.fr)

Vérifiez les résultats précédents avec une table de vérité.


4 : Raisonnement (ou syllogisme)

Le modus ponens : (p et p=>q) => q Un raisonnement est une méthode pour produire une proposition à partir de 2 autres propositions. La forme de base de tout raisonnement est la suivante :

(p et p=>q) => q

La proposition « p=>q » est appelée : proposition majeure ou Majeure. La proposition « p » est appelée : proposition mineure ou Mineure. La proposition « q » est appelée : Conclusion. La forme de base (p et p=>q) => q est appelée : « modus ponens » ou encore « règle du détachement » : c’est une tautologie.

Remarque Quand on a dit « p => q », on n’a dit ni « p », ni « q » : on ne connaît pas les valeurs de vérité de « p » et de « q ». Si maintenant on pose que p est vrai, alors on peut en déduire que q est vrai. On peut écrire : p + p => q = q

La contraposée (modus tollens) : (non q et p => q) => non p Il existe de nombreuses dérivés à la forme de base. La principale est la contraposée ou modus tolens :

(non q et p => q) => non p

Ø Démonstation Sachant que a=>b <=> !(a et !b) : (p et p=>q) => q

ó ! ( (p et p=>q) et !q) ó ! ( p et (p =>q) et !q) ó ! ( !q et (p =>q) et p) ó ! ( (!q et (p =>q)) et !(!p)) ó (!q et (p =>q) => ( !p)



Série 1 1. Démontrez que le modus tollens est une tautologie. 2. Démontrez que le modus ponens est une tautologie. 3. Démontrez que -p + p xor q => q 4. Démontrez que a xor b <=> (a et !b) ou ( !a et b)

Série 2 Pour chaque raisonnement proposé, démontrez sa validité ou sa non validité. Commencer par exprimer les propositions atomiques qu’ils recèlent, puis la ou les propositions complexes et faites les déductions. Pour déterminer les implications, on utilisera la méthode de la condition suffisante : l’antécédent d’une implication est la condition suffisante du conséquent. Il suffit d’avoir l’antécédent pour avoir le conséquent.

1. Pour gagner la course, il faut courir très vite. Or j’ai gagné la course, donc j’ai couru très vite. 2. Il suffit qu’il pleuve pour que l’escargot sorte, or il pleut, donc l’escargot sort. 3. Il suffit qu’il pleuve pour que l’escargot sorte, or l’escargot sort. Donc il pleut. 4. Pour ne pas rater cet exercice, il faut garder la tête froide. Or vous ne perdez pas la tête. Donc

vous ne raterez pas cet exercice. 5. Si mon raisonnement est valide, je ne raterai pas mon exercice. Or ou bien je rate mon

exercice, ou bien la logique est facile. Et précisément la logique n’est pas facile, donc mon raisonnement n’est pas valide.


5 : Applications aux circuits booléens

Forme normale disjonctive

Eléments

Ø PC : proposition conjonctive On appelle proposition conjonctive (PC) une proposition constituée de propositions atomiques ou de leurs négations reliées entre elles uniquement par des conjonctions (et). « p et !q et r » est une proposition conjonctive.

Ø FND : forme normal disjonctive On appelle forme normale disjonctive (FND) une proposition constituée de propositions atomiques ou de leurs négations ou de propositions conjonctives (PC) reliées entre elles uniquement par des disjonctions (ou). « (p et !q et r) ou (!p et q) ou r » est une FND. On l’écrit souvent : p!qr ou !pq ou r.

Ø FD : si on a un atome et sa négation Une FND ne doit pas présenter un atome seul (p, q, etc.) et sa négation dans une PC. « pqr ou !pqr ou r » est une FND. « r » est le seul atome. !r n’est pas présent dans une PC de la FND. « p ou (!p et q) » est une simple forme disjonctive : FD. Ce n’est pas une FND car p est un atome et !p se trouve dans une PC. La FND correspondante est : « p ou q ». Il suffit d’appliquer la distributivité du ou sur le et pour arriver au résultat : p ou (!p et q) <=> (p ou !p) et (p ou q) <=> vrai et (p ou q) <=> p ou q

Ø FND-TD : une FND peut s’écrire sous la forme d’une FND totalement développée Par exemple : « ab ou !ac » <=> « abc ou ab!c ou !abc ou !a!bc » Une FND-TD est une FND dont chaque PC contient tous les atomes de la proposition. A partir d’une FND, on peut trouver la FND-TD en ajoutant à chaque PC tous les cas possibles avec les autres atomes : ce qu’on a fait dans l’exemple.


Propriétés Ø Toute proposition peut s’écrire sous la forme d’une FND. Ø Une proposition peut avoir plusieurs FND. Ø Une proposition a une et une seule FND-TD

Méthode pour construire la FND-TD d’une proposition Il suffit de faire la table de vérité de la proposition traitée. On regarde quelles sont les lignes sont vraies pour la proposition. Chaque ligne vraie va correspondre à une PC de la FNDTD Chaque PC sera la conjonction des propositions atomique, vraies ou fausses (si elles sont fausses on prend leur négation dans la PC).

Méthode 1 pour construire une FND Traduire tous les connecteurs en « non », « et » et « ou ». Eliminer les doubles négations. Utiliser les lois de Morgan pour que les négations portent sur des atomes. Utiliser les lois de la distributivité pour « sortir » les « ou » des parenthèses et « entrer » les « et » dans les parenthèses.

Méthode n°2 pour construire une FND Construire la FNDTD à partir de la table de vérité. Il reste ensuite à transformer le résultat pour obtenir une FND simplifiée. Ce n’est pas toujours facile. Les tableaux de Karnagh nous faciliteront le travail.


Exercices de FND 1. Démontrez que p ou pq <=> p Pour chaque expression :

• Donnez la FND-TD à partir de la table de vérité • Trouvez une FND par la méthode 1. • Transformez la FND en FNT-TD

1. a (b ou !a) ou c 2. ab ou bc et ca 3. (a ou bc)( !a ou !b !c) 4. !( (p=>q)=>r ) 5. (q ou r) => (r=> !q)


Tableaux de Karnaugh

Utilité Ces tableaux permettent de produire des formes normales disjonctives (FND) plus facilement.

Tableau à 2 variables : a et b Le tableau a 4 cases. On croise les valeurs de vérité de a et de b. b �b b �b

a a b a�b a a b a�b

�a �a b �a �b �a �a b �a �b

a +�b Quand on a une expression, par exemple : ab +�b , on colorie la case du ab et la colonne du�b . A partir de là, on analyse le résultat graphique pour produire la FND la plus simple. Ici on voit que la ligne du a est pleine ainsi que la colonne du b, donc on peut écrire : ab +�b = a +�b On aurait pu trouver ce résultat par calcul, mais ça va plus vite avec le tableau. Par calcul : ab +�b ó (a +�b) et (b +�b) ó (a +�b) et (b +�b) ó (a +�b) et Vrai ó (a +�b)

Tableau à 3 variables : a, b et c Le tableau aura 8 cases : on croise les valeurs de vérité de a avec celles des couples possibles entre b et c : b c, b�c, �b�c, �b c dans cet ordre là par convention. b c b�c �b�c �b c

a a b c a b�c a�b�c a�b c

�a �a b c �a b�c b �a�b�c �a�b c

La première ligne correspond à « a », la deuxième à « non a » Les deux premières colonnes correspondent à « b » Les deux dernières colonnes correspondent à « non b » Les deux colonnes du milieu correspondent à « non c » La première et la dernière colonne correspondent à « c »


Ø Utilisation Soit l’expression : non(a)b + abc + non(c)b + non(a)non(b) On remplit le tableau en conséquence : b c b�c �b�c �b c

a a b c a b�c a�b�c a�b c

�a �a b c �a b�c b �a�b�c �a�b c

Quelle FND peut-on produire à partir du tableau ? On a la ligne du non(a) et les colonnes du (b) Donc non(a)b + abc + non(c)b + non(a)non(b) ó non(a) + b

Tableau à 4 variables : a, b, c et d Le tableau aura 16 cases : on croise les valeurs de vérité de du couple ab avec celles du couple cd. L’utilisation est la même que pour un tableau à 3 variables.

Exercices de tableaux de Karnaugh 1. Reprendre les FND-TD des exercices de FND et simplifiez les FNT-TD à l’aide de tableau de

Karnaugh : vérifiez que vous retrouvez les mêmes résultats.

2. Soit A = ab + non(c) et B=non(a) + bc Déterminer la FND et non(A) et de non(B) en utilisant un tableau de Karnaugh, puis sans tableau.

3. Soit A=non(c)a+non(b)c+abd et B=non(a)b+non(b)c+non(c)a Déterminer la FND et non(A) et de non(B) en utilisant un tableau de Karnaugh, puis sans tableau.


Circuit à relais L’intérêt de la FND et du tableau de Karnaugh est de réaliser plus facilement des circuits électroniques.

Notion de relais Les relais peuvent être ouverts ou fermés et ainsi laisser ou non passer le courant. Un relais ouvert vaut 1. Un relais fermé vaut 0.

Circuit ET Le courant circule de l’entrée E vers la sortie S en passant par 2 relais A et B. E ---------------------- A ------------------------ B -----------------------S Le courant passe si A et B sont ouverts. La fonction du circuit est f(A,B) = A et B

Circuit OU Le courant circule de l’entrée E vers la sortie S en passant par 2 relais A et B. |--------------A ------------| E --------------------- | |-----------------------S |--------------B ------------| Le courant passe si A ou B sont ouverts. La fonction du circuit est f(A,B) = A ou B

Circuit complexe en OU |-----A-------------non B----| E --------------------- |--A----------B---------C----|-----------------------S |-------A------------non C---| La fonction du circuit est f(A,B,C) = (A et non B) ou (A et B et C) ou (A et non C) C’est une FND

Circuit complexe en ET |--A--| |-----B----| |--non A--| E --------------------- | |-----| |------|--non B--|-----------------------S |--C--| |--non C--| |-----C-----| La fonction du circuit est f(A,B,C) = (A ou C) et (B ou non C) et (non A ou non B ou C)


Simplification L’objectif est de fabriquer un circuit le plus simple possible. Dans nos 2 exemples complexes, on peut simplifier le circuit. Pour ça, il suffit de trouver la FND correspondant à la fonction du circuit. Pour cela, on peut passer par un tableau de Karnaugh. Ensuite, on peut reconstruire le circuit de façon simplifiée.

Exercices de circuits à relais Simplifier les deux circuits complexes présentés ci-dessus en FND.


Circuit électronique

Circuit de l’additionneur bit a bit On additionne x et y ainsi qu’un report d’addition : c (1 + 1 = 10, je pose 0 et je retiens 1. Le 1 que je retiens, c’est le report d’addition). Le résultat vaut Z, la retenue r L’objectif est de construire le circuit permettant de faire cette addition.

Table de vérité l’additionneur 1 bit Entrées Sorties

x y c Z r 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0

Z = (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c) r = (x y c) + (x ¬y c ) + (¬x y c) + (x y ¬c)

FND de Z et de r r = (x y c) + (x ¬y c ) + (¬x y c) + (x y ¬c) x y x�y �x�y �x y

c c x y c x�y c�x�y c�x y

�c �c x y �c x�y b �c�x�y �c�x y

r= xy + xc + yc Z = (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c) x y x�y �x�y �x y

c c x y c x�y c�x�y c�x y

�c �c x y �c x�y b �c�x�y �c�x y

Cette configuration du tableau de Karnaugh correspond à une situation particulière qu’on n’a pas abordée : le ou exclusif


Z = x ⊕ y ⊕ c

Ø Exercice de vérification Prouver avec une table de vérité que : x ⊕ y ⊕ c ó (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c)

Transformation supplémentaire r= xy + xc + yc ó r = xy + c ( x + y ) ó r = xy + c ( x ⊕ y ) Cette dernière équivalence n’a rien d’évident ! L’intérêt de cette formulation est qu’on trouve une opération commune entre Z et r, ce qui facilitera la construction du circuit.

Ø Exercice de vérification Prouver avec une table de vérité que : xy + c ( x + y ) ó xy + c ( x ⊕ y )

Conclusion Z = x ⊕ y ⊕ c r = xy + c ( x ⊕ y ) = ( x ⊕ y ) c + xy

Circuit électronique de l’additionneur 1 bit

Ø Les 4 portes logique de base des circuits électroniques A

-a

ab

a + b

a ⊕ b


Ø Construction du circuit d’additionneur 1 bit On additionne A et B (qui correspondent à nos x et y précédent). Le report d’addition est Cin (qui correspond à notre c précédent). Le résultat de l’addition est S (qui correspond à notre Z précédent). La retenue est Cout (qui correspond à notre c précédent).

On avait pour notre additionneur : Z = x ⊕ y ⊕ c r = xy + c ( x ⊕ y ) On a donc dans ce schéma : S = A ⊕ B ⊕ Cin

Cout = AB + Cin ( A ⊕ B ) ó Cout = ( A ⊕ B ) Cin + AB

On commence par A ⊕ B : premier XOR S = A ⊕ B ⊕ Cin Cout = ( A ⊕ B ) Cin + AB

Ensuite on fait ⊕ Cin : deuxième XOR : on a S en sortie S = A ⊕ B ⊕ Cin

Ensuite on fait ( A ⊕ B ) Cin : premier ET Cout = ( A ⊕ B ) Cin + AB

Ensuite on fait AB : deuxième ET Cout = ( A ⊕ B ) Cin + AB


Enfin on fait le OU restant : Cout = ( A ⊕ B ) Cin + AB

Ø Exercice de vérification de l’additionneur 1 bit Faire la table de vérité du circuit


LOGIQUE DES PREDICATS

1 : Logique des prédicat (logique d’ordre 1)

Présentation La logique des prédicats ou logique d’ordre 1 permet d’écrire des propositions avec des variables : « Pour tout x, x2>=0 » s’écrit : ∀x ∈ N, x2>=0 « Certains chats sont gris » s’écrit : ∃x, Cx Gx « Tous les hommes sont mortels » s’écrit : ∀x, Hx => Mx La négation de tous les hommes sont mortels s’écrit : -(∀x, Hx => Mx) ou encore ∃x, Hx –Mx Le chapitre présente le formalisme pour aboutir à ces écritures.

Variables et prédicats

Proposition Une proposition est un énoncé ayant un sens et qui est vrai ou faux.

Notion de variable La logique des prédicats fait intervenir des variables dans les énoncés. Une variable correspond à un objet non déterminé.

Ø Exemples x, dans « x est un chat », est une variable. x, dans l’énoncé « x = 3 » est une variable.

Ø Formalisme Les variables s’écrivent : x, y, z, etc. Fin de l’alphabet, en minuscule.

Notion de prédicat Le prédicat, c’est ce qu’on affirme de la variable. C’est l’attribut du sujet si le verbe est « être ». C’est le verbe dans les autres cas.

Ø Exemples Dans l’énoncé « x est un chat », un « chat », ou « chat » est le prédicat. Dans l’énoncé « x mange », « mange » est le prédicat. On peut aussi dire « x est mangeant ».


Ø Formalisme Les prédicats s’écrivent : P, Q, etc. En majuscule. « x est un chat » s’écrit : Cx, C étant le prédicat « Chat ».

Notion de constante Une variable correspond à un objet non déterminé. Une constante correspond à un objet déterminé.

Ø Exemples « Tom est un chat » est une proposition vraie. « Tom» est une constante (le chat du dessin animé). Chat est un prédicat. Tom est un Chat concret. On dit aussi que c’est une « instance » de Chat.

Ø Formalisme Les constantes s’écrivent : a, b, c, etc. Début de l’alphabet, en minuscule. « Tom est un chat » s’écrit Ca, C étant le prédicat « Chat » et « a » étant l’objet Tom.

Notion d’énoncé « Px », « x est un chat », « Cx », « x=3 » sont des énoncés. Etant donné qu’ils incluent une variable, on ne sait pas s’ils sont vrais ou faux. Px n’est donc pas une proposition. Pas plus que « x est un chat », ni « x=3 ».

Rappel : Variable mathématique (ou logique) et variable informatique

Ø Variable mathématique Une variable mathématique a les caractéristiques suivantes : • Elle n’est pas forcément déterminée : quand j’écris x5+x4+x3+x2+x=2, il n’est pas certain

que je puisse trouver la valeur de x ! • Elle peut avoir de 0 à N valeurs : quand j’écris 4x2 + x + 3, la théorie nous dit que x aura

0 valeurs (pas de solution), 1 valeur (une seule solution) ou 2 valeurs possibles (2 solutions). • Les valeurs possibles d’une variable ne change jamais. Par contre, on peut diminuer le

nombre de valeurs possibles. Si on dit x2=1, on a deux valeurs possibles : 1 et -1. Si on ajoute x>0, il ne reste qu’une valeur possible : 1.

Ø Variable mathématique Une variable informatique à des caractéristiques totalement opposées ! • Elle est toujours déterminée : quand on déclare une variable, elle est forcément dans un

état physique auquel correspond une certaine valeur selon l’interprétation qu’on en a (c’est-à-dire selon son type). Même la valeur « undef » correspond à une valeur possible !

• Elle ne peut avoir qu’une seule valeur : quand variable est dans un état unique qui correspond à sa valeur unique.

• La valeur d’une variable change à chaque affectation. En cours de programme, on peut changer la valeur des variables.


Quantificateurs

Notion de quantificateur Pour transformer un énoncé avec un prédicat en proposition, on introduit 2 quantificateurs : • Le symbole ∀ signifie « pour tout » : c’est le quantificateur universel. • Le symbole ∃ signifie « il existe » : c’est le quantificateur existentiel.

Propositions prédicatives Pour passer d’un énoncé prédicatif à une proposition, on précède l’énoncé par un quantificateur associé à une variable : « ∀x Px » est un proposition qui se lit « pour tout x, x est un P » ou « pour tout x, P de x est vrai » « ∃x Px » est une proposition qui se lit « il existe au moins un x tel que x est un P » ou « il existe au moins un x tel que P de x soit vrai ».

Formalisme : virgules et parenthèses Pour faciliter la lecture, on peut mettre des virgules ou des parenthèses entre les termes d’une proposition : « ∀x, Px », « (∀x)Px », « ∀x (Px) »

Exemples On peut trouver beaucoup d’exemples de proposition simple et vraie avec le quantificateur existentiel : « Il existe un chat » : « ∃x Cx » « Il existe x tel que x = 3 » : « ∃x, x∈ N et x=3 » Dans ce dernier cas, on peut aussi écrire : « ∃x ∈ N, x=3 ». On pourrait aussi écrire, mais ce n’est pas l’usage : « ∃x, Nx et x=3 », avec N pour le prédicat « Nombres entiers ». Il est plus difficile de trouver des propositions simples et vraies avec le quantificateur universel. On a toutefois des propriétés mathématiques simples qu’on peut exprimer : « Pour tout x, x2>=0 » : « ∀x ∈ N, x2>=0 »


Construction de proposition simple : 1 seule variable, 1 seul quantificateur

Exemples

Ø Comment traduire : « x > 3,5 » ∃x, x ∈ R ∧ x > 3,5 : « il existe un x tel que x ∈ R et x > 3,5 » Cette proposition est vraie. ∧ est le connecteur « et ». On peut remplacer le « ∧ » par une virgule : ∃x, x ∈ R, x > 3,5 On peut aussi écrire : « ∃x ∈ R, x > 3,5 » et se dit : « il existe au moins un x appartenant à R tel que x > 3,5 » Donc : le ∃ introduit un « tel que » dans la phrase.

Ø Comment traduire : « x2 > x » « ∀x, x ∈ R => x2 > x » c’est-à-dire :« pout tout x, si x appartient à R, alors x2 > x » Cette proposition est vraie. Cette proposition s’écrit habituellement : « ∀x ∈ R, x2 > x » et se dit « pour tout x appartenant à R, x2 > x » Donc : le ∀ introduit un « si … alors » dans la phrase, qui peut être supprimé à l’usage.

Ø Comment traduire : certains hommes sont chauves ? avec ∃ et ∧ C : prédicat Chauve, H : prédicat Homme ∃x, Hx ∧ Cx : il existe x tel que x est un Homme et x est Chauve.

Ø Comment traduire : tous les hommes sont mortels ? avec ∀ et => M : prédicat Mortel, H : prédicat Homme ∀x, Hx => Mx : « pour tout x, si x est un homme alors x est mortel »

Formalisme Plutôt que : « ∃x, x ∈ R ∧ x > 3,5 », on écrit « ∃x∈ R, x > 3,5 » qui traduit : « Il existe un réel tel que x >3,5 » Plutôt que : « ∀x, x ∈ R => x2 > x », on écrit « ∀x ∈ R, x2 > x » qui traduit : « pour tout x appartenant à R, x2 > x »

Ø Généralisation : Soit C, le prédicat Chat, N le prédicat Noir. On peut écrire : « ∃x∈ C, Nx » pour dire « il existe un chat noir ». De même, pout dire « tous les hommes sont mortels», on peut écrire : ∀x∈ H, Mx

Constat Le quantificateur existentiel ∃ est en général associé à une conjonction : ∧ Le quantificateur universel ∀ est en général associé à une implication : =>


Construction de propositions complexes : plusieurs variables, plusieurs quantificateurs

Exemples ∀x ∈ R, ∃y ∈ R, y > x : Traduction : « pour tout x appartenant à R, il existe au moins un y appartenant à R tel que x>y » Cette proposition est vraie. On peut aussi l’écrire ainsi : ∀x, ∃y, (x ∈ R ∧ y ∈ R) => y > x Traduction : « pour tout x, il existe au moins un y tel que si x appartient à R et y appartient à R, alors y >x »

Règle d’écriture Tous les quantificateurs doivent être placés avant les prédicats.

On peut avoir des prédicats unaires, ou binaires ou plus Prédicat Préférer : x préfère y : Pxy Prédidat PréférerA : x préfère y à z : Pxyz

Commutativité des quantificateurs ∀x ∈ R, ∃y ∈ R, y > x ó ∃y ∈ R, ∀x ∈ R, y > x Traduction : : « il existe au moins un y appartenant à R tel que, pour tout x appartenant à R, x>y » ∀x, ∃y, (x ∈ R ∧ y ∈ R) => y > x ó ∃y, ∀x, (x ∈ R ∧ y ∈ R) => y > x Traduction : « il existe au moins un y tel que, pour tout x, si x appartient à R et y appartient à R, alors y >x »

Exercices

Traduisez les énoncés suivants du langage naturel au langage du calcul des prédicats 1. Une porte est ouverte ou fermé. On prendra : Px : x est un porte. Ox : x est ouvert. Fx : x est

fermé. 2. Toutes les vérités sont mathématiques. On prendra : Vx : x est une vérité. Mx : x est

mathématiques. 3. Les élèves préfèrent le cours de python au cours de logique formelle. On prendra : Ex : x est

un élève. Cx : x est un cours. Pxyz : x préfère y à z. 4. Tout ce qui brille n’est pas en or. 5. Il y a des peines et des plaisirs, mais aucune peine n’est un plaisir. 6. Les seules peines qui soient des plaisirs sont les peines d’amour. 7. Il y a des bonnes actions qui ne sont pas récompensées mais aucune mauvaise action n’est

récompensée.


2 : Déduction immédiate

Notion de déduction immédiate La déduction immédiate, c’est ce qui permet de passer d’une proposition à une autre, sans passer par une proposition intermédiaire. La base de la déduction immédiate, c’est le principe d’équivalence A ó ¬(¬A) Ce qui nous amène aux lois de Morgan : ¬(A ∧ B) ó ¬A ∨ ¬B On va donc s’intéresser à la négation des quantificateurs.

Négation des quantificateurs

Approche par le langage naturel Quelle est la négation de « tous les hommes sont mortels » ? « Il existe un homme qui n’est pas mortels » Le « tous » est transformé en « il existe » Le prédicat est nié.

Propriétés ¬ (∀x, Px) ó ∃x, ¬ Px ¬ (∃x, Px) ó ∀x, ¬ Px ¬ (∀x, ∃y, Pxy) ó ∃x, ∀y, ¬ Pxy : ceci étant généralisable quelque soit le nombre de quantificateurs.

Exemples

Ø C : Chat, N : Noir ¬ ( ∃x∈ C, Nx) ó ∀x∈ C, ¬Nx Dire « il est faux qu’il existe un chat noir », c’est dire « aucun chat n’est noir »

Ø ¬ (∀x∈ C, Nx) ó ∃x∈ C, ¬ Nx Dire « il est faux que tous les chats sont noirs », c’est dire « il existe un chat non noir ».

Ø H : Homme, M : Mortel ¬ (∀x, Hx => Mx) ó ∃x, Hx ∧ ¬Mx Dire « il est faut que tous les hommes sont mortels « , c’est dire « il existe un homme qui n’est pas mortel ».

Démonstration

Ø H : Homme, M : Mortel ∀x, Hx => Mx <=> ∀x, -Hx ou Mx


Donc -(∀x, Hx => Mx) <=> -(∀x, -Hx ou Mx) <=> ∃x -(-Hx ou Mx) <=> ∃x Hx et -Mx

Contraposé

Rappel La contraposé : P=>Q ó nonQ => nonP Je parle donc j’existe ó je n’existe pas donc je ne parle pas

Contraposé et quantificateur universel Dire « Tous les hommes sont mortels », c’est dire la même chose que « Tous les immortels sont inhumains ». ∀x, Hx => Mx ó ∀x, ¬Mx => ¬Hx


Carré logique Le carré logique résume dans un schéma les relations et les déductions que l’on peut faire à partir des quatre types de propositions possibles : Universelle affirmative, Universelles négatives, Particulières affirmatives et Particulières négatives. Les diagonales représentent la contradiction : ¬Ua ó Pn et ¬Un ó Pa Attention, le contraire, ou le subcontraire, ce n’est pas la même chose que le contradictoire : contraires et subcontraires n’expriment pas la véritable contradiction. Les termes (toujours, jamais, parfois oui, parfois non) concernent la logique temporelle. Les termes (obligatoire, interdit, permis, facultatif) concernent l’éthique. Les termes (nécessaire, impossible, possible, contingent) concernent la modalité (le pouvoir être). Tous ces termes sont différemment interprétés par les logiciens ! ∀x (Px => Qx) ∀x (Px => ¬Qx) Universelle affirmative Universelle négative Tous les chats sont gris Aucun chat n’est gris Toujours Jamais Obligatoire contraires Interdit

Nécessaire ó Impossible ó Ne peut pas ne pas être Ne peut pas être

Codé A Codé E Subalternes contradictoires Subalternes

Ua => Pa Un => Pn Pa ⊂ Pb Pn ⊂ Un ∃x (Px => Qx) ∃x (Px => ¬Qx)

Particulière affirmative subcontraires Particulière négative Certains chats sont gris Certains chats ne sont pas gris Parfois oui Parfois non Permis=Autorisé Facultatif Possible ó Contingent ó Peut être Peut ne pas être Codé I Codé O


Exercices

Trouvez la négation 1. Dans l’exercice précédent (chapitre 1), donnez la négation des énoncés trouvés en langage

du calcul des prédicats. 2. Traduisez cette négation en langage naturel.

Parmi les énoncés suivants, trouvez les équivalents et les opposés (contradictoire) 1. Pour argumenter de façon logique, on commencera par traduire les énoncés la langue du

calcul des prédicats. 2. Les amours heureuses sont imaginaires. 3. Les amours imaginaires sont heureuses. 4. Les amours malheureuses ne sont pas imaginaires 5. Il n’y a pas d’amours heureuses qui ne soient pas imaginaires 6. Il n’y a d’imaginaire que les amours heureuses 7. Toutes les amours imaginaires sont heureuses


3 : Raisonnement

Rappel : la règle du détachement : (p+ p=>q) => q Un raisonnement, une méthode pour produire une proposition à partir de 2 autres propositions. La règle fondamentale reste celle du détachement (ou modus ponens) : (p + p=>q) => q p=>q est appelée : proposition majeure ou Majeure p est appelée : proposition mineure ou Mineure q est appelée : Conclusion

Application aux prédicats

Présentation Les raisonnements fonctionnent de la même manière en logique des propositions et en logique des prédicats. Il y a 4 règles de raisonnements classique qu’on peut traduire sous forme de prédicat. Ces raisonnements se construisent avec 3 propositions : 1 Majeure, une Mineure et une Conclusion. Chacune de ces propositions peut correspondre à un des coins du carré logique et donc avoir un code. Les raisonnements avaient été classés par des moyens mnémotechnique : 1 mot avec les 3 voyelles correspondant à chaque proposition.

BARBARA Le syllogisme BARBARA est constitué de trois propositions A. (Barbara vient de Barbarum en latin qui veut dire Emplatre). Tous les humains sont mortels (A) Les Français sont des humains (A) Donc les Français sont mortels (A) ∀x, Hx => Mx + ∀x, Fx => Hx = ∀x, Fx => Mx


DARII Le syllogisme DARII est constitué d’une proposition A et de deux propositions I (Darii vient de Darius en latin qui était une pièce d’or perse). Tous les humains sont mortels (A) Je suis un humain (I) Donc je suis mortel(I) a : instance de H valant moi ! ∀x, Hx => Mx + Ha = Ma

CELARENT Le syllogisme CELARENT est constitué d’une proposition A et de deux propositions E (Celarent vient de Celo en latin qui veut dire cacher). Aucun humain n’est immortel (E) Les français sont humains (A) Donc aucun français n’est immortel (E)

∀x, Hx => ¬Ix + ∀x, Fx => Hx = ∀x, Fx => ¬Ix

FERIO Le syllogisme FERIO est constitué d’une proposition E, d’une I et d’une O (Ferio veut dire frapper en latin). Aucun humain n’est immortel Je suis un humain Donc je suis ne suis pas immortels a : instance de H valant moi ! ∀x, Hx => ¬Ix + Ha = ¬Ia

Diagrammes Ces raisonnements se représentent avec des ensembles en mixant les diagrammes de VENN, les diagrammes d’EULER et les instances dans les ensembles.


Exercices Tirer les conclusions des prémisses proposées. Vous devez écrire les prémisses sous la forme de propositions prédicatives. Puis trouver la forme du raisonnement que vous allez appliquer 1. Nul animal à respiration branchiale n’est une baleine. Or tout poisson a une respiration

branchiale. 2. Tous les chats sont des créatures qui comprennent le français. Quelques poulets sont des

chats. 3. Tous les logiciens sont perspicaces. Tout étudiants est logicien. 4. Aucun chat ne sait voler. Les animaux sont des chats. 5. Aucun professeur n’est naïf. Alfred est professeur. 6. Les Français sont européens. Certains francophones sont français. 7. Les animaux légendaires n’existent pas. Les licornes sont des animaux légendaires. 8. Tous les végétaux de ce jardin sont rouges. Ces fleurs viennent de ce jardin.

Documents

Mathématiques appliquées à l’informatique 3 – Logique ...bliaudet.free.fr/IMG/pdf/Maths-03-Logique.pdf · LOGIQUE DES PREDICATS 43 1 : Logique des prédicat (logique d’ordre