109-530: A Karnaugh map ( KM or K-map ) is a diagram that can be used to simplify a Boolean algebra expression. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch 's 1952 Veitch chart , which itself was a rediscovery of Allan Marquand 's 1881 logical diagram (aka. Marquand diagram ). It is also useful for understanding logic circuits. Karnaugh maps are also known as Marquand–Veitch diagrams , Svoboda charts -(albeit only rarely)- and Karnaugh–Veitch maps ( KV maps ). A Karnaugh map reduces
218-451: A Boolean circuit relates time complexity (of an algorithm ) to circuit complexity . Whereas expressions denote mainly numbers in elementary algebra, in Boolean algebra, they denote the truth values false and true . These values are represented with the bits , 0 and 1. They do not behave like the integers 0 and 1, for which 1 + 1 = 2 , but may be identified with the elements of
327-580: A Riemannian manifold , as well as the structure of an abelian Lie group. Perhaps the simplest example of this is when L = Z 2 {\displaystyle \mathbb {Z} ^{2}} : R 2 / Z 2 {\displaystyle \mathbb {R} ^{2}/\mathbb {Z} ^{2}} , which can also be described as the Cartesian plane under the identifications ( x , y ) ~ ( x + 1, y ) ~ ( x , y + 1) . This particular flat torus (and any uniformly scaled version of it)
436-449: A closed path that circles the torus' "hole" (say, a circle that traces out a particular latitude) and then circles the torus' "body" (say, a circle that traces out a particular longitude) can be deformed to a path that circles the body and then the hole. So, strictly 'latitudinal' and strictly 'longitudinal' paths commute. An equivalent statement may be imagined as two shoelaces passing through each other, then unwinding, then rewinding. If
545-418: A donut or doughnut . If the axis of revolution does not touch the circle, the surface has a ring shape and is called a torus of revolution , also known as a ring torus . If the axis of revolution is tangent to the circle, the surface is a horn torus . If the axis of revolution passes twice through the circle, the surface is a spindle torus (or self-crossing torus or self-intersecting torus ). If
654-510: A fiber bundle over S (the Hopf bundle ). The surface described above, given the relative topology from R 3 {\displaystyle \mathbb {R} ^{3}} , is homeomorphic to a topological torus as long as it does not intersect its own axis. A particular homeomorphism is given by stereographically projecting the topological torus into R 3 {\displaystyle \mathbb {R} ^{3}} from
763-482: A group under function composition , isomorphic to the Klein four-group , acting on the set of Boolean polynomials. Walter Gottschalk remarked that consequently a more appropriate name for the phenomenon would be the principle (or square ) of quaternality . A Venn diagram can be used as a representation of a Boolean operation using shaded overlapping regions. There is one region for each variable, all circular in
872-593: A maximal torus ; that is, a closed subgroup which is a torus of the largest possible dimension. Such maximal tori T have a controlling role to play in theory of connected G . Toroidal groups are examples of protori , which (like tori) are compact connected abelian groups, which are not required to be manifolds . Automorphisms of T are easily constructed from automorphisms of the lattice Z n {\displaystyle \mathbb {Z} ^{n}} , which are classified by invertible integral matrices of size n with an integral inverse; these are just
981-752: A product of a Euclidean open disk and a circle. The volume of this solid torus and the surface area of its torus are easily computed using Pappus's centroid theorem , giving: A = ( 2 π r ) ( 2 π R ) = 4 π 2 R r , V = ( π r 2 ) ( 2 π R ) = 2 π 2 R r 2 . {\displaystyle {\begin{aligned}A&=\left(2\pi r\right)\left(2\pi R\right)=4\pi ^{2}Rr,\\[5mu]V&=\left(\pi r^{2}\right)\left(2\pi R\right)=2\pi ^{2}Rr^{2}.\end{aligned}}} These formulas are
1090-589: A product-of-sums expression (POS) leads to OR gates feeding an AND gate. The POS expression gives a complement of the function (if F is the function so its complement will be F'). Karnaugh maps can also be used to simplify logic expressions in software design. Boolean conditions, as used for example in conditional statements , can get very complicated, which makes the code difficult to read and to maintain. Once minimised, canonical sum-of-products and product-of-sums expressions can be implemented directly using AND and OR logic operators. Karnaugh maps are used to facilitate
1199-521: A 1/3 twist (120°): the 3-dimensional interior corresponds to the points on the 3-torus where all 3 coordinates are distinct, the 2-dimensional face corresponds to points with 2 coordinates equal and the 3rd different, while the 1-dimensional edge corresponds to points with all 3 coordinates identical. These orbifolds have found significant applications to music theory in the work of Dmitri Tymoczko and collaborators (Felipe Posada, Michael Kolinas, et al.), being used to model musical triads . A flat torus
SECTION 10
#17330861443521308-455: A Boolean law directly as any tautology , understood as an equation that holds for all values of its variables over 0 and 1. All these definitions of Boolean algebra can be shown to be equivalent. Principle: If {X, R} is a partially ordered set , then {X, R(inverse)} is also a partially ordered set. There is nothing special about the choice of symbols for the values of Boolean algebra. 0 and 1 could be renamed to α and β , and as long as it
1417-492: A flat torus into 3-dimensional Euclidean space R 3 {\displaystyle \mathbb {R} ^{3}} was found. It is a flat torus in the sense that, as a metric space, it is isometric to a flat square torus. It is similar in structure to a fractal as it is constructed by repeatedly corrugating an ordinary torus at smaller scales. Like fractals, it has no defined Gaussian curvature. However, unlike fractals, it does have defined surface normals , yielding
1526-444: A function of ∑ m ( ) {\textstyle \sum m()} and the race hazard free ( see previous section ) minimum equation. A minterm is defined as an expression that gives the most minimal form of expression of the mapped variables. All possible horizontal and vertical interconnected blocks can be formed. These blocks must be of the size of the powers of 2 (1, 2, 4, 8, 16, 32, ...). These expressions create
1635-414: A minimal logical mapping of the minimal logic variable expressions for the binary expressions to be mapped. Here are all the blocks with one field. A block can be continued across the bottom, top, left, or right of the chart. That can even wrap beyond the edge of the chart for variable minimization. This is because each logic variable corresponds to each vertical column and horizontal row. A visualization of
1744-429: A rectangle together, choosing the other two sides instead will cause the same reversal of orientation. The first homology group of the torus is isomorphic to the fundamental group (this follows from Hurewicz theorem since the fundamental group is abelian ). The 2-torus is a twofold branched cover of the 2-sphere, with four ramification points . Every conformal structure on the 2-torus can be represented as such
1853-406: A regular torus. For example, in the following map: If R and P in the above flat torus parametrization form a unit vector ( R , P ) = (cos( η ), sin( η )) then u , v , and 0 < η < π /2 parameterize the unit 3-sphere as Hopf coordinates . In particular, for certain very specific choices of a square flat torus in the 3-sphere S , where η = π /4 above, the torus will partition
1962-454: A so-called "smooth fractal". The key to obtaining the smoothness of this corrugated torus is to have the amplitudes of successive corrugations decreasing faster than their "wavelengths". (These infinitely recursive corrugations are used only for embedding into three dimensions; they are not an intrinsic feature of the flat torus.) This is the first time that any such embedding was defined by explicit equations or depicted by computer graphics. In
2071-609: A special definition explained above – we're in fact moving on a torus, rather than a rectangle, wrapping around the top, bottom, and the sides. Whether glitches will actually occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application. In clocked logic, it is enough that the logic settles on the desired value in time to meet the timing deadline. In our example, we are not considering clocked logic. In our case, an additional term of A D ¯ {\displaystyle A{\overline {D}}} would eliminate
2180-544: A sphere — by adding one additional point that represents the limiting case as a rectangular torus approaches an aspect ratio of 0 in the limit. The result is that this compactified moduli space is a sphere with three points each having less than 2π total angle around them. (Such a point is termed a "cusp", and may be thought of as the vertex of a cone, also called a "conepoint".) This third conepoint will have zero total angle around it. Due to symmetry, M* may be constructed by glueing together two congruent geodesic triangles in
2289-456: A torus is a closed surface defined as the product of two circles : S × S . This can be viewed as lying in C and is a subset of the 3-sphere S of radius √2. This topological torus is also often called the Clifford torus . In fact, S is filled out by a family of nested tori in this manner (with two degenerate circles), a fact which is important in the study of S as
SECTION 20
#17330861443522398-425: A torus is punctured and turned inside out then another torus results, with lines of latitude and longitude interchanged. This is equivalent to building a torus from a cylinder, by joining the circular ends together, in two ways: around the outside like joining two ends of a garden hose, or through the inside like rolling a sock (with the toe cut off). Additionally, if the cylinder was made by gluing two opposite sides of
2507-426: A torus is the product of two circles, a modified version of the spherical coordinate system is sometimes used. In traditional spherical coordinates there are three measures, R , the distance from the center of the coordinate system, and θ and φ , angles measured from the center point. As a torus has, effectively, two center points, the centerpoints of the angles are moved; φ measures the same angle as it does in
2616-563: A torus without stretching the paper (unless some regularity and differentiability conditions are given up, see below). A simple 4-dimensional Euclidean embedding of a rectangular flat torus (more general than the square one) is as follows: where R and P are positive constants determining the aspect ratio. It is diffeomorphic to a regular torus but not isometric . It can not be analytically embedded ( smooth of class C , 2 ≤ k ≤ ∞ ) into Euclidean 3-space. Mapping it into 3 -space requires one to stretch it, in which case it looks like
2725-463: A two-sheeted cover of the 2-sphere. The points on the torus corresponding to the ramification points are the Weierstrass points . In fact, the conformal type of the torus is determined by the cross-ratio of the four points. The torus has a generalization to higher dimensions, the n-dimensional torus , often called the n -torus or hypertorus for short. (This is the more typical meaning of
2834-459: Is R n {\displaystyle \mathbb {R} ^{n}} modulo the action of the integer lattice Z n {\displaystyle \mathbb {Z} ^{n}} (with the action being taken as vector addition). Equivalently, the n -torus is obtained from the n -dimensional hypercube by gluing the opposite faces together. An n -torus in this sense is an example of an n- dimensional compact manifold . It
2943-399: Is A C . For the green grouping, A and B maintain the same state, while C and D change. B is 0 and has to be negated before it can be included. The second term is therefore A B . Note that it is acceptable that the green grouping overlaps with the red one. In the same way, the blue grouping gives the term BC D . The solutions of each grouping are combined: the normal form of
3052-1005: Is a Latin word for "a round, swelling, elevation, protuberance". A torus of revolution in 3-space can be parametrized as: x ( θ , φ ) = ( R + r cos θ ) cos φ y ( θ , φ ) = ( R + r cos θ ) sin φ z ( θ , φ ) = r sin θ {\displaystyle {\begin{aligned}x(\theta ,\varphi )&=(R+r\cos \theta )\cos {\varphi }\\y(\theta ,\varphi )&=(R+r\cos \theta )\sin {\varphi }\\z(\theta ,\varphi )&=r\sin \theta \\\end{aligned}}} using angular coordinates θ , φ ∈ [ 0 , 2 π ) , {\displaystyle \theta ,\varphi \in [0,2\pi ),} representing rotation around
3161-445: 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 in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction ( and ) denoted as ∧ , disjunction ( or ) denoted as ∨ , and negation ( not ) denoted as ¬ . Elementary algebra, on
3270-401: Is a combination of inputs for which the designer doesn't care what the output is. Therefore, "don't care" conditions can either be included in or excluded from any rectangular group, whichever makes it larger. They are usually indicated on the map with a dash or X. The example on the right is the same as the example above but with the value of f (1,1,1,1) replaced by a "don't care". This allows
3379-494: Is a fundamental problem in the design of combinational logic circuits. Modern electronic design automation tools for very-large-scale integration (VLSI) circuits often rely on an efficient representation of Boolean functions known as (reduced ordered) binary decision diagrams (BDD) for logic synthesis and formal verification . Logic sentences that can be expressed in classical propositional calculus have an equivalent expression in Boolean algebra. Thus, Boolean logic
Karnaugh map - Misplaced Pages Continue
3488-458: Is a member of the Lie group SO(4). It is known that there exists no C (twice continuously differentiable) embedding of a flat torus into 3-space. (The idea of the proof is to take a large sphere containing such a flat torus in its interior, and shrink the radius of the sphere until it just touches the torus for the first time. Such a point of contact must be a tangency. But that would imply that part of
3597-406: Is a power of two (i.e., 1, 2, 4, 8...). Minterm rectangles should be as large as possible without containing any 0s. Groups may overlap in order to make each one larger. The optimal groupings in the example below are marked by the green, red and blue lines, and the red and green groups overlap. The red group is a 2 × 2 square, the green group is a 4 × 1 rectangle, and
3706-430: Is a self-dual operation of four arguments x , y , z , t . The principle of duality can be explained from a group theory perspective by the fact that there are exactly four functions that are one-to-one mappings ( automorphisms ) of the set of Boolean polynomials back to itself: the identity function, the complement function, the dual function and the contradual function (complemented dual). These four functions form
3815-411: Is a torus with the metric inherited from its representation as the quotient , R 2 {\displaystyle \mathbb {R} ^{2}} / L , where L is a discrete subgroup of R 2 {\displaystyle \mathbb {R} ^{2}} isomorphic to Z 2 {\displaystyle \mathbb {Z} ^{2}} . This gives the quotient the structure of
3924-457: Is also an example of a compact abelian Lie group . This follows from the fact that the unit circle is a compact abelian Lie group (when identified with the unit complex numbers with multiplication). Group multiplication on the torus is then defined by coordinate-wise multiplication. Toroidal groups play an important part in the theory of compact Lie groups . This is due in part to the fact that in any compact Lie group G one can always find
4033-425: Is also used in set theory and statistics . A precursor of Boolean algebra was Gottfried Wilhelm Leibniz 's algebra of concepts . The usage of binary in relation to the I Ching was central to Leibniz's characteristica universalis . It eventually created the foundations of algebra of concepts. Leibniz's algebra of concepts is deductively equivalent to the Boolean algebra of sets. Boole's algebra predated
4142-421: Is an identity such as x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z between two Boolean terms, where a Boolean term is defined as an expression built up from variables and the constants 0 and 1 using the operations ∧, ∨, and ¬. The concept can be extended to terms involving other Boolean operations such as ⊕, →, and ≡, but such extensions are unnecessary for the purposes to which the laws are put. Such purposes include
4251-466: Is formed by rotating a disk , rather than a circle, around an axis. A solid torus is a torus plus the volume inside the torus. Real-world objects that approximate a solid torus include O-rings , non-inflatable lifebuoys , ring doughnuts , and bagels . In topology , a ring torus is homeomorphic to the Cartesian product of two circles : S 1 × S 1 {\displaystyle S^{1}\times S^{1}} , and
4360-457: Is immaterial. When values and operations can be paired up in a way that leaves everything important unchanged when all pairs are switched simultaneously, the members of each pair are called dual to each other. Thus 0 and 1 are dual, and ∧ and ∨ are dual. The duality principle , also called De Morgan duality , asserts that Boolean algebra is unchanged when all dual pairs are interchanged. One change not needed to make as part of this interchange
4469-447: Is known as the "square" flat torus. This metric of the square flat torus can also be realised by specific embeddings of the familiar 2-torus into Euclidean 4-space or higher dimensions. Its surface has zero Gaussian curvature everywhere. It is flat in the same sense that the surface of a cylinder is flat. In 3 dimensions, one can bend a flat sheet of paper into a cylinder without stretching the paper, but this cylinder cannot be bent into
Karnaugh map - Misplaced Pages Continue
4578-427: Is simplified as follows: Through the use of De Morgan's laws , the product of sums can be determined: Karnaugh maps are useful for detecting and eliminating race conditions . Race hazards are very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjoint, regions circumscribed on the map. However, because of the nature of Gray coding, adjacent has
4687-407: Is sometimes used to denote propositional calculus performed in this way. Boolean algebra is not sufficient to capture logic formulas using quantifiers , like those from first order logic . Although the development of mathematical logic did not follow Boole's program, the connection between his algebra and logic was later put on firm ground in the setting of algebraic logic , which also studies
4796-545: Is the n -fold product of the circle, the n -torus is the configuration space of n ordered, not necessarily distinct points on the circle. Symbolically, T n = ( S 1 ) n {\displaystyle \mathbb {T} ^{n}=(\mathbb {S} ^{1})^{n}} . The configuration space of unordered , not necessarily distinct points is accordingly the orbifold T n / S n {\displaystyle \mathbb {T} ^{n}/\mathbb {S} _{n}} , which
4905-487: Is the quotient of the torus by the symmetric group on n letters (by permuting the coordinates). For n = 2, the quotient is the Möbius strip , the edge corresponding to the orbifold points where the two coordinates coincide. For n = 3 this quotient may be described as a solid torus with cross-section an equilateral triangle , with a twist ; equivalently, as a triangular prism whose top and bottom faces are connected with
5014-400: Is the standard 2-torus, T 2 {\displaystyle \mathbb {T} ^{2}} . And similar to the 2-torus, the n -torus, T n {\displaystyle \mathbb {T} ^{n}} can be described as a quotient of R n {\displaystyle \mathbb {R} ^{n}} under integral shifts in any coordinate. That is, the n -torus
5123-407: Is true). The grid is toroidally connected, which means that rectangular groups can wrap across the edges (see picture). Cells on the extreme right are actually 'adjacent' to those on the far left, in the sense that the corresponding input values only differ by one bit; similarly, so are those at the very top and those at the bottom. Therefore, A D can be a valid term—it includes cells 12 and 8 at
5232-450: The Euler characteristic of the n -torus is 0 for all n . The cohomology ring H ( T n {\displaystyle \mathbb {T} ^{n}} , Z ) can be identified with the exterior algebra over the Z - module Z n {\displaystyle \mathbb {Z} ^{n}} whose generators are the duals of the n nontrivial cycles. As the n -torus
5341-459: The algebra of sets , by translating them into expressions in Boole's algebra, is explained in modern terms by saying that the algebra of sets is a Boolean algebra (note the indefinite article ). In fact, M. H. Stone proved in 1936 that every Boolean algebra is isomorphic to a field of sets . In the 1930s, while studying switching circuits , Claude Shannon observed that one could also apply
5450-472: The hyperbolic plane along their (identical) boundaries, where each triangle has angles of π/2, π/3, and 0. (The three angles of a hyperbolic triangle T determine T up to congruence.) As a result, the Gauss-Bonnet theorem shows that the area of each triangle can be calculated as π - (π/2 + π/3 + 0) = π/6, so it follows that the compactified moduli space M* has area equal to π/3. The other two cusps occur at
5559-450: The indicator function that takes the value 1 on F , and 0 outside F . The most general example is the set elements of a Boolean algebra , with all of the foregoing being instances thereof. As with elementary algebra, the purely equational part of the theory may be developed, without considering explicit values for the variables. While Elementary algebra has four operations (addition, subtraction, multiplication, and division),
SECTION 50
#17330861443525668-400: The models of these axioms as treated in § Boolean algebras . Writing down further laws of Boolean algebra cannot give rise to any new consequences of these axioms, nor can it rule out any model of them. In contrast, in a list of some but not all of the same laws, there could have been Boolean laws that did not follow from those on the list, and moreover there would have been models of
5777-454: The square root gives a quartic equation , ( x 2 + y 2 + z 2 + R 2 − r 2 ) 2 = 4 R 2 ( x 2 + y 2 ) . {\displaystyle \left(x^{2}+y^{2}+z^{2}+R^{2}-r^{2}\right)^{2}=4R^{2}\left(x^{2}+y^{2}\right).} The three classes of standard tori correspond to
5886-462: The two-element field GF(2) , that is, integer arithmetic modulo 2 , for which 1 + 1 = 0 . Addition and multiplication then play the Boolean roles of XOR (exclusive-or) and AND (conjunction), respectively, with disjunction x ∨ y (inclusive-or) definable as x + y − xy and negation ¬ x as 1 − x . In GF(2) , − may be replaced by + , since they denote the same operation; however, this way of writing Boolean operations allows applying
5995-433: The " moduli space " of the torus to contain one point for each conformal equivalence class, with the appropriate topology. It turns out that this moduli space M may be identified with a punctured sphere that is smooth except for two points that have less angle than 2π (radians) around them: One has total angle = π and the other has total angle = 2π/3. M may be turned into a compact space M* — topologically equivalent to
6104-406: The 3-sphere into two congruent solid tori subsets with the aforesaid flat torus surface as their common boundary . One example is the torus T defined by Other tori in S having this partitioning property include the square tori of the form Q ⋅ T , where Q is a rotation of 4-dimensional space R 4 {\displaystyle \mathbb {R} ^{4}} , or in other words Q
6213-466: The Boolean algebra has only three basic operations: conjunction , disjunction , and negation , expressed with the corresponding binary operators AND ( ∧ {\displaystyle \land } ) and OR ( ∨ {\displaystyle \lor } ) and the unary operator NOT ( ¬ {\displaystyle \neg } ), collectively referred to as Boolean operators . Variables in Boolean algebra that store
6322-518: The Karnaugh map has 16 positions. The Karnaugh map is therefore arranged in a 4 × 4 grid. The row and column indices (shown across the top and down the left side of the Karnaugh map) are ordered in Gray code rather than binary numerical order. Gray code ensures that only one variable changes between each pair of adjacent cells. Each cell of the completed Karnaugh map contains a binary digit representing
6431-501: The Laws of Thought (1854). According to Huntington , the term Boolean algebra was first suggested by Henry M. Sheffer in 1913, although Charles Sanders Peirce gave the title "A Boolian [ sic ] Algebra with One Constant" to the first chapter of his "The Simplest Mathematics" in 1880. Boolean algebra has been fundamental in the development of digital electronics , and is provided for in all modern programming languages . It
6540-470: The algebraic systems of many other logics. The problem of determining whether the variables of a given Boolean (propositional) formula can be assigned in such a way as to make the formula evaluate to true is called the Boolean satisfiability problem (SAT), and is of importance to theoretical computer science , being the first problem shown to be NP-complete . The closely related model of computation known as
6649-493: The axioms thus far have all been for monotonic Boolean logic. Nonmonotonicity enters via complement ¬ as follows. The complement operation is defined by the following two laws. All properties of negation including the laws below follow from the above two laws alone. In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, hence in both algebras it satisfies the double negation law (also called involution law) But whereas ordinary algebra satisfies
SECTION 60
#17330861443526758-405: The axis of revolution passes through the center of the circle, the surface is a degenerate torus, a double-covered sphere . If the revolved curve is not a circle, the surface is called a toroid , as in a square toroid. Real-world objects that approximate a torus of revolution include swim rings , inner tubes and ringette rings . A torus should not be confused with a solid torus , which
6867-521: 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;
6976-447: The circuit is A C ¯ + A B ¯ + B C D ¯ {\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}} . Thus the Karnaugh map has guided a simplification of It would also have been possible to derive this simplification by carefully applying the axioms of Boolean algebra , but the time it takes to do that grows exponentially with
7085-537: The corresponding output value of the Boolean function. Optimal groups of 1s or 0s are identified, which represent the terms of a canonical form of the logic in the original truth table. These terms can be used to write a minimal Boolean expression representing the required logic. Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using the minimal number of logic gates . A sum-of-products expression (SOP) can always be implemented using AND gates feeding into an OR gate , and
7194-416: The definition of a Boolean algebra as any model of the Boolean laws, and as a means for deriving new laws from old as in the derivation of x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) from y ∧ z = z ∧ y (as treated in § Axiomatizing Boolean algebra ). Boolean algebra satisfies many of the same laws as ordinary algebra when one matches up ∨ with addition and ∧ with multiplication. In particular
7303-443: 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
7412-415: The effect of reflecting the diagram horizontally and any failure of commutativity would then appear as a failure of symmetry. Idempotence of ∧ and ∨ can be visualized by sliding the two circles together and noting that the shaded area then becomes the whole circle, for both ∧ and ∨. To see the first absorption law, x ∧ ( x ∨ y ) = x , start with the diagram in the middle for x ∨ y and note that
7521-456: The examples here. The interior and exterior of region x corresponds respectively to the values 1 (true) and 0 (false) for variable x . The shading indicates the value of the operation for each combination of regions, with dark denoting 1 and light 0 (some authors use the opposite convention). The three Venn diagrams in the figure below represent respectively conjunction x ∧ y , disjunction x ∨ y , and complement ¬ x . For conjunction,
7630-430: The field of topology , a torus is any topological space that is homeomorphic to a torus. The surface of a coffee cup and a doughnut are both topological tori with genus one. An example of a torus can be constructed by taking a rectangular strip of flexible material such as rubber, and joining the top edge to the bottom edge, and the left edge to the right edge, without any half-twists (compare Klein bottle ). Torus
7739-417: The following laws are common to both kinds of algebra: The following laws hold in Boolean algebra, but not in ordinary algebra: 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
7848-468: The function's output for that combination of inputs. After the Karnaugh map has been constructed, it is used to find one of the simplest possible forms — a canonical form — for the information in the truth table. Adjacent 1s in the Karnaugh map represent opportunities to simplify the expression. The minterms ('minimal terms') for the final expression are found by encircling groups of 1s in the map. Minterm groups must be rectangular and must have an area that
7957-406: The integral matrices with determinant ±1. Making them act on R n {\displaystyle \mathbb {R} ^{n}} in the usual way, one has the typical toral automorphism on the quotient. The fundamental group of an n -torus is a free abelian group of rank n . The k -th homology group of an n -torus is a free abelian group of rank n choose k . It follows that
8066-399: The inverse to eliminate another potential race hazard. Applying De Morgan's laws creates another product of sums expression for f , but with a new factor of ( A + D ¯ ) {\displaystyle \left(A+{\overline {D}}\right)} . The following are all the possible 2-variable, 2 × 2 Karnaugh maps. Listed with each is the minterms as
8175-466: The k-map can be considered cylindrical. The fields at edges on the left and right are adjacent, and the top and bottom are adjacent. K-Maps for four variables must be depicted as a donut or torus shape. The four corners of the square drawn by the k-map are adjacent. Still more complex maps are needed for 5 variables and more. Related graphical minimization methods include: Boolean algebra In mathematics and mathematical logic , Boolean algebra
8284-472: The latter is taken to be the definition in that context. It is a compact 2-manifold of genus 1. The ring torus is one way to embed this space into Euclidean space , but another way to do this is the Cartesian product of the embedding of S 1 {\displaystyle S^{1}} in the plane with itself. This produces a geometric object called the Clifford torus , a surface in 4-space . In
8393-435: The listed laws that were not Boolean algebras. This axiomatization is by no means the only one, or even necessarily the most natural given that attention was not paid as to whether some of the axioms followed from others, but there was simply a choice to stop when enough laws had been noticed, treated further in § Axiomatizing Boolean algebra . Or the intermediate notion of axiom can be sidestepped altogether by defining
8502-471: The logical value of 0 and 1 are called the Boolean variables . They are used to store either true or false values. The basic operations on Boolean variables x and y are defined as follows: Alternatively, the values of x ∧ y , x ∨ y , and ¬ x can be expressed by tabulating their values with truth tables as follows: When used in expressions, the operators are applied according to
8611-425: The modern developments in abstract algebra and mathematical logic ; it is however seen as connected to the origins of both fields. In an abstract setting, Boolean algebra was perfected in the late 19th century by Jevons , Schröder , Huntington and others, until it reached the modern conception of an (abstract) mathematical structure . For example, the empirical observation that one can manipulate expressions in
8720-484: The need for extensive calculations by taking advantage of humans' pattern-recognition capability. It also permits the rapid identification and elimination of potential race conditions . The required Boolean results are transferred from a truth table onto a two-dimensional grid where, in Karnaugh maps, the cells are ordered in Gray code , and each cell position represents one combination of input conditions. Cells are also known as minterms, while each cell value represents
8829-430: The north pole of S . The torus can also be described as a quotient of the Cartesian plane under the identifications or, equivalently, as the quotient of the unit square by pasting the opposite edges together, described as a fundamental polygon ABA B . The fundamental group of the torus is just the direct product of the fundamental group of the circle with itself: Intuitively speaking, this means that
8938-428: The notation has been changed, despite the fact that 0s and 1s are still being used. But if in addition to interchanging the names of the values, the names of the two binary operations are also interchanged, now there is no trace of what was done. The end product is completely indistinguishable from what was started with. The columns for x ∧ y and x ∨ y in the truth tables have changed places, but that switch
9047-452: The number of terms. The inverse of a function is solved in the same way by grouping the 0s instead. The three terms to cover the inverse are all shown with grey boxes with different colored borders: This yields the inverse: Through the use of De Morgan's laws , the product of sums can be determined: Karnaugh maps also allow easier minimizations of functions whose truth tables include " don't care " conditions. A "don't care" condition
9156-420: The other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations. Boolean algebra was introduced by George Boole in his first book The Mathematical Analysis of Logic (1847), and set forth more fully in his An Investigation of
9265-399: The overlap area is indicated in brown. The cells are often denoted by a shorthand which describes the logical value of the inputs that the cell covers. For example, AD would mean a cell which covers the 2x2 area where A and D are true, i.e. the cells numbered 13, 9, 15, 11 in the diagram above. On the other hand, A D would mean the cells where A is true and D is false (that is, D
9374-411: The portion of the shaded area in common with the x circle is the whole of the x circle. For the second absorption law, x ∨ ( x ∧ y ) = x , start with the left diagram for x ∧ y and note that shading the whole of the x circle results in just the x circle being shaded, since the previous shading was inside the x circle. The double negation law can be seen by complementing the shading in
9483-542: The potential race hazard, bridging between the green and blue output states or blue and red output states: this is shown as the yellow region (which wraps around from the bottom to the top of the right half) in the adjacent diagram. The term is redundant in terms of the static logic of the system, but such redundant, or consensus terms , are often needed to assure race-free dynamic performance. Similarly, an additional term of A ¯ D {\displaystyle {\overline {A}}D} must be added to
9592-416: The precedence rules. As with elementary algebra, expressions in parentheses are evaluated first, following the precedence rules. If the truth values 0 and 1 are interpreted as integers, these operations may be expressed with the ordinary operations of arithmetic (where x + y uses addition and xy uses multiplication), or by the minimum/maximum functions: One might consider that only negation and one of
9701-407: The red term to expand all the way down and, thus, removes the green term completely. This yields the new minimum equation: Note that the first term is just A , not A C . In this case, the don't care has dropped a term (the green rectangle); simplified another (the red one); and removed the race hazard (removing the yellow term as shown in the following section on race hazards). The inverse case
9810-406: 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
9919-434: The right hand side would be 1 (and so on). All of the laws treated thus 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
10028-548: The rules of Boole's algebra in this setting, and he introduced switching algebra as a way to analyze and design circuits by algebraic means in terms of logic gates . Shannon already had at his disposal the abstract mathematical apparatus, thus he cast his switching algebra as the two-element Boolean algebra . In modern circuit engineering settings, there is little need to consider other Boolean algebras, thus "switching algebra" and "Boolean algebra" are often used interchangeably. Efficient implementation of Boolean functions
10137-431: The same as for a cylinder of length 2π R and radius r , obtained from cutting the tube along the plane of a small circle, and unrolling it by straightening out (rectifying) the line running around the center of the tube. The losses in surface area and volume on the inner side of the tube exactly cancel out the gains on the outer side. Expressing the surface area and the volume by the distance p of an outermost point on
10246-427: The simplification of Boolean algebra functions. For example, consider the Boolean function described by the following truth table . Following are two different notations describing the same function in unsimplified Boolean algebra, using the Boolean variables A , B , C , D and their inverses. In the example above, the four input variables can be combined in 16 different ways, so the truth table has 16 rows, and
10355-487: The spherical system, but is known as the "toroidal" direction. The center point of θ is moved to the center of r , and is known as the "poloidal" direction. These terms were first used in a discussion of the Earth's magnetic field, where "poloidal" was used to denote "the direction toward the poles". In modern use, toroidal and poloidal are more commonly used to discuss magnetic confinement fusion devices. Topologically ,
10464-449: The study of Riemann surfaces , one says that any two smooth compact geometric surfaces are "conformally equivalent" when there exists a smooth homeomorphism between them that is both angle-preserving and orientation-preserving. The Uniformization theorem guarantees that every Riemann surface is conformally equivalent to one that has constant Gaussian curvature . In the case of a torus, the constant curvature must be zero. Then one defines
10573-1057: The surface of the torus to the center, and the distance q of an innermost point to the center (so that R = p + q / 2 and r = p − q / 2 ), yields A = 4 π 2 ( p + q 2 ) ( p − q 2 ) = π 2 ( p + q ) ( p − q ) , V = 2 π 2 ( p + q 2 ) ( p − q 2 ) 2 = 1 4 π 2 ( p + q ) ( p − q ) 2 . {\displaystyle {\begin{aligned}A&=4\pi ^{2}\left({\frac {p+q}{2}}\right)\left({\frac {p-q}{2}}\right)=\pi ^{2}(p+q)(p-q),\\[5mu]V&=2\pi ^{2}\left({\frac {p+q}{2}}\right)\left({\frac {p-q}{2}}\right)^{2}={\tfrac {1}{4}}\pi ^{2}(p+q)(p-q)^{2}.\end{aligned}}} As
10682-439: The term " n -torus", the other referring to n holes or of genus n . ) Just as the ordinary torus is topologically the product space of two circles, the n -dimensional torus is topologically equivalent to the product of n circles. That is: The standard 1-torus is just the circle: T 1 = S 1 {\displaystyle \mathbb {T} ^{1}=\mathbb {S} ^{1}} . The torus discussed above
10791-428: The third diagram for ¬ x , which shades the x circle. Torus In geometry , a torus ( pl. : tori or toruses ) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanar with the circle. The main types of toruses include ring toruses, horn toruses, and spindle toruses. A ring torus is sometimes colloquially referred to as
10900-426: The three possible aspect ratios between R and r : When R ≥ r , the interior ( x 2 + y 2 − R ) 2 + z 2 < r 2 {\displaystyle {\textstyle {\bigl (}{\sqrt {x^{2}+y^{2}}}-R{\bigr )}^{2}}+z^{2}<r^{2}} of this torus is diffeomorphic (and, hence, homeomorphic) to
11009-399: The top, and wraps to the bottom to include cells 10 and 14—as is B D , which includes the four corners. Once the Karnaugh map has been constructed and the adjacent 1s linked by rectangular and square boxes, the algebraic minterms can be found by examining which variables stay the same within each box. For the red grouping: Thus the first minterm in the Boolean sum-of-products expression
11118-478: The torus, since it has zero curvature everywhere, must lie strictly outside the sphere, which is a contradiction.) On the other hand, according to the Nash-Kuiper theorem , which was proven in the 1950s, an isometric C embedding exists. This is solely an existence proof and does not provide explicit equations for such an embedding. In April 2012, an explicit C (continuously differentiable) isometric embedding of
11227-534: The torus. The typical doughnut confectionery has an aspect ratio of about 3 to 2. An implicit equation in Cartesian coordinates for a torus radially symmetric about the z {\displaystyle z} - axis is ( x 2 + y 2 − R ) 2 + z 2 = r 2 . {\displaystyle {\textstyle {\bigl (}{\sqrt {x^{2}+y^{2}}}-R{\bigr )}^{2}}+z^{2}=r^{2}.} Algebraically eliminating
11336-420: The tube and rotation around the torus' axis of revolution, respectively, where the major radius R {\displaystyle R} is the distance from the center of the tube to the center of the torus and the minor radius r {\displaystyle r} is the radius of the tube. The ratio R / r {\displaystyle R/r} is called the aspect ratio of
11445-482: The two laws Boolean algebra satisfies De Morgan's laws : 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
11554-430: The two other operations are basic because of the following identities that allow one to define conjunction in terms of negation and the disjunction, and vice versa ( De Morgan's laws ): Operations composed from the basic operations include, among others, the following: These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs. A law of Boolean algebra
11663-402: The usual arithmetic operations of integers (this may be useful when using a programming language in which GF(2) is not implemented). Boolean algebra also deals with functions which have their values in the set {0,1} . A sequence of bits is a commonly used example of such a function. Another common example is the totality of subsets of a set E : to a subset F of E , one can define
11772-439: Was done consistently throughout, it would still be Boolean algebra, albeit with some obvious cosmetic differences. But suppose 0 and 1 were renamed 1 and 0 respectively. Then it would still be Boolean algebra, and moreover operating on the same values. However, it would not be identical to our original Boolean algebra because now ∨ behaves the way ∧ used to do and vice versa. So there are still some cosmetic differences to show that
11881-505: Was to complement. Complement is a self-dual operation. The identity or do-nothing operation x (copy the input to the output) is also self-dual. A more complicated example of a self-dual operation is ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . There is no self-dual binary operation that depends on both its arguments. A composition of self-dual operations is a self-dual operation. For example, if f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , then f ( f ( x , y , z ), x , t )
#351648