List of Boolean algebra topics

# List of Boolean algebra topics

Discussion
 Ask a question about 'List of Boolean algebra topics' Start a new discussion about 'List of Boolean algebra topics' Answer questions from other users Full Discussion Forum

Encyclopedia

## Articles with a wide scope and introductions

• Algebra of sets
Algebra of sets
The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion...

• Boolean algebra (structure)
• Boolean algebra (logic)
• Field of sets
• Logical connective
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...

• Propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...

## Boolean functions and connectives

• Ampheck
• Boolean algebras canonically defined
Boolean algebras canonically defined
Boolean algebra is a mathematically rich branch of abstract algebra. Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1...

• Conditioned disjunction
Conditioned disjunction
In logic, conditioned 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 disjunction is given by:[p, q, r] ~\leftrightarrow~ \and .In words, is equivalent to: "if q...

• Evasive Boolean function
Evasive Boolean function
In mathematics, an evasive Boolean function ƒ is a Boolean function for which every decision tree algorithm has running time of exactly n...

• Exclusive or
• Functional completeness
• Logical biconditional
Logical biconditional
In logic and mathematics, the logical biconditional is the logical connective of two statements asserting "p if and only if q", where q is a hypothesis and p is a conclusion...

• Logical conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

• Logical disjunction
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

• Logical equality
Logical equality
Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus...

• Logical implication
• Logical negation
• Logical NOR
Logical NOR
In boolean logic, logical nor 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 is true precisely when neither p nor q is true—i.e. when both of p and q are false...

• Lupanov representation
Lupanov representation
Lupanov'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 need a circuit of size at least 2nn−1...

• Majority function
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....

• Material conditional
Material conditional
The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...

• Minimal negation operator
• Peirce arrow
• Sheffer stroke
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...

• Sole sufficient operator
• Symmetric Boolean function
Symmetric Boolean function
In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input....

• Symmetric difference
Symmetric difference
In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by A\,\Delta\,B\,orA \ominus B....

• Zhegalkin polynomial
Zhegalkin polynomial
Zhegalkin polynomials form one of many possible representations of the operations of boolean algebra. Introduced by the Russian mathematician I.I. Zhegalkin in 1927, they are the polynomials of ordinary high school algebra interpreted over the integers mod 2...

## Examples of Boolean algebras

• Boolean domain
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...

• Interior algebra
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 ordinary propositional logic...

• Lindenbaum–Tarski algebra
Lindenbaum–Tarski algebra
In mathematical logic, the Lindenbaum–Tarski algebra of a logical theory T consists of the equivalence classes of sentences of the theory...

• Two-element Boolean algebra

## Extensions and generalizations

• Complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...

• Derivative algebra (abstract algebra)
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 # xDD ≤ x + xD...

• First-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

• Free Boolean algebra
Free Boolean algebra
In abstract algebra, a branch of mathematics, a free Boolean algebra is a Boolean algebra 〈B,F〉, such that the set B has a subset whose elements are called generators...

• Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...

In abstract algebra, a monadic Boolean algebra is an algebraic structure with signaturewhere ⟨A, ·, +, ', 0, 1⟩ is a Boolean algebra.The prefixed unary operator ∃ denotes the existential quantifier, which satisfies the identities:...

## Syntax

• Algebraic normal form
Algebraic normal form
In Boolean logic, the algebraic normal form is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving , but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers...

• Boolean conjunctive query
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 \wedge \cdots \wedge R_n, where each R_i is a relation symbol and each t_i is a tuple of variables and constants; the number of elements in t_i...

• Canonical form (Boolean algebra)
Canonical form (Boolean algebra)
In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables In...

• Conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...

• Disjunctive normal form
Disjunctive normal form
In boolean logic, a disjunctive normal form is a standardization of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is considered to be in DNF if and only if it is a disjunction of one or more...

• Formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

## Technical applications

• And-inverter graph
And-inverter graph
An and-inverter graph is a directed, acyclic graph that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labeled with variable names, and edges optionally containing...

• Logic gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...

• Boolean analysis
Boolean analysis
Boolean analysis was introduced by Flament . The goal of a Boolean analysis is to detect deterministic dependencies between the items of a questionnaire or similar data-structures in observed response patterns. These deterministic dependencies have the form of logical formulas connecting the items...

## Theorems and specific laws

• Boolean prime ideal theorem
Boolean prime ideal theorem
In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...

• Compactness theorem
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...

• Consensus theorem
Consensus theorem
In Boolean algebra, the consensus theorem is a simplification of the following terms:Proof for this theorem is: LHS = xy + x'z + yz = xy + x'z + xyz + x'yz...

• De Morgan's laws
• Duality (order theory)
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...

• Laws of classical logic
• Peirce's law
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 involves only one sort of connective, namely...

• Stone's representation theorem for Boolean algebras
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 field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...

## People

• Boole, George
George Boole
George Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...

• De Morgan, Augustus
Augustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....

• Jevons, William Stanley
William Stanley Jevons
William Stanley Jevons was a British economist and logician.Irving Fisher described his book The Theory of Political Economy as beginning the mathematical method in economics. It made the case that economics as a science concerned with quantities is necessarily mathematical...

• Peirce, Charles Sanders
• Stone, Marshall Harvey
Marshall Harvey Stone
Marshall Harvey Stone was an American mathematician who contributed to real analysis, functional analysis, and the study of Boolean algebras.-Biography:...

• Venn, John
John Venn
Donald A. Venn FRS , was a British logician and philosopher. He is famous for introducing the Venn diagram, which is used in many fields, including set theory, probability, logic, statistics, and computer science....

• Zhegalkin, Ivan Ivanovich
Ivan Ivanovich Zhegalkin
Ivan Ivanovich Zhegalkin was a Russian mathematician...

## Philosophy

• Boole's syllogistic
Boole's syllogistic
Boolean logic is a system of syllogistic logic invented by 19th-century British mathematician George Boole, which attempts to incorporate the "empty set", that is, a class of non-existent entities, such as round squares, without resorting to uncertain truth values.In Boolean logic, the universal...

• Boolean implicant
Implicant
In Boolean logic, an implicant is a "covering" of one or more minterms in a sum of products of a boolean function. Formally, a product term P in a sum of products is an implicant of the Boolean function F if P implies F...

• Entitative graph
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 1880's, taking the coverage of the formalism only as far as the propositional or sentential aspects of logic are concerned...

• Existential graph
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, and continued to develop the method until his death in 1914.-The graphs:...

• Laws of Form
Laws of Form
Laws of Form is a book by G. Spencer-Brown, published in 1969, that straddles the boundary between mathematics and philosophy...

• Logical graph
Logical graph
A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....

## Visualization

• Truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

• Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...

• Venn diagram
Venn diagram
Venn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...

## Unclassified

• Boolean function
• Boolean-valued function
Boolean-valued function
A boolean-valued function, in some usages is 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....

• Boolean-valued model
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 values in some fixed complete Boolean...

• Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...

• 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
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.In classical logic, with its intended semantics, the truth values are true and false; that is, classical logic is a two-valued logic...

• Stone duality
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 form a natural generalization of Stone's representation...

• Stone space
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 field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...

• Topological Boolean algebra (disambiguation)
Topological Boolean algebra
* In abstract algebra and mathematical logic, topological Boolean algebra is one of the many names that have been used for an interior algebra in the literature....