et q est faux et r est vraie, ou en formule que On voit que la proposition logique composée P ↔ Q est toujours vraie, pour tous les valeurs de vérité de p, q et r
| Previous PDF | Next PDF |
[PDF] Le vrai et le faux en mathématiques au collège et au lycée Michèle
N'est-ce pas un fonctionnement habituel du langage courant ? En voici un autre exemple, dire le contraire de la phrase : "Si tu réussis ton interro de math, tu
[PDF] Logique : vrai/faux ; condition nécessaire, suffisante ou nécessaire
Vrai ou faux : une assertion mathématique est soit vraie, soit fausse Dans le doute, elle est considérée comme fausse Soit une assertion du type : 1
[PDF] Chapitre 1 : sexprimer en mathématiques - Ceremade - Université
Une proposition est un énoncé mathématique complet qui est soit vrai soit faux “P ou Q" veut dire : au moins l'une des propositions P et Q est vraie
[PDF] 42 Tableau de vérité Nous présentons ces définitions en forme de
et q est faux et r est vraie, ou en formule que On voit que la proposition logique composée P ↔ Q est toujours vraie, pour tous les valeurs de vérité de p, q et r
[PDF] Feuille dexercices no 1 1 Propositions, valeur de vérité, variables
On retiendra surtout qu'une proposition est susceptible d'être vraie ou fausse, elle est vraie ou fausse car on n'a pas assez Exercice 1 (Vrai ou faux ?*)
[PDF] Logique - Licence de mathématiques Lyon 1
Napoléon est chinois » est faux et « 3 − 2 = 2 » est faux, or la seule possibilité pour qu'une implication soit fausse est qu'une assertion vraie implique une
[PDF] 1 FAUX 2 VRAI 3 VRAI 4 VRAI 5 FAUX - Maths-francefr
VRAI 5 FAUX Explications 1 Notons X le nombre de boules blanches obtenues au bout de dix tirages La variable aléatoire X est régie par un schéma de
[PDF] 1 Vrai ou faux (justifier) 2 Calcul directs dintégrales et de primitives
Sup'Galilée Année 2017/2018 Etudiants ingénieurs apprentis 1ère année Mathématiques : cours d'harmonisation-TD2 Intégration 1 Vrai ou faux (justifier) 1
[PDF] Maths:Devoir Maison
[PDF] Maths:Devoir Maison :Vitesse moyenne
[PDF] Maths:Devoir Maison:Développements
[PDF] Maths:Le toboggan: théorème de pythagore
[PDF] maths:Une relation efficace(fonction)
[PDF] mathsenligne correction
[PDF] mathusalem bible
[PDF] mathway
[PDF] Mathys possède dix tiges
[PDF] Matière a l'échelle, Macroscopique
[PDF] matière collège 6ème
[PDF] matière colorée 1ere s
[PDF] matiere d'origine végétale
[PDF] matière inerte définition svt
4.2.Tableau de vérité.Nous présentons ces définitions en forme de tableaux de vérité, où
V:=vrai, et F:=faux.
Pour la négation:p¬pVF
FVPour les autres définitions:
p qp?qp?qp?qp→qp↔qV VVFVVVV FVVFFF
F VVVFVF
F FFFFVV
4.3.Propositions logiques composées.Commençons maintenant à combiner. Sip,qetrsont
trois propositions logiques, alorsP:= ((¬q)?(p?r))→p
est aussi une proposition logique. La valeur de vérité dePdépend des valeurs de vérité dep,
qetr. Comment exactement montre le tableau suivant (qui montre aussi des calculs de vérité intermédiaires) :p q r¬q p?r(¬q)?(p?r)((¬q)?(p?r))→pV V VF V FVV V FF V FV
V F VV V VV
V F FV V VV
F V VF V FV
F V FF F FV
F F VV V VF
F F FV F FV
En regardant la dernière colonne on se rend compte quePest faux si et seulement sipest faux etqest faux etrest vraie, ou en formule que (¬p)?((¬q)?r)) est vraie.Ou quePest vraie si et seulement si
¬((¬p)?((¬q)?r))
est vraie. PosonsQ:=¬((¬p)?((¬q)?r))et calculons de nouveau ses valeurs de vérité : 19 20 p q r¬p¬q(¬q)?r) ((¬p)?((¬q)?r))QV V VF F F FV
V V FF F F FV
V F VF V V FV
V F FF V F FV
F V VV F F FV
F V FV F F FV
F F VV V V VF
F F FV V F FV
Considérons aussi la propositionR=p?(q?(¬r). On peut aussi calculer son tableau.p q rPQRV V VVVV
V V FVVV
V F VVVV
V F FVVV
F V VVVV
F V FVVV
F F VFFF
F F FVVV
Conclusion : les propositions composéesP,QetRont la même valeur de vérité, n"importe les valeurs dep,q,r. On ditP,QetRsont des propositions composées (ou formules logiques) logiquement équivalentes. Calculons aussi les vérités de la propositionP↔Q:p q rP QP↔QV V VV VVV V FV VV
V F VV VV
V F FV VV
F V VV VV
F V FV VV
F F VF FV
F F FV VV
On voit que la proposition logique composéeP↔Qest toujours vraie, pour tous les valeurs de vérité dep,qetr. On ditP↔Qest unetautologie, notationP?Q.4.4.Tautologie et contradiction.Nous généralisons.
Définition 4.2.Une proposition logique composée (ou une formule logique) qui est toujours vraie,
quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une tautologie.
Notation :P?V.
Par exemple:p?(¬p)?Vet((p?q)→(p?q))?V.
21Définition 4.3.Une proposition logique composée (ou une formule logique) qui est toujours fausse,
quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une contra-
diction. Notation :P?FPar exemple :p?(¬p)?F.
Définition 4.4.Deux formules logiquesPetQsont appeléeslogiquement équivalentessi la propo- sition logiqueP↔Qest une tautologie. Notation :P?Q.Par exemple:(p↔q)?[(p→q)?(q→p)].
Définition 4.5.SiP→Qest une tautologie, oùPetQsont deux formules logiques, on dit que P→Qest unerègle d"inférence. NotationP?Q.Par exemple:(p?q)?q.
4.5.Propositions logiquement équivalents à l"implication.Considérons la proposition suiv-
ante.Proposition 4.1.Les trois formules logiques "p→q", "(¬q)→(¬p)" et "(¬p)?q" sont logiquement
équivalentes. Ou
Proof.Nous vérifions par un tableau de vérité.p qp→q¬q¬p(¬q)→(¬p)(¬p?q)V VVF F VV
V FFV F FF
F VVF V VV
F FVV V VV
Les trois colonnes correspondantes sont identique. Donc la proposition est vraie.4.6.Formules logiquement équivalentes.Donnons une petite reformulation. On pourrait voir
P=P(p,q,r), Q=Q(p,q,r), R=R(p,q,r)
comme trois formules ou comme trois fonctions qui dépendent des propositions logiquesp,q,r. Par exemple P:{propositions logiques}3→ {propositions logiques} où le triple de propositions(p,q,r)est envoyé vers la propositionP=P(p,q,r).Par définition:PetQsont logiquement équivalentes si les fonctions composées avec la fonction
"vérité" deviennent identiques: SiAetBsont deux ensembles etb?Bun élément fixé, on peut définir lafonction constante,souvent aussi notéb, comme la fonction qui associe à chaque élémenta?Ace même élémentb
(oub(a) =b). Dans le même sens nous considéronsVcomme la proposition composée (ou formule logique) qui a la valeur de véritéVn"importe les valeurs dep,q,r. Et de même pourF. 224.7.Équivalences logiques de base.Une première liste d"équivalences logiques utilisées tout le
temps : Théorème 4.1.Voici des équivalences logiques : p?V?p(Identité) p?F?p(Identité) p?V?V(Domination) p?F?F(Domination) p?p?p(Idempotence) p?p?p(Idempotence)¬(¬p)?p(Loi de la double négation)
p?q?q?p(Commutativité) p?q?q?p(Commutativité) ((p?q)?r)?(p?(q?r))(Associativité) ((p?q)?r)?(p?(q?r))(Associativité)¬(p?q)?((¬p)?(¬q))(Loi de De Morgan)
¬(p?q)?((¬p)?(¬q)(Loi de De Morgan)
Proof.La plupart des preuves est facile: il faut soi-même se convaincre! Nous donnons deux exemples de preuve par tableau : SiP:=p?(q?r)etQ:= (p?q)?(p?r)on ap q rq?r Pp?q p?r QV V VV VV V VV V FF VV V V
V F VF VV V V
V F FF VV V V
F V VV VV V V
F V FF FV F F
F F VF FF V F
F F FF FF F F
EffectivementP?Q(un des deux lois de la distributivité). Montrons¬(p?q)?((¬p)?(¬q))(Loi de De Morgan). SoitP=¬(p?q)etQ= ((¬p)?(¬q)). On a 23p qp?q P¬p¬q QV VV FF F F
V FF VF V V
F VF VV F V
F FF VV V V
EffectivementP?Q.
4.8.Preuve d"equivalences logiques par de l"algèbre.Remarquons tout d"abord que siP,Q
etRsont trois formules logiques (ou propositions composées) etP?QetQ?Ralors aussi P?R. (Et siP?Qalors aussiQ?P(c.-à.d., l"équivalence logique est symmétrique), et on a toujoursP?P.) Donc on peut enchaîner des équivalences logiques pour obtenir d"autres.Nous avons déjà un certain nombre d"équivalence montrées, que nous pouvons utiliser. À la place
d"utiliser un tableau pour vérifier une équivalence logique, on peut aussi utiliser les petites règles
déjà montrées, comme en algèbre. Donnons un exemple. La proposition soi-même est sans importance. Proposition 4.2.SoitP:= ((¬q)?(p?r))→petQ:= (p?(q?(¬r))). On aP?Q. Proof.Nous allons utiliser une suite d"équivalences logiques (avec les raisons) ?(¬(¬q)? ¬(p?r)))?p(Selon De Morgan) ?(q? ¬(p?r)))?p(Double négation) ?(q?((¬p)?(¬r)))?p(Selon De Morgan) ?q?(p?((¬p)?(¬r)))(Assoc. et comm. pour?) ?q?((p?(¬p))?(p?(¬r)))(Distrib.) ?q?(V?(p?(¬r)))(Selon(p?(¬p))?V) ?q?(p?(¬r))(Selon comm. et(p?V)?p) ?Q(Assoc. et commut.)Et voilà !
Chaque ligne est claire. Mais trouver la chaîne n"est pas si évidente. Remarque.On a vu beaucoup de()"s dans cette preuve. Parce quep?(q?r) = (p?q)?r, écrire p?q?r n"est pas ambigu. On supprime des()"s, qui sont dans ce cas superflus.Ainsi pour
p?q?r On pose la convention que "¬" a uneplus haute prioritéque?ou?ou→ou ... 24Donc¬p?qveut dire(¬p)?q(et pas¬(p?q), ce qui est vraiment différent).
Et¬p→qveut dire(¬p)→q.
Mais c"est ambigu d"écrire"p?q?r"et"p?q→r"; on n"a pas le droit d"écrire ça (il faut ajouter
des()"s pour clarifier ce qu"on veut vraiment). Nous ne posons pas de priorités entres les autresopérations.Vous aussi êtes obligés d"évitez des ambiguïtés, en utilisant les()"s et[ ],s. Et à
chaque symbol "(" il faut correspondre un symbol ")".4.9.Règles d"inference de base.Voici quelques règles d"inférence6utilisées tout le temps aussi.
Théorème 4.2.Les suivants sont des équivalences logiques. p?(p?q)(Addition) p?q?p(Simplification) [p?(p→q)]?p(Modus ponens) [¬q?(p→q)]?q?p(Modus tollens) [(p→q)?(q→r)]?(p→r)(Syllogisme par hypothèse) [(p?q)? ¬q]?p(Syllogisme disjonctif)Proof.Aussi facile à montrer avec un tableau de vérité. Par exempleModus ponens:p qp→q p?(p→q)(p?(p→q))→pV VV VV
V FF FV
F VV FV
F FV FV
La dernière colonne contient seulement desV, donc correspond à une tautologie. SiP?QetQ?Ralors aussiP?R. (MaisP?Qn"implique pas en général queQ?P).EtP?Qsi et seulement siP?QetQ→P.
Donc on peut composer des règles d"inférences, et obtenir d"autre règles d"inférence.Par exemple.
Lemme 4.1.Une autre règle d"inférence :
(q?(¬p→ ¬q))?p. Proof.On combine(¬p→ ¬q)?(q→p)avec modus ponens (q?(¬p→ ¬q))?(q?(q→p))?p.Cette règle d"inférence est utilisée dans une preuve par l"absurde, comme nous verrons plus tard.6
Voir [R, §3.1]
254.10.Fonctions propositionnelles et quantifications.Il y a des énoncés comme"n >2"qui
sont presque des propositions logiques mais qui contiennent des indéterminés (comme "n" dansl"exemple). Du moment qu"on précise ces indéterminés elles deviennent des propositions logiques.
C"est donc vraiment une famille de propositions logiques. Par exemplep(n) := "n >2". C"est une famille de propositions logiques, dépendant de la variablenqui varie dans l"ensembleN. Icip(n)est fausse sin= 0,1ou2et vraie sinon (pour n?N).