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

1. Explanation of new material, with the involvement of a computer - 25 minutes.
2. Basic concepts and definitions laid out in "learning" - 10 minutes.
3. Material for the curious - 5 minutes.
4. 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. As arguments to confirm the true thought, true judgments, factual material, statistical data, laws of science, axioms, proven theorems can be used.

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 A 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 A, 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) A(twice no A, i.e. negation of 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 the column A. This will be the column A.

Thus, we can formulate double lawnegations:

If we negate some statement twice, then the result is the original statement. For example, the statement A= 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 A And IN 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 A= 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

1. Basic concepts and definitions (Appendix 1).
2. Material for the curious (Appendix 2).

1.3.1. STATEMENT
1.3.2. LOGICAL OPERATIONS
1.3.3. CONSTRUCTION OF TRUTH TABLES FOR LOGICAL EXPRESSIONS
1.3.4. PROPERTIES OF LOGICAL OPERATIONS
1.3.5. SOLVING LOGICAL PROBLEMS
1.3.6. LOGIC ELEMENTS

1. Familiarize yourself with the presentation materials for the paragraph contained in the electronic supplement to the textbook. Does the presentation complement the information contained in the text of the paragraph?

2. Explain why the following sentences are not statements.
1) What color is this house?
2) The number X does not exceed one.
3) 4X+3.
4) Look out the window.
5) Drink tomato juice!
6) This topic is boring.
7) Ricky Martin is the most popular singer.
8) Have you been to the theatre?

3. Give one example of true and false statements from biology, geography, computer science, history, mathematics, literature.

4. In the following statements, highlight simple statements, marking each of them with a letter; write down each compound statement using letters and signs of logical operations.
1) The number 376 is even and three-digit.
2) In winter, children go skating or skiing.
3) We will celebrate the New Year at the dacha or on Red Square.
4) It is not true that the Sun moves around the Earth.
5) The earth is shaped like a ball, which looks blue from space.
6) At the lesson of mathematics, high school students answered the questions of the teacher, and also wrote independent work.

5. Construct the negatives of the following statements.

6. Let A \u003d "Any likes math lessons", and B \u003d "Any likes chemistry lessons." Express the following formulas in plain language:

7. Some segment of the Internet network consists of 1000 sites. The search server automatically compiled a table of keywords for sites in this segment. Here is her fragment:

920; 80.

8. Build truth tables for the following logical expressions:

9. Give the proof of the logical laws considered in the paragraph using truth tables.

10. Three numbers are given in the decimal number system: A=23, B=19, C=26. Convert A, B and C to the binary number system and perform bitwise logical operations (A v B) and C. Give the answer in decimal number system.

11. Find the meaning of expressions:

12. Find the value of the logical expression (x
1) 1
2) 2
3) 3
4) 4
1) 0. 2) 0. 3) 1. 4) 1.

13. Let A \u003d "The first letter of the name is a vowel", B \u003d "The fourth letter of the name is a consonant." Find the value of the logical expression A v B for the following names:
1) ELENA 2) VADIM 3) ANTON 4) FEDOR
1) 1. 2) 1. 3) 0. 4) 1.

14. The case of John, Brown and Smith is being dealt with. It is known that one of them found and hid the treasure. During the investigation, each of the suspects made two statements:
Smith: "I didn't do it. Brown did it."
John: "Brown is not guilty. Smith did it."
Brown: I didn't do it. John didn't do it."
The court found that one of them lied twice, the other told the truth twice, the third lied once, told the truth once. Which suspect should be acquitted?
Answer: Smith and John.

15. Alyosha, Borya and Grisha found an ancient vessel in the ground. Considering the amazing find, each made two assumptions:
1) Alyosha: “This vessel is Greek and made in the 5th century.”
2) Borya: "This is a Phoenician vessel and was made in the 3rd century."
3) Grisha: “This vessel is not Greek and was made in the 4th century.”
The history teacher told the children that each of them was correct in only one of two assumptions. Where and in what century was the vessel made?
Answer: Phoenician vessel, made in the 5th century.

