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

Articles with a wide scope and introductions

Algebra of sets In mathematics, the algebra of sets, not to be confused with the mathematical structure of ''an'' algebra of sets, defines the properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the re ...

Boolean algebra (structure) In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a gen ...

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 variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

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 under t ...

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

Propositional calculus The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...

Boolean functions and connectives

Ampheck In Boolean logic, logical NOR, non-disjunction, or joint denial is a truth-functional operator which produces a result that is the negation of logical disjunction, logical or. That is, a sentence of the form (''p'' NOR ''q'') is true precis ...

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 In mathematics and computer science, a balanced Boolean function is a Boolean function whose output yields as many 0s as 1s over its Domain of a function, input set. This means that for a uniformly random input string of bits, the probability of get ...

* Bent function *

Boolean algebras canonically defined :''Boolean algebras are models of the equational theory of two values; this definition is equivalent to the lattice and ring definitions.'' Boolean algebra is a mathematically rich branch of abstract algebra. ''Stanford Encyclopaedia of Philosoph ...

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 functi ...

* Boolean matrix *

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 ar ...

* Conditioned disjunction * Evasive Boolean function *

Exclusive or Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...

Functional completeness In Mathematical logic, logic, a functionally complete set of logical connectives or Boolean function, Boolean operators is one that can be used to express all possible truth tables by combining members of the Set (mathematics), set into a Boolean ...

Logical biconditional In logic and mathematics, the logical biconditional, also known as material biconditional or equivalence or bidirectional implication or biimplication or bientailment, is the logical connective used to conjoin two statements P and Q to form th ...

Logical conjunction In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or ...

Logical disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...

Logical equality Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure of arg ...

Logical implication Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure of ...

Logical negation In logic, negation, also called the logical not or logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \overline. It is interpreted intuitively as being true ...

Logical NOR In Boolean logic, logical NOR, non-disjunction, or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form (''p'' NOR ''q'') is true precisely when neither ''p' ...

* Lupanov representation *

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 a binary operation commonly used in logic. When the conditional symbol \to is interpreted as material implication, a formula P \to Q is true unless P is true and Q is false. M ...

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, an axiom with six NAND operations and thre ...

* Peirce arrow * Read-once function *

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 non-conjunction, ...

* Sole sufficient operator * Symmetric Boolean function *

Symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, 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 ...

* 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 ...

* Complete Boolean algebra * Interior algebra *

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 (structure), 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 generat ...

* Monadic Boolean algebra

Generalizations of Boolean algebras

* De Morgan algebra *

First-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...

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'' call ...

* Lindenbaum–Tarski algebra * Skew Boolean algebra

Syntax

Algebraic normal form In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing propositional logic formulas in one of three subforms: * The entire formul ...

Boolean conjunctive query In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form R_1(t_1) \wedge \cdots \wedge R_n(t_n), where each R_i is a relation symbol and each t_i is a tup ...

Canonical form (Boolean algebra) In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF), minterm canonical form, or Sum of Products (SoP or SOP) as a disjunction (OR) of minterms. The De Morgan dual is the canonical conjuncti ...

Conjunctive normal form In Boolean algebra, 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. In au ...

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 and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms. In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in ma ...

Technical applications

* And-inverter graph *

Logic gate A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for ...

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 Ideal (order theory), ideals in a Boolean algebra (structure), Boolean algebra can be extended to Ideal (order theory)#Prime ideals , prime ideals. A variation of this statement for Filte ...

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 generall ...

Consensus theorem In 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 variable (mathematics), variables are the truth values ''true'' and ...

De Morgan's laws In propositional calculus, 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 Validity (logic), valid rule of inference, rules of inference. They are nam ...

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 ...

* 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#Mathematics, axiom in his first axiomatisation of propositional logic. It can be thought of as the law of excluded middle written ...

Stone's representation theorem for Boolean algebras In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first ha ...

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 existential graph is a type of diagrammatic or visual notation for logical expressions, created by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914. They include ...

Existential graph An existential graph is a type of diagrammatic or visual notation for logical expressions, created by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914. They include ...

* ''

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 Ch ...

'' *

Logical graph An existential graph is a type of diagrammatic or visual notation for logical expressions, created by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914. They include ...

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 arg ...

Karnaugh map A Karnaugh map (KM or K-map) is a diagram that can be used to simplify a Boolean algebra expression. Maurice Karnaugh introduced the technique in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of ...

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

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) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

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 calc ...

Indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , then the indicator functio ...

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

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. It is an important tool in ...

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''). Truth values are used in c ...

Stone duality In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they ...

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

* Topological Boolean algebra {{Order theory