Bases de la logique

Question 1

Une propostion (ou assertion)

Answer 1

Une propostion (ou assertion) est un énoncé mathématique qui a une et une seule valeur : vrai ou faux.

Question 2

La négation de la proposition P

Answer 2

La négation de la proposition P est la proposition qui est vraie si et seulement si P est fausse. Elle est noté non P.

Question 3

Si P et Q sont deux propositions, P et Q est la proposition qui est vraie si et seulement si

Answer 3

P et Q sont toutes les deux vraies.

Question 4

Si P et Q sont deux propositions, P ou Q est la proposition qui est vraie si

Answer 4

et seulement si au moins une des deux propositions P ou Q est vraie.

Question 5

non (P et Q)=

Answer 5

(non P) ou (non Q).

Question 6

(non P) ou (non Q)=

Answer 6

non (P et Q)

Question 7

non (P ou Q)=

Answer 7

(non P) et (non Q).

Question 8

(non P) et (non Q) =

Answer 8

non (P ou Q)

Question 9

L’implication P⟹Q est la proposition

Answer 9

non P ou Q

Question 10

Pour démontrer P⟹Q, on suppose que

Answer 10

Pour démontrer P⟹Q, on suppose que PP est vraie et on démontre que QQ est vraie.

Question 11

On dit que les proposition P et Q sont équivalentes lorsque

Answer 11

On dit que les proposition P et Q sont équivalentes lorsque l’on a à la fois P⟹Q et Q⟹P qui sont vraies. On note alors P⟺Q.

Question 12

Le quantificateur pour tout ou quel que soit est noté

Answer 12

Le quantificateur pour tout ou quel que soit est noté ∀x. La proposition ∀ x ∈ E, P(x)∀ x∈ E, P(x) est vraie lorsque, pour tout x∈E, la proposition P(x) est vraie

Question 13

Le quantificateur il existe (au moins un) est noté

Answer 13

Le quantificateur il existe (au moins un) est noté ∃. La proposition ∃x∈E, P(x) est vraie lorsqu’il existe au moins un x∈E telle que la proposition P(x) soit vraie.

Question 14

Le quantificateur il existe un unique est noté

Answer 14

Le quantificateur il existe un unique est noté ∃!. La proposition ∃!x∈E, P(x) est vraie lorsqu’il existe un unique x∈E telle que la proposition P(x) soit vraie.

Question 15

La négation de ∀x∈E, P(x) est

Answer 15

∃x∈E, non P(x).

Question 16

La négation de ∃x∈E, P(x)est

Answer 16

∀x∈E, non P(x).

Question 17

LorsqueP⟹Q, on dit que P est une condition suffisante à

Answer 17

LorsqueP⟹Q, on dit que P est une condition suffisante à Q, et que Q est une condition nécessaire à P.

Question 18

Raisonement par implication :

Answer 18

par implication : pour prouver que P⟹Q, on suppose que P est vraie et on utilise différentes propriétés déjà connues pour établir que Q est vraie.

Question 19

raisonnement par double implication / par équivalence :

Answer 19

• par double implication / par équivalence : Pour démontrer queP⟺Q, il y a deux méthodes standard :
  
  • On raisonne par double implication :
    
    • on suppose d’abord que P est vraie, et on démontre que Q est vraie.
    • Ensuite, on suppose que Q est vraie, et on démontre que P est vraie.
  • On passe de P à Q en utilisant uniquement des équivalences. C’est une méthode souvent déconseillée, car il faut faire très attention à ce que chaque enchaînement logique de la démonstration est bien une équivalence.

Question 20

raisonnement par contraposée :

Answer 20

par contraposée : pour démontrer que P⟹Q, il suffit de démontrer la contraposée de cette proposition, c’est-à-dire non Q⟹non P.

Question 21

raisonnement par l’absurde :

Answer 21

