[PDF] Mathématiques discr`etes Chapitre 3 : Logique prédicats

View - Download Mathématiques discr`etes Chapitre 3 : Logique prédicats

Previous PDF

Next PDF

U.P.S. I.U.T. A, D´epartement d"Informatique Ann´ee 2010-2011 Math

´ematiques discr`etes

Chapitre 3 : Logique, pr´edicats

1. Propositions, Connecteurs

Propositions

D´efinition :On appellepropositionun ´enonc´e ayant un sens et dont on peut dire s"il est vrai ou faux.

Exemples 1

"3 est un entier pair" "7 est un nombre premier" "Toulouse est une ville d"Espagne"

Attention :

"n?Netnest pair" n"est pas une proposition, parce que cet ´enonc´e n"est pas vraiou faux : sa valeur de

v´erit´e d´epend den.

"la pr´esente affirmation est fausse" n"est pas une proposition (il y a des r`egles pr´ecises de construction des

propositions, nous ne rentrons pas dans ces d´etails ici).

Usuellement, on d´esigne les propositions par des lettres :A,B,C ...,p,q,r,...et on leur attribue une

valeur de v´erit´e: vrai (V,1) ou faux (F,0).

Connecteurs

En calcul arithm´etique, les nombres s"ajoutent, se retranchent, se multiplient,... de fa¸con analogue, lecalcul

propositionnelpermet de combiner les propositions entre elles au moyen deconnecteurs logiques, ce proc´ed´e

permet de construire d"autres propositions.

Sipest une proposition (un ´enonc´e sans ambigu¨ıt´e) on lui associe satable de v´erit´e(toutes les ´eventualit´es).

p 0 1

1) N´egation

Lan´egationdepest la proposition qui est fausse lorsquepest vraie, et vraie lorsquepest fausse. On la

note non(p), ou¬pou p. p¬p 01 10

2) Conjonction

Soientpetqdeux propositions. Leurconjonctionest vraie lorsque toutes les deux sont vraies, on l"obtient

en liantpetqpar le mot "et" :petq, not´e aussip?q. pqp?q 000 010 100
111
1

Exemples 2

•p: "3 est un entier pair" ;q: "4 est un entier impair" •p: "6 est un multiple de 2" ;q: "6 est un multiple de 3"

3) Disjonction

Soientpetqdeux propositions. Leurdisjonctionest vraie lorsque l"une au moins est vraie, on l"obtient en

liantpetqpar le mot "ou" :pouq, not´e aussip?q. pqp?q 000 011 101
111

Exemples 3

•p: "9 est un multiple de 2";q: "9 est un multiple de 3" •p: "12 est un multiple de 5";q: "12 est un multiple de 7"

Remarque :dans le langage courant, le oufran¸cais a une connotation d"exclusivit´e (les deux propositions

ne peuvent ˆetre vraies simultan´ement, par exemple : "fromage ou dessert";"une porte est ouverte ou

ferm´ee"), alors que le ou logique admet cette ´eventualit´e. Pour ´eviter cette confusion, on d´efinit leou exclusif, not´ew. pqpwq 000 011 101
110

Exercice de cours 1.

Quelles sont les valeurs de v´erit´e des propositions suivantes? On commencera par les ´ecrire `a l"aide de connecteurs logiques et de propositions plus simples. P="il n"est pas vrai que 23 n"est pas divisible par 7" Q="πvaut 4 et la somme des angles d"un triangle vaut 180 degr´es" R="πvaut 4 ou la somme des angles d"un triangle vaut 180 degr´es"

Exemple 4

Dressons la table de v´erit´e de la proposition

A= (p?q)? ¬p.

pqp?q¬pA 00 01 10 11 2 Exercice de cours 2. Dresser la table de v´erit´e de la proposition suivante :

B= (¬p? ¬q)?p.

4) Implication

Soientpetqdeux propositions. La proposition "pimpliqueq", appel´ee aussi "pentraˆıneq", "sipalorsq",

not´eep→qest d´efinie par le tableau de v´erit´e suivant : pqp→q 001 011 100
111

Exemples 5

•p: "3 est plus grand que 4";q: "6 est plus grand que 7" •p: "No¨el est en mars";q: "il neige tous les jours de juillet" Exercice de cours 3. On consid`ere la proposition suivante, dont on consid`ere qu"elle est vraie : P="Si j"ai 1000 euros dans la poche, alors je peux acheter un caf´e". a) ´ecrireP`a l"aide de 2 propositions plus simples et du connecteur logique→. b) que peut-on dire si j"ai 1000 euros dans la poche? c) que peut-on dire si je n"ai pas 1000 euros dans la poche? d) que peut-on dire si je peux m"acheter un caf´e? e) que peut-on dire si je ne peux pas m"acheter un caf´e?

