Logics- a science that studies the laws and forms of thinking; the doctrine of methods of reasoning and evidence.
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.
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.
Every proposition is either 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:
BUT= (Aristotle is the founder of logic),
AT= (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, BUT = 1, AT = 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.
Basic operations of propositional algebra.
Logical operation CONJUNCTION(lat. conjunctio - I bind):
- in natural language corresponds to the union and;
- designation: & ;
- in programming languages the notation is: and;
- other name: logical multiplication.
A conjunction is a logical operation that associates each two simple statements with a compound statement that is true if and only if both original statements are true.
Conjunction truth table:
| BUT | AT | BUT&AT |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operation DISJUNCTION(lat. disjunctio - I distinguish):
Disjunction is a logical operation that associates each two simple statements with a compound statement that is false if and only if both original statements are false and true when at least one of the two statements that form it is true.
Disjunction truth table:
| BUT | AT | BUTAT |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Logical operation INVERSE(lat. inversio - turn over):
Negation is a logical operation that associates each simple statement with a compound statement, which consists in the fact that the original statement is negated.
Negative Truth Table:
| BUT | not A |
| 0 | 1 |
| 1 | 0 |
The logical addition function OR (LogValue1;LogValue2;…) evaluates to TRUE (True) only when at least one boolean argument is TRUE (1).
The logical negation function NOT(LogValue) evaluates to TRUE (True) when the logical argument is FALSE (0) and, conversely, the value FALSE (False) when the logical argument is TRUE (1).
Logical operation IMPLICATION(lat. implicatio - I closely associate):
An implication is a logical operation that associates every two simple statements with a compound statement that is false if and only if the condition (the first statement) is true and the consequence (the second statement) is false.
Implication truth table:
| BUT | AT | BUTAT |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operation EQUIVALENCE(lat. aequivalens - equivalent):
- in natural language corresponds to turns of speech then and only then and if and only if;
- designation: ~ ;
- other name: equivalence.
An equivalence is a logical operation that assigns to each two simple statements a compound statement that is true if and only if both original statements are both true or both false.
Equivalence truth table:
| BUT | AT | BUT~AT |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical operations have the following precedence: actions in brackets, inversion, &, , ~.
A table showing what values a compound statement takes for all combinations (sets) of values of its simple statements is called truth table compound utterance.
Compound statements in the algebra of logic are written using logical expressions. For any logical expression, it is enough to simply build a truth table.
The algorithm for constructing a truth table:
- count the number of variables n in a logical expression;
- determine the number of rows in a table m = 2 n ;
- count the number of logical operations in the formula;
- establish the sequence of execution of logical operations, taking into account brackets and priorities;
- determine the number of columns in the table: the number of variables plus the number of operations;
- write out sets of input variables, taking into account the fact that they are a natural series of n-bit binary numbers from 0 to 2 n -1;
- fill in the truth table by columns, performing logical operations in accordance with the sequence established in clause 4.
Sets of input variables, in order to avoid errors, are recommended to be listed as follows:
a) determine the number of sets of input variables;
b) divide the column of values of the first variable in half and fill the upper part of the column with 0, and the lower part -1;
c) divide the column of values of the second variable into four parts and fill each quarter with alternating groups of 0 or 1, starting with group 0;
d) continue dividing the columns of values of subsequent variables by 8, 16, etc. parts and filling them with groups 0 or 1 until groups 0 and 1 will not consist of one character.
Example. For the formula A&(B C), construct a truth table algebraically and using spreadsheets.
The number of boolean variables is 3, therefore, the number of rows in the truth table should be 2 3 = 8.
The number of logical operations in the formula is 5, therefore, the number of columns in the truth table should be 3 + 5 = 8.
| BUT | AT | C | ATC | BUT & (ATC) |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Boolean function call the function F(X 1, X 2, ..., X n), whose arguments X 1, X 2, ..., X n(independent variables) and the function itself (dependent variable) take the values 0 or 1.
A table showing what values a logical function takes on for all combinations of the values of its arguments is called the truth table of a logical function. Logic function truth table n arguments contains 2 n lines, n argument value columns and 1 function value column.
Logic functions can be specified in a tabular way or analytically - in the form of appropriate formulas.
If a logical function is represented using disjunctions, conjunctions and inversions, then this form of representation is called normal.
There are 16 different logical functions from two variables.
Boolean expressions called equivalent, if their truth values coincide for any values of the logical variables included in them.
In the algebra of logic, there are a number of laws that allow equivalent transformations of logical expressions. Let us present the relations reflecting these laws.
- The law of double negation:
not (not A) = A.
Double negation excludes negation. - Commutative (commutative) law:
- for logical addition:
A B = B A;
A&B=B&A.The result of the operation on statements does not depend on the order in which these statements are taken.
- Associative (associative) law:
- for logical addition:
(A B) C = A (B C);For logical multiplication:
(A & B) & C = A & (B & C).With the same signs, brackets can be placed arbitrarily or even omitted.
- Distributive (distributive) law:
- for logical addition:
(A B) & C = (A & C) (B & C);For logical multiplication:
(A & B) C = (A C) & (B C).Defines the rule for bracketing a general statement.
- Law of general inversion (de Morgan's laws):
- for logical addition:
;For logical multiplication:
. - The law of idempotence (from the Latin words idem - the same and potens - strong; literally - equivalent):
- for logical addition:
A A = A;For logical multiplication:
A&A=A.Law means no exponents.
- Constant exclusion laws:
- for logical addition:
A 1 = 1, A 0 = A;For logical multiplication:
A&1 = A, A&0 = 0. - The law of contradiction:
A & (not A) = 0.It is impossible for contradictory statements to be true at the same time.
- Law of exclusion of the third:
A (not A) = 1.Of the two contradictory statements about the same subject, one is always true, and the second is false, the third is not given.
- Absorption law:
- for logical addition:
A(A&B)=A;For logical multiplication:
A & (A B) = A. - The law of exclusion (gluing):
- for logical addition:
(A & B) (& B) = B;For logical multiplication:
(A B) & (B) = B. - Law of contraposition (reversal rule):
(AB) = (BA).The validity of the above laws can be proved in a tabular way: write out all sets of values A and B, calculate the values of the left and right parts of the expression being proved on them, and make sure that the resulting columns match.
Example. Simplify the boolean expression:
- Efimova O., Morozov V., Ugrinovich N. Course of computer technology with the basics of informatics. Textbook for senior classes. - M.: LLC "AST Publishing House"; ABF, 2000
- Taskbook-workshop on informatics. In 2 volumes / Ed. I.Semakina, E.Khenner. - M.: Basic Knowledge Laboratory, 2001
- Ugrinovich N. Informatics and information technologies. Grade 10-11 - M .: Basic Knowledge Laboratory, JSC "Moscow textbooks", 2001
Tasks and tests on the topic "Fundamentals of formal logic"
- Access DBMS Logic - Logical and mathematical models Grade 10
Lessons: 5 Assignments: 9 Quizzes: 1
- Solving logical problems by means of mathematical logic
Lessons: 4 Assignments: 6 Tests: 1
Dear student!
Work 1 presents three topics that form the basis of the course "Information Technology". We hope that you already have minimal experience with a computer and got acquainted with its device in middle school.
The topic "Computer communications. Internet" is of great interest lately, many young people spend almost all their free time in the global network. I would like to remind you that mastery of the Internet implies not only the ability to “surf” the network and visit interesting “chats” from time to time, but also understand the principles of organizing information in the global network, understand its structure, protocols, be able to configure the browser and e-mail programs, to know and observe the ethics of working on the Internet, and of course to use the network for its most important purpose - to expand one's horizons.
We did not cover the technology of creating Web sites in this course, believing that the minimum knowledge for creating a web home page can be gleaned from additional literature. Creating sites at a professional level requires some training, which is based on the skills of working with text and graphics, as well as the ability to program.
The topic "Logic" usually causes some confusion among students, not everyone understands the importance of studying this topic. I would like to note that knowledge of logic is important not only as a basis for further study of programming languages and principles of working with databases, but also as a "simulator" for the development of a special type of thinking. A person who excels in the study of logic has tremendous advantages in communication. It is very flattering to hear in your address: "It is logical", "there is logic in your reasoning."
The lesson on informatics is designed for students of the 10th grade of a general education school, the curriculum of which includes the section "Algebra of Logic". This topic is very difficult for students, so I, as a teacher, wanted to interest them in studying the laws of logic, simplifying logical expressions and approaching the solution of logical problems with interest. In the usual form, giving lessons on this topic is tedious and troublesome, and some definitions are not always clear to the children. In connection with the provision of information space, I had the opportunity to post my lessons in the “learning” shell. Students, having registered in it, can attend this course in their free time and reread what was not clear in the lesson. Some students, having missed lessons due to illness, make up for the missed topic at home or at school and are always ready for the next lesson. This form of teaching suited many children very much, and those laws that were incomprehensible to them are now learned in computer form much easier and faster. I offer one of these informatics lessons, which is conducted integratively with ICT.
Lesson plan
- Explanation of new material, with the involvement of a computer - 25 minutes.
- Basic concepts and definitions laid out in "learning" - 10 minutes.
- Material for the curious - 5 minutes.
- Homework - 5 minutes.
1. Explanation of new material
Laws of formal logic
The simplest and most necessary true connections between thoughts are expressed in the basic laws of formal logic. These are the laws of identity, non-contradiction, excluded middle, sufficient reason.
These laws are fundamental because in logic they play a particularly important role, they are the most general. They allow you to simplify logical expressions and build inferences and proofs. The first three of the above laws were identified and formulated by Aristotle, and the law of sufficient reason - by G. Leibniz.
The law of identity: in the process of a certain reasoning, every concept and judgment must be identical to itself.
The law of non-contradiction: it is impossible that one and the same eye at the same time be and not be inherent in the same thing in the same respect. That is, it is impossible to affirm and deny something at the same time.
Law of the excluded middle: of two contradictory propositions, one is true, the other is false, and the third is not given.
Law of Sufficient Reason: Every true thought must be sufficiently justified.
The last law says that the proof of something presupposes the justification of precisely and only true thoughts. False thoughts cannot be proven. There is a good Latin proverb: "To err is common to every person, but only a fool is to insist on a mistake." There is no formula for this law, since it has only a substantive character. True judgments, factual material, statistical data, laws of science, axioms, proven theorems can be used as arguments to confirm a true thought.
Laws of Propositional Algebra
Algebra of propositions (algebra of logic) is a section of mathematical logic that studies logical operations on propositions and the rules for transforming complex propositions.
When solving many logical problems, it is often necessary to simplify the formulas obtained by formalizing their conditions. Simplification of formulas in the algebra of propositions is carried out on the basis of equivalent transformations based on the basic logical laws.
The laws of the algebra of propositions (algebra of logic) are tautologies.
Sometimes these laws are called theorems.
In propositional algebra, logical laws are expressed as equality of equivalent formulas. Among the laws, those that contain one variable are especially distinguished.
The first four of the following laws are the basic laws of propositional algebra.
Identity law:
Every concept and judgment is identical to itself.
The law of identity means that in the process of reasoning one cannot replace one thought with another, one concept with another. If this law is violated, logical errors are possible.
For example, discussion They say correctly that the tongue will bring you to Kyiv, but I bought smoked tongue yesterday, which means that now I can safely go to Kyiv incorrect, since the first and second words "language" denote different concepts.
In discussion: Movement is eternal. Going to school is movement. Therefore, going to school is forever the word "motion" is used in two different senses (the first - in the philosophical sense - as an attribute of matter, the second - in the ordinary sense - as an action to move in space), which leads to a false conclusion.
Law of non-contradiction:
A proposition and its negation cannot be true at the same time. That is, if the statement BUT is true, then its negation not A must be false (and vice versa). Then their product will always be false.
It is this equality that is often used when simplifying complex logical expressions.
Sometimes this law is formulated as follows: two statements that contradict each other cannot be true at the same time. Examples of non-compliance with the law of non-contradiction:
1. There is life on Mars and there is no life on Mars.
2. Olya graduated from high school and is in the 10th grade.
Law of the excluded middle:
At the same moment in time, the statement can be either true or false, there is no third. True either BUT, or not A. Examples of the implementation of the law of the excluded middle:
1. The number 12345 is either even or odd, there is no third.
2. The company is operating at a loss or breakeven.
3. This liquid may or may not be an acid.
The law of the excluded middle is not a law recognized by all logicians as a universal law of logic. This law is applied where knowledge deals with a rigid situation: "either - or", "true-false". Where there is uncertainty (for example, in reasoning about the future), the law of the excluded middle often cannot be applied.
Consider the following statement: This suggestion is false. It cannot be true because it claims to be false. But it cannot be false either, because then it would be true. This statement is neither true nor false, and therefore the law of the excluded middle is violated.
Paradox(Greek paradoxos - unexpected, strange) in this example arises from the fact that the sentence refers to itself. Another famous paradox is the hairdresser problem: In one city, a hairdresser cuts the hair of all residents, except for those who cut their own hair. Who cuts the barber's hair? In logic, because of its formality, it is not possible to obtain the form of such a self-referential statement. This once again confirms the idea that with the help of the algebra of logic it is impossible to express all possible thoughts and arguments. Let us show how, based on the definition of propositional equivalence, the rest of the laws of the propositional algebra can be obtained.
For example, let's define what is equivalent to (equivalent to) BUT(twice no BUT, i.e. negation of negation BUT). To do this, we will build a truth table:
By definition of equivalence, we must find the column whose values match the values of the column BUT. This will be the column BUT.
Thus, we can formulate double lawnegations:
If we negate some statement twice, then the result is the original statement. For example, the statement BUT= Matroskin- cat is equivalent to saying A = It is not true that Matroskin is not a cat.
Similarly, the following laws can be derived and verified:
Constant properties:
Laws of idempotency:
No matter how many times we repeat: TV on or TV on or TV on... the meaning of the sentence will not change. Likewise from repetition It's warm outside, it's warm outside... not one degree warmer.
The laws of commutativity:
A v B = B v A
A & B = B & A
operands BUT and AT in the operations of disjunction and conjunction can be interchanged.
Associativity laws:
A v(B v C) = (A v B) v C;
A & (B & C) = (A & B) & C.
If the expression uses only the disjunction operation or only the conjunction operation, then you can neglect the brackets or arrange them arbitrarily.
Distributivity laws:
A v (B & C) = (A v B) &(A v C)
(distributive disjunction
regarding conjunction)
A & (B v C) = (A & B) v (A & C)
(distributivity of the conjunction
regarding disjunction)
The distributive law of conjunction with respect to disjunction is similar to the distributive law in algebra, but the law of distributive disjunction with respect to conjunction has no analogue, it is valid only in logic. Therefore, it needs to be proven. The proof is best done using a truth table:
Absorption laws:
A v (A & B) = A
A & (A v B) = A
Carry out the proof of the absorption laws yourself.
De Morgan's laws:
Verbal formulations of de Morgan's laws:
Mnemonic rule: on the left side of the identity, the operation of negation stands above the entire statement. On the right side, it seems to be broken and negation stands above each of the simple statements, but at the same time the operation changes: disjunction to conjunction and vice versa.
Examples of the implementation of de Morgan's law:
1) Statement It is not true that I know Arabic or Chinese is identical to the statement I don't know Arabic and I don't know Chinese.
2) Statement It's not true that I learned my lesson and got a D on it is identical to the statement Either I didn't learn the lesson, or I didn't get an A on it.
Replacement of implication and equivalence operations
The operations of implication and equivalence are sometimes not among the logical operations of a particular computer or compiler from a programming language. However, these operations are necessary for solving many problems. There are rules for replacing these operations with sequences of negation, disjunction, and conjunction operations.
So, replace operation implications possible according to the following rule:
To replace the operation equivalence there are two rules:
It is easy to verify the validity of these formulas by constructing truth tables for the right and left sides of both identities.
Knowledge of the rules for replacing the operations of implication and equivalence helps, for example, to correctly construct the negation of an implication.
Consider the following example.
Let the statement be given:
E = It is not true that if I win the competition, I will get a prize.
Let BUT= I will win the contest
B = I will receive a prize.
Hence, E = I will win the competition, but I will not receive a prize.
The following rules are also of interest:
You can also prove their validity using truth tables.
Their expression in natural language is interesting.
For example, the phrase
If Winnie the Pooh ate honey, then he is full
is identical to the phrase
If Winnie the Pooh is not full, then he did not eat honey.
Exercise: think of phrases-examples on these rules.
2. Basic concepts and definitions in Appendix 1
3. Material for the curious in Appendix 2
4. Homework
1) Learn the laws of logic using the Algebra of Logic course located in the information space (www.learning.9151394.ru).
2) Check the proof of De Morgan's laws on a PC by constructing a truth table.
Applications
- Basic concepts and definitions (
§four. Equivalent, TI and TL formulas of the algebra of logic. Basic equivalences. (Laws of logical operations). The law of duality.
Definition.
Two formulas of the algebra of logic A and B are called EQUIVALENT if they take the same logical values on any set of elementary propositions included in the formulas. The equivalence of formulas will be denoted by the sign º, and the notation A ºB means that the formulas A and B are equivalent.
Formula A is called IDENTICALLY TRUE (or TAUTOLOGY) if it takes the value 1 for all values of the variables included in it.
A formula is called IDENTICALLY FALSE (or CONTRADICTION) if it takes the value 0 for all values of the variables included in it.
There is the following connection between the concepts of equivalence and equivalence: if the formulas A and B are equivalent, then the formula A"B is a tautology, and vice versa, if the formula A"B is a tautology, then the formulas A and B are equivalent.
The most important equivalences of the algebra of logic can be divided into three groups.
1. Basic equivalences.
Laws of idempotence.
Law of contradiction
Law of the excluded middle
double negative law
absorption laws
2. Equivalences expressing some logical operations in terms of others.
Here 3, 4, 5, 6 are Morgan's laws.
It is clear that equivalences 5 and 6 are obtained from equivalences 3 and 4, respectively, if we take negations from both parts of the latter and use the law of removal of double negations.
Thus, the first four equivalences need proof. Let's prove one of them: the first one.
Since for the same logical values x and y the formulas are true https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21">. Therefore, in this case, both the equivalence parts have the same true value.
Let now x and y have different logical values. Then the equivalence and one of the two implications or will be false. But at the same time, the conjunction will also be false. 
.
Thus, in this case, both parts of the equivalence have the same logical meaning.
Equivalences 2 and 4 are proved similarly.
It follows from the equivalences of this group that any formula of the algebra of logic can be replaced by a formula equivalent to it, containing only two logical operations: conjunction and negation or disjunction and negation.
Further exclusion of logical operations is not possible. So, if we use only conjunction, then such a formula as negation cannot be expressed using the conjunction operation.
However, there are operations by which any of the five logical operations that we use can be expressed. Such an operation is, for example, the operation “Schaeffer's Stroke”. This operation is indicated by the symbol ½ left " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">
Modern computers based on "ancient" electronic computers are based on certain postulates as the basic principles of operation. They are called the laws of the algebra of logic. For the first time, such a discipline was described (of course, not in as much detail as in its modern form) by the ancient Greek scientist Aristotle.
Representing a separate branch of mathematics, within which the propositional calculus is studied, the algebra of logic has a number of well-defined conclusions and conclusions.
In order to better understand the topic, we will analyze the concepts that will help in the future to learn the laws of the algebra of logic.
Perhaps the main term in the discipline under study is a statement. This is a statement that cannot be both false and true at the same time. He always has only one of these characteristics. At the same time, it is conventionally accepted to give the value 1 to truth, 0 to falsity, and call the statement itself some kind of A, B, C. In other words, the formula A=1 means that the statement A is true. Expressions can be handled in a variety of ways. Let's briefly consider the actions that can be performed with them. Note also that the laws of the algebra of logic cannot be mastered without knowing these rules.
1. Disjunction two statements - the result of the operation "or". It can be either false or true. The character "v" is used.
2. Conjunction. The result of such an action, performed with two propositions, will be a new one only if both original propositions are true. The operation "and", the symbol "^" is used.
3. Implication."If A, then B" operation. The result is a statement that is false only if A is true and B is false. The "->" symbol is used.
4. Equivalence. Operation "A if and only if B when". This statement is true if both variables have the same value. The symbol "<->».
There are also a number of operations close to implication, but they will not be considered in this article.
Now let's take a closer look at the basic laws of the algebra of logic:
1. Commutative or commutative states that changing the places of logical terms in the operations of conjunction or disjunction does not affect the result.
2. Associative or associative. According to this law, variables in the operations of conjunction or disjunction can be combined into groups.
3. Distribution or distribution. The essence of the law is that the same variables in the equations can be taken out of brackets without changing the logic.
4. De Morgan's law (inversion or negation). The negation of the operation of conjunction is equivalent to the disjunction of the negation of the original variables. The negation of the disjunction, in turn, is equal to the conjunction of the negation of the same variables.
5. Double negation. The negation of a certain statement twice results in the original statement, three times - its negation.
6. The law of idempotency looks like this for logical addition: x v x v x v x = x; for multiplication: x^x^x^=x.
7. The law of non-contradiction says: two statements, if they are contradictory, cannot be true at the same time.
8. The law of the exclusion of the third. Among two contradictory statements, one is always true, the other is false, the third is not given.
9. The law of absorption can be written in this way for logical addition: x v (x ^ y) = x, for multiplication: x ^ (x v y) = x.
10. The law of gluing. Two adjacent conjunctions can stick together to form a conjunction of lower rank. In this case, the variable by which the original conjunctions were glued disappears. Example for logical addition:
(x^y) v (-x^y)=y.
We have considered only the most used laws of the algebra of logic, which in fact can be many more, since often logical equations take on a long and ornate form, which can be reduced by applying a number of similar laws.
As a rule, special tables are used for the convenience of counting and identifying results. All existing laws of the algebra of logic, the table for which has the general structure of a grid rectangle, are painted, distributing each variable into a separate cell. The larger the equation, the easier it is to deal with using tables.
Laws of Propositional Algebra
Algebra of propositions (algebra of logic) is a section of mathematical logic that studies logical operations on propositions and the rules for transforming complex propositions.
When solving many logical problems, it is often necessary to simplify the formulas obtained by formalizing their conditions. Simplification of formulas in the algebra of propositions is carried out on the basis of equivalent transformations based on the basic logical laws.
Laws of propositional algebra (algebra of logic) are tautologies.
Sometimes these laws are called theorems.
In propositional algebra, logical laws are expressed as equality of equivalent formulas. Among the laws, those that contain one variable are especially distinguished.
The first four of the following laws are the basic laws of propositional algebra.
Identity law:
A=A
Every concept and judgment is identical to itself.
The law of identity means that in the process of reasoning one cannot replace one thought with another, one concept with another. If this law is violated, logical errors are possible.
For example, reasoning Correctly says that language will bring you to Kyiv, but I bought a smoked language yesterday, which means that now I can safely go to Kyiv incorrectly, since the first and second words “language” denote different concepts.
In reasoning: Movement is eternal. Going to school is movement. Therefore, going to school forever the word "movement" is used in two different senses (the first - in the philosophical sense - as an attribute of matter, the second - in the ordinary sense - as an action to move in space), which leads to a false conclusion.
Law of non-contradiction :
At the same moment in time, the statement can be either true or false, there is no third. Either A is true or not A. Examples of the implementation of the law of the excluded middle:
1. The number 12345 is either even or odd, the third is not given.
2. The company operates at a loss or break even.
3. This liquid may or may not be an acid.
The law of the excluded middle is not a law recognized by all logicians as a universal law of logic. This law applies where cognition deals with a rigid situation: "either-or", "true-false". Where there is uncertainty (for example, in reasoning about the future), the law of the excluded middle often cannot be applied.
Consider the following statement: This sentence is false. It cannot be true because it claims to be false. But it cannot be false either, because then it would be true. This statement is neither true nor false, and therefore the law of the excluded middle is violated.
The paradox (Greek paradoxos - unexpected, strange) in this example arises from the fact that the sentence refers to itself. Another well-known paradox is the barber problem: In one city, the barber cuts the hair of all residents, except for those who cut their own hair. Who cuts the barber's hair? In logic, because of its formality, it is not possible to obtain the form of such a self-referential statement. This once again confirms the idea that with the help of the algebra of logic it is impossible to express all possible thoughts and arguments. Let us show how, based on the definition of propositional equivalence, the rest of the laws of the propositional algebra can be obtained.
For example, let's determine what is equivalent (equivalent) A (double negation A, i.e. negation of the negation A). To do this, we will build a truth table:
By definition of equivalence, we must find the column whose values match the values of column A. This will be column A.
Thus, we can formulate the law of double negation:
If we negate some statement twice, then the result is the original statement. For example, the statement A = Matroskin - cat is equivalent to A = It is not true that Matroskin is not a cat.
Similarly, the following laws can be derived and verified:
Constant properties:
Laws of idempotency:
No matter how many times we repeat: the TV is on or the TV is on or the TV is on... the meaning of the statement will not change. Similarly, from repetition it is warm outside, it is warm outside, ... it will not become one degree warmer.
The laws of commutativity:
A v B = B v A
A & B = B & A
Operands A and B in the operations of disjunction and conjunction can be interchanged.
Associativity laws:
A v(B v C) = (A v B) v C;
A & (B & C) = (A & B) & C.
If the expression uses only the disjunction operation or only the conjunction operation, then you can neglect the brackets or arrange them arbitrarily.
Distributivity laws:
A v (B & C) = (A v B) &(A v C)
(distributive disjunction
regarding conjunction)
A & (B v C) = (A & B) v (A & C)
(distributivity of the conjunction
regarding disjunction)
The distributive law of conjunction with respect to disjunction is similar to the distributive law in algebra, but the law of distributive disjunction with respect to conjunction has no analogue, it is valid only in logic. Therefore, it needs to be proven. The proof is best done using a truth table:
Absorption laws:
A v (A & B) = A
A & (A v B) = A
Carry out the proof of the absorption laws yourself.
De Morgan's laws:
Verbal formulations of de Morgan's laws:
Mnemonic rule: on the left side of the identity, the negation operation is above the entire statement. On the right side, it seems to be broken and negation stands above each of the simple statements, but at the same time the operation changes: disjunction to conjunction and vice versa.
Examples of the implementation of de Morgan's law:
1) The statement It is not true that I know Arabic or Chinese is identical to the statement I do not know Arabic and I do not know Chinese.
2) The statement It is not true that I learned the lesson and got a deuce for it is identical to the statement Either I did not learn the lesson, or I did not get a deuce for it.
Replacement of implication and equivalence operations
The operations of implication and equivalence are sometimes not among the logical operations of a particular computer or compiler from a programming language. However, these operations are necessary for solving many problems. There are rules for replacing these operations with sequences of negation, disjunction, and conjunction operations.
So, you can replace the implication operation in accordance with the following rule:
There are two rules for replacing the equivalence operation:
It is easy to verify the validity of these formulas by constructing truth tables for the right and left sides of both identities.
Knowledge of the rules for replacing the operations of implication and equivalence helps, for example, to correctly construct the negation of an implication.
Consider the following example.
Let the statement be given:
E = It is not true that if I win the competition, I will receive a prize.
Let A = I will win the contest,
B = I will receive a prize.
Then
From here, E = I will win the competition, but I will not receive a prize.