pour démontrer que P⟹Q, on peut supposer que P et non Q sont toutes les deux vraies, et obtenir une contradiction.

Question 22

Raisonement par récurrence :

Answer 22

• par récurrence : Le raisonnement par récurrence est utilisé pour démontrer des propriétés qui dépendent d’un entier nn. Il est basé sur le principe suivant:
  
  • Théorème (principe de récurrence) : Soit P(n) une propriété concernant un entier naturel nn. On suppose que P(0) est vraie et que, pour tout entier naturel k, si P(k) est vraie, alorsP(k+1) est vraie. Alors la propriété P(n) est vraie pour tout entier naturel n.

Pour bien rédiger une démonstration par récurrence, il est nécessaire de faire apparaitre clairement les 4 étapes : définir précisément quelle est la propriété P(n)P(n) que l’on souhaite démontrer, écrire la phase d’initialisation, la phase d’hérédité, puis la conclusion. Il existe deux erreurs fréquentes de rédaction de la phase d’hérédité.

• commencer cette phase par la phrase : ``supposons que, pour tout n∈N, P(n) est vraie et prouvons P(n+1)’’. Si P(n) est vraie pour tout entier n, il n’y a plus rien à prouver!
• commencer cette phase par la phrase : ``supposons qu’il existe un n∈N tel queP(n) est vraie et prouvons P(n+1). L’erreur est plus subtile. Le principe de récurrence s’écrit formellement

(P(0) vraie ET (∀n∈N P(n)⟹P(n+1)) ⟹ ∀n∈N, P(n) vraie..

La dernière rédaction serait correcte si le principe de récurrence s’écrivait

(P(0) vraie ET (∃n∈N P(n)⟹P(n+1))⟹∀n∈N,P(n) vraie.

ce qui est faux.

Pour ne pas faire d’erreurs, je vous conseille de toujours commencer la phase d’hérédité par : Soit n∈N tel que P(n) est vraie'' ou alorsSupposons que P(n) est vraie pour un certain n∈N’’.

Question 23

Raisonement par récurrence forte:

Answer 23

Raisonement par récurrence forte: si on veut prouver qu’une proposition P(n) dépendant de l’entier naturel n est vraie pour tout entier n, on peut procéder de la façon suivante :

• initialisation : prouver que P(0) est vraie.
• hérédité : prouver que, pour tout entier nn, si P(0),P(1),…,P(n) sont toutes vraies, alors P(n+1) est vraie.

Question 24

Raisonement par disjonction de cas :

Answer 24

Raisonement par disjonction de cas :

le raisonnement par disjonction de cas s’utilise quand on veut démontrer une propriété P dépendant d’un paramètre x appartenant à un ensemble E, et que la justification dépend de la valeur de x.

On écrit alors E=E1∪⋯∪En, et on sépare les raisonnements suivant que x∈E1, x∈E2,…,….

• On emploie fréquemment ce raisonnement pour:
  
  • résoudre des (in)équations avec des valeurs absolues (le raisonnement dépend du signe de la quantité à l’intérieur de la valeur absolue),
  • démontrer des propriétés en arithmétique (on sépare le raisonnement suivant la parité de certains entiers, leur congruence modulo n…),
  • résoudre des problèmes de géométrie (disjonction selon la position relative de deux objets géométriques).

Question 25

Raisonement par analyse/synthèse :

Answer 25

Raisonement par analyse/synthèse : le raisonnement par analyse/synthèse, qu’on pourrait aussi appeler raisonnement par condition nécessaire/condition suffisante, est un raisonnement que l’on emploie souvent lorsqu’on cherche toutes les solutions d’un problème donné.

Il comporte deux phases :

• L’analyse. On suppose que x est solution du problème, et on trouve un certain nombre de conditions nécessaires satisfaites par x.
• La synthèse. On vérifie que les conditions obtenues à l’issue de la phase d’analyse sont en fait également suffisantes pour que x soit solution du problème.