5) Equivalence

Soientpetqdeux propositions. La proposition "pest ´equivalent `aq" est not´eep↔q. C"est la conjonction

dep→qetq→p. pqp↔q 001 010 100
111
Exercice de cours 4. Donner les tables de v´erit´e des propositions suivantes :

C= (p→q)?q;D=q↔ ¬p.

Exercice de cours 5. Soient les propositions :

p="Jean est fort en math´ematiques", q="Jean est fort en informatique",r="Jean est fort en anglais". Repr´esenter les affirmations suivantes sous forme symbolique `a l"aide des propositionsp,qetr: P

1="Jean est fort en math´ematiques mais faible en anglais",

P

2="Jean n"est ni fort en math´ematiques ni fort en informatique",

P

3="Jean est fort en informatique ou il est `a la fois faible en anglais et fort en math´ematiques",

3 P4="Jean est fort en informatique s"il est fort en math´ematiques", P

5="Jean ne peut ˆetre fort en informatique sans ˆetre fort en anglais".

D´efinition :On appelletautologieune proposition toujours vraie, not´ee?, et on appellecontradiction

(ou antilogie) une proposition toujours fausse, not´ee?.

D´efinition :On dit queqest unecons´equence logiquedepsip→qest une tautologie. On ´ecrit alors

p?q. On dit quepetqsontlogiquement ´equivalentessip↔qest une tautologie (autrement dit,petqont la mˆeme table de v´erit´e). On note alorsp?qoup≡q.

Propri´et´es :

•double n´egation :¬(¬p)≡p,

•idempotence :p?p≡p;p?p≡p,

•commutativit´e :p?q≡q?p;p?q≡q?p;p↔q≡q↔p mais attention :p→q?≡q→p. •associativit´e : (p?q)?r≡p?(q?r) ; (p?q)?r≡p?(q?r). •distributivit´e : (p?q)?r≡(p?r)?(q?r) ; (p?q)?r≡(p?r)?(q?r).

•absorption :p?(p?q)≡p;p?(p?q)≡p.

•lois de Morgan :¬(p?q)≡(¬p)?(¬q) ;¬(p?q)≡(¬p)?(¬q).

•implication :p→q≡

p?q. •exportabilit´e : (p?q)→r≡p→(q→r).

•contraposition :p→q≡

q→p.

Exemples 6

V´erifions les propri´et´es suivantes : idempotence, distributivit´e.

Exercice de cours 6.

V´erifier en dressant leur table de v´erit´e les propri´et´es suivantes :

•absorption

p?(p?q)≡p p?(p?q)≡p

•contraposition

p→q≡ q→p

Exercice de cours 7.

V´erifier que l"on a

(p↔q)↔r≡p↔(q↔r) mais que

2. Formes propositionnelles

A partir de l"ensemble des nombres r´eels, on ajoute des variables et on combine le tout pour former des

polynˆomes. De la mˆeme fa¸con, `a partir des propositions on ajoute des variablesp,q,r...appel´eesvariables

propositionnelles. En les combinant `a l"aide de connecteurs logiques on obtient lesformes propositionnelles,

ouformules. C"est ce que nous avons d´ej`a commenc´e `a faire pr´ec´edemment.

D´efinition :SoitPAun ensemble de lettres, appel´eesvariables propositionnelles. L"ensemble desformes

propositionnelles(ouformules) surPAse d´efinit comme suit : 4

- une proposition est une forme propositionnelle,- sipest une variable propositionnelle, alorsp´ecrit tout seul est une forme propositionnelle,

- siPest une forme propositionnelle, alors¬Pl"est aussi, - siPetQsont deux formes propositionnelles, alorsP?Q,P?Q,P→QetP↔Qle sont aussi. Dans une forme propositionnelle, quand on remplace les variables pardes propositions, on obtient une

proposition `a laquelle on peut attribuer une valeur de v´erit´e. Onpeut ´egalement dresser la table de v´erit´e

d"une formule, en fonction des valeurs de v´erit´e des variables qui la composent.

Exemples 7

•f(p,q) =p?q,

•g(p,q) =p?q,

•P(p) =p?p, c"est une tautologie,

•Q(p) =p?p, c"est une contradiction.

Il y a 16 formes propositionnelles fonctions de 2 variables :

000100011100011101

010010010011011011

100001001010110111

110000100101101111

on reconnaˆıt : f1=?f2=p↓qf3f4f5=p?qf6f7f8=p↔q f9f10f11f12f13=p→qf14f15=p?qf16=? La forme propositionnellef2est not´ee↓"pierce". On peut exprimerp↓qen fran¸cais en disant "nip, niq". D´efinition :Unefonction d"interpr´etation(ouinterpr´etation) est une application

I:PA-→ {0,1}

p?-→I(p)

cette application attribue `a chaque variable propositionnelleune valeur logique, et permet donc d"´evaluer

