This is a list of topics around Boolean algebra and propositional logic.

Articles with a wide scope and introductions

* Algebra of sets * Boolean algebra (structure) *

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...

Field of sets In mathematics, a field of sets is a mathematical structure consisting of a pair ( X, \mathcal ) consisting of a set X and a family \mathcal of subsets of X called an algebra over X that contains the empty set as an element, and is closed un ...

Logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

Propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...

Boolean functions and connectives

* Ampheck *

Analysis of Boolean functions In mathematics and theoretical computer science, analysis of Boolean functions is the study of real-valued functions on \^n or \^n (such functions are sometimes known as pseudo-Boolean functions) from a spectral perspective. The functions studied a ...

* Balanced boolean function *

Bent function In the mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance bet ...

* Boolean algebras canonically defined *

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...

Boolean matrix In mathematics, a Boolean matrix is a matrix with entries from a Boolean algebra. When the two-element Boolean algebra is used, the Boolean matrix is called a logical matrix. (In some contexts, particularly computer science, the term "Boolean matri ...

Boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are i ...

Conditioned disjunction In logic, conditioned disjunction (sometimes called conditional disjunction) is a ternary logical connective introduced by Church. Given operands ''p'', ''q'', and ''r'', which represent truth-valued propositions, the meaning of the conditioned d ...

Evasive Boolean function In mathematics, an evasive Boolean function ''ƒ'' (of ''n'' variables) is a Boolean function for which every decision tree algorithm has running time of exactly ''n''. Consequently, every decision tree algorithm that represents the fun ...

Exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...

Functional completeness In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. ( ...

Logical biconditional In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective (\leftrightarrow) used to conjoin two statements and to form the statement " if and only if ", where is known as th ...

Logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...

Logical disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...

Logical equality Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It gives the functional value ''true'' if both functional arguments have the same logical valu ...

Logical implication Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is one ...

* Logical negation * Logical NOR *

Lupanov representation Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a way of representing Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital ...

Majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...

Material conditional The material conditional (also known as material implication) is an operation commonly used in logic. When the conditional symbol \rightarrow is interpreted as material implication, a formula P \rightarrow Q is true unless P is true and Q i ...

Minimal axioms for Boolean algebra In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, if one chooses to take commutativity for gra ...

* Peirce arrow *

Read-once function In mathematics, a read-once function is a special type of Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching functio ...

Sheffer stroke In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called nand ("not and") ...

Sole sufficient operator In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. ( ...

* Symmetric Boolean function *

Symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...

* Zhegalkin polynomial

Examples of Boolean algebras

Boolean domain In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...

Complete Boolean algebra In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...

Interior algebra In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and or ...

Two-element Boolean algebra In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose ''underlying set'' (or universe or ''carrier'') ''B'' is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that ''B ...

Extensions of Boolean algebras

* Derivative algebra (abstract algebra) *

Free Boolean algebra In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called ''generators'', such that: #Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean opera ...

Monadic Boolean algebra In abstract algebra, a monadic Boolean algebra is an algebraic structure ''A'' with signature :⟨·, +, ', 0, 1, ∃⟩ of type ⟨2,2,1,0,0,1⟩, where ⟨''A'', ·, +, ', 0, 1⟩ is a Boolean algebra. The monadic/unary ...

Generalizations of Boolean algebras

De Morgan algebra __NOTOC__ In mathematics, a De Morgan algebra (named after Augustus De Morgan, a British mathematician and logician) is a structure ''A'' = (A, ∨, ∧, 0, 1, ¬) such that: * (''A'', ∨, ∧, 0,&nbs ...

First-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...

* Lindenbaum–Tarski algebra * Skew Boolean algebra

Syntax

* Algebraic normal form * Boolean conjunctive query * Canonical form (Boolean algebra) *

Conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a cano ...

Disjunctive normal form In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...

Formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...

Technical applications

And-inverter graph An and-inverter graph (AIG) is a directed, acyclic Graph (discrete mathematics), graph that represents a structural implementation of the logical functionality of a digital circuit, circuit or network. An AIG consists of two-input nodes represent ...

* Logic gate *

Boolean analysis Boolean analysis was introduced by Flament (1976).Flament, C. (1976). "L'analyse booleenne de questionnaire", Paris: Mouton. The goal of a Boolean analysis is to detect deterministic dependencies between the items of a questionnaire or similar data ...

Theorems and specific laws

Boolean prime ideal theorem In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by consi ...

Compactness theorem In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generally ...

Consensus theorem In Boolean algebra, the consensus theorem or rule of consensus is the identity: :xy \vee \barz \vee yz = xy \vee \barz The consensus or resolvent of the terms xy and \barz is yz. It is the conjunction of all the unique literals of the terms, ...

De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British math ...

Duality (order theory) In the mathematical area of order theory, every partially ordered set ''P'' gives rise to a dual (or opposite) partially ordered set which is often denoted by ''P''op or ''P'd''. This dual order ''P''op is defined to be the same set, but with th ...

* Laws of classical logic *

Peirce's law In logic, Peirce's law is named after the philosopher and logician Charles Sanders Peirce. It was taken as an axiom in his first axiomatisation of propositional logic. It can be thought of as the law of excluded middle written in a form that i ...

* Stone's representation theorem for Boolean algebras

People

* Boole, George * De Morgan, Augustus * Jevons, William Stanley * Peirce, Charles Sanders * Stone, Marshall Harvey * Venn, John * Zhegalkin, Ivan Ivanovich

Philosophy

* Boole's syllogistic * Boolean implicant *

Entitative graph An entitative graph is an element of the diagrammatic syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic beginning in the 1880s, taking the coverage of the formalism only as far as the propositional or ...

Existential graph An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on graphical logic as early as 1882,Peirce, C. S., " n Junctures and Fractures in Logic (editors' title for ...

* ''

Laws of Form ''Laws 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 C ...

'' *

Logical graph A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. In his papers on '' qualitative logic'', '' entitative graphs'', and '' existential grap ...

Visualization

Truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...

Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...

Venn diagram A Venn diagram is a widely used diagram style that shows the logical relation between sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple set relationships ...

Unclassified

Boolean-valued model In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take v ...

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

Boolean differential calculus Boolean differential calculus (BDC) (German: (BDK)) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions. Boolean differential calculus concepts are analogous to those of classical differential cal ...

* Indicator function (also called the ''characteristic function'', but that term is used in probability theory for a different concept) *

Espresso heuristic logic minimizer The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. ...

Logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. Matrix representation ...

Logical value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progra ...

* Stone duality *

Stone space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...

* Topological Boolean algebra {{Order theory