Absorption theorem written in two forms - disjunctive and

conjunctive, respectively:

A + AB \u003d A (16)

A (a + c) \u003d a (17)

We prove the first theorem. Let's bring the letter A for brackets:

BUT + AB \u003d A (1 + B)

According to Theorem (3) 1 + In \u003d. 1, therefore

A (1 + c) \u003d a 1 \u003d a

To prove the second theorem, reveal the brackets:

A (a + c) \u003d a + a + av \u003d a + av

It turned out the expression, just proven.

Consider several examples on the use of the absorption theorem when

simplify boolean formulas.

Gluing theorem also has two forms - disjunctive and

conjunctive:

We prove the first theorem:

since according to theorems (5) and (4)

To prove the second theorem, open brackets:

According to Theorem (6) therefore:

By the absorption theorem (16) A + av \u003d a

The absorption theorem, as well as the gluing theorem, is applied when simplified

boolean formulas, for example:

Theorem de Morgana Binds all three basic operations Boolean algebra

Disjunction, conjunction and inversion:

The first theorem is read like this: conjunction inversion is disjunction

inversions. Second: Inversion of disjunction is the conjunction of inversions. You can prove the Morgan's theorems using truth tables for the left and right parts.

Theorem de Morgana is also applicable to a larger number of variables:

Lecture 5.

Inverting complex expressions

Theorem de Morgan is applicable not only to individual conjunctions

or disjunction, but also to more complex expressions.

We find the inversion of the expression AV + CD. , presented in the form of disjunction of conjunctions. Inverting will be considered finished if the signs of denial cost only over variables. We introduce notation: Av \u003d x;

CD \u003d Y,then

We will find and substitute in the expression (22):

In this way:

Consider the expression presented in conjunctive form:

(A + B) (C + D)

Find his inversion in the form

We introduce notation: A + B \u003d x; C + D \u003d Y,then

Find and substitute them in the expression

In this way:

When inverting complex expressions, you can use the following rule. To find the inversion, it is necessary to replace the signs of conjunction to be replaced by the signs of disjunction, and the signs of disjunction are signs of conjunction and put inversion over each variable:

Concept of milk function

INthe general case function (lat. FUNCTIO - execution, compliance,

display) is some rule (law), according to which each element of the set X representing an area of \u200b\u200bindependent variable values x, put in compliance with a certain element of the set F,

under which the area of \u200b\u200bvalues \u200b\u200bof the dependent variable is understood f. . In case of boolean functions X \u003d F. \u003d (0,1). The rule, with which the function is specified, any boolean formula can serve, for example:

Symbol f. here the function is indicated that is, as well as arguments A, In, s,binary variable.

Arguments are independent variables, they can take any values \u200b\u200b- either 0, or 1. The function f. - dependent variable. Its value is fully determined by the values \u200b\u200bof variables and logical connections between them.

The main feature of the function: To determine its value, in the general case it is necessary to know the values \u200b\u200bof all the arguments from which it depends. For example, the above function depends on the three arguments A, B, S.If you take a \u003d 1, then we get

i.e. it turned out a new expression, no equal to zero, nor

unity. Let now IN\u003d 1. then

i.e. and in this case it is not known what is equal to the function, zero or unit.

We finally take FROM\u003d 0. Then we get: f. = 0. Thus, if in the initial expression, take a \u003d 1, IN= 1, FROM = 0, the function will take zero value: f \u003d. 0.

Consider the concept of set of variable values .

If all the arguments on which the function depends, some values \u200b\u200bare assigned, they are talking about the set of argument values \u200b\u200bthat can be

call just a set. The set of argument values \u200b\u200bis a sequence of zeros and units, for example, 110, where the first digit corresponds to the first argument, the second - the second and third is the third. Obviously, it is necessary to agree in advance what the first, second or, permiss the fifth argument. To do this, it is convenient to use the alphabetic location of the letters.

For example, if

then according to the Latin alphabet, the first is the argument R, second -

Q,third - X fourth - W. Then on the set of argument values \u200b\u200bis easy

find the value of the function. Let, for example, given a set of 1001. According to him

records, i.e. on the set 1001, the specified function is equal to one.

Once again, we note that the set of argument values \u200b\u200bis a totality