16. Find out what signal should be at the output of the electronic circuit for each possible set of signals at the inputs. Make a worksheet of the circuit. What logical expression describes the circuit?

Building truth tables for logical expressions

Examination basic logical operations.

53. The table shows queries and the number of pages found on them for a certain segment of the Internet.

Request	Pages found (in thousands)
CHOCOLATE | ZEFIR	15 000
CHOCOLATE & MARBLE	8 000
ZEFIR	12 000

How many pages (in thousands) will be found for the query CHOCOLATE? Solve the problem using Euler circles:

54. The table shows queries and the number of pages found on them for a certain segment of the Internet.

Request	Pages found (in thousands)
ZUBR & TOUR	5 000
BISON	18 000
TOUR	12 000

How many pages (in thousands) will be found for the query ZUBR | TOUR?Solve the problem using Euler circles:

55. The table shows queries and the number of pages found on them for a certain segment of the Internet.

Request	Pages found (in thousands)
FOOTBALL | HOCKEY	20 000
FOOTBALL	14 000
HOCKEY	16 000

How many pages (in thousands) will be found for FOOTBALL & HOCKEY? Solve the problem using Euler circles:

Tasks.

1. Explain why the following sentences are not statements.

1) What color is this house?

2) The number X does not exceed one.

4) Look out the window.

5) Drink tomato juice!

6) This topic is boring.

7) Ricky Martin is the most popular singer.

8) Have you been to the theatre?

3. In the following statements, highlight simple statements, marking each of them with a letter; write down each compound statement using letters and signs of logical operations.

1) The number 376 is even and three-digit.

2) In winter, children go skating or skiing.

3) We will celebrate the New Year at the dacha or on Red Square.

4) It is not true that the Sun moves around the Earth.

5) The earth has the shape of a ball, which looks blue from space.

6) At the lesson of mathematics, high school students answered the questions of the teacher, and also wrote independent work.

4. Build the negatives of the following statements.

1) Today the theater is performing the opera "Eugene Onegin".

2) Every hunter wants to know where the pheasant is sitting.

3) The number 1 is a prime number.

4) Natural numbers ending in O are not prime numbers.

5) It is not true that the number 3 is not a divisor of the number 198.

6) Kolya solved all the tasks of the test.

7) In every school, some students are interested in sports.

8) Some mammals do not live on land.

5. Let A \u003d " Anya likes math lessons", and B = " But notI like chemistry lessons. Express the following formulas in plain language:

6. Consider the electrical circuits shown in the figure:

They show the parallel and series connections of switches known to you from the physics course. In the first case, for the bulb to light up, both switches must be turned on. In the second case, it is enough that one of the switches is turned on. Try to independently draw an analogy between the elements of electrical circuits and objects and operations of the algebra of logic:

Wiring diagram	Algebra of logic
Switch
Switch on
Switch off
Serial connection of switches
Parallel connection of switches

7. Some segment of the Internet network consists of 1000 sites. The search server automatically compiled a table of keywords for sites in this segment. Here is its fragment:

Keyword	The number of sites for which this word is a keyword
catfish	250
swordsmen	200
guppies	500

On request catfish & guppies 0 sites were found, by request catfish & swordtails- 20 sites, and upon request swordtails & guppies- 10 sites.How many sites will be found on request catfish | swordsmen | guppies?
For how many sites of the considered segment is the statement false"Catfish - the keyword of the site OR swordsmen -site keyword OR guppy - site keyword" ?
8. Build truth tables for the following logical expressions:

9. Prove the logic considered in the paragraph some laws with the help of truth tables.

