25 connectés 3741 membres
Recherche :
Historique des modifications de ce cours:
Dernière version du 10.06.2008 14h44
1 Propositions et propriétés sur un ensemble 1.1 Propositions 1.1.1 Principe de non-contradiction 1.1.2 Principe du tiers exclu 1.2 Propriétés sur un ensemble 1.2.1 Un peu de vocabulaire : les ensembles 1.3 Propriétés sur un ensemble 1.3.1 Partie de l'univers associée à une propriété définie sur cet univers 1.3.2 Négation d'une propriété définie sur E 1.3.3 Négation d'une propriété et ensemble associé 1.3.4 Théorème 1 (première forme) 1.3.5 Théorème 1 (deuxième forme 2 Connecteurs "ou", "et" 2.1 Définitions 2.2 Associativité des connecteurs "ou", "et" 2.3 Distributivité de "ou" sur "et", de "et" sur "ou" 2.4 Théorème 2 3 Connecteur "implique" 3.1 Définition 3.2 Théorème 3 3.3 Théorème 4 4 Connecteur "équivaut" (équivalence logique) 4.1 Définition 4.1.1 Propriété 5 Démonstration par l'absurde 6 Quantificateurs 6.1 Quantificateur universel 6.2 Quantificateur existentiel 6.3 Théorème 5
[Inachevé] Cette leçon est absolument élémentaire, elle ne présuppose aucune connaissance au-delà d'un honnête programme de Troisième. D'ailleurs, autrefois, elle était la première leçon que voyait tout élève entrant en Seconde Scientifique (2nde C à l'époque, en France). La Logique est une base extrêmement précieuse, non seulement pour le futur scientifique, mais pour le futur technologue (électronicien, électrotechnicien), le futur philosophe ou pourquoi pas le futur juriste - en fait, pour tous ceux qui auront besoin d'un raisonnement sain et efficace.
Une proposition est une affirmation qui a un sens. "qui a un sens" signifie précisément : "dont on peut dire sans ambiguïté si c'est vrai ou faux". Ainsi, "Il fait beau en ce moment" est une proposition : on peut voir si c'est vrai ou faux en regardant le ciel, sans autre problème. "2 est plus grand que 3" est une proposition, clairement fausse. Par contre, "je mens" n'est pas une proposition : - si je fais l'hypothèse qu'elle est vraie, elle affirme justement que la personne qui parle est en train de mentir, et donc je dois en déduire qu'elle est fausse ; - si par contre, je suppose qu'elle est fausse, alors la personne ne ment pas, et elle dit la vérité, aussi, je dois en déduire qu'elle est vraie. On posera axiomatiquement les principes :
Une proposition ne peut à la fois être vraie et fausse.
Une proposition ne peut avoir d'autre "valeur de vérité" que "V" (vrai) ou "F" (faux).
On appelle ensemble toute collection d'objets, réels ou imaginaires. Par exemple, l'ensemble des livres que je possède ; l'ensemble des voitures de sport de ma collection privée (je n'en ai encore aucune, mais peut-être un jour...) que nous appellerons ensemble vide ; l'ensemble des entiers naturels (il y en a une infinité : 0, 1, 2, ..., 2008, ... 1 000 000, ...), etc. Les objets contenus dans ces collections seront appelés éléments des ensembles, ou objets appartenant à ces ensembles. Si l'on connaît la liste des éléments d'un ensemble , on peut écrire selon la syntaxe : (pour dire que est l'ensemble des chiffres) Sinon, on peut écrire une description déterminant sans ambiguïté les éléments de l'ensemble : = {entiers naturels} ou = {0,1,2,....} pour suggérer que la liste s'allonge indéfiniment. On peut aussi écrire (lire : l'ensemble des chiffres est l'ensemble des entiers naturels tels que est compris entre 0 et 9). On notera par exemple pour dire que 134 000 est un élément de l'ensemble des entiers naturels, ou appartient à l'ensemble . et pour dire que la Porsche 911 n'appartient pas à ma collection de voitures de sport...( se lit "appartient à " ou "élément de", et se lit "n'appartient pas à" ou "n'est pas élément de") En général, on se donne toujours un ensemble contenant tout ce dont j'ai besoin pour un propos déterminé, ensemble qu'on appellera univers. Par exemple, si je me propose de calculer le nombre de chaussettes que je puis m'acheter, je choisirai a priori , car ce nombre est forcément entier naturel. Si je fais de la géométrie élémentaire et raisonne sur les angles d'un triangle, je puis me contenter de poser , etc. Si je considère d'autres ensembles, ce ne peut être que des ensembles contenus dans cet univers , c'est-à-dire des ensembles dont tous les éléments sont pris parmi les éléments de . On dit qu'un ensemble est inclus dans , et l'on écrit si tous les éléments de sont éléments de . ( se lit : "est inclus dans", ou "est une partie de") Si , le complémentaire de dans est l'ensemble des éléments de qui n'appartienent pas à , on le note de plusieurs façons : , parfois s'il n'y a pas ambiguïté. Attention, on lit : complémentaire de A, : E moins A, : complémentaire de dans . Exemple, si est l'ensemble des entiers pairs, son complémentaire dans est , l'ensemble des entiers impairs. Comme on peut dire que , on peut définir et (nous verrons que ) : , ou si l'on préfère : et étant deux ensembles quelconques inclus dans l'univers, on peut définir plus généralement comme ensemble des éléments de qui n'appartiennent pas à , et comme ensemble des éléments de qui n'appartiennent pas à . On a donc : (lire : est l'ensemble des éléments de tels que n'appartient pas à ) (lire : moins est l'ensemble des éléments de tels que n'appartient pas à ) Soient deux ensembles et dans l'univers. On définit leur réunion comme l'ensemble des éléments appartenant à au moins l'un des deux : (lire : union est l'ensemble des éléments de tels que appartient à ou à ; attention, le "ou" ici n'est pas exclusif, et ne signifie pas "ou bien... ou bien", mais "au moins à l'un des deux") On définit ausi leur intersection comme l'ensemble des éléments appartenant à la fois à l'un et à l'autre : (lire : inter est l'ensemble des éléments de tels que appartient à et à ) On appelle application d'un ensemble sur un ensemble l'objet mathématique qui à tout élément fait correspondre un et un seul élément noté . On note ceci pour dire que prend des éléments de pour les faire correspondre à des éléments de (on dit que est l' ensemble de départ ou source de l'application et que est l' ensemble d'arrivée ou but de . On note aussi la correspondance réalisée par entre éléments de et .
Soit un ensemble. Si est un élément quelconque de , et une proposition pour tout fixé, alors on dit que est une propriété définie sur . On peut définir ceci en disant que est une application de sur l'ensemble , parce que l'on connaît tout sur si l'on a la liste complète des éléments de pour lesquels est vraie, ou fausse (on a noté pour "vraie" et pour "fausse").
Exemples : la propriété : " est un nombre pair". Il est clair que est l'application telle que
A toute propriété , associons l'ensemble des éléments de tels que la proposition est vraie. Ainsi, à la propriété : "x est pair", définie sur , on associe l'ensemble des nombres pairs.
Soit une propriété définie sur un ensemble (qu'on appellera donc univers). On dit qu'une propriété définie sur le même ensemble est une négation de si pour tout , lorsque est vraie, est fausse, et lorsque est fausse, est vraie :
Ainsi, une négation de la propriété "x est pair" est "x est impair" , une autre négation est "x n'est pas pair" , ou "il est faux d'affirmer que x est pair"...
Si est une négation de , on écrit : [Nous préciserons plus loin la signification de la notation (équivalence logique); disons ici qu'elle signifie que les propriétés ont toujours la même valeur de vérité]
Résultat élémentaire, mais à remarquer : une négation de est , et dans l'autre sens, une négation de est ; en effet, regardons le tableau :
Autre moyen de voir ce résultat : Négation de "x est plus petit que 20" : "x n'est pas plus petit que 20", soit "x est plus grand ou égal à 20". On se rappellera qu'une négation d'une inégalité stricte est une inégalité large, et une négation d'une inégalité large est une inégalité stricte.
Si une propriété est associée à l'ensemble inclus dans , alors une négation est associée à son complémentaire . Par exemple, la propriété : "x est pair" est associée à l'ensemble Une négation est :"x est impair" et elle est associée à .
On peut exprimer la définition de la négation par la "table de vérité" :
On en tire immédiatement (par simple lecture !) le théorème : Si est une négation de , alors est une négation de . Ce théorème s'exprime aussi par Si , alors
Nions deux fois de suite une propriété sur un ensemble :
Le simple examen des colonnes de la table de vérité donne l'énoncé du théorème : Une négation d'une négation d'une propriété est équivalente à Autrement dit :
Soient deux propriétés définies sur le même ensemble . est une propriété sur qui est :
On peut exprimer cette définition par la "table de vérité" :
Remarque La conjonction ou veut donc dire, non pas "ou bien..ou bien", mais "au moins l'une des deux (propriétés) est vraie". C'est le ou inclusif, et non exclusif. est une propriété sur qui est
On peut exprimer cette définition par la "table de vérité"
Une simple table de vérité montre qu'on a et aussi
Enoncé : Une négation de est . Une négation de est . Soit : Preuve : Nous nous bornerons à dresser une table de vérité pour prouver la première ligne d'abord :
On a prouvé, par l'identité des 3e et 6e colonnes, la première ligne du théorème. Pour démontrer la deuxième ligne, posons La première ligne (déjà prouvée ici), peut s'écrire Mais le théorème 1 sous sa première forme permet d'écrire , donc on obtient et le même théorème 1 sous sa première forme donne Exemples Une négation de "achète du pain ou des croissants" est "n'achète ni pain ni croissants" Une négation de "Tu as eu ton Bacc et tu es admis en Math Sup" est "Tu as raté ton Bacc ou tu n'es pas admis en Math Sup" (c'est-à-dire : "Tu n'as pas atteint les deux objectifs qui étaient tous les deux attendus" Une négation de ", c'est-à-dire de est ou, précisons (!) : Une négation de est Une négation de c'est-à-dire de est : Une négation de , c'est-à-dire de , soit de () est () ce qui s'écrit encore : une négation de est
Soient deux propriétés sur le même ensemble . La propriété (lire : implique ) définie sur est une propriété
Cela donne la table de vérité :
On peut interpréter comme "Si est vraie, alors est vraie" (en remarquant bien : "Si est fausse, je n'ai rien dit"!)
Beaucoup de néophytes ont des difficultés en considérant l'exemple suivant : Un père dit à son fils : "Si tu as ton Bacc, (alors) je t'offre une moto" Quatre cas peuvent être envisagés :
On se dit que dans le 3e cas, la promesse du père n'est pas tenue ! Mais si ! Il n'a jamais rien promis, rien affirmé, pour le cas où son fls n'a pas le Baccalauréat. D'ailleurs, l'enfant a pu avoir un accident au milieu de l'année scolaire, fait 3 mois d'hôpital et n'a pas pu passer l'examen. L'enfant a pu échouer au Bacc, mais fait autre chose de plus méritoire encore Le père peut simplement être bon et décider de l'encourager, y compris s'il existe des raisons non mentionnées ici... Le père aurait menti uniquement si l'enfant réussissait au Bacc mais n'avait pas la récompense promise. D'où la pertinence de la définition énoncée plus haut.
Les implications et sont logiquement équivalentes. Cela s'écrit : La deuxième implication est dite contraposée de la première. Preuve Dressons juste une table de vérité :
Autre preuve est fausse uniquement ssi est vraie et est fausse, c'est-à-dire si est fausse et est vraie, c'est-à-dire ssi est vraie.
Exemples "Si j'ai (au moins) 18 ans, je peux voter" équivaut à "Si je peux voter, alors j'ai (au moins) 18 ans" équivaut à (les deux implications sont d'ailleurs vraies pour tout )
équivaut à Preuve : on pourrait dresser une table de vérité, mais il est plus simple de dire que est faux ssi et sont tous deux faux, c'est-à-dire que est vraie et est fausse.
Exemple "Si tu n'es pas sage, tu seras privé de cinéma" équivaut à "Tu es sage ou tu seras privé de cinéma". " est multiple de 4 " équivaut à " n'est pas multiple de 4 ou est pair" ; ce qu'il faut comprendre, c'est que tout entier est non multiple de 4 ou pair ! En effet, les non-multiples de 4 contiennent tous les entiers impairs ; en leur adjoignant les entiers pairs, on obtient tous les entiers naturels.
Soient deux propriétés définies sur un ensemble . La propriété est définie comme Autrement dit, on a la table de vérité :
Autrement dit, signifie que ont la même valeur de vérité. Le théorème 3 (qui dit qu'une implication équivaut à sa contraposition) donne la
équivaut à Autrement dit, deux propriétés sont équivalentes entre elles ssi leurs négations sont équivalentes entre elles.
On voudrait prouver qu'une propriété est vraie. Pour cela, on considère une négation qu'on adjoint à un ensemble cohérent de propriétés toutes vraies (par exemple, les règles connues de l'algèbre des réels). Soit une propriété connue, , dont on a la certitude qu'elle est vraie. Si l'on peut montrer qu'avec l'hypothèse , c'est-à-dire l'hypothèse que est fausse, et en utilisant les données de , on peut déduire logiquement que est fausse, alors on dira qu'on a obtenu une contradiction, et que par suite, on peut conclure que est vraie. En effet, on a déduit de l'hypothèse " est fausse" la conséquence " est fausse". Cela revient au même que de déduire de l'hypothèse " est vraie" la conclusion " est vraie" ; or on savait que est toujours vraie, donc on doit conclure que est vraie aussi. Exemple On veut montrer qu'il existe des nombres premiers aussi grands qu'on veut (c'est-à-dire qu'il n'existe pas de plus grand nombre premier) Supposons donc qu'il existe un plus grand nombre premier, (tous les nombres qui le dépassent seraient donc non premiers). Or il est clair que le nombre est strictement supérieur à . On a donc émis l'hypothèse que serait non premier. Il ne serait donc divisible par au moins un l'un des nombres premiers 2, 3, 5,..., . Or la division euclidienne de par tout nombre compris entre 2 et donne pour reste 1 (si était divisible par l'un de ces nombres premiers, le reste serait 0) : Ce qui veut dire qu'on obtient une contradiction : ne peut avoir de diviseur premier ; il est donc premier, et strictement supérieur à , ce qui est contradictoire. On a donc démontré qu'il existe des nombres premiers aussi grands qu'on veut.
Le quantificateur universel, noté (lire "pour tout..." ou "pour tous les..."), est défini par (lire : "Pour tout de , (est vraie)") N.B. On a noté l'ensemble inclus dans associé à la propriété .
Le quantificateur existentiel, noté (lire "il existe...", "il existe au moins un..."), est défini par (lire : "Il existe (au moins un) de tel que (soit vraie)")
Une négation de est Une négation de est On peut écrire Preuve Démontrons la première ligne : Pour démontrer la deuxième ligne, contentons-nous de poser Le résultat qui vient d'être démontré s'écrit Le théorème 1, sous sa première forme, permet d'écrire ceci : ce qui est exactement la deuxième ligne, que nous voulions démontrer. Exemple Une négation de "Tous les hommes sont forts" est "Il existe au moins un homme qui n'est pas fort" Considérons la propriété : "Pour tout réel , il existe un réel , tel que est l'inverse de " ce qui s'écrit (c'est une propriété fausse, bien sûr !) Une négation de est (c'est vrai, évidemment, car cet existe : c'est 0) Cet exemple se généralise aisément à : il suffit de remplacer par et réciproquement, et de remplacer à la fin par une négation .
Dernière mise à jour: le 10.06.2008 à 15:44 Licence: Libre de partager, modifier - Devoir de citer la source - Pas d'utilisation commerciale Daskoo.org, partage de cours
