Algebra of Logic

Algebra of Logic

 

the branch of mathematical logic which is concerned with the investigation of statements from the point of view of their logical values (truth and falsehood) and logical operations upon them. The algebra of logic arose in the middle of the 19th century in the works of G. Boole and was subsequently developed by C. Peirce, P. S. Poret-skii, B. Russell, D. Hubert, and others. The creation of the algebra of logic represented an attempt to solve traditional logical problems by algebraic methods. With the advent of the theory of sets in the 1870’s, which absorbed part of the elementary subject matter of the algebra of logic, and with the further development of mathematical logic during the last quarter of the 19th century and the first half of the 20th century, the subject matter of the algebra of logic was considerably altered. The primary topic of the algebra of logic became statements. A statement is any proposition about which the assertion of truth or falsehood has meaning. Examples of statements are “The whale is an animal,” “All angles are right angles,” and so forth. The first statement is clearly true and the second is false. The logical connectives “and,” “or,” “if..., then...,” “equivalently,” the particle “not,” and so forth, which are used in ordinary discourse, permit the construction of new, more “complex” statements from those already given. Thus, from the statements “x>2,” “≤3,” one can form the statement “x>2 and x≤3” using the connective “and”; using the connective “or,” the statement “x>2 or x≤3” is constructed; using the connective “if..., then...,” the statement “if x>2, then x≤3” can be formed, and so forth. The truth or falsehood of statements obtained in this manner depends on the truth and falsehood of the initial statements and the corresponding interpretation of the connectives as operations on the statements.

Connectives. Formulas. In the algebra of logic, truth is designated by the symbol T and falsehood by F. Often the numbers 1 and 0 are used instead of the symbols T and F. The connectives “and,” “or,” “if..., then...,” and “equivalently” are denoted by the symbols & (conjunction), V (disjunction), → (implication), and ∼ (equivalence), respectively. For negation, the symbol (overhead dash) is introduced. Together with individual statements, examples of which were presented above, so-called variable statements—that is, such variables whose values can be any preset individual statements—are also used in the algebra of logic. Further, the concept of the formula, which is formalization of the concept of a “complex” statement, is introduced inductively; A, B, C, . . . denote individual statements, and X, Y, Z, . . . denote variable statements. Each of these letters is called a formula. If the symbol * denotes any of the connectives enumerated above, and ચ and ℬ are formulas, then (ચ * ℬ) and ચ are formulas. An example of a formula is ((X&Y)→Z̄). In the algebra of logic, the connectives and the particle “not” are considered to be operations on quantities that take the values 0 and 1, and the result of the application of these operations is also 0 or 1. The conjunction X&Y is equal to 1 if and only if both X and Y are equal to 1. The disjunction XV Y is equal to 0 if and only if both X and Y are 0. The implication X → Y is equal to 0 if and only if X is 1 and Y is 0. The equivalence X ∽ Y equals 1 if and only if the values of X and Y are the same. The negation equals 1 if and only if X is 0. The operations introduced permit each formula, for given values of the expressions within it, to be assigned one of the two values 0 or 1. Thus, each formula can be simultaneously considered as some method of specification or realization of so-called functions of the algebra of logic (logical functions)—that is, functions that are defined on collections of 0’s and l’s and which also take as values 0 or 1. For the assignment of logical functions, tables are sometimes used containing all collections of variable values and the function values for these collections. Thus, for example, the composite table which specifies the functions X̄, X&Y, XVY, X → Y, and X ∼ Y has the form

xyx&Yxvyx→yx∼y
0010011
0110110
1000100
1101111

Tables for arbitrary logical functions are arranged analogously. This is the so-called tabular method of specifying logical functions. These tables are sometimes called truth tables.

For the transformation of formulas into equal formulas, the following equalities play an important role in the algebra of logic: (1) X&Y = Y&X, XVY = YVX (commutative law); (2) (X&Y)&Z = X&(Y&Z), (XV Y)VZ = XV(YVZ) (associative law); (3) X&(XVY) = X, XV (X&Y) = X (absorption law); (4)X&(YVZ) = (X&Y) V(X&Z) (distributive law); (5) X&X̄ = 0 (contradiction law); (6) X VX̄ = 1 (law of the excluded middle); and (7) X → Y = X̄ V Y, X ∼ Y = (X&Y) V(X̄&Ȳ). These equalities, which are established, for example, by means of truth tables, permit one to obtain other equalities without using the tables. The method of obtaining the other equalities are the so-called identity transformations which change, generally speaking, the expression but not the function that is realized by this expression. For example, the law of idempotence X VX = X is obtained by means of the absorption laws. The equalities referred to above permit, in a number of cases, a considerable simplification in the writing of formulas by eliminating “superfluous parentheses.” Thus, relations (1) and (2) afford the possibility of using in place of the formulas (...(ચ1 & ચua;2) &...) & ચ, and (...(ℬ1 V ℬ2) V...)Vℬ8 the more compact forms ચ1 & ચ2 & ... & ચ, and ℬ1 Vℬ2V. . .ℬ8. The first expression is said to be the conjunction of the factors ચ1,...,ચB, and the second is said to be the disjunction of the terms ℬ1,..., ℬ8. Equalities (5), (6), and (7) also indicate that constants 0 and 1, implication, and equivalence, considering them as functions, can be expressed in terms of conjunction, disjunction, and negation. Moreover, every function of the algebra of logic can be realized by a formula that is written using the symbols &, V, and