la valeur de v´erit´e d"une forme propositionnelle surPA. Une forme propositionnelle poss´edantnvariables

admet 2 ninterpr´etations diff´erentes.

D´efinition :SoitPune forme propositionnelle. On appellemod`eledePtoute interpr´etation qui rendP

vraie.

Exemples 8

•P=p?qalorsId´efinie parI(p) = 0etI(q) = 1est un mod`ele deP •Q=p?(q?r): alorsId´efinie parI(p) =I(q) =I(r) = 0est un mod`ele deQ

•toute interpr´etation est mod`ele d"une tautologie, et une contradiction n"admet pas de mod`ele.

Exercice de cours 8. D´eterminer (si possible) un mod`ele des formes propositionnelles suivantes; A= (p? ¬q)?(q→p);B= (p→q)?(p→ ¬q)C= ((p→q)?(r→p))→ p. 5 D´efinition :SoitF={P1,...,Pn}un ensemble de formules, etPune autre formule (n"appartenant pas

n´ecessairement `aF). On dit quePest unecons´equence logiquedeF, et on ´ecritF ?P, si tout mod`ele

commun aux ´el´ements deFest un mod`ele deP, ce qui revient `a dire que (P1?P2?...?Pn)→Pest

une tautologie. Les ´el´ements deFsont appel´es lespr´emisses.

Exemple 9

•Transitivit´e (r`egle du syllogisme) :{p→q,q→r} ?p→r. Exercice de cours 9. V´erifier les cons´equences logiques suivantes :

•Modus-Ponens :{p,p→q} ?q.

•Modus-Tollens :{

q,p→q} ?p. P??P→Qo`uPetQsont deux formes propositionnelles. D´efinition :SoitF={P1,...,Pn}un ensemble de formules. On dit queFestcoh´erent, ou que les formules deFsontcompatiblessi elles ont au moins un mod`ele en commun, ce qui revient `a dire que P

1?P2?...?Pnadmet au moins un mod`ele.

Dans le cas contraire, on dit que les formules sontincompatibles, ou quel"ensembleFest incoh´erent

(inconsistant).

Exemples 10

• {p,p?q}sont compatibles

• {p?q,p?q}sont incompatibles

Exercice de cours 10. Les formules suivantes sont-elles compatibles? {p→q,q→p}, {p→q,q→ ¬p}. Th´eor`eme :SoitF={P1,...,Pn}un ensemble de formules. Une formulePest une cons´equence logique deFsi et seulement si la contradiction?est une cons´equence deF ??

P?=?P1,...,Pn,P?. Ce que l"on

´ecrit :

F ?Pest ´equivalent `aF ??

P?? ?.

Ce qui revient `a dire que l"ensemble est

?P1,...,Pn,

P?incoh´erent.

3. Sch´emas de raisonnement

Une des questions qui se pose est de d´eterminer si une formule est une cons´equencelogique d"un ensemble

de formules.

3.1 Exemple

supposons que nous ayons valid´e les hypoth`eses suivantes : *les gens qui ont de la rougeole doivent prendre le m´edicament X *les gens qui ont de la fi`evre et des points rouges au fond de la gorge ont la rougeole *ceux pour qui la temp´erature d´epasse 38 ◦sont consid´er´es comme ayant la fi`evre. Jean a des points rouges au fond de la gorge et a une temp´erature de 39 ◦5 La question est :Est-ce-que Jean doit prendre le m´edicament X?.

L"assertion "Jean doit prendre le m´edicament X" est consid´er´ee comme une formule `a d´emontrer.

On pose :

r:" avoir la rougeole" x:" doit prendre le m´edicament X" f: " avoir la fi`evre"quotesdbs_dbs45.pdfusesText_45

[PDF] planches pendule pdf

[PDF] exercice produit scalaire corrigé

[PDF] le pendul'or - 200 planches pdf

[PDF] danger du pendule

[PDF] cicéron de la divination

[PDF] cicéron de divinatione texte latin

[PDF] médecine parallèle définition

[PDF] futuribles pdf

[PDF] enseigner au canada avec le crpe

[PDF] médecine parallèle liste

[PDF] enseigner le francais au canada

[PDF] médecine conventionnelle et médecine traditionnelle

[PDF] salaire enseignant canada

[PDF] définition médecine conventionnelle

[PDF] enseigner au canada avec un diplome français