Given three numbers in the decimal number system: A = 23, B = 19, C = 26. Convert A, B and C to the binary number system and perform bitwise logical operations (A v B) & C. Give the answer in the decimal number system.
11. Find expression values:
1) (1 v 1) v (1 v 0);
2) ((1 v 0) v 1) v 1);
3) (0 & 1) & 1;
4) 1 & (1 & 1) & 1;
5) ((1 v 0) & (1 & 1)) & (0 v 1);
6) ((1 & 1) v 0) & (0 v 1);
7) ((0 & 0) v 0) & (1 v 1);
8) (A v 1) v (B v 0);
9) ((1 & A) v (B & 0)) v 1;
10) 1 v A & 0.
12. Find the value of a boolean expression

For the specified values ​​of the number X: 1) 1 2) 2 3) 3 4) 4

Formulas and laws of logic

In an introductory lesson on fundamentals of mathematical logic, we got acquainted with the basic concepts of this section of mathematics, and now the topic is receiving a natural continuation. In addition to the new theoretical, or rather not even theoretical - but general educational material, practical tasks await us, and therefore if you came to this page from a search engine and / or are poorly oriented in the material, then please follow the link above and start from the previous article. In addition, for practice we need 5 truth tables logical operations which I highly recommend rewrite by hand.

DO NOT remember, DO NOT print, namely, once again comprehend and rewrite on paper with your own hand - so that they are before your eyes:

– table NOT;
- table I;
– OR table;
– implication table;
- Equivalence table.

It is very important. In principle, it would be convenient to number them "Table 1", "Table 2", etc., but I have repeatedly emphasized the flaw in this approach - as they say, in one source the table will be the first, and in the other - one hundred and first. Therefore, we will use "natural" names. We continue:

In fact, you are already familiar with the concept of a logical formula. I will give a standard, but rather witty definition: formulas propositional algebras are called:

1) any elementary (simple) statements;

2) if and are formulas, then formulas are also expressions of the form
.

There are no other formulas.

In particular, a formula is any logical operation, such as logical multiplication. Pay attention to the second point - it allows recursive way to "create" an arbitrarily long formula. Because the are formulas, then is also a formula; since and are formulas, then - also a formula, etc. Any elementary statement (again by definition) may enter the formula more than once.

Formula Not is, for example, a record - and here there is an obvious analogy with "algebraic garbage", from which it is not clear whether numbers should be added or multiplied.

The logical formula can be thought of as logic function. Let's write the same conjunction in functional form:

Elementary statements in this case also play the role of arguments (independent variables), which in classical logic can take 2 values: true or lie. In what follows, for convenience, I will sometimes call simple statements variables.

The table describing the logical formula (function) is called, as already mentioned, truth table. Please - a familiar picture:

The principle of forming the truth table is as follows: "at the input" you need to list all possible combinations truths and lies that elementary propositions (arguments) can accept. In this case, the formula includes two statements, and it is easy to find out that there are four such combinations. “At the output”, we get the corresponding logical values ​​​​of the entire formula (function).

I must say that the “exit” here turned out to be “in one step”, but in the general case the logical formula is more complex. And in such "difficult cases" it is necessary to observe order of execution of logical operations:

- negation is performed first;
- secondly - conjunction;
- then - disjunction;
- then the implication ;
- and, finally, the lowest priority has the equivalent.

So, for example, the entry implies that you first need to carry out logical multiplication, and then - logical addition:. Just like in "ordinary" algebra - "first we multiply, and then we add."

The order of actions can be changed in the usual way - brackets:
- here, first of all, disjunction is performed and only then a more “strong” operation.

Probably everyone understands, but just in case a firefighter: and this two different formulas! (both formally and substantively)

Let's make a truth table for the formula. This formula includes two elementary statements and “at the input” we need to list all possible combinations of ones and zeros. To avoid confusion and inconsistencies, we agree to list combinations strictly in that order (which I actually use de facto from the very beginning):

The formula includes two logical operations, and according to their priority, first of all, you need to perform negation statements. Well, we negate the “pe” column - we turn units into zeros, and zeros into units:

