Lecture
PROPOSITIONAL ALGEBRA is a component part of one of the modern, rapidly developing branches of mathematics – mathematical logic. Mathematical logic is applied in computer science and makes it possible to model the simplest thought processes. One of the entertaining applications of propositional algebra – is the solving of logic puzzles.
The algebra of logic (propositional algebra) — is a branch of mathematical logic in which logical operations on propositions are studied . Most often it is assumed that propositions can be only true or false, that is, the so-called binary or two-valued logic is used, in contrast to, for example, three-valued logic.
The science of the «algebra of logic» owes its existence to the English mathematician George Boole, who studied the logic of propositions. The first course on the algebra of logic in Russia was given by P. S. Poretsky at Kazan State University.
Its founder is J. Boole, an English mathematician and logician, who based his logical teaching on the analogy between algebra and logic. The algebra of logic became the first system of mathematical logic in which algebraic symbolism began to be applied to logical inferences in operations with concepts considered from the side of their extensions. Boole set himself the task of solving logic problems by means of the methods applied in algebra. He tried to express any judgment in the form of equations with symbols, in which logical laws similar to the laws of algebra operate.
Subsequently the algebra of logic was improved by W. S. Jevons, E. Schröder, P. S. Poretsky, C. Peirce, G. Frege, who developed the theory of the propositional calculus, and D. Hilbert, who achieved success in applying the method of formalization in operations with logical propositions. Contributions were made by B. Russell, who together with A. Whitehead gave mathematical logic its modern form; I. I. Zhegalkin, whose merit was the further development of the calculus of classes and a significant simplification of the theory of logical-addition operations; V. I. Glivenko carried the subject of the algebra of logic far beyond the study of extensional operations with concepts.
The algebra of logic in its modern presentation deals with the study of operations on propositions, that is, on sentences that are characterized by only one quality — their truth value (true, false). In classical algebra of logic a proposition can have at any one time only one of two truth values: «true» or «false». The algebra of logic also studies propositions — functions, which can take the values «true» and «false» depending on what value is given to the variable entering the proposition — function.
Algebra – is a science that studies a set of certain elements and actions (operations) on them. If the elements of the algebra – are natural numbers, and the operations – are addition and multiplication, then this is the algebra of natural numbers. Vector algebra studies actions with directed segments (vectors).
The objects of propositional algebra are propositions. A proposition – is a true or false declarative sentence. A declarative sentence that speaks of a single event is called a simple proposition. For example, the sentence «The Moon – is a satellite of the Earth» is a simple proposition, while the sentence «Do not litter!» is not a proposition.
The basic elements with which the algebra of logic operates are propositions.
Propositions are built over the set {B, 
, 
, 
, 0, 1}, where B — is a non-empty set on whose elements three operations are defined:
negation (a unary operation),
conjunction (binary),
disjunction (binary),
and the logical zero 0 and the logical one 1 — are constants.
The following names are also used
).
).The unary operation of negation in the text of formulas is written either as a symbol before the operand (
) or as a bar over the operand (
), which is more compact but in general less noticeable.
Propositions are denoted by capital letters of the Latin alphabet. If a proposition A is true, one writes A = 1, if false, one uses the notation A = 0.
As in other algebras, in propositional algebra actions are defined on its objects (propositions), by performing which one obtains new propositions. The combination of two propositions into one by means of the conjunction «AND» is called the operation of logical multiplication. The proposition obtained in this way is called the logical product. For example, proposition A – «Mushrooms grow in the forest», proposition B – «Lewis Carroll – is a mathematician»; let us form the product of these propositions AB – «Mushrooms grow in the forest and Lewis Carroll – is a mathematician». The truth of the product of propositions depends on the truth of the propositions being multiplied and can be determined by means of the following table:
| A | B | AB |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
The combination of two propositions into one by means of the conjunction «OR», used in the non-exclusive sense, is called the operation of logical addition. For example, proposition A – «December – is a winter month», B – «In summer it sometimes rains»; let us define the proposition A+B – «December – is a winter month or in summer it sometimes rains». The truth of the logical sum can be established by means of the following table:
| A | B | A+B |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
The operation of logical negation is performed on a single proposition. To perform the operation of logical negation (denoted 
) – means to obtain from the given proposition a new one, by attaching the words «it is not true that …» to the whole proposition. The truth of the proposition 
is determined by the table:
| A |  |
| 1 | 0 |
| 0 | 1 |
Using the operations defined above, one can form compound propositions from simple ones. For example, all possible values for the proposition 
can be written in the form of a table
| A | B |  |
A |
|
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
, involutivity of negation, the law of double-negation elimination
Among propositions a special place is occupied by those in whose truth table there are either only ones or only zeros. This means that the proposition is either always true or always false, regardless of the truth of the propositions entering it. For example, the proposition 
is always true, and the proposition 
is always false. This can be proved by constructing the truth table of these propositions.
Compound propositions that are true for any values of the other propositions entering them are called identically true, and propositions that are false for any values of the other propositions entering them are called identically false.
Identically true or identically false propositions, if they occur in formulas, are replaced in them respectively by one or zero:
, 
.
Among propositions there are those whose truth tables coincide. These propositions are called equivalent. Equivalent are, for example, the propositions 
and 
(that is 
). This can be checked by constructing the truth tables of these propositions:
|
A |
B |
|
 |
 |