Normal forms. The set of all formulas whose construction involves the use of variable statements, some of the symbols &, V. →, ∼, and the constants 0 and 1 is said to be the language over the given symbols and constants. Equalities (1) − (7) indicate that for every formula in the language over &,V,→, ∼, 0, 1, a formula can be found that is equal to it in the language over &, V, , 0, and 1. For example, Algebra of Logic.

A special role in the latter language is played by the class of formulas that can be written in the form ચ1Vચ2ચV. . .Vચ8, 0 or 1, where s ≥ 1 and each ચ1 is a variable statement, or its negation, or the conjunction of such terms. In this case, each ચi does not contain the identical factors and does not contain factors of the form X and X simultaneously, and all ચ are pairwise distinct. Here, the parentheses are omitted, since it is assumed that the operation of conjunction connects “more strongly” than disjunction; that is, during a calculation with given values ot the variables, the values ચ1 must be calculated first. These expressions are called disjunctive normal forms (dnf). Each formula ચ that realizes a nonconstant function in the language over &, V, →, ∼, ,0, and 1 by means of equalities (1) − (7) can be reduced to a dnf that is equal to it which contains all the variables of the formula ચ and any number of other variables, while each ચ1 in this dnf contains the same variables. Such a dnf is called a full dnf of the formula ચ. The possibility of reduction to a full dnf is the basis of the algorithm that determines the equality or inequality of two preset formulas.

An important role in the algebra of logic and its applications is played by the so-called abbreviated dnf. A dnf is abbreviated if the following conditions are satisfied: (1) there is no pair of terms ચi and ચj in it such that any factor of ચi is also in ચj; (2) for any two such terms ચi and ચj, of which one contains as a factor some variable and the other contains the negation of this variable (under the condition that in the given pair of terms there is no other variable for which this occurs), there is (in this same dnf) a term ચj equal to the conjunction of the remaining factors of these two terms. Every dnf can be reduced to an abbreviated dnf which is equal to it by means of equalities (1) − (7). For example, the abbreviated dnf for the formula ((X ∼ (Y → Z)) → (X&Z)) is X̄&Ȳ VZ VX&Y.

In addition to the dnf, the conjunctive normal form (cnf) is also used. This is an expression that can be obtained from the dnf by replacing Vwith & and & with V. For example, the cnf (XVY)&(X̄VZ) is obtained from the dnf X&YVX̄& Z. The operation (or function) f is said to be dual for the operation ψ if the table that assigns f is obtained from the table that assigns ψ by replacing all 0’s with l’s and l’s with 0’s (including replacement of the function values). For example, conjunction and disjunction are duals of each other, negation is self-dual, the constants 0 and 1 are duals of each other, and so forth. The transformation of formulas in which the symbols of all the operations in an expression are replaced by the symbols of the dual operations, as well as 1 by 0 and 0 by 1, is called a duality transformation. If the equality ચ = ℬ is true and ચ * is the dual to ચ and ℬ* is the dual to ℬ, then ચ* = ℬ*, which is said to be the dual to the former, is true. This is the so-called principle of duality. Examples of dual equalities are the pairs of laws (1), (2), and (3); equality (5) is the dual to equality (6), and each cnf is the dual to some dnf. The full cnf and abbreviated cnf are defined as cnf s such that the expressions dual to them are a full dnf and an abbreviated dnf, respectively.

Consequences. Hypotheses. Minimization. Full and abbreviated dnf s and cnf s are used for the solution of the problem of reviewing all the hypotheses and all the consequences of a given formula. By the hypothesis of a formula ચ we mean a formula ℬ such that (ℬ → ચ) = 1, and by the consequence of a formula ચ, we mean a formula ચ such that (ચ → ℬ) = 1. The hypothesis of a formula ચ is called simple if it is the conjunction of variables or their negations, and if, after discarding any of its factors, it ceases to be the hypothesis of formula ચ. Analogously, the consequence of a formula ચ is called simple if it is the disjunction of variables or their negations, and if, after discarding any of its terms, it ceases to be the consequence of formula ચ. The solution of the problem of reviewing the hypotheses and consequences is based on the designation of an algorithm that constructs all the simple hypotheses and consequences for a given formula and on obtaining from them all the remaining hypotheses and consequences by means of laws (2) − (7).