zeros and units. Binary numbers are also sets of zeros and units.

Hence the question arises - whether the sets are not considered as binary

numbers? It is possible, and in many cases it is very convenient, especially if binary

the number is translated into the decimal system. For example, if

A \u003d 0, B \u003d 1, C \u003d 1, D. = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

i.e. the specified set has number 6 in the decimal system.

If the decimal number is required to find the values \u200b\u200bof the arguments,

we enter in reverse sequence: First, the decimal number is translated into binary, then the ones are reading as much zeros to the left so that the total number of discharges is equal to the number of arguments, after which they find the values \u200b\u200bof the arguments.

Let, for example, it is required to find the values \u200b\u200bof arguments A, In, s, d, e, fquantity with number 23. We translate the number 23 to the binary system by the method

division into two:

As a result, we obtain 23 10 \u003d 10111 2. This is the number five-digit, and total

arguments Six, therefore, on the left it is necessary to write down one zero:

23 10 \u003d 010111 2. From here we find:

A \u003d 0, B \u003d 1, C \u003d 0, d \u003d 1, e \u003d 1, f \u003d 1.

How many sets exist if the number is known p arguments? Obviously, as much as n-discharge binary numbers exist, i.e. 2 n

Lecture 6.

Set the bull function

One way we already know. This is analytical, i.e. in the form of a mathematical expression using binary variables and logical operations. In addition to him, there are other ways, the most important of which is tabular. The table lists all possible sets of argument values \u200b\u200band for each dialing indicates the value of the function. Such a table is called the matching table (truth).

On the example of the function

find out how to build a table of conformity for it.

The function depends on the three arguments A, B, S. Therefore in the table

we provide three columns for arguments A, B, C and one column for the values \u200b\u200bof the function f. To the left of the column, but it is useful to place another column. In it we will record decimal numbers that correspond to sets, if they are considered as three-bit binary numbers. This decimal

the column is entered for the convenience of working with the table, therefore, in principle,

it can be neglected.

Fill the table. In the line with the number of LLC recorded:

A \u003d B \u003d C \u003d0.

Determine the value of the function on this set:

In the F column, write zero in the row with a set of 000.

Next set: 001, t. e. A \u003d B \u003d 0, C \u003d 1. Find the function

on this set:

On the set 001, the function is 1, therefore, in the column F in the string with

number 001 is written by one.

Similarly, calculate the values \u200b\u200bof the functions on all other sets and

fill the entire table.

Associativity

x 1 (x 2 x 3) \u003d (x 1 x 2) x 3;

x 1 ú (x 2 ú x 3) \u003d (x 1 ú x 2) ú x 3.

Commutativeness

x 1 x 2 \u003d x 2 x 1

x 1 ú x 2 \u003d x 2 ú x 1

Distribution of conjunction relative to disjunction

x 1 (x 2 ú x 3) \u003d x 1 x 2 ú x 1 x 3.

Distribution of disjunction relative to conjunction

x 1 ú (x 2 × x 3) \u003d (x 1 ú) 2) × (x 1 ú). *

Idmpotency (tautology)

Twice no

Properties Constant

x & 1 \u003d x; (universal set laws)

x & 0 \u003d 0; (the laws of zero set)

Rules (laws) de Morgana

The law of contradiction (optional)

The law of exception of the third (optional)

Evidence of all these formulas trivial. One of the options is the construction of the truth tables with the left and right part and their comparison.

Rules of gluing

The gluing rule for elementary conjunctions follows from the distribution law, the law of complementivity and the law of the universal set: the disjunction of two adjacent conjunctions can be replaced by elementary conjunction, which is the total part of the social conjunction .

The gluing rule for elementary sums follows from the distributional law of the second kind, the law of complementarity and the law of the zero set: the conjunction of two adjacent disjunctures can be replaced by one elementary disjunction, which is the total part of the technical disjunction .

The absorption rule

The absorption rule for the sum of two elementary works follows from the distribution law of the first kind and laws of the universal set: the disjunction of two elementary conjunctions, of which one is an integral part of the other, can be replaced by a conjunction that has the number of operands .

