Résumé de cours : bases de la logique

Propositions et connecteurs logiques

• Une proposition (ou assertion) est un énoncé mathématique qui a une et une seule valeur : vrai ou faux.
• La négation de la proposition $P$ est la proposition qui est vraie lorsque $P$ est fausse, et qui est fausse lorsque $P$ est vraie . Elle est notée $\textrm{non }P$.
• Si $P$ et $Q$ sont deux propositions, $P$ et $Q$ est la proposition qui est vraie si et seulement si les deux propositions $P$ et $Q$ sont simultanément vraies.
• Si $P$ et $Q$ sont deux propositions, $P$ ou $Q$ est la proposition qui est vraie si et seulement si au moins une des deux propositions $P$ ou $Q$ est vraie.
• $$\textrm{non }(P\textrm{ et }Q)=(\textrm{non }P)\textrm{ ou }(\textrm{non }Q).$$
• $$\textrm{non }(P\textrm{ ou }Q)=(\textrm{non }P)\textrm{ et }(\textrm{non }Q).$$
• L'implication $P\implies Q$ est la proposition qui est fausse si et seulement si $P$ est vraie et $Q$ est fausse.
  $P\implies Q$ signifie que si P est vraie, alors Q est vraie.
  Pour démontrer $P\implies Q$, on suppose que $P$ est vraie et on démontre que $Q$ est vraie.
• On dit que les proposition $P$ et $Q$ sont équivalentes lorsque l'on a $P$ et $Q$ sont deux propositions simultanément vraies ou simultanément fausses. On note alors $P\iff Q$.

Quantificateurs

• Le quantificateur pour tout ou quel que soit est noté $\forall $. La proposition $\forall x\in E,\ P(x)$ est vraie lorsque, pour tout $x\in E$, la proposition $P(x)$ est vraie.
• Le quantificateur il existe (au moins un) est noté $\exists$. La proposition $\exists x\in E,\ P(x)$ est vraie lorsqu'il existe au moins un $x\in E$ telle que la proposition $P(x)$ soit vraie.
• Le quantificateur il existe un unique est noté $\exists!$. La proposition $\exists! x\in E,\ P(x)$ est vraie lorsqu'il existe un unique $x\in E$ telle que la proposition $P(x)$ soit vraie.
• La négation de $\forall x\in E,\ P(x)$ est $\exists x\in E,\ \textrm{non }P(x)$.
• La négation de $\exists x\in E,\ P(x)$ est $\forall x\in E,\ \textrm{non }P(x)$.

Conditions nécessaires, conditions suffisantes

• Lorsque $P\implies Q$, on dit que $P$ est une condition suffisante à $Q$, et que $Q$ est une condition nécessaire à $P$.
• Lorsque $P\iff Q$, on dit que $P$ est une condition nécessaire et suffisante pour que $Q$ soit vraie