Upload
buithien
View
219
Download
0
Embed Size (px)
Citation preview
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
LogiquePartie 1 : Propositions Predicats
Laurent Debize
BTS SIO
1/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Calculs propositionnelsPropositionsConnecteurs logiques
Proprietes des operateurs logiquesNon, Ou, EtDistributiviteLois de De MorganProprietes du connecteur si alors
Calcul des predicatsPredicatQuantificateurs
2/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Calculs propositionnels
En logique, deux objets sont rencontres :
• Des propositions (� phrases �mathematiques)
• Des connecteurs logiques (pour manipuler ces � phrases �)
3/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
PropositionsLes expressions mathematiques sont composees :
• de termes (ou � mots � mathematiques) qui doivent respecter uneorthographeLes termes representent des objetsExemples :
−4 ;1
6; x ; A
• d’enonces (ou � phrases � mathematiques) qui doivent respecterune syntaxe (ou � grammaire �)Les enonces enoncent des faitsExemples :
• 2 + 2 = 4• 8 est divisible par 3• y > 7• −x + y = 3 (a = b qu’on lit � a egale b � signifie que a et b
representent la meme entite mathematique)4/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Propositions
RemarqueCertaines expressions n’ont aucun sens mathematique :Exemples :
1
0; + = × ;
√−1
Parmi les enonces precedents certains sont vrais, d’autres faux.� Vrai (V) � et � Faux (F) � sont appeles valeurs de verite.La logique qui ne comporte que ces deux valeurs de verite est appeleelogique binaire : un enonce qui n’est pas vrai est faux et reciproquement.
Exemples :
• � 2 + 2 = 4 � est un enonce vrai
• � 5 est un nombre impair � est un enonce vrai
• � pour tout reel x , x2 + 1 < 0 � est un enonce faux
5/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
PropositionsDefinitionOn appelle proposition ou assertion un enonce qu’on peut juger sansambiguıte Vrai ou Faux.
NotationLes propositions sont generalement notees par des lettres majuscules (P,Q, etc.)
Exemples
• 2 + 2 = 4 est un enonce qu’on peut juger, sans ambiguıte, qu’il estvrai donc c’est une proposition vraie.
• � 8 est divisible par 3 � est un enonce qu’on peut juger, sansambiguıte, qu’il est faux donc c’est une proposition fausse.
• � Le professeur est sympathique �, enonce tres subjectif, n’est pasune proposition.
• � x + 2 = 0 � n’est pas une proposition car la valeur de veritedepend du reel x.
6/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 1
7/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Connecteurs logiques
A partir de propositions initiales, on peut definir de nouvelles propositionsau moyen de connecteurs logiques comme :
• la negation
• la conjonction
• la disjonction
• l’implication
• l’equivalence
Ces transformations sont appelees des operations logiques.
Ces operations logiques peuvent aussi etre definies par leurs tablesoperatoires appelees tables de verite.
8/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
NegationDefinitionSoit P une proposition.La negation de la proposition P est la proposition � non P �.Elle est vraie lorsque P est fausse et vice-versa.
NotationCette proposition est notee ¬P, P ou non P.¬ est le connecteur NON.
Table de verite
P ¬PV FF V
ExempleSoient a un reel et P la proposition � a > 3 �.La proposition ¬P est la proposition � a ≤ 3 �.
9/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Conjonction
DefinitionSoient P et Q deux propositions.La conjonction des propositions P et Q est la proposition � P et Q �.Elle n’est vraie que si les propositions P et Q sont vraies simultanement.
NotationCette proposition est notee P ∧ Q.∧ est le connecteur ET.
Table de verite
P Q P ∧ QV V VV F FF V FF F F
10/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Conjonction
ExempleSoient a un reel, P la proposition � a > 3 � et Q la proposition� a > 8 �.La proposition P ∧ Q est la proposition � a > 8 �.
11/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Disjonction
DefinitionSoient P et Q deux propositions.La disjonction des propositions P et Q est la proposition � P ou Q �.Elle est vraie si au moins une de deux propositions P et Q est vraie.
NotationCette proposition est notee P ∨ Q.∨ est le connecteur OU.
Table de verite
P Q P ∨ QV V VV F VF V VF F F
12/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Disjonction
ExempleSoient a un reel, P la proposition � a > 3 � et Q la proposition� a > 8 �.La proposition P ∨ Q est la proposition � a > 3 �.
RemarqueLe connecteur ∨ utilise en logique n’est pas le OU du langage courant :choisir � fromage ou dessert � est le plus souvent interprete comme unchoix exclusif (ou l’un ou l’autre mais pas les deux).
13/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 2
14/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Equivalence
DefinitionSoient P et Q deux propositions.L’equivalence des propositions P et Q est la proposition � P si etseulement si Q �.Elle est vraie si les deux propositions P et Q ont la meme valeur de verite.
NotationCette proposition est notee � P ⇔ Q �
⇔ est le connecteur ...SI ET SEULEMENT SI...
Table de verite
P Q P ⇔ QV V VV F FF V FF F V
15/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Equivalence
ExempleSoient a un reel, P la proposition � a > 3 � et Q la proposition � a2 > 9et a > 0 �.On a P ⇔ Q
16/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
ImplicationDefinitionSoient P et Q deux propositions.L’implication des propositions P et Q est la proposition � P implique Q �.Elle est vraie si les deux propositions P et Q sont vraies, ou si P estfausse.
NotationCette proposition est notee � P ⇒ Q �, � Si P alors Q �, � P entraıneQ �
⇒ est le connecteur SI... ALORS...
Table de verite
P Q P ⇒ QV V VV F FF V VF F V
17/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Implication
ExempleSoient a un reel, P la proposition � a > 8 � et Q la proposition� a > 3 �.Si � a > 8 � est vrai alors � a > 3 � est vrai, et si � a > 8 � est fauxalors � a > 3 � est soit vrai soit faux.On a donc P ⇒ Q
RemarqueLes deux dernieres lignes de la table de verite de � P ⇒ Q � montrentque le sens que les mathematiques donnent aux mots � implique � et� entraıne � est plus general que le langage courant.Exemple :
• � 2 + 2 = 5 � ⇒ � La France a gagne la coupe du monde en1998 � est vraie
• � La France a gagne la coupe du monde en 2014 � ⇒� 2 + 2 = 5 � est vraie
18/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 3
19/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Calculs propositionnelsPropositionsConnecteurs logiques
Proprietes des operateurs logiquesNon, Ou, EtDistributiviteLois de De MorganProprietes du connecteur si alors
Calcul des predicatsPredicatQuantificateurs
20/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Proprietes des operateurs logiques
Dans cette partie, P, Q et R designent des propositions, V et F designentles valeurs de verite vrai et faux.
Proprietes du connecteur NON
• ¬(¬P) = P
• ¬V = F et ¬F = V
Proprietes du connecteur OU
• idempotence : P ∨ P = P
• commutativite : P ∨ Q = Q ∨ P
• associativite : (P ∨ Q) ∨ R = P ∨ (Q ∨ R) que l’on peut donc noterP ∨ Q ∨ R (a demontrer dans l’exercice 4)
• P ∨ F = P et P ∨ V = V
21/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Proprietes des operateurs logiques
Proprietes du connecteur ET
• idempotence : P ∧ P = P
• commutativite : P ∧ Q = Q ∧ P
• associativite : (P ∧ Q) ∧ R = P ∧ (Q ∧ R) que l’on peut donc noterP ∧ Q ∧ R (cf exercice 4)
• P ∧ F = F et P ∧ V = P
22/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 5
23/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Proprietes des operateurs logiques
Distributivite
• P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
• P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)
ExempleSoit a un reel. Soient les propositions :
• P : � a > 0 �
• Q : � a < −3 �
• R : � 3 < a �
P ∧ (Q ∨ R) est la proposition (a > 0) ∧ (a < −3 ∨ 3 < a)c’est-a-dire (a > 0 ∧ a < −3) ∨ (a > 0 ∧ 3 < a)soit F ∨ (a > 0 ∧ 3 < a)donc P ∧ (Q ∨ R) = 3 < a
24/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 6
25/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Proprietes des operateurs logiques
Lois de De Morgan
• ¬(P ∨ Q) = (¬P) ∧ (¬Q)
• ¬(P ∧ Q) = (¬P) ∨ (¬Q)
ExempleSoit a un reel. Soient les propositions :
• P : � a < −3 �
• Q : � 3 < a �
P ∨ Q est la proposition (a < −3) ∨ (3 < a)¬(P ∨ Q) est la proposition ¬((a < −3) ∨ 3 < a))
c’est-a-dire (a ≥ −3) ∧ (3 ≥ a)soit −3 ≤ a ≤ 3
26/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Proprietes des operateurs logiques
Proprietes du connecteur ⇒• reflexivite : P ⇒ P
• anti-symetrie : Si (P ⇒ Q) ∧ (Q ⇒ P) alors P ⇔ Q
• transitivite : Si (P ⇒ Q) ∧ (Q ⇒ R) alors P ⇒ R
• contraire : (P ⇒ Q) = (¬P ∨ Q) (cf exercice 7)
• contra-posee : (P ⇒ Q) = (¬Q ⇒ ¬P) (cf exercice 10)
ExempleSoit a un reel.La proposition (vraie) � a > 3⇒ a2 > 9 � est equivalente ala proposition (vraie) � a2 ≤ 9⇒ a ≤ 3 �
27/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Calculs propositionnelsPropositionsConnecteurs logiques
Proprietes des operateurs logiquesNon, Ou, EtDistributiviteLois de De MorganProprietes du connecteur si alors
Calcul des predicatsPredicatQuantificateurs
28/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Calcul des predicats
Rappel
• Une constante est un nombre dont la valeur est fixee
• Une variable est un nombre pouvant prendre differentes valeurs
29/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Predicat
DefinitionOn appelle predicat (ou fonction propositionnelle) un enonce contenantune ou plusieurs variables et qui se transforme en proposition suivant lavaleur attribuee a ces variables.
Exemples
• x etant une variable reelle, � 2x + 1 = 7 � est un predicat a unevariablecar si x = 3 alors 2x + 1 = 7 est un enonce vraiet si x 6= 3 alors 2x + 1 = 7 est un enonce faux.
• � 5x + 5y = 15 � est un predicat a deux variables.
30/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Quantificateurs
DefinitionUne proposition peut contenir des quantificateurs. Il en existeprincipalement 2 :
• Le quantificateur ∀ est appele quantificateur universel. Il se lit� quel que soit � ou � pour tout �.
• Le quantificateur ∃ est appele quantificateur existentiel. Il se lit� il existe �.
Une proposition comporte des virgules :
• Apres le quantificateur ∀, la virgule signifie � on a �.
• Apres le quantificateur ∃, la virgule signifie � tel que �.
31/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Quantificateurs
Exemple de quantificateur universelPour tout reel x dans [−1; +∞[, on sait que x + 1 > 0.On note : ∀x ∈ [−1; +∞[, x + 1 > 0.
Remarque : x + 1 > 0 est un predicat alors que∀x ∈ [−1; +∞[, x + 1 > 0 est une proposition (vraie ici)
Exemple de quantificateur existentielOn sait qu’il existe au moins un reel x tel que x − 1 > 0.On note : ∃x ∈ R, x − 1 > 0.
Remarques :
• x − 1 > 0 est un predicat alors que ∃x ∈ R, x − 1 > 0. est uneproposition (vraie ici)
• La proposition ne dit pas comment trouver x , ni combien de tels xexistent
32/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Negation des quantificateurs
ProprietesSoit p(x) un predicat a une variable :
• La negation de la proposition � ∀x , p(x) � est la proposition� ∃x , ¬p(x) �
• La negation de la proposition � ∃x , p(x) � est la proposition� ∀x , ¬p(x) �
33/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Negation des quantificateurs
Exemples
• La proposition � ∃x , x2 = 4 � a pour negation la proposition� ∀x , x2 6= 4 �
• Puisque (P ⇒ Q) = (¬P ∨ Q), la negation de (P ⇒ Q) est laproposition (P ∧ ¬Q)
• La negation de la proposition � ∀x , x ∈ E ⇒ p(x) � est laproposition � ∃x , x ∈ E ∧ ¬p(x) �
• La negation de la proposition � ∃x , x ∈ E ⇒ p(x) � est laproposition � ∀x , x ∈ E ∧ ¬p(x) �
34/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 8
35/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Ordre des quantificateurs
ExemplePour x et y reels, considerons les propositions :
� ∀x , ∃y , y = x2 � et � ∃y , ∀x , y = x2 �
� ∀x , ∃y , y = x2 � signifie que tout reel x possede un carre y . C’est uneproposition vraie.� ∃y , ∀x , y = x2 � signifie qu’il existe au moins un reel y egal a tous lescarres des nombres reels. C’est une proposition fausse.
L’ordre des quantificateurs ∀ et ∃ n’est donc pas indifferent !
36/37
Calculs propositionnels Proprietes des operateurs logiques Calcul des predicats
Exercice 9 a 14
37/37