The absorption rule for the work of elementary sums follows from the distribution law of the second kind and the laws of zero set: the conjunction of two elementary disjunctions, of which one is an integral part of the other, can be replaced by elemental disjunction with a smaller number of operands.

Deployment rule

This rule determines the reverse gluing effect.

The rule of deployment of the elementary work into the logical amount of elementary works of greater rank (in the limit to R \u003d n, i.e. to the constituent of the unit, as will be considered below) follows from the laws of the universal set, the first-order distribution law and is produced in three stages:

In the unfolded elementary product of rank R introduced as a factory N-R units, where N-rank constituents of the unit;

Each unit is replaced by a logical sum of some not available in the initial elementary product of the variable and its denial: x I V. `x I. = 1;

The disclosure of all brackets on the basis of the distribution law of the first kind, which leads to the deployment of the initial elementary product of the rank R to the logical sum 2 N-R constituent of the unit.

The disclosure rule of the elementary product is used to minimize the functions of the logic algebra (FAL).

The rule of deployment of the elementary sum of rank R to the work of the elementary sums of rank N (zero constituent) follows their laws of zero set (6) and the secondary-kind distribution law (14) and produced in three stages:

In the deployable amount of rank R, N-R zeros is injected as the terms;

Each zero is represented as a logical product of some, not available in the initial amount of variable and its denial: x I.·` x I. = 0;

The resulting expression is converted on the basis of the second-type distribution law (14) in such a way that the initial amount of rank R turned into a logical product of 2 N-R constituent of zero.

16. The connection of the full system. Examples of complete systems (with proof)

Definition. The set of functions of the Logic algebra A is called the full system (in P2), if any function of the logic algebra can be expressed by formula over A.

Function system A \u003d ( F 1, F 1, ..., f m ), which is complete, called basis.

The minimum basis is called such a basis for which the removal of at least one function f 1. forming this basis turns the system of functions (F 1, F 1, ..., F M) In incomplete.

Theorem. The system A \u003d (∨, &,) is complete.

Evidence. If the function of the algebra logic F is different from the identical zero, the F is expressed in the form of a perfect disjunctive normal form, which includes only disjunction, conjunction and denial. If F ≡ 0, then f \u003d x & x. Theorem is proved.

Lemma. If the system A is complete, and any function of the system A can be expressed by the formula over some other system B, then B is also a complete system.

Evidence. Consider an arbitrary function of the Logic algebra F (x 1, ..., x n) and two systems of functions: a \u003d (G 1, G 2, ...) and B \u003d (H 1, H 2, ...). Due to the fact that the system A is full, the function F can be expressed as a formula above it:

f (x 1, ..., x n) \u003d ℑ

where g i \u003d ℜ i

that is, the function F is represented as

f (x 1, ..., x n) \u003d ℑ [ℜ1, ℜ2, ...]

in other words, it can be represented by formula over B. Thus, all the functions of the logic algebra, we get that the system B is also full. Lemma is proved.

Theorem. The following systems are complete in P 2:

4) (& ⊕, 1) Zhegalkin's basis.

Evidence.

1) known (Theorem 3) that the system A \u003d (& V,) is full. We show that the system is B \u003d (V ,. Indeed, from the de Morgana law (X & Y) \u003d (X ∨ Y) we obtain that x & y \u003d (x ∨ y), that is, the conjunction is expressed through disjunction and denial, and All functions of the system A are expressed by formulas over the system B. According to Lemma, the B is full.

2) Similar to clause 1: (x ∨ y) \u003d x & y ⇔ x ∨ y \u003d (x & y) and from Lemma 2 it follows the true statement of claim 2.

3) x | y \u003d (x & y), x | x \u003d x; x & y \u003d (x | y) \u003d (x | y) | (x | y) and according to Lemma 2, the system is full.

4) x \u003d x ⊕1 and according to Lemma 2, the system is full.

Theorem is proved.

17. Algebra Zhegalkin. Properties of operations and fullness

A plurality of boolean functions specified in Zhegalkin S4 \u003d (⊕, & 1) called algebra Zhegalkina.

Basic properties.

1. commutativeness

h1⊕H2 \u003d H2⊕H1 H1 & H2 \u003d H2 & H1

2. associativity

