On a vu qu’un énoncé comme “x>0” n’est pas une proposition puisqu’il ne possède pas de valeur de vérité claire. Si \(x=-1\text{,}\) l’énoncé devient une proposition fausse, alors que si \(x=2\text{,}\) il devient une proposition vraie. Bien que certains énoncés avec variables peuvent sembler vrais, peu importe la valeur de la variable, on préfèrera ne pas les considérer comme des propositions. Un exemple d’un tel énoncé serait \(x^2\geq 0\text{.}\) Comme fonction réelle, il est vrai qu’un nombre au carré est toujours positif. Il existe toutefois d’autres contextes où cette équation ne serait plus nécessairement vraie. 1
Dans cette section, on définit le quantificateur existentiel et le quantificateur universel. On explique aussi comme obtenir la négation d’une proposition quantifiée.
Un énoncé qui contient une ou des variables est appelé un prédicat. Ce n’est pas une proposition, car la valeur de vérité dépendra de la valeur des variables. On spécifie normalement un ensemble univers \(\Omega\) qui consiste aux diverses possibilités que peuvent prendre les variables. Pour des valeurs spécifiques des variables, le prédicat devient une proposition.
Sous-section2.3.2Quantificateurs existentiel et universel
On peut donc transformer un prédicat en proposition en assignant aux variables certaines valeurs. On peut aussi ajouter un quantificateur à un prédicat. Un quantificateur est un mot du genre “certains, quelques, toutes, etc.” qui vient parler, d’une manière plus ou moins précise, de combien de valeurs de la variable on s’intéresse. Ainsi si on dit, “pour certaines valeurs de \(x\in \R\) on a \(x>4\)”,on obtient une proposition. Dans ce cas-ci, elle est vraie, mais si on avait dit “pour toutes les valeurs de \(x\in \R\text{,}\) on a \(x>4\)”, on aurait obtenu une proposition fausse.
En mathématiques, il y a deux principaux quantificateurs qui sont utilisés. Le quantificateur existentiel et le quantificateur universel. Le premier s’intéresse à l’existence d’une valeur des variables qui rendent le prédicat vrai. Il n’est même pas nécessaire de la trouver cette valeur, et il pourrait y en avoir plus d’une. L’important, c’est qu’elle existe. Le quantificateur universel lui veut que le prédicat soit vrai pour toutes les valeurs de l’ensemble univers.
Soit \(P(x)\) un prédicat et \(\Omega\) l’ensemble univers de la variable \(x\text{.}\) Une proposition existentielle est un énoncé de la forme “il existe \(x\in \Omega\) tel que \(P(x)\) est vrai”. D’un point de vue symbolique, on la dénote \(\exists x\in \Omega \, P(x)\) (le symbole \(\exists\) se lit “il existe”). La proposition est vraie s’il existe au moins une valeur dans \(\Omega\) qui rende \(P(x)\) vrai et est fausse si toutes les valeurs de \(\Omega\) font que \(P(x)\) est faux.
Avec une proposition contenant un quantificateur existentiel, on obtient la valeur de vérité “vraie” dès qu’ (au moins) une valeur de \(\Omega\) rende le prédicat vrai. Pour que la proposition soit fausse, il faut toutefois vérifier que le prédicat est faux pour toutes les valeurs dans \(\Omega\text{,}\) ou du moins argumenter cela.
Il y a en fait deux types de mammifères qui pondent des oeufs. L’ornithorynque est probablement l’exemple le plus connu, mais il y a aussi les échidnés.
Ceci constitue un bon exemple de l’existence d’une valeur, sans toutefois pouvoir la déterminer. Comme la croissance d’une personne est un processus continu et qu’un humain nait normalement entre 46 et 56 cm (le record étant de 71!), il existe bel et bien un moment où l’auteur mesurait 100 cm. Bien malin toutefois celui qui pourra dire quand cela s’est produit.
Alors que le quantificateur existentiel souhaite l’existence d’une valeur rendant le prédicat vrai, le quantificateur universel lui veut que le prédicat soit vrai pour toutes les valeurs de l’univers considéré.
Soit \(P(x)\) un prédicat et \(\Omega\) l’ensemble univers de la variable \(x\text{.}\) Une proposition universelle est un énoncé de la forme “pour tout \(x\in \Omega\) on a que \(P(x)\) est vrai”. D’un point de vue symbolique, on la dénote \(\forall x\in\Omega \, P(x)\) (le symbole \(\forall\) se lit “pour tout”). La proposition est vraie si chaque valeur de \(x\) dans \(\Omega\) rend \(P(x)\) vrai et est fausse dès qu’une valeur de \(x\) font que \(P(x)\) est faux.
Avec une proposition contenant un quantificateur universel, il faut vérifier (ou argumenter pour) toutes les valeurs de \(\Omega\) pour que la proposition soit vraie. Pour qu’elle soit fausse, il suffit d’exhiber une valeur de \(x\) pour laquelle \(P(x)\) est faux.
La proposition est vraie, la parité d’un nombre créant une dichotomie des nombres naturels. On aura les outils nécessaires pour formaliser ceci prochainement.
Une proposition universelle est souvent présentée à l’aide d’une implication. On retrouve donc fréquemment, pour des prédicats \(P\) et \(Q\text{,}\) la forme
En langage courant, cela signifie que pour tout \(x\) dans l’ensemble univers, avoir la propriété \(P(x)\) implique aussi avoir la propriété \(Q(x)\text{.}\)
Par exemple, on pourrait dire \(\forall x\in \R\text{,}\) si \(x>2\) alors \(x^2>4\text{.}\) Ceci n’est pas très surprenant comme propriété. Cette proposition apporte toutefois une vision intéressante sur la table de vérité de l’implication, en particulier, pourquoi les ligne \(F\)-\(V\) et \(F\)-\(F\) sont vraies.
Si dans son ensemble la proposition “\(\forall x\in \R\text{,}\) si \(x>2\) alors \(x^2>4\)” est vraie, alors selon la définition du quantificateur universel, il faut que “si \(x>2\) alors \(x^2>4\)” soit vraie pour toutes les valeurs de \(x\text{.}\) En particulier, il faut que
\(-3>2\rightarrow (-3)^2>4\) soit vraie (ce qui correspond à \(F\)-\(V\))
Il existe bien entendu plusieurs manières équivalentes d’écrire des propositions. Par exemple, “si \(\Omega\) est l’ensemble des polygones, \(\forall x\in \Omega\text{,}\) si \(x\) est un carré alors \(x\) est un rectangle” pourrait être écrite de manière équivalente comme “\(\forall x\) carré, \(x\) est un rectangle.”
D’un point de vue pratique, et dans le but d’alléger l’écriture, on omet parfois l’écriture des quantificateurs universels. Ainsi, la proposition \(x>2\rightarrow x^2>4\) doit être comprise comme la proposition quantifiée \(\forall x\in \R \,x>2\rightarrow x^2>4 \text{.}\) On décide de garder l’écriture complète avec le quantificateur dans ce chapitre, mais il est possible qu’à l’occasion on le laisse tomber aussi au profit d’une écriture plus concise. Dans un souci de distinction, on introduit la notation suivante:
Sous-section2.3.3Négation et combinaisons de quantificateurs
On s’intéresse maintenant à la négation d’une proposition quantifiée. On reprend la proposition \(p=\)“il y a un mammifère qui pond des oeufs”. Quelle est sa négation? À première vue, on pourrait penser que c’est “il y a un mammifère qui ne pond pas d’oeufs”, mais ce n’est pas tout à fait cela. Si on veut inverser la valeur de vérité de \(p\text{,}\) et donc dire “il est faux de dire qu’il y a un mammifère qui pond des oeufs”,il faudrait que tous les mammifères ne pondent pas d’oeufs.
De même, pour nier la proposition \(q=\)“tous les oiseaux peuvent voler”, on cherche à exprimer “il est faux de dire que tous les oiseaux peuvent voler”. Intuitivement, on comprend donc que c’est équivalent à dire qu’il existe un oiseau qui ne peut pas voler. Ainsi,
On répète ici qu’après analyse, cela ne devrait pas trop surprendre. S’il n’y a pas un objet avec une propriété, alors tous les objets n’ont pas la propriété. De même, si ce n’est pas tous les objets qui ont une propriété, alors il existe (au moins) un objet qui n’a pas la propriété. Le symbolisme en apparence complexe ne doit pas distraire du caractère simple de la chose.
On peut nier cette proposition en écrivant \(\forall a\in \Omega,\neg (a \text{ est dans le prénom de l'auteur})\text{,}\) qui devient \(\forall a\in \Omega,a \text{ n'est pas dans le prénom de l'auteur}\text{.}\)
Cette proposition est équivalente à \(\forall n\in\N\, n\text{ est pair ou impair}\text{.}\) Sa négation devient donc une proposition avec un quantificateur existentiel qui a la forme \(\exists n\in \N \, n\text{ est n'est pas pair et } n\text{ n'est pas impair}\text{.}\) On aurait aussi pu écrire plus simplement le prédicat comme \(n\) est ni pair ni impair. Le “et” fait toutefois ressortir la loi de De Morgann dans la négation du “ou”.
Il est également possible d’utiliser plus d’un quantificateur avec un prédicat. La forme symbolique mathématique prend alors toute son importance. Par exemple, on imagine la proposition suivante “il existe un gardien pour tous les animaux du zoo”. Qu’est-ce que cela signifie? Est-ce
il y a un seul gardien qui s’occupe de tous les animaux du zoo;
Pour cet exemple particulier, ce n’est pas trop grave si on interprète incorrectement la phrase “il existe un gardien pour tous les animaux du zoo”. Par contre en informatique, dans un contexte de programmation, il est primordial de bien interpréter ce qui est demandé afin que l’ordinateur puisse appliquer ce que l’utilisateur veut.
On imagine un prédicat en deux variables \(P(x,y)\text{.}\) La proposition \(\forall x\,\exists y P(x,y)\) peut s’interpréter de la manière suivante. On imagine quelqu’un qui choisit un \(x\text{.}\) Il faut ensuite trouver un \(y\) tel que \(P(x,y)\) est vrai. Le choix de \(y\) risque de dépendre du \(x\) qui est choisi.
Par contre dans la proposition \(\exists x\,\forall y P(x,y)\text{,}\) c’est le \(x\text{,}\) s’il existe, qui dépendra des \(y\text{.}\) On doit trouver un \(x\) qui fonctionnera peu importe le \(y\) que quelqu’un choisirait
Pour cette proposition, il suffit de trouver un triangle pour lequel tout cercle, le triangle sera à la droite du cercle. En regardant la figure 2.3.9, on constate que les triangles \(d\) et \(i\) satisfont cette propriété. En effet, les trois cercles \(a,b,c\) sont tous à la gauche de ces triangles. On peut donc dire que \(d\) et \(i\) sont à la droite de tous les cercles. Ainsi, la proposition est vraie.
Pour cette proposition, on cherche un cercle et un triangle de la même couleur. Aucun triangle n’est bleu, ce qui élimine les triangles \(a,c\text{.}\) Par contre, le cercle \(b\) et le triangle \(f\) (ou \(i\)) sont rouges. La proposition est donc vraie.
Cette fois-ci, il n’est pas suffisant de trouver deux formes de la même couleur. Il faut s’assurer que pour chaque triangle, il existe un carré ayant la même couleur. On identifie trois triangles, soit \(d,f\) et \(i\text{.}\) Le triangle \(d\) est vert. On vérifie sur la figure 2.3.9 que le carré \(e\) est aussi vert. Le triangle \(f\) est rouge, tout comme le triangle \(i\text{.}\) Dans les deux cas, le carré \(g\) ou le carré \(h\) sont aussi rouges. La propriété est donc vraie.
On doit vérifier la condition pour chaque triangle. Pour le triangle \(d\text{,}\) il est vrai de dire que tous les carrés sont sur une ligne inférieure, comme on peut le voir sur la figure 2.3.9. Par contre il y a des carrés sur la même ligne que le triangle \(f\) (les carrés \(e,g\)) et des carrés sur des lignes supérieures au triangle \(i\)(toujours les carrés \(e,g\)). Pour ces raisons, la proposition est fausse.
Comment se comportent les propositions formées de plus d’un quantificateur lorsqu’on considère leur négation? À l’aide des règles établies plus haut et en procédant en étape, on peut arriver à trouver la négation d’une telle proposition. On donne deux exemples de propositions formées de deux quantificateurs. D’autres se trouvent dans les exercices.
Dans un premier temps, on considère la proposition
\begin{equation*}
\exists x \, \forall y \, P(x,y)\text{.}
\end{equation*}
On pose \(Q(x,y)\) la proposition \(\forall y P(x,y)\text{.}\) La proposition originale s’écrit donc comme \(\exists x \, Q(x,y)\text{.}\) Selon la négation d’une proposition quantifiée par un quantificateur existentiel, on a \(\neg(\exists x \, Q(x,y))\equiv \forall x \,\neg Q(x,y)\text{.}\) On peut ensuite calculer la négation de \(Q(x,y)\) en utilisant la règle pour la négation d’une proposition quantifiée par un quantificateur universel. On obtient \(\neg Q(x,y)=\neg(\forall y P(x,y))=\exists y \neg P(x,y)\text{.}\) Ainsi,
\begin{equation*}
\neg (\exists x \, \forall y \, P(x,y))\equiv \forall x\, \exists y\, \neg P(x,y)\text{.}
\end{equation*}
La négation d’une proposition quantifiée par un quantificateur existentiel est une proposition quantifiée par un quantificateur universel suivi de la négation du prédicat.
La négation d’une proposition quantifiée par un quantificateur universel est une proposition quantifiée par un quantificateur existentiel suivi de la négation du prédicat.
Dans une ferme, on retrouve les animaux suivants: un chien blanc et noir ainsi qu’un chien brun, treize vaches de couleur blanche et noire, seize moutons blancs, quatre chats noirs, trente-trois poules brunes.
\(BN,Br,B,N,J,G\) respectivement pour possède la couleur blanc et noir, brun, blanc, noir, jaune et enfin gris, et plus généralement \(C\) pour une allusion à la couleur quelconque.
La proposition \(\exists a\in F\, c(a)\wedge Br(a)\) peut être interprétée comme “il existe un chat brun”. Identifier les prédicats et transcrire en symbolique les propositions suivantes.
Est-ce que \(\forall x\,\exists y \,P(x,y)\equiv \exists y\,\forall x \,P(x,y) \text{?}\) Argumenter ou donner un exemple où l’équivalence n’est pas vraie.
Est-ce que \(\forall x\,\forall y \,P(x,y)\equiv \forall y\,\forall x \,P(x,y) \text{?}\) Argumenter ou donner un exemple où l’équivalence n’est pas vraie.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
Si l’urne ne contient aucune bille, cette proposition est vraie. En effet, la négation de la proposition est
\begin{equation*}
\exists b \in U \text{ couleur}(b) \neq \text{ blanche.}
\end{equation*}
Or, si l’urne est vide, cette proposition ne peut pas être vraie, et donc est fausse. Si la négation est fausse, alors l’énoncé initial doit être vrai.
Pour tout nombre réel \(x\text{,}\) il existe un nombre réel \(y\) tel que \(x < y\text{.}\) Cette proposition est vraie. Pour chaque \(x\text{,}\) il suffit de prendre, par exemple, \(y=x+1\text{.}\)
Il existe un nombre réel \(x\) tel que, pour tout nombre réel \(y\text{,}\) on a \(x \leq y\text{.}\) Cette proposition est fausse. En effet, pour tout nombre réel \(x\) on peut trouver un nombre réel \(y\) pour lequel la proposition \(x \leq y\) est fausse. Il suffit de poser, par exemple, \(y=x-1\text{.}\)
Pour tout nombre réel \(x\text{,}\) et pour tout nombre réel \(y\text{,}\) si \(xy\) est strictement positif, alors \(x\) et \(y\) sont tous les deux strictement positifs. Cette proposition en fausse, car le prédicat est faux lorsque \(x=y=-1\text{.}\)
Pour toutes paires de nombres réels \(x\) et \(y\text{,}\) si \(x\) et \(y\) sont strictement positifs, alors \(xy\) est strictement positif. Cette proposition est vraie par les propriétés des nombres réels.
La proposition \((a)\) reste vraie. En effet, pour tout \(x \in \[-1,1\[\text{,}\) on peut trouver un nombre réel \(y\) tel que \(x< y < 1\text{.}\) Cependant, la proposition \((b)\) change de valeur et devient vraie. En effet, en prenant \(x=-1\text{,}\) le prédicat est vrai pour tout nombre réel \(y\in \[-1,1\[\text{.}\)
S’il existe un \(x\) tel que \(P\) et \(Q\) sont vraies, alors certainement qu’il existe un \(x\) tel que \(P\) est vraie et un \(x\) (le même!) tel que \(Q\) est vraie. Est-ce qu’on peut affirmer l’inverse?
C’est faux. Soit \(P(x)\) le prédicat « \(x\) est plus grand que \(1\) » et \(Q(x)\) le prédicat « \(x\) est plus petit que \(0\text{.}\) D’un côté, il est impossible d’avoir une valeur de \(x\) qui est à la fois plus grande que \(1\) et plus petite que \(0\text{.}\) Par contre, il exsite une valeur de \(x\) pour lequel \(x\) est plus grand que \(1\) et il existe une valeur de \(x\) qui est plus petite que \(0\text{.}\)
On suppose qu’il existe \(x\) pour lequel \(P(x)\vee Q(x)\) est vrai. Alors pour ce \(x\text{,}\) on a que \(P(x)\) est vrai ou \(Q(x)\) est vrai, peut-être les deux. Donc, il existe un \(x\) rendant \(P(x)\) vrai ou il existe un \(x\) rendant \(Q(x)\) vrai.
D’un autre côté, si \(\exists x \,P(x)\vee \exists x \,Q(x)\) est vraie, alors soit \(\exists x \, P(x)\) ou soit \(\exists x \, Q(x)\text{.}\) Dans les deux cas, ce même \(x\) rend vrai le prédicat \(P(x)\vee Q(x)\text{.}\)
Si \(\forall x\,(P(x)\wedge Q(x))\) est vraie, alors pour tout \(x\text{,}\) on doit avoir \(P(x)\) et \(Q(x)\text{.}\) C’est donc vrai de dire que \(\forall x \, P(x)\) et \(\forall x \, Q(x)\text{.}\)
De plus, si \(\forall x \,P(x)\wedge \forall x \,Q(x)\) est vraie, alors pour tout \(x\text{,}\) on doit avoir \(P(x)\wedge Q(x)\) et donc, les propositions sont équivalentes.
C’est faux. On considère \(P(x)\) la proposition « \(x<0\)» et \(Q(x)\) la proposition « \(x\geq 0\)». Il est certainement vrai que, pour tout \(x\text{,}\) on a \(P(x)\) ou \(Q(x)\) puisque \(Q(x)\) est la négation de \(P(x)\text{.}\) La proposition \(\forall x \, (P(x)\vee Q(x))\) est une tautologie. Cependant, la proposition \(\forall x\, P(x)\) est fausse puisque certains nombres réels sont plus grands que \(0\) et la proposition \(\forall x \, Q(x)\) est fausse puisqu’il existe aussi des nombres réels plus petis que \(0\text{.}\) Les deux propositions ne sont pas équivalentes.
Pour chaque proposition, décrire en mots, déterminer la valeur de vérité et écrire la négation sous une forme symbolique simplifiée. L’ensemble univers est toujours la grille et sera omis pour alléger l’écriture des propositions.
Pour chaque proposition, décrire en symbole, déterminer la valeur de vérité et écrire la négation en langage courant. L’ensemble univers est toujours la grille et sera omis pour alléger l’écriture des propositions.
