Legal Algebra
The following laws apply in Boolean algebra, but not in ordinary algebra: This semantics allows a translation between the tautologies of propositional logic and the equations of Boolean algebra. Any tautology Φ of propositional logic can be expressed as the Boolean equation Φ = 1, which will be a theorem of Boolean algebra. Conversely, each sentence Φ = Ψ of Boolean algebra corresponds to the tautologies (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) and (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). If → is in language, these last tautologies can also be written as (Φ→Ψ) ∧ (Ψ→Φ) or as two separate theorems Φ→Ψ and Ψ→Φ; If ≡ is present, only one tautology Φ ≡ Ψ can be used. The term “algebra” refers to both a subject, namely the subject of algebra, and an object, namely an algebraic structure. While the above dealt with the subject of Boolean algebra, this section deals with mathematical objects called Boolean algebras, which are defined in general as any model of Boolean laws. We begin with a special case of the term that can be defined without reference to laws, namely concrete Boolean algebras, and then give the formal definition of the general term. While expressions in elementary algebra refer primarily to numbers, in Boolean algebra they refer to false and true truth values. These values are represented by bits (or binary digits) 0 and 1.
They do not behave like the integers 0 and 1, for which 1 + 1 = 2, but can be identified with the elements of the two-element field GF(2), i.e. the integer arithmetic modulo 2, for which 1 + 1 = 0. Addition and multiplication then play the Boolean roles of XOR (exclusive-or) or AND (conjunction), where the disjunction x ∨ y (inclusive-ou) is definable as x + y – xy and the negation ¬x as 1 − x. In GF(2), − can be replaced by + because they denote the same operation; However, this way of writing Boolean operations allows the use of the usual arithmetic operations of integers (this can be useful when using a programming language in which GF(2) is not implemented). The Boolean algebras we have seen so far were all concrete and consisted of binary vectors or equivalent subsets of a set. Such a Boolean algebra consists of a set and operations on that set that can be shown to satisfy the laws of Boolean algebra. As with elementary algebra, the purely equational part of the theory can be developed without taking into account the explicit values of the variables. [16] Boolean operations are used in numerical logic to combine bits transmitted on individual wires in order to interpret them via {0,1}. If a vector of n identical binary gates is used to combine two binary vectors of n bits each, the individual binary operations can be collectively understood as a single operation on the values of a Boolean algebra with 2n elements.
This observation can easily be proven as follows. Certainly, any law satisfied by all concrete Boolean algebras is satisfied by the prototypical law, since it is concrete. Conversely, any law that fails for a concrete Boolean algebra must have failed at a certain bit position, in which case that position itself provides a one-bit counterexample to that law. Non-degeneracy ensures that there is at least one bit position because there is only one vector of empty bits. The set {0,1} and its Boolean operations discussed above can be understood as a special case of binary vectors of length one, which can also be understood as the two subsets of a one-element set by identifying binary vectors with subsets. We call this prototypic Boolean algebra, justified by the following observation. Implication differs from implication in that the latter is a binary operation that returns a value in a Boolean algebra, the former is a binary relation that holds or does not hold. In this sense, implication is an external form of involvement, that is, outside of Boolean algebra, where the reader of the sequence is also external, interpreting and comparing antecedents and followers in some Boolean algebras. The natural interpretation of ⊢ {displaystyle vdash } is as ≤ in the partial order of Boolean algebra defined by x ≤ y if and only if x∨y = y.
This ability to mix external involvement ⊢ {displaystyle vdash } and internal involvement → in a logic is one of the main differences between sequential and propositional calculus. [30] Can this list be shorter? Again, the answer is yes. First, some of the above laws are implicit by others. A sufficient subset of the above laws consists of the pairs of laws of association, commutativity and absorption, the distribution of ∧ over ∨ (or the other law of distributivity – one is enough), and the two complementary laws. In fact, it is the traditional axiomatization of Boolean algebra as a complementary distributive network. For the purposes of this definition, it is irrelevant whether the transactions comply with the law, whether by Order in Council or by evidence. All concrete Boolean algebras satisfy the laws (by proof instead of fiat), so every concrete Boolean algebra is a Boolean algebra according to our definitions. This axiomatic definition of a Boolean algebra as a set and of certain operations satisfying certain laws or axioms by fiat is completely analogous to the abstract definitions of group, ring, field, etc. characteristic of modern or abstract algebra. (By the way, historically, X itself did not need to be empty to exclude degenerate or one-element Boolean algebra, which is the only exception to the rule that all Boolean algebras satisfy the same equations, since degenerate algebra satisfies all equations.
However, this exclusion contradicts the preferred definition purely based on equations of “Boolean algebra”, because there is no way to exclude one-element algebra with equations alone – 0 ≠ 1 does not count because it is a denied equation. Therefore, modern authors allow degenerate Boolean algebra and leave X blank.) In the case of Boolean algebras, the answer is yes. In particular, the many finite equations we have listed above are sufficient. We say that Boolean algebra is axiomatisable in a finite or finite way. In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of variables are true and false, usually denoted 1 and 0, respectively. Instead of elementary algebra, where the values of variables are numbers and the prime operations are addition and multiplication, the main operations of Boolean algebra are conjunction (and) as ∧, disjunction (or) as ∨, and negation (non) as ¬. It is therefore a formalism to describe logical operations, just as elementary algebra describes numerical operations. The assumption of x = 2 in the third law above shows that it is not an ordinary algebra law, since 2 is × 2 = 4. The remaining five laws can be falsified in ordinary algebra by all variables being 1. For example, in the absorption law, 1, the left side would be 1 (1 + 1) = 2, while the right side would be 1 (and so on).
Let a,b,c be three variables. Next, here are some basic rules of algebra that are applicable to these variables. It is weaker in the sense that it does not imply any representability in itself. Boolean algebras are special here, for example, an algebra of relations is a Boolean algebra with an additional structure, but it is not true that every algebra of relations can be represented in the proper sense for algebras of relations. In the 1930s, while studying circuits, Claude Shannon observed that the rules of Boolean algebra could also be applied in this context,[8] and he introduced circuit algebra as a means of analyzing and designing circuits by algebraic means in the form of logic gates. Shannon already had the abstract mathematical apparatus, so he converted his commutation algebra to a two-element Boolean algebra. In modern circuit engineering environments, there is little need to consider other Boolean algebras, so “switching algebra” and “Boolean algebra” are often used interchangeably. [9] [10] [11] Syntactically, each Boolean term corresponds to a propositional formula of propositional logic. In this translation between Boolean algebra and propositional logic, the Boolean variables x,y become propositional variables (or atoms) P,Q,…, Boolean terms such as x∨y become propositional formulas P∨Q, 0 becomes false, or ⊥ and 1 becomes true or T.
It is practical, when referring to generic sentences, to use the Greek letters Φ, Ψ. metavariables (variables outside the language of propositional calculus that are used when talking about propositional calculus) to designate sentences. For any complete axiomatization of Boolean algebra, such as the axioms of a complementary distributive network, a sufficient condition for an algebraic structure of this type to satisfy all Boolean laws is that it satisfies only those axioms. The following definition is therefore equivalent.
