Introduction
Study questions:
Concepts and definitions of mathematical logic.
Basic operations of propositional algebra.
Laws and consequences of Boolean algebra.
Conclusion
Introduction
The theoretical basis for the construction of computers are special mathematical disciplines. One of them is the algebra of logic, or Boolean algebra (J. Boole is an English mathematician of the 19th century, the founder of this discipline). Its apparatus is widely used to describe computer circuits, their design and optimization.
1. Concepts and definitions of mathematical logic.
Logics- a science that studies the laws and forms of thinking; the doctrine of methods of reasoning and evidence.
Mathematical logic (theoretical logic, symbolic logic) is a branch of mathematics that studies the proofs and questions of the foundations of mathematics. "The subject of modern mathematical logic is varied." According to the definition of P. S. Poretsky, "mathematical logic is logic by subject, mathematics by method." According to the definition of N. I. Kondakov, “mathematical logic is the second, after traditional logic, stage in the development of formal logic, applying mathematical methods and a special apparatus of symbols and exploring thinking with the help of calculus (formalized languages).” This definition corresponds to the definition of S. K. Kleene: mathematical logic is "the logic developed with the help of mathematical methods." Also, A. A. Markov defines modern logic as “an exact science that applies mathematical methods.” All these definitions do not contradict, but complement each other.
The use of mathematical methods in logic becomes possible when judgments are formulated in some exact language. Such precise languages have two sides: syntax and semantics. Syntax is a set of rules for constructing language objects (usually called formulas). Semantics is a set of conventions that describe our understanding of formulas (or some of them) and allow us to consider some formulas to be true and others not.
Mathematical logic studies the logical connections and relationships underlying logical (deductive) inference, using the language of mathematics.
The laws of the world, the essence of objects, the common in them, we learn through abstract thinking. The main forms of abstract thinking are concepts, judgments and inferences.
concept- a form of thinking that reflects the essential features of an individual object or class of homogeneous objects. Concepts in language are expressed in words.
The scope of the concept- a set of objects, each of which has attributes that make up the content of the concept. The concepts of general and singular are distinguished.
The following relations of concepts are distinguished by volume:
identity or coincidence of volumes, meaning that the volume of one concept is equal to the volume of another concept;
subordination or inclusion of volumes: the volume of one of the concepts is fully included in the volume of the other;
exception volumes - a case in which there is not a single feature that would be in two volumes;
intersection or partial coincidence of volumes;
subordination volumes - the case when the volumes of two concepts, excluding each other, are included in the volume of the third.
Judgment- this is a form of thinking in which something is affirmed or denied about objects, signs or their relations.
inference- a form of thinking, through which from one or more judgments, called premises, we, according to certain rules of inference, obtain a judgment-conclusion.
Algebra in the broad sense of the word, the science of general operations similar to addition and multiplication, which can be performed not only on numbers, but also on other mathematical objects.
Algebra of logic (propositional algebra, Boolean algebra 1 ) - a branch of mathematical logic, which studies logical operations on statements. Most often it is assumed (so-called binary or binary logic, in contrast to, for example, ternary logic) that statements can only be true or false.
Examples of algebras: algebra of natural numbers, algebra of rational numbers, algebra of polynomials, algebra of vectors, algebra of matrices, algebra of sets, etc. The objects of the algebra of logic or Boolean algebra are propositions.
statement- this is any sentence of any language (statement), the content of which can be determined as true or false.
Any statement or true, or false; it cannot be both at the same time.
In natural language, utterances are expressed in declarative sentences. Exclamatory and interrogative sentences are not statements.
Statements can be expressed using mathematical, physical, chemical and other signs. From two numerical expressions, statements can be made by connecting them with equal or inequality signs.
The statement is called simple(elementary) if no part of it is itself a statement.
A statement made up of simple statements is called composite(difficult).
Simple statements in the algebra of logic are denoted by capital Latin letters:
A= (Aristotle is the founder of logic),
IN= (Bananas grow on apple trees).
Justification of the truth or falsity of simple statements is decided outside the algebra of logic. For example, the truth or falsity of the statement: "The sum of the angles of a triangle is 180 degrees" is established by geometry, and - in Euclid's geometry this statement is true, and in Lobachevsky's geometry it is false.
A true statement is assigned 1, a false one - 0. Thus, A = 1, IN = 0.
The algebra of logic is abstracted from the semantic content of statements. She is interested in only one fact - the given statement is true or false, which makes it possible to determine the truth or falsity of compound statements by algebraic methods.
Introduction
The theme of the test is "Mathematical Logic".
BOOL or BOOL, as well as BUUL, George (1815-1864) - English mathematician, who is considered the founder of mathematical logic.
Mathematical logic is a branch of mathematics devoted to the analysis of reasoning methods, while, first of all, the forms of reasoning are studied, and not their content, i.e. the formalization of reasoning is studied.
The formalization of reasoning goes back to Aristotle. Aristotelian (formal) logic acquired its modern form in the second half of the 19th century in the work of George Boole “The Laws of Thought”.
Intensively mathematical logic began to develop in the 50s of the XX century in connection with the rapid development of digital technology.
1. Elements of mathematical logic
The main branches of mathematical logic are the propositional calculus and the predicate calculus.
A proposition is a sentence that can be either true or false.
The propositional calculus is an introductory section of mathematical logic that deals with logical operations on propositions.
A predicate is a logical function of n variables that takes values of true or false.
Predicate calculus is a branch of mathematical logic, the object of which is the further study and generalization of propositional calculus.
The theory of Boolean algebras (Boolean functions) is the basis for exact methods of analysis and synthesis in the theory of switching circuits in the design of computer systems.
1.1 Basic concepts of the algebra of logic
The algebra of logic is a branch of mathematical logic that studies logical operations on propositions.
In algebra, logicians are only interested in the truth value of propositions. Truth values are usually denoted:
1 (true) 0 (false).
Each logical operation corresponds to a function that takes the values 1 or 0, whose arguments also take the values 1 or 0.
Such functions are called logical or boolean, or functions of the algebra of logic (FAL). In this case, the logical (Boolean) variable x can only take two values:
.Thus,
- a logical function, in which the logical variables are statements. Then the logical function itself is a complex proposition.In this case, the algebra of logic can be defined as a collection of a set of logical functions with all kinds of logical operations specified in it. Such logical operations as conjunction (read AND), disjunction ( OR), implication, equivalence, negation ( NOT), correspond to logical functions, for which the designations are accepted
(&, ), ~, - (), and there is a truth table:| x~y | ||||||
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
This is a tabular way to set the FAL. Along with them, functions are specified using formulas in a language containing variables. x , y , …, z(possibly indexed) and symbols of some specific functions - an analytical way to set the FAL.
The most common is the language containing logical symbols
~, –. The formulas of this language are defined as follows:1) all variables are formulas;
2) if P And Q- formulas, then
P ~ Q, - formulas.For example, the expression
~ - formula. If variable x , y , z assign values from the binary set 0, 1 and perform calculations in accordance with the operations indicated in the formula, then we get the value 0 or 1.They say that the formula implements the function. So the formula
~ implements the function h (x , y , z):| x | y | z | h (x, y, z) |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Let P And Q– formulas that implement functions f (x 1 , x 2 , …, x n) And g (x 1 , x 2 , …, x n). The formulas are: P = Q if the functions f And g match, i.e. their truth tables match. An algebra whose main set is the entire set of logical functions, and whose operations are disjunction, conjunction, and negation, is called the Boolean algebra of logical functions.
Let us present the laws and identities that define the operations
– and their connection with operations , ~:1. Idempotence of conjunction and disjunction:
.2. Commutativity of conjunction and disjunction:
.3. Associativity of conjunction and disjunction:
.4. Distributivity of conjunction with respect to disjunction and disjunction with respect to conjunction:
.
5. Double negation:
.6. Laws of de Morgan:
=, =.7. Bonding:
.8. Absorption
.9. Actions with constants 0 and 1.
The main idea of mathematical logic is the formalization of knowledge and reasoning. It is known that the most easily formalized knowledge is mathematical. Thus, mathematical logic is essentially the science of mathematics, or metamathematics. The central concept of mathematical logic is ``mathematical proof''. Indeed, "proof" (in other words, deductive) reasoning is the only kind of reasoning recognized in mathematics. Reasoning in mathematical logic is studied in terms of form, not meaning. Essentially, reasoning is modeled by a purely ``mechanical'' process of rewriting text (formulas). This process is called withdrawal. They also say that mathematical logic operates only with syntactic concepts. However, it is usually still important how the reasoning relates to reality (or our ideas). Therefore, one must still keep in mind a certain meaning of the formulas and the derivation. In this case, the term semantics is used (synonymous with the word ``sense"") and the syntax and semantics are clearly separated. When people are really only interested in syntax, the term ``formal system'' is often used. We will use a synonym for this term - ``calculus"" (the terms ``formal theory"" and ``axiomatics"") are also used. The object of formal systems are lines of text (sequences of characters), with the help of which formulas are written.
A formal system is defined if:
An alphabet is specified (a set of symbols used to build formulas).
A set of formulas, called axioms, has been singled out. These are starting points in conclusions.
A set of inference rules is given that allow one to obtain a new formula from some formula (or a set of formulas).
Basic principles of operations
Negation
The negation of a logical proposition is a logical proposition that takes the value "true" if the original proposition is false, and vice versa. This is a special logical operation. Depending on the location, external and internal negation are distinguished, the properties and roles of which differ significantly.
1. External negation (propositional) serves to form a complex statement from another (not necessarily simple) statement. It affirms the absence of the state of affairs described in the denied statement. Traditionally, a negative proposition is said to be true if, and only if, the negated proposition is false. In natural language, negation is usually expressed by "it is not true that" followed by the negative statement.
In the languages of formal theories, negation is a special unary propositional connective used to form another, more complex formula from one formula. For negation notation, the symbols "negation", "-" or "-- 1" are usually used. In classical propositional logic, the formula -A is true if and only if the formula A is false.
However, in non-classical logic, negation may not have all the properties of classical negation. In this regard, a completely logical question arises about the minimum set of properties that a certain unary operation must satisfy in order to be considered a negation, as well as about the principles for classifying various negations in non-classical formal theories (see: Dunn J.M. and Hardegree G.M. Algebraic Methods in Philosophical Logic, Oxford, 2001).
In fact, the above traditional understanding of external (propositional) negation can be expressed through the system of the following requirements: (I) If A is true (false), then non-A is false (true); (II) If not-A is true (false), then A is false (true). Formally, the requirements (I) and (II) can be expressed through the condition (1) However, it turns out that condition (1) can be decomposed into two weaker conditions: (2) "counterposition" and "introduction of double negation". As a result, it becomes possible to identify a subminimal negation that satisfies condition (2), but does not satisfy condition (3). It is natural to formulate a condition inverse to (3) and formalizing the principle of "removal of double negation": ( 4) --.- A = A. The minimal negation (i.e., satisfying condition (1) or conditions (2) and (3) together) for which condition (4) is satisfied is called de Morgan's negation. Minimal negation, satisfying the additional property (5): If A -- * B, then for any C it is true that A p C ("the absurdity property") -- is called intuitionistic negation. It is possible to formulate the principle (6), which is dual to the principle of absurdity: If B |=Au - S p A, then for any C it is true that C p A. Satisfying this principle of negation. is a form of negation in paraconsistent logic. Finally, de Morgan's negation (properties (2), (3), (4)), for which (5) or (6) holds, is called ortho-negation. negation is called Boole's negation, or classical negation.
2. Internal negation is part of a simple statement. Distinguish between negation in the composition of the bundle (negative bundle) and terminal negation.
Negation in the composition of the link is expressed using the particle "not" before the link-verb (if any) or before the semantic verb. It serves to express judgments about the absence of some kind of relationship (“Ivan does not know Peter”), or to form a negative predicative link as part of categorical attributive judgments.
Term negation is used to form negative terms. It is expressed through the prefix "not" or close to it in meaning ("All unripe apples are green").
Conjunction
The conjunction of two logical statements is a logical statement, true only when they are simultaneously true (from Latin conjunctio - union, connection), in a broad sense - a complex statement formed with the help of the union "and". In principle, one can speak of the conjunction of an infinite number of propositions (for example, the conjunction of all true sentences in mathematics). In logic, a conjunction is a logical connective (operation, function; denoted by: &,); a complex statement formed with its help is true only if its components are equally true. In classical propositional logic, conjunction together with negation constitute a functionally complete system of propositional connectives. This means that any other propositional connective can be defined through them. One of the properties of a conjunction is commutativity (that is, the equivalence of A & B and B & A). However, sometimes they speak of a non-commutative, i.e., ordered conjunction (an example of a statement from such a conjunction is: “The coachman whistled, and the horses galloped”).
Disjunction
The disjunction of two logical statements is a logical statement that is true only if at least one of them is true.
(from Latin disjunctio - separation, isolation), in a broad sense - a complex statement formed from two or more sentences using the union "or", expressing alternativeness, or choice.
In symbolic logic, a disjunction is a logical connective (operation, function) that forms a complex statement from sentences A and B, usually denoted as A V B, which is true if at least one of the two disjunctive terms is true: A or in.
In classical logic, disjunction together with negation forms a functionally complete system of propositional connectives, which makes it possible to define other propositional connectives through them.
Traditionally, it is customary to distinguish the considered (non-strict) disjunction from the strict (separative) disjunction, which is characterized by the fact that the corresponding statement is true under the condition that one and only one disjunctive term is true.
implication
The implication of two logical statements A and B is a logical statement that is false only when B is false and A is true (from Latin implicatio - plexus, from implico - I tightly connect) - a logical connective corresponding to the grammatical construction “if. ., then ... ”, with the help of which a complex statement is formed from two simple statements. In an implicative statement, an antecedent (base) is distinguished - a statement that comes after the word "if", and a consequent (consequence) - a statement that follows the word "then". An implicative statement represents in the language of logic a conditional statement of an ordinary language. The latter plays a special role, both in everyday and in scientific reasoning, its main function is to substantiate one by referring to something else.
The connection between the justifier and the justified, expressed by the conditional statement, is difficult to characterize in a general way, and only sometimes its nature is relatively clear. This connection can be, in particular, the connection of logical consequence that takes place between the premises and the conclusion of the correct conclusion ("If all living multicellular creatures are mortal and the jellyfish is such a creature, then it is mortal"). The connection can be a law of nature (“If a body is subjected to friction, it will begin to heat up”) or a causal relationship (“If the Moon is at a node in its orbit at a new moon, a solar eclipse occurs”). The connection under consideration may also have the character of social patterns, rules, traditions, etc. (“If the economy changes, politics also changes”, “If a promise is made, it must be kept”).
The connection expressed by the conditional presupposes that the consequent necessarily "follows" from the antecedent and that there is some general law, having been able to formulate which, we can logically deduce the consequent from the antecedent. For example, the conditional statement "If bismuth is a metal, it is plastic" implies the general law "All metals are plastic", making the consequent of this statement a logical consequence of its antecedent.
Both in ordinary language and in the language of science, the conditional statement, in addition to the function of justification, can also perform a number of other tasks. It can formulate a condition that is not related to the c.-l. an implied general law or rule (“If I want to, I will cut my cloak”), to fix some kind of sequence (“If last summer was dry, then this year it is rainy”), to express disbelief in a peculiar form (“If you solve the problem, I will prove Fermat's Great Theorem”), opposition (“If cabbage grows in the garden, then an apple tree grows in the garden”), etc. The multiplicity and heterogeneity of the functions of a conditional statement significantly complicates its analysis.
In logical systems, one abstracts from the peculiarities of the usual use of a conditional statement, which leads to various implications. The most famous of them are material implication, strict implication and relevant (relevant) implication.
Material implication is one of the main links in classical logic. It is defined as follows: the implication is false only if the antecedent is true and the consequent is false, and true in all other cases. The conditional "If A, then B" implies some real connection between what is said in A and B; the expression "A materially implies B" does not imply such a connection.
Strict implication is defined through the modal notion of (logical) impossibility: "A strongly implies B" means "It is impossible for A to be true and B false."
In relevant logic, implication is understood as a conditional conjunction in its usual sense. In the case of a relevant implication, it cannot be said that a true proposition can be justified by reference to any proposition and that any proposition can be justified by a false proposition.
Equivalence
The equivalence of two logical statements is a logical statement that is true only when they are both true or false (from late Latin equivalens - equivalent) - a generic name for all kinds of relations such as equality, i.e. reflexive, symmetric and transitive binary relations. Examples: equivalence (coincidence in meaning, meaning, content, expressive and (or) deductive possibilities between concepts, concepts, scientific theories or formal systems formalizing them) congruence or similarity of geometry, figures; isomorphism; equivalence of sets and other equivalence of any objects means their equality (identity) in some respect
(for example, isomorphic sets are indistinguishable in their "structure", if by "structure" we mean the totality of those properties with respect to which these sets are isomorphic). Any equivalence relation generates a partition of the set on which it is defined into pairwise non-intersecting "equivalence classes" in one class, the equivalent elements of this set are assigned to each other.
The consideration of equivalence classes as new objects is one of the main ways of generating (introducing) abstract concepts in logico-mathematical (and natural science in general) theories. So, considering fractions a/b and c/d with integer numerators and denominators equivalent, if ad=bc, rational numbers are introduced into consideration as classes of equivalent fractions; considering sets equivalent, between which it is possible to establish a one-to-one correspondence, they introduce the concept of cardinality (cardinal number) of a set (as a class of sets equivalent to each other); considering two pieces of matter equivalent, entering into identical chemical reactions under equal conditions, they come to the abstract concept of chemical composition, etc.
The term "equivalence" is often used not (only) as generic, but as a synonym for some of its particular meanings ("equivalence of theories" instead of "equivalence", "equivalence of sets" instead of "equivalence", "equivalence of words" in abstract algebra instead of "identity " and so on.).
quantifier statement
A quantifier with a universal quantifier.
A quantifier logical proposition with a universal quantifier ("xA(x))" is a logical proposition that is true only if, for each object x in the given collection, the proposition A(x) is true.
Quantifier with existential quantifier.
A quantified logical proposition with an existential quantifier ($xA(x)) is a logical proposition that is true only if, in the given collection, there exists an object x such that the proposition A(x) is true.
Structure of mathematical logic
The section "mathematical logic" consists of three parts: on the informal axiomatic method, on the logic of propositions and on the logic of predicates (of the first order). The axiomatic method of construction is the first step towards the formalization of the theory. Most of the problems considered in mathematical logic consist in proving certain statements. Mathematical logic has many branches. It uses a tabular construction of propositional logic, uses a special language of symbols and formulas of propositional logic.
Informal axiomatic method
An axiomatic method that does not fix the rigidly applied language and thus does not fix the boundaries of a meaningful understanding of the subject, but requires an axiomatic definition of all concepts special for a given subject of study. This term does not have a generally accepted definition.
The history of the development of the axiomatic method is characterized by an ever-increasing degree of formalization. The informal axiomatic method is a certain step in this process.
The original, given by Euclid, axiomatic construction of geometry was distinguished by the deductive nature of the presentation, which was based on definitions (explanations) and axioms (obvious statements). Consequences were drawn from them, relying on common sense and evidence. At the same time, the derivation sometimes implicitly used the assumptions of geometry, character, not fixed in the axioms, especially those related to the movement in space and the mutual arrangement of lines and points. Subsequently, geometry, concepts and the axioms regulating their use, implicitly used by Euclid and his followers, were revealed. At the same time, the question arose whether all the axioms were really revealed. The guiding principle for resolving this issue was formulated by D. Hilbert: "It should be ensured that one can speak with equal success instead of points, lines and planes about tables, chairs and beer mugs." If the proof does not lose its probative force after such a replacement, then indeed all the special assumptions used in this proof are fixed in the axioms. The degree of formalization achieved with this approach is the level of formalization characteristic of the informal axiomatic method. The classic work of D. Hilbert "Fundamentals of Geometry" can serve as a standard here.
The informal axiomatic method is used not only to give a certain completeness to an axiomatically expounded concrete theory. It is an effective tool for mathematical research. Since when studying a system of objects by this method, their specificity, or "nature", is not used, the proven statements are transferred to any system of objects that satisfies the considered axioms. According to the informal axiomatic method, axioms are implicit definitions of original concepts (rather than obvious truths). What are the objects under study - it does not matter. Everything you need to know about them is formulated in axioms. The subject of study of an axiomatic theory is any of its interpretations.
The informal axiomatic method, in addition to the indispensable axiomatic definition of all special concepts, has another characteristic feature. It is a free, non-axiomatic, content-based use of ideas and concepts that can be applied to any conceivable interpretation, regardless of its content. In particular, set-theoretic and logical concepts and principles, as well as concepts related to the idea of counting, etc. are widely used. on which the properties of an axiomatically given system of objects are formulated and proved. Fixing the language leads to the concept of a formal axiomatic system and creates a material basis for identifying and clearly describing acceptable logical principles, for the controlled use of set-theoretic and other general or non-special concepts for the area under study. If there are no means (words) in the language for conveying set-theoretic concepts, then all evidence based on the use of such means is eliminated. If the language has means for expressing certain set-theoretic concepts, then their use in proofs can be limited to certain rules or axioms.
By fixing the language in different ways, different theories of the main object of consideration are obtained. For example, considering the language of the narrow predicate calculus for group theory, one obtains an elementary group theory in which one cannot formulate any statement about subgroups. If we pass to the language of predicate calculus of the second stage, then it becomes possible to consider properties in which the concept of a subgroup appears. The formalization of the informal axiomatic method in group theory is the transition to the language of the Zermelo-Fraenkel system with its axiomatics.
Axiomatic Method
The axiomatic method is a method of constructing a scientific theory, in which it is based on some initial propositions (judgments) - axioms, or postulates, from which all other statements of this theory must be derived in a purely logical way, through evidence. The construction of science based on the axiomatic method is usually called deductive. All concepts of the deductive theory (except for a fixed number of initial ones) are introduced by means of definitions expressing them through previously introduced concepts. To one degree or another, deductive proofs characteristic of the axiomatic method are used in many sciences, but the main area of its application is mathematics, logic, and also some branches of physics.
The idea of the axiomatic method was first expressed in connection with the construction of geometry in ancient Greece (Pythagoras, Plato, Aristotle, Euclid). The modern stage of development of the axiomatic method is characterized by the concept of the formal axiomatic method put forward by Hilbert, which sets the task of accurately describing the logical means of deriving theorems from axioms. Hilbert's main idea is a complete formalization of the language of science, in which its judgments are considered as sequences of signs (formulas) that acquire meaning only with some specific interpretation. To derive theorems from axioms (and in general some formulas from others), special formulas are formulated. inference rules. The proof in such a theory (calculus, or formal system) is a certain sequence of formulas, each of which is either an axiom or is obtained from the previous formulas of the sequence according to some rule of inference. Unlike such formal proofs, the properties of the formal system itself as a whole are studied contain. by means of metatheory. The main requirements for axiomatic formal systems are consistency, completeness, and independence of the axioms. Hilbert's program, which assumed the possibility of proving the consistency and completeness of all classical mathematics, as a whole turned out to be unfeasible. In 1931 Gödel proved the impossibility of complete axiomatization of sufficiently developed scientific theories (for example, the arithmetic of natural numbers), which testified to the limitations of the axiomatic method. The basic principles of axiomatic methods have been criticized by proponents of intuitionism and constructive direction.
In the modern world, we are increasingly using a variety of machines and gadgets. And not only when it is necessary to apply literally inhuman strength: move the load, lift it to a height, dig a long and deep trench, etc. Robots today assemble cars, multicookers cook food, and calculators perform elementary arithmetic calculations. More and more often we hear the expression "Boolean algebra". Perhaps the time has come to understand the role of man in the creation of robots and the ability of machines to solve not only mathematical, but also
Logics
Translated from Greek, logic is an ordered system of thinking that creates relationships between given conditions and allows you to draw conclusions based on premises and assumptions. Quite often we ask each other: "Is it logical?" The received answer confirms our assumptions or criticizes the train of thought. But the process does not stop: we continue to reason.
Sometimes the number of conditions (introductory) is so great, and the relationships between them are so intricate and complex that the human brain is not able to "digest" everything at once. It may take more than one month (week, year) to understand what is happening. But modern life does not give us such time intervals for making decisions. And we resort to the help of computers. And this is where the algebra of logic appears, with its own laws and properties. Having loaded all the initial data, we allow the computer to recognize all the relationships, eliminate contradictions and find a satisfactory solution.
Mathematics and Logic
The famous Gottfried Wilhelm Leibniz formulated the concept of "mathematical logic", the problems of which were understandable only to a narrow circle of scientists. This direction did not arouse particular interest, and until the middle of the 19th century, few people knew about mathematical logic.
Of great interest in the scientific community was a dispute in which the Englishman George Boole announced his intention to create a branch of mathematics that has absolutely no practical application. As we remember from history, industrial production was actively developing at that time, all kinds of auxiliary machines and machine tools were being developed, that is, all scientific discoveries had a practical orientation.
Looking ahead, let's say that Boolean algebra is the most used part of mathematics in the modern world. So Bull lost his argument.
George Bull
The personality of the author deserves special attention. Even considering that in the past people grew up before us, it is still impossible not to note that at the age of 16, J. Buhl taught at a village school, and by the age of 20 he opened his own school in Lincoln. The mathematician was fluent in five foreign languages, and in his spare time he read the works of Newton and Lagrange. And all this is about the son of a simple worker!
In 1839, Boole first submitted his scientific papers to the Cambridge Mathematical Journal. The scientist is 24 years old. Boole's work so interested the members of the Royal Society that in 1844 he received a medal for his contribution to the development. Recall that Buhl himself had no education.
Idea
In principle, Boolean algebra is very simple. There are expressions) that, from the point of view of mathematics, can be defined with only two words: “true” or “false”. For example, in the spring the trees bloom - true, in the summer it snows - a lie. The beauty of this math is that there is no strict need to use only numbers. For the algebra of judgments, any statements with an unambiguous meaning are quite suitable.
Thus, the algebra of logic can be used literally everywhere: in scheduling and writing instructions, analyzing conflicting information about events, and determining the sequence of actions. The most important thing is to understand that it is completely unimportant how we determine the truth or falsity of the statement. These "hows" and "whys" need to be abstracted away. Only the statement of fact matters: true-false.
Of course, for programming, the functions of the algebra of logic are important, which are written with the corresponding signs and symbols. And to learn them means to master a new foreign language. Nothing is impossible.
Basic concepts and definitions
Without going into depth, let's deal with the terminology. So, Boolean algebra assumes the presence of:
- statements;
- logical operations;
- functions and laws.
Statements are any affirmative expressions that cannot be interpreted ambiguously. They are written as numbers (5 > 3) or formulated in familiar words (elephant is the largest mammal). At the same time, the phrase “the giraffe has no neck” also has the right to exist, only Boolean algebra will define it as “false”.
All statements must be unambiguous, but they can be elementary and compound. The latter use logical connectives. That is, in the algebra of judgments, compound statements are formed by adding elementary statements by means of logical operations.
Boolean algebra operations
We already remember that operations in the algebra of judgments are logical. Just as number algebra uses arithmetic operations to add, subtract, or compare numbers, elements of mathematical logic allow you to make complex statements, give negations, or calculate the final result.
For formalization and simplicity, logical operations are written by formulas familiar to us in arithmetic. The properties of Boolean algebra make it possible to write equations and calculate unknowns. usually written using a truth table. Its columns define the calculation elements and the operation that is performed on them, and the rows show the result of the calculation.
Basic logical actions
The most common operations in Boolean algebra are negation (NOT) and logical AND and OR. Almost all actions in the algebra of judgments can be described in this way. Let's take a closer look at each of the three operations.
Negation (not) applies to only one element (operand). Therefore, the negation operation is called unary. To write the concept of "not A" use the following symbols: ¬A, A¯¯¯ or!A. In tabular form, it looks like this:
The following statement is characteristic of the negation function: if A is true, then B is false. For example, the Moon revolves around the Earth - true; The earth revolves around the moon - a lie.
Boolean multiplication and addition
The logical AND is called the conjunction operation. What does it mean? First, that it can be applied to two operands, i.e. AND is a binary operation. Secondly, that only in the case of the truth of both operands (both A and B) is the expression itself true. The proverb "Patience and work will grind everything" suggests that only both factors will help a person cope with difficulties.
Symbols used for writing: A∧B, A⋅B or A&&B.
A conjunction is similar to multiplication in arithmetic. Sometimes they say so - logical multiplication. If we multiply the elements of the table by rows, we get a result similar to logical reasoning.
A disjunction is a logical OR operation. It takes the value of truth when at least one of (either A or B). It is written like this: A∨B, A+B or A||B. The truth tables for these operations are:
Disjunction is like arithmetic addition. The logical addition operation has only one limitation: 1+1=1. But we remember that in digital format, mathematical logic is limited to 0 and 1 (where 1 is true, 0 is false). For example, the statement “in a museum you can see a masterpiece or meet an interesting interlocutor” means that you can see works of art, or you can meet an interesting person. At the same time, the variant of the simultaneous accomplishment of both events is not excluded.
Functions and laws
So, we already know what logical operations Boolean algebra uses. Functions describe all the properties of elements of mathematical logic and allow you to simplify complex compound conditions of problems. The most understandable and simple property seems to be the rejection of derived operations. Derivatives are exclusive OR, implication and equivalence. Since we have studied only the basic operations, we will also consider the properties only of them.
Associativity means that in statements like "and A, and B, and C," the order of the listing of the operands does not matter. The formula will write it like this:
(A∧B)∧V=A∧(B∧V)=A∧B∧V,
(A∨B)∨C=A∨(B∨C)=A∨B∨C.
As you can see, this is characteristic not only of conjunction, but also of disjunction.
commutativity states that the result of a conjunction or disjunction does not depend on which element was considered first:
A∧B=B∧A; A∨B=B∨A.
distributivity allows you to expand brackets in complex logical expressions. The rules are similar to opening brackets in multiplication and addition in algebra:
A∧(B∨B)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
One and zero properties, which can be one of the operands, are also analogous to algebraic multiplication by zero or one and addition by one:
A∧0=0,A∧1=A; A∨0=A,A∨1=1.
Idempotency tells us that if, with respect to two equal operands, the result of the operation turns out to be similar, then we can “throw out” the extra operands that complicate the course of reasoning. Both conjunction and disjunction are idempotent operations.
B∧B=B; B∨B=B.
Absorption also allows us to simplify equations. Absorption states that when another operation with the same element is applied to an expression with one operand, the result is the operand from the absorbing operation.
A∧B∨B=B; (A∨B)∧B=B.
Sequence of operations
The sequence of operations is of no small importance. Actually, as for algebra, there is a priority of functions that Boolean algebra uses. Formulas can be simplified only if the significance of the operations is observed. Ranking from the most significant to the least, we get the following sequence:
1. Denial.
2. Conjunction.
3. Disjunction, exclusive OR.
4. Implication, equivalence.
As you can see, only negation and conjunction do not have equal priorities. And the priority of disjunction and XOR are equal, as well as the priorities of implication and equivalence.
Implication and equivalence functions
As we have already said, in addition to the basic logical operations, mathematical logic and the theory of algorithms use derivatives. The most commonly used are implication and equivalence.
An implication, or logical consequence, is a statement in which one action is a condition, and the other is a consequence of its implementation. In other words, this is a sentence with "if ... then" prepositions. "If you like to ride, love to carry sleds." That is, for skiing, you need to tighten the sled up the hill. If there is no desire to move down the mountain, then you don’t have to carry the sled. It is written like this: A→B or A⇒B.
Equivalence implies that the resulting action occurs only if both operands are true. For example, night turns into day when (and only when) the sun rises over the horizon. In the language of mathematical logic, this statement is written as follows: A≡B, A⇔B, A==B.
Other laws of Boolean algebra
The algebra of judgments is developing, and many interested scientists have formulated new laws. The postulates of the Scottish mathematician O. de Morgan are considered the most famous. He noticed and defined such properties as close negation, complement and double negation.
close denial assumes that there is no negation before the parenthesis: not (A or B) = not A or NOT B.
When an operand is negated, regardless of its value, one speaks of addendum:
B∧¬B=0; B∨¬B=1.
And finally twice no compensates for itself. Those. either the negation disappears before the operand, or only one remains.
How to solve tests
Mathematical logic implies the simplification of given equations. Just as in algebra, you must first ease the condition as much as possible (get rid of complex inputs and operations with them), and then proceed to search for the correct answer.
What can be done to simplify? Convert all derived operations to simple ones. Then open all the brackets (or vice versa, take it out of brackets to shorten this element). The next step should be to apply the properties of Boolean algebra in practice (absorption, properties of zero and one, etc.).
Ultimately, the equation should consist of the minimum number of unknowns combined by simple operations. The easiest way to find a solution is to achieve a large number of close negatives. Then the answer will pop up by itself.
One of the names of modern logic, which came in the second. floor. 19 early 20th century instead of traditional logic. The term symbolic logic is also used as another name for the modern stage in the development of the science of logic. Definition… … Philosophical Encyclopedia
mathematical logic- SYMBOLIC LOGIC, mathematical logic, theoretical logic, the area of logic in which logical conclusions are investigated by means of logical calculus based on a strict symbolic language. The term L. With." was, apparently, the first time ... ... Encyclopedia of Epistemology and Philosophy of Science
MATHEMATICAL LOGIC- It is also called symbolic logic. M. l. this is the same Aristotelian syllogistic logic, but only cumbersome verbal conclusions are replaced in it by mathematical symbols. This achieves, firstly, brevity, secondly, clarity, in ... ... Encyclopedia of cultural studies
MATHEMATICAL LOGIC- MATHEMATICAL logic, deductive logic, using mathematical methods for studying the ways of reasoning (conclusions); mathematical theory of deductive reasoning methods ... Modern Encyclopedia
MATHEMATICAL LOGIC- deductive logic, including mathematical methods for studying methods of reasoning (conclusions); mathematical theory of deductive reasoning methods. Mathematical logic is also called the logic used in mathematics ... Big Encyclopedic Dictionary
MATHEMATICAL LOGIC- (symbolic logic), analytical section of logic, the result of applying mathematical methods to problems of classical logic. Considers concepts that can be true or false, the relationship between concepts and the operation of them, including ... ... Scientific and technical encyclopedic dictionary
MATHEMATICAL LOGIC- one of the leading sections of modern logic and mathematics. Formed in 1920 Art. as a realization of the idea of the possibility of writing down all the initial assumptions in the language of signs similar to mathematical ones and thereby replacing reasoning with calculations. ... ... The latest philosophical dictionary
mathematical logic- noun, number of synonyms: 1 logistics (9) ASIS synonym dictionary. V.N. Trishin. 2013 ... Synonym dictionary
mathematical logic- - Telecommunication topics, basic concepts of EN mathematical logic ... Technical Translator's Handbook
MATHEMATICAL LOGIC- theoretical logic, symbolic logic, a branch of mathematics devoted to the study of mathematical. proofs and questions of the foundations of mathematics. Historical essay. The idea of building a universal language for all mathematics and formalization based on ... ... Mathematical Encyclopedia
Books
- Mathematical logic, Ershov Yuri Leonidovich, Palyutin Evgeny Andreevich. The book outlines the basic classical calculus of mathematical logic: the propositional calculus and the predicate calculus; there is a summary of the main concepts of set theory and theory ... Buy for 1447 UAH (Ukraine only)
- Mathematical logic, YL Ershov. The book outlines the main classical calculus of mathematical logic: propositional calculus and predicate calculus; there is a summary of the basic concepts of set theory and theory ...