h1⊕ (H2⊕H3) \u003d (H1⊕H2) ⊕H3 H1 & (H2 & H3) \u003d (H1 & H2) & H3

3. distribution

h1 & (H2⊕H3) \u003d (H1 & H2) ⊕ (H1 & H3)

4. properties Constant

5. H⊕H \u003d 0 H & H \u003d H
Statement. Through Operations, Zhegalkin algebra can be expressed by all other boolean functions:

x → Y \u003d 1⊕X⊕XY

x ↓ y \u003d 1⊕x⊕y⊕xy

18. Zhegalkina Polina. Construction methods. Example.

Polynomial zhegalkina (polynomial module 2) from n. The variables x 1, x 2 ... x n is called the expression of the form:

c 0 ⊕C 1 x 1 ⊕C 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n,

where permanent C k can take values \u200b\u200b0 whether 1.

If the polynomial zhegalkina does not contain the works of individual variables, then it is called linear (linear function).

For example, f \u003d x⊕yz⊕xyz and f 1 \u003d 1⊕x⊕y⊕z - polynomials, and the second is a linear function.

Theorem. Each Boolean function is represented as a zhegalkin polynomial one.

We present the main methods for the construction of zhegalkin polynomials from the specified function.

1. Method of uncertain coefficients. Let p (x 1, x 2 ... x n) be the desired zhegalkin polynomial, which realizes the specified function f (x 1, x 2 ... x n). We write it in the form

P \u003d c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Find the coefficients C k. To do this, consistently give the variable x 1, x 2 ... x n values \u200b\u200bfrom each row of the truth table. As a result, we obtain a system of 2 N of equations with 2 n by unknown, having a single solution. After deciding it, we find the coefficients of the polynomial P (x 1, x 2 ... x n).

2. The method based on the transformation of formulas over the set of ligaments (, &). Build some formula F. Over the sets of ligaments (, &), implementing this function f (x 1, x 2 ... x n). Then replaced everywhere of the specimula A on A⊕1, disclose brackets, using the distributional law (see Property 3), and then apply properties 4 and 5.

Example. Build polynomial zhegalkin functions f (x, y) \u003d x → y

Decision.
1. (Method of indefinite coefficients). We write the desired polynomine in the form:

P \u003d C 0 ⊕C 1 X⊕C 2 Y⊕c 12 XY

Using the truth table of the implication, we get that

f (0,0) \u003d p (0,0) \u003d c 0 \u003d 1

f (0,1) \u003d p (0,1) \u003d c 0 ⊕c 2 \u003d 1

f (1.0) \u003d p (1.0) \u003d c 0 ⊕c 1 \u003d 0

f (1,1) \u003d p (1,1) \u003d c 0 ⊕c 1 ⊕c 2 ⊕c 12 \u003d 1

Where we consistently find, C 0 \u003d 1, C 1 \u003d 1, C 2 \u003d 0, C 12 \u003d 1

Consequently: X → Y \u003d 1⊕x⊕xy.

2. (Method of transforming formulas.). We have: x → y \u003d xvy \u003d (xy) \u003d (x (y⊕1)) ⊕1 \u003d 1⊕x⊕xy
Note that the advantage of Zhegalkin's algebra (compared to other algebras) is the arithmeticization of logic, which allows the conversion of boolean functions is quite simple. Its disadvantage compared to the Boolean algebra is the bulky of formulas.

Similar information.

Formulas and laws of logic

At the introductory lesson dedicated to the basics of mathematical logicWe got acquainted with the basic concepts of this section of mathematics, and now the topic gets a natural continuation. In addition to the new theoretical, or rather, practical tasks are expected to be expected not even theoretical material, and therefore if you have entered this page from the search engine and / or poorly oriented in the material, then please go along the above link and start from the previous article. In addition, for practice, we will need 5 tastes of truth logic operationsthat I am highly recommend rewrite.

Do not remember, do not print, namely, it is once again to reflect and personally rewrite on paper - so that they are before our eyes:

- Table not;
- Table and;
- table or;
- implication table;
- Equivalence table.

It is very important. In principle, they would be comfortable to continue "Table 1", "Table 2", etc.But I repeatedly emphasized the flaw of 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 the "natural" names. We continue:

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

1) any elementary (simple) statements;

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

