La logique et ses paradoxes La logique et ses paradoxes Yves SAGNIER La logique est pour certains le soubassement indispensable des mathématiques dont elle fait partie, pour d'autres, ce sont les mathématiques qui sont un sous-ensemble de la logique. En tout cas, au cours de l'histoire des mathématiques, les deux ont toujours été étroitement liées. En fait, pendant longtemps, on s'occupait de mathématiques en utilisant des raisonnements logiques implicites qu'on ne citait plus tant ils paraissaient évidents. C'est au XIXème et au XXème siècle que l'imbrication logique-mathématique a réellement été mise en exergue, spécialement à l'occasion de l'émergence de paradoxes dont on ne savait trop à laquelle des deux les attribuer. C'est Boole qui le premier a échafaudé un édifice logique dérivé de l'algèbre. La base fondamentale de l'algèbre de Boole est qu'une proposition ne peut avoir que deux valeurs de vérité : VRAIE (V) ou FAUSSE (F). Par exemple, pour les 4 opérateurs définis ci-dessus, on a les tables suivantes :
Introduction à la logique mathématique Polycopié première partie. (Notes des années précédentes susceptibles d'être modifiées.)TD : fiche 1, fiche 2, fiche 3. Les notes du cours Logique et théorie des ensembles de Patrick Dehornoy fournissent une bonne ressource bibliographique pour cette partie. Autre référence bibliographique : Jean-Louis Krivine, Théorie des ensemble, Cassini 2007. Polycopié seconde partie.
Logique avec Python Qu’est-ce qu’un booléen ? Voir la page sur Wikipédia C’est une variable qui ne peux prendre que deux valeurs : VRAI ou FAUX.En Python, le type d’une telle variable est bool, les deux valeurs possibles sont True ou False. Expressions booléennes Une expression booléenne a deux valeurs possibles : True ou False.Python attribue à une expression booléenne la valeur False si c’est : la constante False la constante None une séquence ou une collection vide une donnée numérique de valeur 0. >>> type(False)<class 'bool'>>>> type(True)<class 'bool'>>>> FalseFalse>>> bool(None)False>>> bool(' ')True>>> bool('')False>>> bool(0)False>>> bool(156.87)True Opérateurs relationnels ou de comparaison Ce sont les opérateurs == , ! * Illustration pour x = 7 et y = 17 Cela donne dans le shell de Python : >>> x=7>>> y=17>>> x==yFalse>>> x! * Illustration avec deux chaînes de caractères >>>a='encyclopédie1'>>>b='encyclopédie2'>>>a==bFalse>>>len(a)13>>>a[:12]==b[:12]True Exercices Python 2/ Écrire un programme qui dira si
Paradoxes mathématiques Les chroniques suivantes ont pour thèmes les paradoxes mathématiques. Elles illustraient les programmes d'interrogations de l'année 2002-2003. Les paradoxes sémantiques Les paradoxes de logique mathématique et de théorie des ensembles Les paradoxes sur la notion d'infini Les paradoxes de la théorie de la mesure Les paradoxes des probabilités et des statistiques Les paradoxes sur les nombres Un paradoxe "physique" Le paradoxe de Langevin.
Lois de Morgan ChronoMath, une chronologie des MATHÉMATIQUES à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges Si A et B sont deux propositions susceptibles d'être vraies ou fausses, notons nonA (resp. nonB) la négation de A (resp. de B). On nomme lois de Morgan, les deux lois usuelles de logique propositionnelle : non (A ou B) = (nonA) et (nonB) nier A ou B, c'est nier A et nier B (ni A ni B) dire que x = ±1 est faux c'est dire x ≠ 1 et x ≠ -1 non (A et B) = (nonA) ou (nonB) nier la coexistence de A et de B, c'est nier A ou nier B dire que x est divisible par 2 et par 3 est faux, c'est dire que x est non divisible par 2 ou que x est non divisible par 3 i Les égalités "logiques"ci-dessus, utilisées par ailleurs dans cette page sont en fait des équivalences logiques : au lieu de « égale » on conviendra de lire « revient à dire ». » Aristote , Frege Diagramme de Venn (représentation d'Euler) : » »Cantor L'ellipse A (resp. ∗∗∗1. © Serge Mehl - www.chronomath.com
La logique d'Aristote ChronoMath, une chronologie des MATHÉMATIQUES à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges Outre la notion de syllogisme, on doit à Aristote les acceptions actuelles du vocabulaire (cadre jaune) lié au raisonnement déductif (on parle aussi de raisonnement hypothético-déductif), exposées dans les Topiques et dans ses traités sur la logique, Les Analytiques, La métaphysique : C'est chez Aristote que l'on trouve pour la première fois un langage propositionnel du type : si P alors Q et des lettres utilisées pour exprimer des propositions non explicitées. « Tout homme est mortel », « Cet enfant a les yeux bleus », « 124 n'est pas multiple de 3 » sont des propositions. Autre sens, plus récent, de prédicat (fonction propositionnelle) : » Cette logique basée sur le VRAI et le FAUX connut, dans les années 1930, quelques soucis avec l'apparition de propositions indécidables et la vague intuitionniste de Brouwer. 1. 2. 3. 4. non(P ∧ nonP) 5. P ∨nonP
Lois de De Morgan Un article de Wikipédia, l'encyclopédie libre. Représentation graphique des lois de De Morgan. Énoncé en français[modifier | modifier le code] La négation de la conjonction de deux propositions est équivalente à la disjonction des négations des deux propositions, ce qui signifie que « non(A et B) » est identique à « (non A) ou (non B) ». La négation de la disjonction de deux propositions est équivalente à la conjonction des négations des deux propositions, ce qui signifie que « non(A ou B) » est identique à « (non A) et (non B) ». Énoncé mathématique[modifier | modifier le code] Sachant que la conjonction s'exprime par le signe : , la disjonction s'exprime par le signe : et la négation d'une formule s'écrit De ces quatre implications valides en logique classique, trois sont valides en logique intuitionniste, mais pas : Justification[modifier | modifier le code] Pour justifier ces formules, on peut par exemple, utiliser la méthode sémantique des tables de vérité. et Vrai au rang n=2Si vrai au rang n
XOR swap algorithm Using the XOR swap algorithm to exchange nibbles between variables without the use of temporary storage The algorithm is primarily a novelty and a way of demonstrating properties of the exclusive or operation. It is sometimes discussed as a program optimization, but there are almost no cases where swapping via exclusive or provides benefit over the standard, obvious technique. The algorithm[edit] Conventional swapping requires the use of a temporary storage variable. X := X XOR Y; // XOR the values and store the result in XY := Y XOR X; // XOR the values and store the result in YX := X XOR Y; // XOR the values and store the result in X Since XOR is a commutative operation, either X XOR Y or Y XOR X can be used interchangeably in any of the foregoing three lines. In the above System/370 assembly code sample, R1 and R2 are distinct registers, and each XR operation leaves its result in the register named in the first argument. Proof of correctness[edit] exhibits the following properties (where
LE DÉMINEUR ET LA LOGIQUE, RÉDUCTION ET ÉQUIVALENCE J’ai souvent entendu la blague suivante quand j’apprenais à programmer. Vous donnez à un robot [1] un paquet de pâtes, une casserole, une plaque chauffante, et un robinet d’eau. Puis vous lui apprenez comment faire des pâtes. Quelques jours plus tard, vous demandez au robot de faire des pâtes, en lui disant qu’il y a de l’eau bouillante dans la casserole. Vous voyez alors le robot vider la casserole dans l’évier. Une introduction à la notion de réduction Intuitivement, effectuer une réduction signifie que, à partir de la première situation, vous pouvez atteindre la seconde facilement. Peut-être que le robot ne sait pas comment ignorer des étapes. L’intérêt des réductions Jusqu’à présent, la réduction n’était pas passionnante. Naïvement, on pourrait imaginer que cette réduction ne présente plus d’intérêt. Puisque mon paragraphe précédent commençait par « naïvement », vous vous doutez certainement qu’il était faux. La notion d’équivalence Un vrai exemple d’équivalence Le démineur Propositions
Forme prénexe Un article de Wikipédia, l'encyclopédie libre. et ) apparaissent à gauche dans cette formule. C’est-à-dire, G est en forme prénexe si et seulement si avec une formule sans quantificateurs. Toutes les formules du premier ordre sont logiquement équivalentes à une formule en forme prénexe. La complexité d'une formule de logique mise en forme prénexe se mesure à son premier quantificateur et au nombre d'alternance de blocs de quantificateurs universels ou existentiels qui le suivent et précèdent la formule sans quantificateur. Règles de transformations[modifier | modifier le code] Pour mettre une formule logique en forme prénexe, on peut utiliser les règles de transformation suivantes entre formules équivalentes : La variable x ne doit avoir aucune occurrence libre dans G (voir Calcul des prédicats). Remarques[modifier | modifier le code] Il n'y a pas de règles simples de transformation pour une formule comportant le connecteur mais ces règles suffisent car est un système complet de connecteurs.
Transformation de Möbius En mathématiques, et plus particulièrement en géométrie, les transformations de Möbius sont de manière générale des automorphismes du compactifié d'Alexandrov de noté , définies comme la composée d'un nombre fini d'inversions par rapport à des hyperplans ou des hypersphères. En particulier, si on identifie à la sphère de Riemann , alors on peut prouver que les transformations de Möbius conservant l'orientation sont de la forme : avec a, b, c et d quatre complexes tels que ad – bc ≠ 0, la formule ci-dessus étant à prendre au sens suivant si z = ∞ ou si cz + d = 0 : Définition générale[modifier | modifier le code] Soit n un entier naturel, on munit ℝn de sa structure euclidienne canonique et on définit alors les inversions de par rapport à un hyperplan ou à une hypersphère (qu'on appellera parfois plan et sphère par abus de langage) : De plus, ces inversions sont des homéomorphismes. Définition — L'ensemble des transformations de Möbius, est le sous-groupe des homéomorphismes de . , on note . sur . de