Logique algébriqueEn logique mathématique, la logique algébrique est le raisonnement obtenu en manipulant des équations avec des variables libres. Ce qui est maintenant généralement appelé la logique algébrique classique se concentre sur l'identification et la description algébrique des modèles adaptés à l'étude de différentes logiques (sous la forme de classes d'algèbres qui constituent la sémantique algébrique de ces systèmes déductifs) et aux problèmes connexes, comme la représentation et la dualité.
Déduction naturelleEn logique mathématique, la déduction naturelle est un système formel où les règles de déduction des démonstrations sont proches des façons naturelles de raisonner. C'est une étape importante de l'histoire de la théorie de la démonstration pour plusieurs raisons : contrairement aux systèmes à la Hilbert fondés sur des listes d'axiomes logiques plus ou moins ad hoc, la déduction naturelle repose sur un principe systématique de symétrie : pour chaque connecteur, on donne une paire de règles duales (introduction/élimination) ; elle a conduit Gentzen à inventer un autre formalisme très important en théorie de la démonstration, encore plus « symétrique » : le calcul des séquents ; elle a permis dans les années 1960 d'identifier la première instance de l'isomorphisme de Curry-Howard.
Logique combinatoireEn logique mathématique, la logique combinatoire est une théorie logique introduite par Moses Schönfinkel en 1920 lors d'une conférence et développée dès 1929 par Haskell Brooks Curry pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer. Plus récemment, elle a été utilisée en informatique comme modèle théorique de calcul et comme base pour la conception de langages de programmation fonctionnels.
Laws of FormLaws of Form (hereinafter LoF) is a book by G. Spencer-Brown, published in 1969, that straddles the boundary between mathematics and philosophy. LoF describes three distinct logical systems: The "primary arithmetic" (described in Chapter 4 of LoF), whose models include Boolean arithmetic; The "primary algebra" (Chapter 6 of LoF), whose models include the two-element Boolean algebra (hereinafter abbreviated 2), Boolean logic, and the classical propositional calculus; "Equations of the second degree" (Chapter 11), whose interpretations include finite automata and Alonzo Church's Restricted Recursive Arithmetic (RRA).
Functional verificationFunctional verification is the task of verifying that the logic design conforms to specification. Functional verification attempts to answer the question "Does this proposed design do what is intended?" This is complex and takes the majority of time and effort (up to 70% of design and development time) in most large electronic system design projects. Functional verification is a part of more encompassing design verification, which, besides functional verification, considers non-functional aspects like timing, layout and power.
Law of thoughtThe laws of thought are fundamental axiomatic rules upon which rational discourse itself is often considered to be based. The formulation and clarification of such rules have a long tradition in the history of philosophy and logic. Generally they are taken as laws that guide and underlie everyone's thinking, thoughts, expressions, discussions, etc. However, such classical ideas are often questioned or rejected in more recent developments, such as intuitionistic logic, dialetheism and fuzzy logic.
Ancilla bitIn reversible computing, ancilla bits are extra bits being used to implement irreversible logical operations. In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit.
Principe de bivalenceLe principe de bivalence est un principe de logique selon lequel toute proposition p ne peut avoir qu'une seule des deux valeurs de vérité. Elle est soit vraie, soit fausse. Une logique respectant le principe de bivalence est dite logique bivalente. La logique classique est bivalente. Le principe de bivalence énonce que quelque chose est soit vrai, soit faux. Quelle que soit la proposition p, p est soit vraie, soit fausse. Le principe de bivalence rend les deux valeurs de vérité que sont le vrai et le faux conjointement exhaustifs.
Proposition contraposéeEn logique, la contraposition est un type de raisonnement consistant à affirmer l'implication « si non B alors non A » à partir de l'implication « si A alors B ». L'implication « si non B alors non A » est appelée contraposée de « si A alors B ». Par exemple, la proposition contraposée de la proposition « s'il pleut, alors le sol est mouillé » est « si le sol n'est pas mouillé, alors il ne pleut pas ». Considérons l'exemple suivant :S'il pleut, alors le sol est mouillé.
Problème à promesseDans la théorie de la complexité computationnelle, un problème à promesse est une généralisation d'un problème de décision où l'entrée doit appartenir à un sous-ensemble donné de toutes les entrées possibles (la promesse ou précondition), et la sortie reste binaire. Contrairement aux problèmes de décision, les instances positives et négatives n'épuisent pas l'ensemble de toutes les entrées. Si une entrée qui ne satisfait pas la promesse est donnée à un algorithme pour résoudre un problème de promesse, l'algorithme est autorisé à produire n'importe quoi, et peut même ne pas s'arrêter.