There are no other formulas.

In particular, the formula is any logical operation, such as logical multiplication. Pay attention to the second point - it allows recursive How to "create" an arbitrarily long formula. Insofar as - formulas, then - also formula; Since both - formulas, then - also formula, etc. Any elementary statement (again according to the definition) It can enter the formula repeatedly.

Formula not It is, for example, a recording - and here is the apparent analogy with "algebraic garbage", from which it is not clear - whether the numbers need to be folded or multiplied.

The logical formula can be viewed as logical function. We write in a functional form the same conjunction:

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

The table describing the logical formula (function) is called, as has already been voiced, title Title. Please - familiar picture:

The principle of forming a truth table: "At the inlet" you need to list all possible combinations Truths and lies that can take elementary statements (arguments). In this case, the formula includes two statements, and it is easy to find out that four of these combinations are four. "At the output", we obtain the appropriate logical values \u200b\u200bof the entire formula (function).

I must say that the "output" here turned out "in one step", but in general, the logical formula is more complex. And in such "difficult cases" must be observed the procedure for performing logical operations:

- first of all denials;
- in the second place - conjunction;
- then - disjunction;
- then implication;
- And finally, the lowest priority has equivalence.

For example, the record implies that you first need to carry out logical multiplication, and then - logical addition :. Just like in the "normal" algebra - "First, we multiply, and then fold."

The procedure can be changed with the usual method - brackets:
- Here, first of all, disjunction is performed and only then the "strong" operation.

Probably, everyone understands, but for every fire: and this two different Formulas! (both in the formal and in meaningful plan)

Make a truth table for formula. This formula includes two elementary statements and "at the entrance" we need to list all possible combinations of units and zeros. To avoid confusion and discrepancies to 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 must be performed negation statements. Well, we deny the "PE" column - the units convert to zeros, and zeros - in units:

At the second step, we look at the columns and and apply to them operation or. A little closer forward, I will say that the disjunction is permutable (and is the same thing)And therefore columns can be analyzed in the usual way - from left to right. When performing a logical addition, it is convenient to use the following applied argument: "If two zero - put zero, if at least one unit is one":

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

... carefully carefully ... We look at the final columns .... In the statement algebra such formulas are called equivalent or identical:

(Three horizontal screenshots are identity icon)

In the 1st part of the lesson, I promised to express implication through basic logic operations, and the promise did not make it comes to wait! Those who wish can invest in implication meaningful meaning (for example, "If it rains, then the street is raw") And independently analyze the equivalent statement.

Formulate general definition: two formulas are called equivalent (identical)if they take the same values \u200b\u200bfor any set of values \u200b\u200bincluded in these formulas of variables (elementary statements). Also say that "Formulas are equivalent if their truth tables coincide"But I do not really like this phrase.

Exercise 1

Make a table of truth for the formula and make sure that the identity familiar to you.

Once again we repeat the problem of solving the problem:

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

2) implications "weaker" conjunction, but they are located in brackets. Fill the column, while it is convenient to use the following applied argument: "If zero follows from the unit, then put zero, in all other cases - a unit". Next, fill the column for implication, and at the same time, attention! - Columns and should be analyzed "right to left"!

3) and at the final stage fill the final column. And here it is convenient to talk like this: "If in columns and two units, then put a unit, in all other cases - zero".

And finally, we draw with the truth table equivalents .

Basic equivalence algebra statements

With two of them we just met, but they are clear, not limited. The identities are quite a lot and I will list the most important and most famous of them:

Communction commutativity and switchability of disjunction

Commutativeness - This is a permutation:

Familiar with the 1st grade rules: "From the permutation of multipliers (terms), the work (amount) does not change". But with all the apparent elementality of this property, it is not always fair, in particular, noncommutative is matrix multiplication (In general, they cannot be rearranged), but vector artwork vectors - Anti-commutative (the permutation of vectors involves changing the sign).

And, moreover, here 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 a meaningful point of view, but indistinguishable from the standpoint of formal truth. ... such students know each of us, and from ethical considerations we will not voice specific names \u003d)

Associativity of logical multiplication and addition

Or, if "School" is a combination property:

Distributing properties

