Tautologie (logique)
From Wikipedia, the free encyclopedia
En logique mathématique, la tautologie est une proposition toujours vraie selon les règles du calcul propositionnel.
En calcul propositionnel, à la suite du Tractatus logico-philosophicus de Wittgenstein paru en 1921, on appelle tautologie (du calcul propositionnel) une proposition (ou énoncé) toujours vraie, c'est-à-dire vraie quelle que soit la valeur de vérité, vraie ou fausse, de ses constituants élémentaires[1]. Dit autrement, la table de vérité de cet énoncé prend toujours la valeur vrai. Par exemple « s'il fait beau, alors il fait beau » qui est de la forme « si A, alors A » (ou « A implique A ») est une tautologie. Les tautologies ainsi définies peuvent paraître sans réelle signification, n'apporter aucune information. Si c'est bien le cas de celle précitée, les tautologies propositionnelles peuvent tout de même être bien plus complexes. Affirmer que « de A1, … , An on déduit B », revient à affirmer que la proposition « si A1, … , si An alors B » est une tautologie. Or, comme le remarque Kleene le raisonnement logique ordinaire revient à manier de telles relations de déduction (pas forcément dans le cadre du calcul propositionnel)[2].
Il reste qu'en calcul propositionnel classique, la question de savoir si un énoncé donné est une tautologie qui est décidable, c'est-à-dire que cette question peut être théoriquement résolue de façon purement mécanique, par exemple par les tables de vérité. Cependant, ce problème est co-NP-complet, le temps de calcul devient rapidement prohibitif (du moins dans l'état actuel des connaissances).