|
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
The operations of propositional algebra have the following important properties:
| Logical multiplication: | Logical addition: |
| A·B = B·A | A + B = B + A |
| (AB)C = A(BC) | (A + B)+ C = A + (B + C) |
| A·A = A | A + A = A |
| A·1 = A | A + 1 = 1 |
| A·0 = 0 | A + 0 = A |
| A(B + C) = AB + AC | A + BC = (A + B)(A + C)A + BC = (A + B)(A + C) |
 |
 |
Negation:
The formulas highlighted in bold are called the formulas of Augustus De Morgan (1806–1871). Using these formulas one can, in particular, transform propositions: replace complex ones with simpler ones.
In propositional algebra, as in other algebras, identity transformations are possible, but logical addition and multiplication have specific properties A + A = A, AA = A, A + 1 = A. This leads to the unusual nature of actions on the polynomials of propositional algebra. Suppose we need to multiply two compound propositions:
(A + B)(A + C) = AA + AC + AB + BC = A + AB + AC + BC.
Consider now the first two summands A + AB = A(1 + B) = A1 = A and similarly A+ AC = A. Thus, we finally obtain (A + B)(A + C) = A+ BC.
The transformation A + AB = A occurs very often in propositional algebra and is called «absorption». There is another kind of equally frequently occurring identity transformation, which is called «gluing».
Its essence is as follows: 
(the gluing occurred over the symbol B). Correspondingly, for the compound proposition 
the gluing can be performed over the symbol 
, that is, the identity transformation holds 
.
The laws of propositional algebra considered above can be applied to solving logic puzzles. For example:
Problem:
Alyosha, Borya and Grisha dug up an ancient vessel. About where and when it was made, each of the schoolboys made two conjectures:
Alyosha: «This vessel is Greek and the vessel was made in the 5th century»;
Borya: «This vessel is Phoenician and the vessel was made in the 3rd century»;
Grisha: «This is not a Greek vessel and it was made in the 4th century».
The history teacher told the boys that each of them is right in only one of his two conjectures. Where and in what century was the vessel made?
Solution:
Let us introduce notations for the simple propositions:
«This vessel is Greek» – 
;
«This vessel is Phoenician» – F;
«The vessel was made in the 5th century» – 5;
«The vessel was made in the 3rd century» – 3;
«The vessel was made in the 4th century» – 4.
One can compose the formulas of the propositions of each of the schoolboys, taking into account the teacher's statement. The formula of Alyosha's proposition has the form G5. The teacher said that Alyosha is right in only one of his statements, therefore either G = 1, or 5 = 1. The true proposition will be 
, that is the proposition «The vessel is Greek and was not made in the 5th century, or the vessel is not Greek and was made in the 5th century». Similarly, Borya's proposition can be represented by the formula 
and Grisha's proposition by the formula 
.
The obtained formulas can be regarded as logical equations and the system solved:
.
The first proposition is multiplied by the second:
.
The product 
– is false because the vessel cannot be made simultaneously in Greece and Phoenicia; the product 
– is false because the vessel cannot be made simultaneously in the 3rd and 5th centuries. After excluding these propositions, the following equation is obtained: 
. This equation is multiplied by the third logical equation of the composed system:
.
The propositions 
are excluded as false. From the obtained proposition 
it follows that «The vessel was made in Phoenicia and the vessel was made in the 5th century». This statement is consistent with the data of the posed problem.
The example of solving a logic puzzle demonstrates the semantic interconnection of the simple propositions entering a compound proposition. Compound propositions may include propositions interconnected in meaning; however, propositions may also be contradictory. Thus, one of the applications of propositional algebra is its use for analyzing complex, and at times contradictory, texts. Propositional algebra makes it possible to learn to model the simplest thought processes. «These methods enable you to acquire clarity of thought, the ability to find your own original solution to difficult problems, cultivate in you the habit of systematic thinking and, what is especially valuable, the ability to detect the logical errors, flaws and gaps of those who have not tried to master the attractive art of logic. Try it. That is all I ask of you», – Lewis Carroll (the pseudonym of Charles Lutwidge Dodgson (1832–1898)) – a well-known English mathematician and man of letters.
Comments