Please note that in the 2nd case it will incorrect to talk about the "disclosure of the brackets", in a certain sense here "fiction" - after all, they can be removed at all:, because Multiplication is a stronger operation.

And again - these seemingly "banal" properties are carried out far from all algebraic systems, and moreover, they require evidence (about which we will talk very soon). By the way, the second distributional law is unfair even in our "ordinary" algebra. And in fact:

Law idempotency

What to do, Latin ....

Directly some kind of principle of a healthy psyche: "I and I am me", "I or I am - this is also me" \u003d)

And immediately some similar identities:

... Hmm, something I even podzavis ... So the doctor of philosophy can be waking up tomorrow \u003d)

Dual denial law

Well, here already suggests an example with the Russian language - everyone knows that two particles do not mean "yes." And in order to strengthen the emotional color of negation often use three "not":
- Even with tiny proof it turned out!

Absorption laws

- "Was there a boy?" \u003d)

In the right identity, the brackets can be omitted.

Laws de Morgana

Suppose that a strict teacher (whose name you are also known :)) puts the exam if - The student answered the 1st question and – The student answered the 2nd question. Then the statement says that Student not Passed the examwill be equivalent to the statement - Student not answered the 1st question or on the 2nd question.

As noted above, equivalence is subject to evidence, which is standardly carried out using the truth tables. In fact, we have already proven equivalence, expressing implication and equivalence, and now it's time to consolidate the technique of solving this task.

We prove identity. Since it includes a single statement, then "at the entrance" is possible only two options: one or zero. Next you attribute a single column and apply to them rule I.:

As a result, the formula was obtained "at the exit", the truth of which coincides with the truth of the statement. Evidence is proved.

Yes, this proof is primitive (and someone will say that and "stupid")But a typical teacher in the Matlogic will unwind the soul for him. Therefore, even such simple things should not be negligible.

Now you will be convinced, for example, in the justice of the law de Morgana.

First, we will make a table of truth for the left side. Since the disjunction is in brackets, then first of all I carry it out, after which I deny the column:

Next, make a truth table for the right side. Here, too, everything is transparent - first of all we hold more "strong" denials, then apply to columns rule I.:

The results coincided, therefore, identity is proved.

Any equifiability can be represented as identically true formula . It means that With any source set of zeros and units "At the output" it turns out a strictly unit. And this is a very simple explanation: since the truth tables and coincide, then, of course, they are equivalent to. Connections, for example, the equivalence of the left and right part of the just proven identity de Morgana:

Or, if more compact:

Task 2.

Prove the following equivalence:

b)

Summary at the end of the lesson. Not lazy! Try not easy to make truth tables, but also clearly Formulate conclusions. As I recently noted, neglecting simple things can do very and very expensive!

We continue to get acquainted with the laws of logic!

Yes, quite right - we are already working with them:

True for , called identically true formula or law of Logic.

By virtue of the previously reasonable transition from equivagivity to the identically true formula, all the above identities are laws of logic.

Formula that takes the value Falsefor any set of values \u200b\u200bof the variables included in it, called identically false formula or contradiate.

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

Proof trivial:

"At the output" obtained exclusively zeros, therefore, the formula is really the identity is false.

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

It is impossible to argue such an extensive topic in a single article, and therefore I will limit only by several laws:

The law of an excluded third

- In classical logic, any statement is truly or false and the third is not given. "To be or not to be" - this is what the question is.

Independently make a truth sign and make sure that it is identically true formula.

The law of contraposition

This law was actively worried when we discussed the essence. required condition, remember: "If during the rain on the street, then it follows from this that if it is dry on the street, then the rain was definitely not".

Also follows from this law that if just straight theorem , it will necessarily be true and the statement that is sometimes called opposite Theorem.

If true inverse theorem, then due to the law of contraposition, and the theorem, opposite inverse:

And back to our meaningful examples: for statements - the number is divided into 4, - the number is divided into 2 Fair straight and opposite theorems but false inverse and opposite inverse Theorems. For the "adult" formulation of the Pythagore theorem, all 4 "directions" are true.

Silogism law

Also a classic genre: "All oaks - trees, all trees - plants, therefore, all oaks - plants".

Well, here again, I want 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 definitely a plant \u003d) ... although, if you think about, then maybe with informal too \u003d )

