Calcul des propositionsLe calcul des propositions ou calcul propositionnel, (ou encore logique des propositions) fait partie de la logique mathématique. Il a pour objet l'étude des relations logiques entre « propositions » et définit les lois formelles selon lesquelles les propositions complexes sont formées en assemblant des propositions simples au moyen des connecteurs logiques et celles-ci sont enchaînées pour produire des raisonnements valides. Il est un des systèmes formels, piliers de la logique mathématique dont il aide à la formulation des concepts.
Proposition (philosophie)Une proposition est en philosophie ce qui dans un énoncé est susceptible d'être conservé lors d'une traduction et de recevoir une valeur de vérité, c'est-à-dire d'être vrai ou faux. Un exemple courant pour désigner ce qu'est une proposition par rapport à un énoncé ou à une phrase est de comparer les deux énoncés ou phrases suivantes : « Il pleut. » « It's raining. » Ces deux énoncés ou phrases ont la même proposition, à savoir qu'il pleut. Un autre exemple courant dans le domaine est de comparer « La neige est blanche » et « Snow is white ».
Connecteur logiqueEn logique, un connecteur logique est un opérateur booléen utilisé dans le calcul des propositions. Comme dans toute approche logique, il faut distinguer un aspect syntaxique et un aspect sémantique. D'un point de vue syntaxique, les connecteurs sont des opérateurs dans un langage formel pour lesquels un certain nombre de règles définissent leur usage, au besoin complétées par une sémantique. Si l'on se place dans la logique classique, l'interprétation des variables se fait dans les booléens ou dans une extension multivalente de ceux-ci.
Formule propositionnelleEn logique mathématique une proposition, ou formule propositionnelle, ou expression propositionnelle est une expression construite à partir de connecteurs et de variables propositionnelles. En logique propositionnelle classique, une formule propositionnelle, ou expression propositionnelle, est une formule bien formée qui possède une valeur de vérité. Si les valeurs de toutes les variables propositionnelles dans une formule propositionnelle sont données, une unique valeur de vérité peut être déterminée.
Vérité logiqueLa vérité logique est l'un des concepts les plus fondamentaux de la logique. D'une manière générale, une vérité logique est une proposition qui est vraie indépendamment de la vérité ou la fausseté de ses propositions constitutives. En d'autres termes, une vérité logique est une affirmation qui n'est pas seulement vraie, mais qui est vraie sous toutes les interprétations de ses composants logiques (autres que ses constantes logiques). Ainsi, des vérités logiques telles que "si p, alors p" peuvent être considérées comme des tautologies.
Atomic sentenceIn logic and analytic philosophy, an atomic sentence is a type of declarative sentence which is either true or false (may also be referred to as a proposition, statement or truthbearer) and which cannot be broken down into other simpler sentences. For example, "The dog ran" is an atomic sentence in natural language, whereas "The dog ran and the cat hid" is a molecular sentence in natural language. From a logical analysis point of view, the truth or falsity of sentences in general is determined by only two things: the logical form of the sentence and the truth or falsity of its simple sentences.
Problème SATvignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.
SatisfaisabilitéEn logique mathématique, la satisfaisabilité ou satisfiabilité et la validité sont des concepts élémentaires de sémantique. Une formule est satisfaisable s'il est possible de trouver une interprétation (modèle), une façon d'interpréter tous les éléments constitutifs de la formule, qui rend la formule vraie. Une formule est universellement valide, ou en raccourci valide si, pour toutes les interprétations, la formule est vraie.
Problème 2-SATEn informatique théorique, le problème 2-SAT est un problème de décision. C'est une restriction du problème SAT qui peut être résolu en temps polynomial, alors que le problème général est NP complet. Le problème 2-SAT consiste à décider si une formule booléenne en forme normale conjonctive, dont toutes les clauses sont de taille 2, est satisfaisable. De telles formules sont appelées 2-CNF ou formules de Krom. On considère des formules en forme normale conjonctive, c'est-à-dire que ce sont des ET de OU de littéraux (un littéral est une variable ou la négation d'une variable).
Stoic logicStoic logic is the system of propositional logic developed by the Stoic philosophers in ancient Greece. It was one of the two great systems of logic in the classical world. It was largely built and shaped by Chrysippus, the third head of the Stoic school in the 3rd-century BCE. Chrysippus's logic differed from Aristotle's term logic because it was based on the analysis of propositions rather than terms. The smallest unit in Stoic logic is an assertible (the Stoic equivalent of a proposition) which is the content of a statement such as "it is day".
Horn-satisfiabilitéUne formule de Horn est une conjonction de clauses contenant chacune au plus un littéral positif, c'est-à-dire une conjonction de clauses de Horn. Puisque le problème SAT est NP-complet, donc vérifiable en temps polynomial et plus difficile que tout problème dans NP, il est naturel de rechercher des problèmes proches mais plus "faciles" à résoudre. C'est notamment le cas de la satisfaisabilité d'une formule de Horn, puisqu'il s'agit d'un problème P-complet, plus difficile que tout problème dans P.
Table de véritéUne table de vérité (parfois appelée fonction de vérité) est une table mathématique utilisée en logique classique — en particulier le calcul propositionnel classique et l'algèbre de Boole — pour représenter de manière sémantique des expressions logiques et calculer la valeur de leur fonction relativement à chacun de leurs arguments fonctionnels (chaque combinaison de valeur assumée par leurs variables logiques).
TautologieLa tautologie (du grec ancien ταὐτολογία, composé de ταὐτό, « la même chose », et λέγω, « dire » : le fait de redire la même chose) est une phrase ou un effet de style ainsi tourné que sa formulation ne puisse être que vraie. La tautologie est apparentée au truisme (ou lapalissade) et au pléonasme. En logique mathématique, le mot « tautologie » désigne une proposition toujours vraie selon les règles du calcul propositionnel. On utilise aussi l'adjectif tautologique en mathématiques pour désigner des structures qui émergent naturellement de la définition de certains objets.
Satisfiability modulo theoriesEn informatique et en logique mathématique, un problème de satisfiabilité modulo des théories (SMT) est un problème de décision pour des formules de logique du premier ordre avec égalité (sans quantificateurs), combinées à des théories dans lesquelles sont exprimées certains symboles de prédicat et/ou certaines fonctions. Des exemples de théories incluent la théorie des nombres réels, la théorie de l’arithmétique linéaire, des théories de diverses structures de données comme les listes, les tableaux ou les tableaux de bits, ainsi que des combinaisons de celles-ci.
Formule atomiqueEn logique mathématique, une formule atomique ou atome est une formule qui ne contient pas de sous-formules propres. La structure d'une formule atomique dépend de la logique considérée, p. ex. en logique des propositions, les formules atomiques sont les variables propositionnelles. Les atomes sont les formules les plus simples dans un système logique et servent à construire les formules les plus générales.
LogiqueLa logique — du grec , qui est un terme dérivé de signifiant à la fois « raison », « langage » et « raisonnement » — est, dans une première approche, l'étude de l'inférence, c'est-à-dire des règles formelles que doit respecter toute argumentation correcte. Le terme aurait été utilisé pour la première fois par Xénocrate. La logique antique se décompose d'abord en dialectique et rhétorique. Elle est depuis l'Antiquité l'une des grandes disciplines de la philosophie, avec l'éthique (philosophie morale) et la physique (science de la nature).
Valeur de véritéUne valeur de vérité est une valeur attribuée à chaque proposition logique. Pour donner une valeur de vérité à une proposition, on attribue des valeurs de vérité aux variables qu'elle contient. La valeur d'une proposition formés de deux propositions P et Q et d'un connecteur est calculée à partir des valeurs de vérité attribuées à P et à Q. Ainsi la valeur de vérité attribuée à « P et Q » sera « p.q » où « . » est la multiplication. En conséquence, P et Q est vrai si et seulement si P et Q sont chacun vrais.
ContradictionEn logique des propositions, une contradiction ou antilogie est une formule qui est toujours fausse, quelle que soit la valeur des variables propositionnelles. On dit aussi que la formule est insatisfaisable, antilogique ou encore contradictoire. L’antilogie, de symbole , s’oppose à la tautologie qui est toujours vraie. La contradiction est une relation existant entre deux ou plusieurs termes ou deux ou plusieurs propositions dont l’un(e) affirme ce que l’autre nie : « A » et « non-A » sont contradictoires, les phrases « Tous les hommes sont barbus » et « Quelques hommes ne sont pas barbus » sont contradictoires.
Truth functionIn logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly one truth value; and inputting the same truth value(s) will always output the same truth value.
Équivalence logiqueEn logique classique, deux propositions P et Q sont dites logiquement équivalentes ou simplement équivalentes quand il est possible de déduire Q à partir de P et de déduire P à partir de Q. En calcul des propositions, cela revient à dire que P et Q ont même valeur de vérité : P et Q sont soit toutes les deux vraies, soit toutes les deux fausses. L'équivalence logique s'exprime souvent sous la forme si et seulement si, dans des cadres comme l'enseignement ou la métamathématique pour parler des propriétés de la logique elle-même, et non du connecteur logique qui lie deux propositions.