In the second step, we look at the columns and apply to them OR operation. Looking ahead a little, I will say that the disjunction is permutable (and are the same thing), and therefore the columns can be analyzed in the usual order - from left to right. When performing logical addition, it is convenient to use the following applied reasoning: “If there are two zeros, we put zero, if at least one unit, we put one”:

The truth table is built. And now let's remember the good old implication:

…attentively-attentively… look at the final columns…. In propositional algebra, such formulas are called equivalent or identical:

(three horizontal lines are the identity icon)

In the 1st part of the lesson, I promised to express the implication through basic logical operations, and the fulfillment of the promise was not long in coming! Those who wish can put meaningful meaning into the implication (e.g. "If it's raining, it's damp outside") and independently analyze the equivalent statement.

Let's formulate general definition: the two formulas are called equivalent (identical), if they take the same values ​​for any set of values ​​included in these variable formulas (elementary statements). They also say that "formulas are equivalent if their truth tables are the same" but I don't really like that phrase.

Exercise 1

Make a truth table for the formula and make sure that the identity you know is true.

Let's repeat the procedure for solving the problem:

1) Since the formula includes two variables, there will be 4 possible sets of zeros and ones in total. We write them down in the order specified above.

2) Implications are “weaker” than conjunctions, but they are located in brackets. We fill in the column, while it is convenient to use the following applied reasoning: “if zero follows from one, then we put zero, in all other cases - one”. Next, fill in the column for the implication , and at the same time, attention!– columns and should be analyzed “from right to left”!

3) And at the final stage, fill in the final column. And here it is convenient to argue like this: “if there are two ones in the columns, then we put one, in all other cases - zero”.

And finally, we check the truth table equivalences .

Basic Equivalences of Propositional Algebra

We have just met two of them, but the matter, of course, is not limited to them. There are quite a few identities and I will list the most important and most famous of them:

Commutativity of conjunction and commutativity of disjunction

commutativity is a permutation:

Familiar from the 1st grade rules: “From a rearrangement of factors (terms), the product (sum) does not change”. But for all the seeming elementarity of this property, it is far from always true, in particular, it is non-commutative matrix multiplication (in general, they cannot be rearranged), A cross product of vectors– anticommutatively (permutation of vectors entails a sign change).

And besides, here again I want to emphasize the formalism of mathematical logic. So, for example, phrases "The student passed the exam and drank" And "The student drank and passed the exam" different from the content point of view, but indistinguishable from the standpoint of formal truth. ... Each of us knows such students, and for ethical reasons we will not name specific names =)

Associativity of logical multiplication and addition

Or, if “school-style” is an associative property:

Distribution Properties

Please note that in the 2nd case it will be incorrect to talk about "opening the brackets", in a sense, here is a "fiction" - after all, they can be removed altogether: multiplication is a stronger operation.

And again, these seemingly “banal” properties are far from being satisfied in all algebraic systems, and, moreover, require proof (which we will talk about very soon). By the way, the second distributive law is not valid even in our “ordinary” algebra. And indeed:

Law of idempotence

What to do, latin....

Just some principle of a healthy psyche: “I and I are me”, “I or I am also me” =)

And here are some similar identities:

... well, something I even hung up ... so tomorrow you can wake up with a Ph.D. =)

The law of double negation

Well, here the example with the Russian language already suggests itself - everyone knows very well that two particles “not” mean “yes”. And in order to enhance the emotional coloring of denial, three “not” are often used:
- even with a tiny bit of proof it worked!

Absorption laws

- Was it a boy? =)

In the right identity, the brackets can be omitted.

De Morgan's laws

Suppose a strict teacher (whose name you also know :)) puts an exam if - The student answered the 1st question And – The student answered the 2nd question. Then the statement stating that Student Not passed the exam, will be equivalent to the statement - Student Not answered the 1st question or to the 2nd question.

As noted above, equivalences are subject to proof, which is standardly carried out using truth tables. In fact, we have already proved the equivalences that express the implication and the equivalence, and now it is time to fix the technique for solving this problem.