Make a truth table for formula. In accordance with the priority of logical operations, adhere to the following algorithm:

1) Perform the implications and. Generally speaking, you can immediately fulfill the 3rd implication, but it is more convenient with it (And permissible!) sort out a little later;

2) Apply to columns rule I.;

3) Now we carry out;

4) And at the final step, we use the implication of columns and.

Feel free to control the process of index and middle finger :))


From the last column, I think everything is clear without comment:
As required to prove.

Task 3.

Find out whether the law of logic will be the following formula:

Summary at the end of the lesson. Yes, and I almost forgot - let's treat the initial sets of zeros and units in exactly the same order as in the proof of the Slogism law. Rows Of course, it is possible to rearrange, but it will greatly accumulate with my decision.

Transformation of logical formulas

In addition to its "logical" appointment, equivalence is widely used to convert and simplify formulas. Roughly speaking, one part of the identity can be changed to another. So, for example, if you met a fragment in the logical formula, then according to the law of idempotency instead, it is possible (and necessary) to write simple. If you see, simplify the recording before the absorption law. Etc.

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

where - any (arbitrarily complex) Formulas.

We convert, for example, complex implication (1st identity):

Next, we apply to the bracket "Complex" law de Morgana, while, by the priority of operations, it is the law where :

Brackets can be removed, because Inside there is more "strong" conjunction:

Well, and with commutativity, everything is simple - it is not necessary to designate anything ... Something I got into the soul of Silogism's law :))

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

Let's say out loud logical chain "with oak, tree, a plant", and you will understand that the meaningful meaning of the law has not changed from the permutation of implications. Is that the wording has become original.

As a workout, a strict formula.

Where to begin? First of all, deal with the procedure for action: here the negation is applied to a whole bracket, which is "fastened" with the statement of "slightly weaker" conjunction. Essentially, we have a logical product of two multipliers :. Of the two remaining operations, implication has lower priority, and therefore the entire formula has the following structure :.

As a rule, in the first step (steps) get rid of equivalence and implications (if they are) and reduce the formula to three basic logical operations. What you say here .... Logical.

(1) We use identity . And our case.

Then usually follow the "disassembly" with brackets. First, the whole solution, then comments. In order not to be "oil oil", I will use the "ordinary" equality icons:

(2) Apply the de Morgana law to external brackets, where.

The considered operations on sets are subject to some laws that resemble the well-known elementary laws of algebra numbers. This defines the name algebra Setwhich is often referred to as the milk algebra sets, which is associated with the name of the English mathematics John Bul, which laid the idea of \u200b\u200ban analogy between algebra and logic.

For arbitrary sets A, B, and C. Fair the following identities (Table 3.1):

Table 3.1

1. The law of identity
2. Common communion	2 '. Commitment intersection
3. Associative association	3 '. Associative intersection
4. Distribution of association relative to the intersection	four'. Distribution of intersection regarding the union
5. Action laws with empty and versatile multiple (the law excluded the third)	five'. Action laws with empty and versatile multiple (law contradiction)
6. Combination Idmpnotation Law	6 '. Law Implement Law
7. De Morgana Law	7 '. Law de Morgana
8. The law of elimination (absorption)	eight'. Elimination law (absorption)
9. The law of gluing	nine'. The law of gluing
10. Perestsky law	10'. Perestsky law
11. The Law of Involution (Double Supplement)

The laws of the algebra sets in relation to the operations of the intersection () and association () are subject to the principle of duality: if in any law all the intersection marks replace the unification signs, and all the signs of the intersection - the intersection signs, the universal sign (U) replace the sign of the empty set (Ø), and an empty sign is a universal sign, then we will get a loyal identity again. For example (by virtue of this principle), from follows, etc.

3.1. Checking the truth of identities using Euler-Venna charts

All the laws of algebra sets can be clearly present and prove using Euler-Venna charts. For this you need:

Draw the appropriate diagram and shade all sets in the left part of equality.

Draw another diagram and do the same for the right part of equality.

This identity is truly then and only when the same area is shaded on both diagrams.

Note 3.1.Two intersecting circles divide all the universal set into four areas (see Fig.3.1)

