In mathematics and mathematical logic,
Contents 1 History 2 Values 3 Operations 3.1 Basic operations 3.2 Secondary operations 4 Laws 4.1 Monotone laws 4.2 Nonmonotone laws 4.3 Completeness 4.4 Duality principle 5 Diagrammatic representations 5.1 Venn diagrams
5.2
6 Boolean algebras 6.1 Concrete Boolean algebras 6.2 Subsets as bit vectors 6.3 The prototypical Boolean algebra 6.4 Boolean algebras: the definition 6.5 Representable Boolean algebras 7 Axiomatizing Boolean algebra 8 Propositional logic 8.1 Applications 8.2 Deductive systems for propositional logic 8.2.1
9 Applications 9.1 Computers 9.2 Two-valued logic 9.3 Boolean operations 9.3.1 Boolean searches 10 See also 11 References 11.1 General 12 Further reading 13 External links History[edit]
Boole's algebra predated the modern developments in abstract algebra
and mathematical logic; it is however seen as connected to the origins
of both fields.[5] In an abstract setting,
AND (conjunction), denoted x∧y (sometimes x AND y or Kxy), satisfies x∧y = 1 if x = y = 1 and x∧y = 0 otherwise. OR (disjunction), denoted x∨y (sometimes x OR y or Axy), satisfies x∨y = 0 if x = y = 0 and x∨y = 1 otherwise. NOT (negation), denoted ¬x (sometimes NOT x, Nx or !x), satisfies ¬x = 0 if x = 1 and ¬x = 1 if x = 0. Alternatively the values of x∧y, x∨y, and ¬x can be expressed by tabulating their values with truth tables as follows. x displaystyle x y displaystyle y x ∧ y displaystyle xwedge y x ∨ y displaystyle xvee y 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 x displaystyle x ¬ x displaystyle neg x 0 1 1 0 If the truth values 0 and 1 are interpreted as integers, these operations may be expressed with the ordinary operations of arithmetic, or by the minimum/maximum functions: x ∧ y = x y = min ( x , y ) x ∨ y = x + y − x y = max ( x , y ) ¬ x = 1 − x displaystyle begin aligned xwedge y&=xy=min(x,y)\xvee y&=x+y-xy=max(x,y)\neg x&=1-xend aligned One may consider that only the negation and one of the two other operations are basic, because of the following identities that allow to define the conjunction in terms of the negation and the disjunction, and vice versa: x ∧ y = ¬ ( ¬ x ∨ ¬ y ) x ∨ y = ¬ ( ¬ x ∧ ¬ y ) displaystyle begin aligned xwedge y&=neg (neg xvee neg y)\xvee y&=neg (neg xwedge neg y)end aligned Secondary operations[edit] The three Boolean operations described above are referred to as basic, meaning that they can be taken as a basis for other Boolean operations that can be built up from them by composition, the manner in which operations are combined or compounded. Operations composed from the basic operations include the following examples: x → y = ¬ x ∨ y displaystyle xrightarrow y=neg x vee y x ⊕ y = ( x ∨ y ) ∧ ¬ ( x ∧ y ) displaystyle xoplus y=(xvee y)wedge neg (xwedge y) x ≡ y = ¬ ( x ⊕ y ) displaystyle xequiv y=neg (xoplus y) These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs. x displaystyle x y displaystyle y x → y displaystyle xrightarrow y x ⊕ y displaystyle xoplus y x ≡ y displaystyle xequiv y 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 The first operation, x → y, or Cxy, is called material
implication. If x is true then the value of x → y is taken
to be that of y. But if x is false then the value of y can be ignored;
however the operation must return some boolean value and there are
only two choices. So by definition, x → y is true when x
is false. (
Associativity of ∨ displaystyle vee : x ∨ ( y ∨ z ) displaystyle xvee (yvee z) = ( x ∨ y ) ∨ z displaystyle =(xvee y)vee z Associativity of ∧ displaystyle wedge : x ∧ ( y ∧ z ) displaystyle xwedge (ywedge z) = ( x ∧ y ) ∧ z displaystyle =(xwedge y)wedge z Commutativity of ∨ displaystyle vee : x ∨ y displaystyle xvee y = y ∨ x displaystyle =yvee x Commutativity of ∧ displaystyle wedge : x ∧ y displaystyle xwedge y = y ∧ x displaystyle =ywedge x Distributivity of ∧ displaystyle wedge over ∨ displaystyle vee : x ∧ ( y ∨ z ) displaystyle xwedge (yvee z) = ( x ∧ y ) ∨ ( x ∧ z ) displaystyle =(xwedge y)vee (xwedge z) Identity for ∨ displaystyle vee : x ∨ 0 displaystyle xvee 0 = x displaystyle =x Identity for ∧ displaystyle wedge : x ∧ 1 displaystyle xwedge 1 = x displaystyle =x Annihilator for ∧ displaystyle wedge : x ∧ 0 displaystyle xwedge 0 = 0 displaystyle =0 The following laws hold in Boolean Algebra, but not in ordinary algebra: Annihilator for ∨ displaystyle vee : x ∨ 1 displaystyle xvee 1 = 1 displaystyle =1 ∨ displaystyle vee : x ∨ x displaystyle xvee x = x displaystyle =x ∧ displaystyle wedge : x ∧ x displaystyle xwedge x = x displaystyle =x Absorption 1: x ∧ ( x ∨ y ) displaystyle xwedge (xvee y) = x displaystyle =x Absorption 2: x ∨ ( x ∧ y ) displaystyle xvee (xwedge y) = x displaystyle =x Distributivity of ∨ displaystyle vee over ∧ displaystyle wedge : x ∨ ( y ∧ z ) displaystyle xvee (ywedge z) = ( x ∨ y ) ∧ ( x ∨ z ) displaystyle =(xvee y)wedge (xvee z) Taking x = 2 in the third law above shows that it is not an ordinary algebra law, since 2×2 = 4. The remaining five laws can be falsified in ordinary algebra by taking all variables to be 1, for example in Absorption Law 1 the left hand side would be 1(1+1) = 2 while the right hand side would be 1, and so on. All of the laws treated so far have been for conjunction and disjunction. These operations have the property that changing either argument either leaves the output unchanged or the output changes in the same way as the input. Equivalently, changing any variable from 0 to 1 never results in the output changing from 1 to 0. Operations with this property are said to be monotone. Thus the axioms so far have all been for monotonic Boolean logic. Nonmonotonicity enters via complement ¬ as follows.[4] Nonmonotone laws[edit] The complement operation is defined by the following two laws. Complementation 1 x ∧ ¬ x = 0 Complementation 2 x ∨ ¬ x = 1 displaystyle begin aligned & text Complementation 1 &xwedge neg x&=0\& text Complementation 2 &xvee neg x&=1end aligned All properties of negation including the laws below follow from the above two laws alone.[4] In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, whence in both algebras it satisfies the double negation law (also called involution law) Double negation ¬ ( ¬ x ) = x displaystyle begin aligned & text Double negation &neg (neg x ) &=xend aligned But whereas ordinary algebra satisfies the two laws ( − x ) ( − y ) = x y ( − x ) + ( − y ) = − ( x + y ) displaystyle begin aligned (-x)(-y)&=xy\(-x)+(-y)&=-(x+y)end aligned
De Morgan 1 ¬ x ∧ ¬ y = ¬ ( x ∨ y ) De Morgan 2 ¬ x ∨ ¬ y = ¬ ( x ∧ y ) displaystyle begin aligned & text De Morgan 1 &neg xwedge neg y&=neg (xvee y) \& text De Morgan 2 &neg xvee neg y&=neg (xwedge y) end aligned Completeness[edit]
The laws listed above define Boolean algebra, in the sense that they
entail the rest of the subject. The laws Complementation 1 and 2,
together with the monotone laws, suffice for this purpose and can
therefore be taken as one possible complete set of laws or
axiomatization of Boolean algebra. Every law of Boolean algebra
follows logically from these axioms. Furthermore, Boolean algebras can
then be defined as the models of these axioms as treated in the
section thereon.
To clarify, writing down further laws of
Figure 2. Venn diagrams for conjunction, disjunction, and complement For conjunction, the region inside both circles is shaded to indicate
that x∧y is 1 when both variables are 1. The other regions are left
unshaded to indicate that x∧y is 0 for the other three combinations.
The second diagram represents disjunction x∨y by shading those
regions that lie inside either or both circles. The third diagram
represents complement ¬x by shading the region not inside the circle.
While we have not shown the Venn diagrams for the constants 0 and 1,
they are trivial, being respectively a white box and a dark box,
neither one containing a circle. However we could put a circle for x
in those boxes, in which case each would denote a function of one
argument, x, which returns the same value independently of x, called a
constant function. As far as their outputs are concerned, constants
and constant functions are indistinguishable; the difference is that a
constant takes no arguments, called a zeroary or nullary operation,
while a constant function takes one argument, which it ignores, and is
a unary operation.
Venn diagrams are helpful in visualizing laws. The commutativity laws
for ∧ and ∨ can be seen from the symmetry of the diagrams: a
binary operation that was not commutative would not have a symmetric
diagram because interchanging x and y would have the effect of
reflecting the diagram horizontally and any failure of commutativity
would then appear as a failure of symmetry.
The lines on the left of each gate represent input wires or ports. The value of the input is represented by a voltage on the lead. For so-called "active-high" logic, 0 is represented by a voltage close to zero or "ground", while 1 is represented by a voltage close to the supply voltage; active-low reverses this. The line on the right of each gate represents the output port, which normally follows the same voltage conventions as the input ports. Complement is implemented with an inverter gate. The triangle denotes the operation that simply copies the input to the output; the small circle on the output denotes the actual inversion complementing the input. The convention of putting such a circle on any port means that the signal passing through this port is complemented on the way through, whether it is an input or output port. The Duality Principle, or De Morgan's laws, can be understood as asserting that complementing all three ports of an AND gate converts it to an OR gate and vice versa, as shown in Figure 4 below. Complementing both ports of an inverter however leaves the operation unchanged. More generally one may complement any of the eight subsets of the
three ports of either an AND or OR gate. The resulting sixteen
possibilities give rise to only eight Boolean operations, namely those
with an odd number of 1's in their truth table. There are eight such
because the "odd-bit-out" can be either 0 or 1 and can go in any of
four positions in the truth table. There being sixteen binary Boolean
operations, this must leave eight operations with an even number of
1's in their truth tables. Two of these are the constants 0 and 1 (as
binary operations that ignore both their inputs); four are the
operations that depend nontrivially on exactly one of their two
inputs, namely x, y, ¬x, and ¬y; and the remaining two are x⊕y
(XOR) and its complement x≡y.
Boolean algebras[edit]
Main article:
The laws satisfied by all nondegenerate concrete Boolean algebras coincide with those satisfied by the prototypical Boolean algebra. This observation is easily proved as follows. Certainly any law
satisfied by all concrete Boolean algebras is satisfied by the
prototypical one since it is concrete. Conversely any law that fails
for some concrete
A
For the purposes of this definition it is irrelevant how the
operations came to satisfy the laws, whether by fiat or proof. All
concrete Boolean algebras satisfy the laws (by proof rather than
fiat), whence every concrete
A
The section on axiomatization lists other axiomatizations, any of
which can be made the basis of an equivalent definition.
Representable Boolean algebras[edit]
Although every concrete
A
The obvious next question is answered positively as follows. Every
That is, up to isomorphism, abstract and concrete Boolean algebras are the same thing. This quite nontrivial result depends on the Boolean prime ideal theorem, a choice principle slightly weaker than the axiom of choice, and is treated in more detail in the article Stone's representation theorem for Boolean algebras. This strong relationship implies a weaker result strengthening the observation in the previous subsection to the following easy consequence of representability. The laws satisfied by all Boolean algebras coincide with those satisfied by the prototypical Boolean algebra. It is weaker in the sense that it does not of itself imply
representability. Boolean algebras are special here, for example a
relation algebra is a
⊢ displaystyle vdash A, B→C,…. The two halves of a sequent are called the antecedent and the succedent respectively. The customary metavariable denoting an antecedent or part thereof is Γ, and for a succedent Δ; thus Γ,A ⊢ displaystyle vdash Δ would denote a sequent whose succedent is a list Δ and whose
antecedent is a list Γ with an additional proposition A appended
after it. The antecedent is interpreted as the conjunction of its
propositions, the succedent as the disjunction of its propositions,
and the sequent itself as the entailment of the succedent by the
antecedent.
⊢ displaystyle vdash is as ≤ in the partial order of the
⊢ displaystyle vdash and internal implication → in the one logic is among the essential
differences between sequent calculus and propositional calculus.[20]
Applications[edit]
x y displaystyle xy ), and disjunction (OR) is defined via De Morgan's law. Interpreting
these values as logical truth values yields a multi-valued logic,
which forms the basis for fuzzy logic and probabilistic logic. In
these interpretations, a value is interpreted as the "degree" of truth
– to what extent a proposition is true, or the probability that the
proposition is true.
Boolean operations[edit]
The original application for Boolean operations was mathematical
logic, where it combines the truth values, true or false, of
individual formulas.
Natural languages such as English have words for several Boolean
operations, in particular conjunction (and), disjunction (or),
negation (not), and implication (implies). But not is synonymous with
and not. When used to combine situational assertions such as "the
block is on the table" and "cats drink milk," which naively are either
true or false, the meanings of these logical connectives often have
the meaning of their logical counterparts. However, with descriptions
of behavior such as "Jim walked through the door", one starts to
notice differences such as failure of commutativity, for example the
conjunction of "Jim opened the door" with "Jim walked through the
door" in that order is not equivalent to their conjunction in the
other order, since and usually means and then in such cases. Questions
can be similar: the order "Is the sky blue, and why is the sky blue?"
makes more sense than the reverse order. Conjunctive commands about
behavior are like behavioral assertions, as in get dressed and go to
school. Disjunctive commands such love me or leave me or fish or cut
bait tend to be asymmetric via the implication that one alternative is
less preferable. Conjoined nouns such as tea and milk generally
describe aggregation as with set union while tea or milk is a choice.
However context can reverse these senses, as in your choices are
coffee and tea which usually means the same as your choices are coffee
or tea (alternatives). Double negation as in "I don't not like milk"
rarely means literally "I do like milk" but rather conveys some sort
of hedging, as though to imply that there is a third possibility. "Not
not P" can be loosely interpreted as "surely P", and although P
necessarily implies "not not P" the converse is suspect in English,
much as with intuitionistic logic. In view of the highly idiosyncratic
usage of conjunctions in natural languages,
Doublequotes are used to combine whitespace-separated words into a single search term.[22] Whitespace is used to specify logical AND, as it is the default operator for joining search terms: "Search term 1" "Search term 2" The OR keyword is used for logical OR: "Search term 1" OR "Search term 2" A prefixed minus sign is used for logical NOT: "Search term 1" −"Search term 2" See also[edit]
Binary number
References[edit] ^ Boole, George (2003) [1854]. An Investigation of the Laws of
Thought. Prometheus Books. ISBN 978-1-59102-089-9.
^ "The name
General[edit] Mano, Morris; Ciletti, Michael D. (2013). Digital Design. Pearson. ISBN 978-0-13-277420-8. Further reading[edit] J. Eldon Whitesitt (1995).
Historical perspective
External links[edit] The Wikibook How To Search has a page on the topic of: Boolean Logic The Wikibook Electronics has a page on the topic of: Boolean Algebra Boolean
v t e Digital electronics Components Combinational logic
Theory Digital signal (electronics)
Boolean algebra
Logic synthesis
Logic in computer science
Design Logic synthesis Register-transfer level Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Applications
radio Digital photography Digital telephone Digital video cinema television Electronic literature Design issues Metastability Runt pulse v t e Major fields of computer science Note: This template roughly follows the 2012 ACM Computing Classification System. Hardware Printed circuit board Peripheral Integrated circuit Very-large-scale integration Energy consumption Electronic design automation
Networks Network architecture
Network protocol
Network components
Network scheduler
Software organization Interpreter Middleware Virtual machine Operating system Software quality Software notations and tools Programming paradigm Programming language Compiler Domain-specific language Modeling language Software framework Integrated development environment Software configuration management Software library Software repository Software development
Theory of computation Model of computation Formal language Automata theory Computational complexity theory Logic Semantics Algorithms
Mathematics of computing Discrete mathematics Probability Statistics Mathematical software Information theory Mathematical analysis Numerical analysis Information systems Database management system
Information storage systems
Enterprise information system
Social information systems
Geographic information system
Decision support system
Security Cryptography Formal methods Security services Intrusion detection system Hardware security Network security Information security Application security Human–computer interaction Interaction design Social computing Ubiquitous computing Visualization Accessibility Concurrency Concurrent computing Parallel computing Distributed computing Multithreading Multiprocessing Artificial intelligence Natural language processing
Knowledge representation and reasoning
Machine learning Supervised learning Unsupervised learning Reinforcement learning Multi-task learning Cross-validation Graphics Animation Rendering Image manipulation Graphics processing unit Mixed reality Virtual reality Image compression Solid modeling Applied computing E-commerce Enterprise software Computational mathematics Computational physics Computational chemistry Computational biology Computational social science Computational engineering Computational healthcare Digital art Electronic publishing Cyberwarfare Electronic voting Video game Word processing Operations research Educational technology Document management Book Category Portal WikiProject Commons v t e Areas of mathematics outline topic lists Branches Arithmetic History of mathematics
Philosophy of mathematics
Algebra
Calculus Analysis Differential equations / Dynamical systems Numerical analysis Optimization Functional analysis Geometry Discrete Algebraic Analytic Differential Finite Topology Trigonometry Applied Probability
Mathematical physics
Mathematical statistics
Statistics
Divisions Pure Applied Discrete Computational Category Portal Commons WikiProject v t e Mathematical logic General Formal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax Theory Systems Formal system
Deductive system
Axiomatic system
Hilbert style systems
Natural deduction
Traditional logic Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram Propositional calculus Boolean logic Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logic Predicate logic First-order Quantifiers Predicate Second-order Monadic predicate calculus Naive set theory Set
Empty set
Element
Enumeration
Extensionality
Finite set
Infinite set
Subset
Power set
Countable set
Set theory Foundations of mathematics
Zermelo–Fraenkel set theory
Model theory Model Interpretation Non-standard model Finite model theory Truth value Validity Proof theory Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax Computability theory Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function Authority control GND: 41462 |