Let's prove the identity. Since it includes a single statement, then only two options are possible “at the input”: one or zero. Next, we assign a single column and apply to them rule AND:

As a result, "at the output" a formula is obtained, the truth of which coincides with the truth of the statement. Equivalence has been proven.

Yes, this proof is primitive (and someone will say that it's "stupid"), but a typical math logic teacher will shake his soul out for him. Therefore, even such simple things should not be treated with disdain.

Now let's make sure, for example, of the validity of de Morgan's law.

First, let's create a truth table for the left side. Since the disjunction is in brackets, we first of all perform it, after which we negate the column:

Next, we compile a truth table for the right side. Here, too, everything is transparent - first of all, we carry out more “strong” negatives, then apply to the columns rule AND:

The results matched, so the identity is proved.

Any equivalence can be represented as identically true formula. It means that FOR ANY initial set of zeros and ones"at the output" is obtained strictly unity. And there is a very simple explanation for this: since the truth tables and coincide, then, of course, they are equivalent. Let us combine, for example, the left and right parts of the just proved de Morgan identity by equivalence:

Or, more compactly:

Task 2

Prove the following equivalences:

b)

Brief solution at the end of the lesson. Let's not be lazy! Try not only to make truth tables, but also clearly formulate conclusions. As I noted recently, neglecting simple things can be very, very expensive!

We continue to get acquainted with the laws of logic!

Yes, absolutely right - we are already working with them with might and main:

True at , is called identically true formula or the law of logic.

By virtue of the previously justified transition from equivalence to the identically true formula, all the identities listed above are the laws of logic.

Formula that takes a value Lie at any set of values ​​of the variables included in it, is called identically false formula or contradiction.

A signature example of contradiction from the ancient Greeks:
No statement can be true and false at the same time.

The proof is trivial:

“Output” received exclusively zeros, therefore, the formula is really identical false.

However, any contradiction is also a law of logic, in particular:

It is impossible to cover such a vast topic in a single article, and therefore I will limit myself to just a few more laws:

Law of the excluded middle

- in classical logic, any statement is true or false, and there is no third way. “To be or not to be” – that is the question.

Make your own truth table and make sure that it is identically true formula.

Law of counterposition

This law was actively exaggerated when we discussed the essence necessary condition, remember: “If it’s damp outside during the rain, then it follows that if it’s dry outside, then it definitely didn’t rain”.

It also follows from this law that if fair is straight theorem, then the statement, which is sometimes called opposite theorem.

If true reverse theorem, then by virtue of the law of contraposition, the theorem is also valid, opposite reverse:

And let's go back to our meaningful examples: for statements - a number is divisible by 4, - a number is divisible by 2 fair straight And opposite theorems, but false reverse And opposite reverse theorems. For the "adult" formulation of the Pythagorean theorem, all 4 "directions" are true.

Law of the syllogism

Also a classic of the genre: “All oaks are trees, all trees are plants, therefore all oaks are plants”.

Well, here again I would like to note the formalism of mathematical logic: if our strict Teacher thinks that a certain Student is an oak, then from a formal point of view, this Student is certainly a plant =) ... although, if you think about it, it can be from an informal one too = )

Let's make a truth table for the formula. In accordance with the priority of logical operations, we adhere to the following algorithm:

1) perform the implications and . Generally speaking, you can immediately execute the 3rd implication, but it is more convenient with it (and allowed!) figure it out a little later

2) apply to columns rule AND;

3) now we execute;

4) and at the final step apply the implication to the columns And .

Feel free to control the process with your index and middle fingers :))


From the last column, I think everything is clear without comments:
, which was to be proved.

Task 3

Find out if the following formula is a law of logic:

Brief solution at the end of the lesson. Yes, and I almost forgot - let's agree to list the initial sets of zeros and ones in exactly the same order as in the proof of the syllogism law. Of course, the lines can be rearranged, but this will make it very difficult to reconcile with my solution.

Converting Boolean Formulas