Note 3.2. Three intersecting circles divide all the universal set for eight regions (see Fig.3.2):

Note 3.2. When recording conditions of various examples, notation is often used:

 - from ... follows ...;

 - Then and only when ....

Task 3.1. . Simplify the expressions of the algebra sets:

Decision.

A task 3 .2 . Prove identities:

(Av) \\ B \u003d a \\ in;

A (VС) \u003d a \\ (a \\ c)  (a \\ s).

Decision.

Task 3.3. . Prove the following ratios in two ways: with the help of diagrams and by determining the equality of sets.

Decision.

2. Proof by determining the equality of sets.

By definition, the sets x and y are equal, if relations are simultaneously satisfied: xy and yx.

First, we show that
. Let be h. - arbitrary element of the set
, i.e h.
. It means that h.u I. h.
. From here it follows that h.a or h.. If a h., then h.ā, and therefore
. If h.V, T.
and therefore
. Thus, every element of the set.
. There are also a set of multiple
I.e

Now we will prove the opposite, that is, that
. Let be
. If a h.ā, T. h.u I. h.a, which means h.v. Hence it follows that
. If
T. h.u I. h.. It means h.v, that is
. From here it follows that every element of the set
is also a set of multiple
, i.e
.

It means
As required to prove.

A (BC) \u003d (AB)  (AC);

1. Proof with the help of a diagram:

Let be h. (VС). Then h.a I. h.ВС If a h.V, T. h.v, which is not contrary to the said, and therefore h. (Av)  (АС). If h.С, TO. h.АС. Hence, h. (AB)  (AC). So, it is proved that A (BC)  (AB)  (AC.

Let now h. (AB)  (AC). If a h.Av, T. h.a I. h.. Hence it follows that h.a I. h.ВС, that is h. (VС). If h.АС, T. h.a I. h.c. From here it follows that h.a I. h.ВС, that is h. (VС). Thus, (AB)  (AC)  A (BC). Consequently, A (BC) \u003d (AB)  (AC). Q.E.D.

In case of evidence of sufficiency, we received that AV \u003d . Obviously, c, so the ratio is proved. In evidence, the most general case was considered. However, there are still some options when building diagrams. For example, the case of equality AV \u003d C or
, case of empty set and so on. Obviously, all possible options to take into account is difficult. Therefore, it is believed that the proof of relations with the help of diagrams is not always correct.

2. Proof by determining the equality of sets.

Necessity. Let AV and the element h.a. We show that in this case the element of the set A will also be the element of the set
.

Consider two cases: h.v or
.

If a h.V, T. h.АВС, that is h.c, and, as a result,
.

If
, that I.
. The need is proved.

Let now
and h.v. We show that the element h.there will also be an element of a set C.

If a h.v, then h.a I. h.. Insofar as
So h.c. Sufficiency is proved.

1. Proof with the help of a diagram:

2. Proof by determining the equality of sets.

Let Av Consider item h.V (or
). Similarly: h.a (or h.ā). That is, every element of the set there is also an element of the set ā. And this may be in case
. Q.E.D.

Task 3.4. Express the symbolically indicated areas and simplify the obtained expressions.

Decision.

The desired area consists of two isolated parts. Conditionally let's call them top and bottom. The set, which they depict, can be described like this:

M \u003d ( x. x.a I. h.B I. h.С or h.С I. h.a I. h.V).

From the definition of operations over sets, we get:

M \u003d ((Av) \\ C)  (C \\ A \\ B).

We write this expression with the help of basic operations - additions, association and intersection:

It is impossible to simplify this expression because we have one entry of each symbol. This is the simplest view of this formula.

This area can be viewed as a union of sets A \\ B \\ C and AVС. By definition M \u003d ( x. x.a I. x.B I. h.С or h.a I. h.B I. h.С). We simplify:

Tasks for self solutions.

1. Simplify:

2. Prove with the help of diagrams, laws algebra sets and definitions of sets of sets:

(Av) \\ B \u003d a \\ in;

A (VС) \u003d a \\ (a \\ c)  (a \\ s);

Av \u003d Av  A \u003d B;

A \\ B \u003d   AV \u003d A.

3. To find out if there are many x, satisfying with any equality:

Ah \u003d a; (answer );