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

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

* Propositional calculus

Boolean functions and connectives

* Ampheck * Analysis of Boolean functions *

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 input set. This means that for a uniformly random input string of bits, the probability of getting a 1 is 1/2. E ...

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

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

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

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

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 * Exclusive or * Functional completeness *

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

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

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

* Logical equality * Logical implication * Logical negation * Logical NOR *

Lupanov representation Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a way of representing Boolean circuits so as to show that the reciprocal of the Shannon effect. Shannon had showed that almost all Boolean functions of ''n'' variables ne ...

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

* Material conditional *

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 * Sheffer stroke *

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 *

Zhegalkin polynomial Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Iva ...

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

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

* Two-element Boolean algebra

Extensions of Boolean algebras

Derivative algebra (abstract algebra) In abstract algebra, a derivative algebra is an algebraic structure of the signature : where : is a Boolean algebra and D is a unary operator, the derivative operator, satisfying the identities: # 0D = 0 # ''x' ...

* Free Boolean algebra * Monadic Boolean algebra

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,&nb ...

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

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 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 logical formulas in one of three subforms: * The entire formula is purely tru ...

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

* 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 * Formal system

Technical applications

* And-inverter graph *

Logic gate A logic gate is an idealized or physical device implementing 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 ...

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

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

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

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

* Existential graph * '' Laws of Form'' * Logical graph

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 * Venn diagram

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

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

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

* Stone space * Topological Boolean algebra {{Order theory