The abbreviated dnf has important applications. We note first of all the problem of minimization of a logical function, which is part of the so-called control system synthesis problem. The minimization of logical functions consists of constructing for a given logical function a dnf which realizes this function and has the smallest total number of factors in its terms, that is, has minimal “complexity.” Such dnfs are called minimal. Every minimal dnf for a given nonconstant function is obtained from the abbreviated dnf of any formula that realizes this function by discarding some terms ચi from this abbreviated dnf.

Languages. Interpretations In the language over &, V, →, ∼, 0, 1, and +, where the symbol + is interpreted as modulo-2 addition, let us establish the following relations: (8) XVY = ((X&Y) + X) + Y, X̄ = X + 1; (9) X → Y = X̄&Y, X ∼ Y = (X + Y) + 1; (10) X + Y = (X&Ȳ)V(X̄&Y), 1 = XVX̄. These equalities permit the translation of formulas in the language over &,V, →, ∼, 0, and linto formulas equal to them in a language over &, +, and 1, and vice versa. The identity transformations in the latter language are accomplished by means of equalities that were established for conjunction and complements: (11) X + Y = Y + X; (12) (X + Y) + Z = X + (Y + Z); (13) X&(Y + Z) = X&Y + X&Z, (14) X&X = X, X + (Y + Y) = X, X&1 = X. Here, as before, it is assumed that conjunction connects “more strongly” than the symbol +. These equalities are sufficient to derive any true equality in the language over &, + , and 1 by means of identity transformations, in the same manneras in the consideration of the language over &, V, →, ∼, ,0, and 1. An expression in the language &, +, and 1 is called a reduced polynomial if it (1) has the form ચ1 + ચ2 + . . . + ચ3, where each ચi is 1, or a variable, or the conjunction of different variables free from negations, ચij for ij and s ≥ 1; or (2) is equal to 1 + 1. For example, the expression X & Y & Z + X & Y + 1 is a reduced polynomial. Every formula in the algebra of logic can be reduced to a reduced polynomial.

In addition to the languages considered, there are other languages that are equivalent to them. (Two languages are called equivalent if, by means of certain transformation rules, every formula of one of these languages is translated into a certain formula in the other language which is equal to it, and vice versa.) Any system of operations (and constants) which has the property that every logical function can be represented by these operations (and constants) is adequate to serve as the basis of such a language. Such systems are said to be functionally complete. Examples of complete systems are Algebra of Logic, and {X + Y, 1, X & Y}. There exists an algorithm which determines the completeness or incompleteness of an arbitrary finite system of logical functions. Also considered are languages that are based on a system of operations which is not functionally complete, and there is an infinite number of such languages. Among them are infinitely many pairwise nonequivalent languages (in the sense of the absence of translatability from one language into the other by means of identity transformations). However, for every language constructed on the basis of some set of logical operations, there is a finite system of equalities in this language such that every equality of this language is derivable by means of identity transformations from the equalities of this system. Such a system of equalities is called a deductively complete system of equalities of the language.

Considering one or another of the above-mentioned languages together with a certain complete system of equalities of this language, one sometimes diverts oneself from the tabular assignment of the operations that are the basis of this language and from the fact that the values of its variables are statements. In place of this, one assumes various interpretations of the language, which consists of one or another set of objects (serving as the values of the variables) and of a system of operations on the objects of this set which satisfy the equalities of the complete system of_equalities of this language. Thus, the language over & V, , 0, and 1, as a result of such a step, is converted into the language of the so-called Boolean algebra, the language over &, +, and 1 is converted into the language of the so-called Boolean ring (with unity), a language over & and V into a language of a distributive lattice, and so forth.

The algebra of logic is developing chiefly under the influence of problems arising in its areas of applications. The most important of these is in the theory of electric circuits. For the description of the latter, in certain cases, one has to deviate from the use of only the ordinary two-valued algebra of logic and consider one or another of its multivalued generalizations.

REFERENCES

Hubert, D., and B. Ackerman. Osnovy teoreticheskoi logiki. Moscow, 1947. (Translated from German.)
Tarski, A. Vvedenie ν logiku i metodologiiu deduktivnykh nauk. Moscow, 1948. (Translated from English.)
Kleene, S. C. Vvedenie ν metamatematiku. Moscow, 1957. (Translated from English.)
Novikov, P. S. Elementy matematicheskoi logiki. Moscow, 1959.

V. B. KUDRIAVTSEV