In addition to their "logical" purpose, equivalences are widely used to transform and simplify formulas. Roughly speaking, one part of the identity can be exchanged for another. So, for example, if you come across a fragment in a logical formula, then, according to the law of idempotency, you can (and should) write simply instead of it. If you see , then, according to the law of absorption, simplify the notation to . And so on.

In addition, there is one more important thing: identities are valid not only for elementary propositions, but also for arbitrary formulas. For example:

, where are any (as complex as you like) formulas.

Let us transform, for example, the complex implication (1st identity):

Further, we apply the “complex” de Morgan law to the bracket, while, due to the priority of operations, it is the law , where :

Parentheses can be removed, because inside there is a more “strong” conjunction:

Well, with commutativity, in general, everything is simple - you don’t even need to designate anything ... something sunk into my soul the law of syllogism :))

Thus, the law can be rewritten in a more intricate form:

Speak aloud the logical chain “with an oak, a tree, a plant”, and you will understand that the substantive meaning of the law has not changed at all from the rearrangement of implications. Is that the wording has become more original.

As a training, we simplify the formula.

Where to begin? First of all, to understand the order of actions: here the negation is applied to a whole bracket, which is “fastened” with the statement by a “slightly weaker” conjunction. In essence, we have before us the logical product of two factors: . Of the two remaining operations, implication has the lowest priority, and therefore the entire formula has the following structure: .

As a rule, at the first step (steps) get rid of the equivalence and implication (if they are) and reduce the formula to three basic logical operations. What can I say…. Logically.

(1) We use the identity . And in our case.

This is usually followed by "disassembly" with brackets. First the whole solution, then the comments. In order not to get "butter oil", I will use the "usual" equality icons:

(2) We apply de Morgan's law to the outer brackets, where .

§ 1.3. Elements of the algebra of logic

Elements of the algebra of logic. Questions and tasks

1. Familiarize yourself with the presentation materials for the paragraph contained in the electronic supplement to the textbook. Does the presentation complement the information contained in the text of the paragraph?

2. Explain why the following sentences are not statements.

1) What color is this house?
2) The number X does not exceed one.
3) 4X + 3.
4) Look out the window.
5) Drink tomato juice!
6) This topic is boring.
7) Ricky Martin is the most popular singer.
8) Have you been to the theatre?

3. Give one example of true and false statements from biology, geography, computer science, history, mathematics, literature.

4. In the following statements, highlight simple statements, marking each of them with a letter; write down each compound statement using letters and signs of logical operations.

1) The number 376 is even and three-digit.
2) In winter, children go skating or skiing.
3) We will celebrate the New Year at the dacha or on Red Square.
4) It is not true that the Sun moves around the Earth.
5) The earth is shaped like a ball, which looks blue from space.
6) At the lesson of mathematics, high school students answered the questions of the teacher, and also wrote independent work.

5. Construct the negatives of the following statements.

1) Today the opera "Eugene Onegin" is going on in the theater.
2) Every hunter wants to know where the pheasant is sitting.
3) The number 1 is a prime number.
4) Natural numbers ending in 0 are not prime numbers.
5) It is not true that the number 3 is not a divisor of the number 198.
6) Kolya solved all the tasks of the test.
7) In every school, some students are interested in sports.
8) Some mammals do not live on land.

6. Let A = "Anna likes math lessons", and B = "Ana likes chemistry lessons". Express the following formulas in plain language:

7. Some segment of the Internet network consists of 1000 sites. The search server automatically compiled a table of keywords for sites in this segment. Here is its fragment:

On request catfish & guppies 0 sites were found, by request catfish & swordtails- 20 sites, and upon request swordtails & guppies- 10 sites.

How many sites will be found on request catfish | swordsmen | guppies?

For how many sites of the considered segment is the statement false "Catfish - the keyword of the site OR swordtails - the keyword of the site OR guppies - the keyword of the site"?

8. Build truth tables for the following logical expressions:

9. Carry out the proof of the logical laws considered in the paragraph using truth tables.