Determining the truth value of statements. Establishing the truth of complex statements

Propositional logic , also called propositional logic, is a branch of mathematics and logic that studies the logical forms of complex statements constructed from simple or elementary statements using logical operations.

Propositional logic abstracts from the content of statements and studies their truth value, that is, whether the statement is true or false.

The picture above is an illustration of a phenomenon known as the Liar Paradox. At the same time, in the opinion of the author of the project, such paradoxes are possible only in environments that are not free from political problems, where someone can a priori be labeled a liar. In the natural multi-layered world the subject of “truth” or “false” only individual statements are evaluated . And later in this lesson you will be introduced to the opportunity to evaluate many statements on this subject for yourself (and then look at the correct answers). Including complex statements in which simpler ones are interconnected by signs of logical operations. But first, let’s consider these operations on statements themselves.

Propositional logic is used in computer science and programming in the form of declaring logical variables and assigning them logical values ​​“false” or “true”, on which the course of further execution of the program depends. In small programs where only one boolean variable is involved, the boolean variable is often given a name such as "flag" and the meaning is "flag is up" when the variable's value is "true" and "flag is down." , when the value of this variable is "false". In large programs, in which there are several or even many logical variables, professionals are required to come up with names for logical variables that have a form of statements and a semantic meaning that distinguishes them from other logical variables and is understandable to other professionals who will read the text of this program.

Thus, a logical variable with the name “UserRegistered” (or its English-language analogue) can be declared in the form of a statement, which can be assigned the logical value “true” if the conditions are met that the registration data was sent by the user and this data is recognized as valid by the program. In further calculations, the values ​​of the variables may change depending on the logical value (true or false) of the UserRegistered variable. In other cases, a variable, for example, with the name “More than Three Days Left Before the Day”, can be assigned the value “True” before a certain block of calculations, and during further execution of the program this value can be saved or changed to “false” and the progress of further execution depends on the value of this variable programs.

If a program uses several logical variables, the names of which have the form of statements, and more complex statements are built from them, then it is much easier to develop the program if, before developing it, we write down all the operations from statements in the form of formulas used in statement logic than we do during This lesson is what we will do.

Logical operations on statements

For mathematical statements one can always make a choice between two different alternatives, “true” and “false,” but for statements made in “verbal” language, the concepts of “truth” and “false” are somewhat more vague. However, for example, such verbal forms, like “Go home” and “Is it raining?” are not statements. Therefore it is clear that statements are verbal forms in which something is stated . Interrogative or exclamatory sentences, appeals, as well as wishes or demands are not statements. They cannot be evaluated with the values ​​"true" and "false".

Statements, on the contrary, can be considered as quantities that can take on two meanings: “true” and “false”.

For example, the following judgments are given: “a dog is an animal”, “Paris is the capital of Italy”, “3

The first of these statements can be evaluated with the symbol “true”, the second with “false”, the third with “true” and the fourth with “false”. This interpretation of statements is the subject of propositional algebra. We will denote statements with big letters in Latin letters A, B, ..., and their meanings, that is, true and false, respectively AND And L. In ordinary speech, connections between statements “and”, “or” and others are used.

These connections allow, by connecting different statements with each other, to form new statements - complex statements . For example, the connective "and". Let the statements be given: " π more than 3" and the statement " π less than 4". You can organize a new - complex statement " π more than 3 and π less than 4". Statement "if π irrational then π ² is also irrational" is obtained by connecting two statements with the connective "if - then". Finally, we can obtain from any statement a new one - a complex statement - by denying the original statement.

Considering statements as quantities that take on meanings AND And L, we will define further logical operations on statements , which allow us to obtain new complex statements from these statements.

Let two arbitrary statements be given A And B.

1 . The first logical operation on these statements - conjunction - represents the formation of a new statement, which we will denote A ∧ B and which is true if and only if A And B are true. In ordinary speech, this operation corresponds to the connection of statements with the connective “and”.

Truth table for conjunction:

2 . Second logical operation on statements A And B- disjunction expressed as A ∨ B, is defined as follows: it is true if and only if at least one of the original statements is true. In ordinary speech, this operation corresponds to connecting statements with the connective “or”. However, here we have a non-dividing “or”, which is understood in the sense of “either or” when A And B both cannot be true. In defining propositional logic A ∨ B true both if only one of the statements is true, and if both statements are true A And B.

Truth table for disjunction:

3 . The third logical operation on statements A And B, expressed as A → B; the statement thus obtained is false if and only if A true, but B false. A called by parcel , B - consequence , and the statement A → B - following , also called implication. In ordinary speech, this operation corresponds to the “if-then” connective: “if A, That B". But in the definition of propositional logic, this statement is always true regardless of whether the statement is true or false B. This circumstance can be briefly formulated as follows: “from the false everything follows.” In turn, if A true, but B is false, then the entire statement A → B false. It will be true if and only if A, And B are true. Briefly, this can be formulated as follows: “false cannot follow from the true.”

Truth table to follow (implication):

4 . The fourth logical operation on statements, more precisely on one statement, is called the negation of a statement A and is denoted by ~ A(you can also find the use of not the symbol ~, but the symbol ¬, as well as an overscore above A). ~ A there is a statement that is false when A true, and true when A false.

Truth table for negation:

5 . And finally, the fifth logical operation on statements is called equivalence and is denoted A ↔ B. The resulting statement A ↔ B a statement is true if and only if A And B both are true or both are false.

Truth table for equivalence:

Most programming languages ​​have special symbols to denote the logical meanings of statements; they are written in almost all languages ​​as true and false.

Let's summarize the above. Propositional logic studies connections that are completely determined by the way in which some statements are built from others, called elementary. In this case, elementary statements are considered as wholes and cannot be decomposed into parts.

Let us systematize in the table below the names, notations and meaning of logical operations on statements (we will soon need them again to solve examples).

True for logical operations laws of algebra logic, which can be used to simplify logical expressions. It should be noted that in propositional logic one abstracts from the semantic content of a statement and limits itself to considering it from the position that it is either true or false.

Example 1.

1) (2 = 2) AND (7 = 7) ;

2) Not(15;

3) ("Pine" = "Oak") OR ("Cherry" = "Maple");

4) Not("Pine" = "Oak") ;

5) (Not(15 20) ;

6) (“Eyes are given to see”) And (“Under the third floor is the second floor”);

7) (6/2 = 3) OR (7*5 = 20) .

1) The meaning of the statement in the first brackets is “true”, the meaning of the expression in the second brackets is also true. Both statements are connected by the logical operation “AND” (see the rules for this operation above), therefore the logical value of this entire statement is “true”.

2) The meaning of the statement in brackets is “false”. Before this statement there is a logical operation of negation, therefore the logical meaning of this entire statement is “true”.

3) The meaning of the statement in the first brackets is “false”, the meaning of the statement in the second brackets is also “false”. Statements are connected by the logical operation "OR" and none of the statements has the value "true". Therefore, the logical meaning of this entire statement is “false.”

4) The meaning of the statement in brackets is “false”. This statement is preceded by the logical operation of negation. Therefore, the logical meaning of this entire statement is “true.”

5) The statement in the inner brackets is negated in the first brackets. This statement in inner brackets has the meaning "false", therefore its negation will have the logical meaning "true". The statement in the second brackets means "false". These two statements are connected by the logical operation “AND”, that is, “true AND false” is obtained. Therefore, the logical meaning of this entire statement is “false.”

6) The meaning of the statement in the first brackets is “true”, the meaning of the statement in the second brackets is also “true”. These two statements are connected by the logical operation “AND”, that is, “true AND truth” is obtained. Therefore, the logical meaning of the entire given statement is “true.”

7) The meaning of the statement in the first brackets is “true”. The meaning of the statement in the second brackets is "false". These two statements are connected by the logical operation “OR”, that is, “true OR false”. Therefore, the logical meaning of the entire given statement is “true.”

Example 2. Write the following complex statements using logical operations:

1) "User is not registered";

2) “Today is Sunday and some employees are at work”;

3) “The user is registered if and only if the data submitted by the user is considered valid.”

1) p- single statement “User is registered”, logical operation: ;

2) p- single statement “Today is Sunday”, q- "Some employees are at work", logical operation: ;

3) p- single statement “User is registered”, q- “The data sent by the user was found valid”, logical operation: .

Solve examples of propositional logic yourself, and then look at the solutions

Example 3. Compute the logical values ​​of the following statements:

1) (“There are 70 seconds in a minute”) OR (“A running clock tells the time”);

2) (28 > 7) AND (300/5 = 60) ;

3) ("TV - electrical appliance") And ("Glass - wood");

4) Not((300 > 100) OR ("You can quench your thirst with water"));

5) (75 < 81) → (88 = 88) .

Example 4. Write down the following complex statements using logical operations and calculate their logical values:

1) “If the clock shows the time incorrectly, then you may arrive at class at the wrong time”;

2) “In the mirror you can see your reflection and Paris, the capital of the USA”;

Example 5. Determine the Boolean Value of an Expression

(p → q) ↔ (r → s) ,

p = "278 > 5" ,

q= "Apple = Orange",

p = "0 = 9" ,

s= "The hat covers the head".

Propositional logic formulas

Concept logical form complex statement is clarified using the concept propositional logic formulas .

In examples 1 and 2 we learned to write complex statements using logical operations. Actually, they are called propositional logic formulas.

To denote statements, as in the mentioned example, we will continue to use the letters

p, q, r, ..., p 1 , q 1 , r 1 , ...

These letters will play the role of variables that take the truth values ​​“true” and “false” as values. These variables are also called propositional variables. We will further call them elementary formulas or atoms .

To construct propositional logic formulas, in addition to the letters indicated above, signs of logical operations are used

~, ∧, ∨, →, ↔,

as well as symbols that provide the possibility of unambiguous reading of formulas - left and right brackets.

Concept propositional logic formulas let's define it as follows:

1) elementary formulas (atoms) are formulas of propositional logic;

2) if A And B- propositional logic formulas, then ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B) are also formulas of propositional logic;

3) only those expressions are propositional logic formulas for which this follows from 1) and 2).

The definition of a propositional logic formula contains a listing of the rules for the formation of these formulas. According to the definition, every propositional logic formula is either an atom or is formed from atoms as a result of the consistent application of rule 2).

Example 6. Let p- single statement (atom) “All rational numbers are real”, q- "Some real numbers are rational numbers" r- "some rational numbers are real." Translate the following formulas of propositional logic into the form of verbal statements:

6) .

1) "no real numbers, which are rational";

2) "if not all rational numbers are real, then no rational numbers, which are valid";

3) “if all rational numbers are real, then some real numbers are rational numbers and some rational numbers are real”;

4) “all real numbers are rational numbers and some real numbers are rational numbers and some rational numbers are real numbers”;

5) “all rational numbers are real if and only if it is not the case that not all rational numbers are real”;

6) “it is not the case that it is not the case that not all rational numbers are real and there are no real numbers that are rational or there are no rational numbers that are real.”

Example 7. Create a truth table for the propositional logic formula , which in the table can be designated f .

Solution. We begin compiling a truth table by recording values ​​(“true” or “false”) for single statements (atoms) p , q And r. All possible values are written in eight rows of the table. Further, when determining the values ​​of the implication operation and moving to the right in the table, we remember that the value is equal to “false” when “false” follows from “true”.

Note that no atom has the form ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B) . Complex formulas have this type.

The number of parentheses in propositional logic formulas can be reduced if we accept that

1) in complex formula we will omit the outer pair of brackets;

2) let’s arrange the signs of logical operations “in order of precedence”:

↔, →, ∨, ∧, ~ .

In this list, the ↔ sign has the largest scope and the ~ sign has the smallest scope. The scope of action of an operation sign refers to those parts of the formula of propositional logic to which the occurrence of this sign in question is applied (on which it acts). Thus, it is possible to omit in any formula those pairs of parentheses that can be restored, taking into account the “order of precedence”. And when restoring parentheses, first all parentheses related to all occurrences of the sign ~ are placed (we move from left to right), then to all occurrences of the sign ∧, and so on.

Example 8. Restore the parentheses in the propositional logic formula B ↔ ~ C ∨ D ∧ A .

Solution. The brackets are restored step by step as follows:

B ↔ (~ C) ∨ D ∧ A

B ↔ (~ C) ∨ (D ∧ A)

B ↔ ((~ C) ∨ (D ∧ A))

(B ↔ ((~ C) ∨ (D ∧ A)))

Not every propositional logic formula can be written without parentheses. For example, in formulas A → (B → C) and ~( A → B) further exclusion of brackets is not possible.

Tautologies and contradictions

Logical tautologies (or simply tautologies) are formulas of propositional logic such that if letters are arbitrarily replaced by statements (true or false), the result will always be a true statement.

Since the truth or falsity of complex statements depends only on the meanings, and not on the content of the statements, each of which corresponds to a specific letter, then checking whether this statement tautology, can be substituted in the following way. In the expression under study, the values ​​1 and 0 (respectively “true” and “false”) are substituted for the letters in all possible ways and the logical values ​​of the expressions are calculated using logical operations. If all these values ​​are equal to 1, then the expression under study is a tautology, and if at least one substitution gives 0, then it is not a tautology.

Thus, a propositional logic formula that takes the value “true” for any distribution of the values ​​of the atoms included in this formula is called identical to the true formula or tautology .

The opposite meaning is a logical contradiction. If all values ​​of statements are equal to 0, then the expression is a logical contradiction.

Thus, a propositional logic formula that takes the value “false” for any distribution of the values ​​of the atoms included in this formula is called identically false formula or contradiction .

In addition to tautologies and logical contradictions, there are formulas of propositional logic that are neither tautologies nor contradictions.

Example 9. Construct a truth table for a propositional logic formula and determine whether it is a tautology, a contradiction, or neither.

Solution. Let's create a truth table:

In the meanings of the implication we do not find a line in which “true” implies “false”. All values ​​of the original statement are equal to "true". Hence, this formula propositional logic is a tautology.

Example 1. Establish the truth of a statement · C
Solution. A complex statement includes 3 simple statements: A, B, C. The columns in the table are filled with values ​​(0, 1). All are indicated possible situations. Simple statements are separated from complex ones by a double vertical line.
When compiling a table, care must be taken not to confuse the order of actions; When filling out the columns, you should move “from the inside out,” i.e. from elementary formulas to more and more complex ones; the last column filled in contains the values ​​of the original formula.

The table shows that this statement is true only in the case when A = 0, B = 1, C = 1. In all other cases it is false.

Equivalence of statements.

Using truth tables, you can establish the equivalence of two or more statements.

Statements are said to be equivalent if the corresponding values ​​of each of them coincide in the truth table.

Example 2. It is stated that the statement A+B·C is equivalent to the statement (A+B)· (A+C)
Solution. The verification is carried out by compiling a truth table.

Comparing the 5th and 8th columns, we make sure that all the values ​​​​obtained by the formula A + B · C coincide with the values ​​​​obtained by the formula (A + B) · (A + C), i.e. the statements are equivalent (equivalent). One can replace the other.
Equivalent (equivalent) statements are connected by the sign º A + B · Cº (A + B) · (A + C).
Let us note the difference between equivalence and equivalence.
Equivalence is a logical operation that allows, given two given statements A and B, to construct a new A and B.
Equivalence is the relationship between two constituent statements, consisting in the fact that their truth values ​​are always the same.

Tautology.

Let a statement A· be given and it is necessary to construct a truth table.
Statement A is false, its truth does not depend on the truth of statement A.

Consider the statement B+.
In this case, the statement B+ is always true, regardless of the truth of B.

Statements whose truth is constant and does not depend on the truth of the simple statements included in them, but is determined only by their structure, are called identical or tautologies.
There are identically true and identically false statements.
In formulas, each identically true statement is replaced by 1, and each identically false statement is replaced by 0. The law of the excluded middle.
A º 0
B+ º 1

Example 3. Prove the tautology (XÙ Y)® (XÚ Y)
Solution.

Because the statement (XÙ Y)® (XÚ Y) is always true, then it is a tautology.

Example 4. Prove the tautology ((X® Y)Ù (Y® Z))® (X® Z)
Solution.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F

The table shows that the statement under study is a tautology, because it is truly constant.

Questions and assignments.

1. Which of the following statements:

a) (A+C); b) +B; c) +C); d) A+;
equivalent statement (B+C)

2. Use truth tables to determine which following formulas- tautologies:
A) " ); b) ; V) ;

G) ; e) (X® Y) « (Y® X); f) (X® Y) « ;

g) (X® Y)« .

3. Establish the truth of a statement

4. Are the statements equivalent:
And ?

5. Determine whether this statement is a tautology:
A) ; b)

6. For each formula, come up with sentences that they formalize:
A) ; b) ; V) .

7. From simple sayings: “Victor is a good swimmer” - A; “Victor dives well” - B; “Victor sings well” - C, a complex statement has been composed, the formula of which looks like:
X=(A+C)· (A+B). Determine whether the statement X is equivalent to the statement: “Victor is a good swimmer and Victor sings well.”

8.
A) ; b) ;
c) ((X1® X2)® X3)Ù (X3 « X1); d) ((X® Y)Ù (Y® Z))® (X® Z).

9. Determine the truth of the statements:
A) , , ;
b) , , ;
V) , , ;
G) , , .

Laws of logic

Equivalences of propositional logic formulas are often called laws of logic.
Knowledge of the laws of logic allows you to check the correctness of reasoning and evidence.
Violations of these laws lead to logical errors and the contradictions arising from them.
We list the most important of them:
1. Xº X Law of identity
2. Law of contradiction
3. Law of the excluded middle
4. The law of double negatives
5. XÙ Xº X , XÚ Xº C Laws of idempotency
6. C Ù U º U Ù C , C Ú U º U Ú C Laws of commutability (commutability)
7. (C Ù U) Ù Z ºC Ù (U Ù Z) , (C Ú U) Ú Z º C Ú (U Ú Z) - Laws of associativity (combination)
8. C Ù (U Ú Z) º (C Ù U) Ú (C Ù Z), C Ú (U Ù Z) º (C Ú U) Ù (C Ú Z) - Laws of distributivity (distribution)
9. , De Morgan's laws
10. XÙ 1º C , C Ú 0 º C
11. C Ù 0 º 0 , C Ú 1 º 1
12. C Ù (C Ú U) º C , C Ú (C Ù U) º C Absorption laws
13. (C Ú U) Ù ( Ú U) º U , (C Ù U) Ú ( Ú U) º U Laws of gluing

1st law formulated by the ancient Greek philosopher Aristotle. The law of identity states that the thought contained in a certain statement remains unchanged throughout the entire argument in which this statement appears.

Law of contradiction says that no sentence can be true at the same time as its negation.
“This apple is ripe” and “This apple is not ripe.”

Law of the excluded middle says that for every statement there are only two possibilities: this statement is either true or false. There is no third option. “Today I will get 5 or I won’t.” Either a proposition is true or its negation.

The law of double negation. To deny the negation of a statement is the same as to affirm this statement.
“It is not true that 2×2¹ 4”

Laws of idempotency. In the algebra of logic there are no exponents and coefficients. A conjunction of identical “factors” is equivalent to one of them.

Laws of commutativity and associativity. Conjunction and disjunction are similar to the multiplication and addition signs of the same name.
Unlike addition and multiplication of numbers, logical addition and multiplication are equal in relation to distributivity: not only is conjunction distributive relative to disjunction, but also disjunction is distributive relative to conjunction.

The meaning of De Morgan's laws(Augustus de Morgan (1806-1871) - Scottish mathematician and logician) can be expressed in brief verbal formulations:
- the negation of a logical product is equivalent to the logical sum of the negations of the factors.
- the negation of a logical sum is equivalent to the logical product of the negations of the terms.

You can prove the laws of logic:
1) using truth tables;
2) using equivalences.
Let us prove the laws of adhesion and absorption using equivalences:
1) (C Ú U) Ù ( Ú U) º (C + U) × ( + U) º C × + U × + U × U + C × U ºU × + U + C × U º U × +U (1 + C) º U × + U º U ( + 1) º U (Gluing Law)

2) C Ù (C Ú U) º C × C +C × U º C +C × U º C (1 + U) º C (Law of absorption)

Exercise. Prove the laws of logic using truth tables.

Identity transformations

Simplification of formulas.

Example 1. Simplify the formula (AÚB) · (AÚC)
Solution.
a) Open the brackets (A Ú B) · (A ÚC) º A · A Ú A · C Ú B · A Ú B · C
b) According to the law of equivalence A · A º A, therefore,
A · A Ú A · C ÚB · A Ú B · C º A ÚA · C Ú B · A Ú B · C
c) In the statements A and A·C, we take A out of brackets and using the property AÚ1º 1, we obtain AÚA·СÚ B · A Ú B · C º A ·(1 ÚС) Ú B · A Ú B · Сº A ÚB · A Ú B·C
d) Similar to point c), let’s take statement A out of brackets.
AÚB · A Ú B · Сº A (1ÚB)ÚB · Сº A Ú B · С
Thus, we have proven the law of distributivity.

2. Transformations “absorption” and “bonding”

Example 2. Simplify the expression AÚ A · B

Solution. A ÚA · B º A (1 Ú B) º A - absorption

Example 3. Simplify the expression A · B Ú A · - logical addition signs;
- signs of logical multiplication.
And will be used:
- signs of negation and logical multiplication;
- signs of negation and logical addition.

Example 5. Transform the formula so that it does not use logical addition signs.
Solution. Let's use the law of double negation and then De Morgan's formula.

Example 6. Transform the formula so that it does not use logical multiplication signs.
Solution. Using de Morgan's formulas and the law of double negation we get:

Here: 1 - true, 0 - false.

• 1. X: triangle ABC- acute-angled. X: It is not true that triangle ABC is acute. It's the same as: X: triangle ABC - right or obtuse
• 2. A: Ivanova M. received a 4 in the mathematics exam. : It is not true that Ivanova M. received a 4 in mathematics.

Definition: The disjunction of statements A and B is a statement AB that is true under the condition that at least one of the statements A or B is true.

It is read "A or B".

Truth table for AB

Example: 1. This time the defendant appeared and the trial took place. - true

2. B right triangle the sum of any two angles is greater than or equal to the third angle and the hypotenuse is less than the leg. - lie

Definition: An implication of statements A and B is a statement AB that is false only if A is true and B is false.

It is read: “If A, then B.”

Truth table

Example: 1. If I pass the test, I will go to the cinema.

2. If the triangle is isosceles, then the angles at its base are equal. Definition: The equivalent of statements A and B is a statement AB that is true if and only if A and B have the same truth (i.e., either both are true or both are false).

They read: “And if and only if B” or “A is necessary and sufficient for B”

Truth table

The second task, solved by means of propositional algebra, is to determine the truth of a particular statement based on the compilation of its formula (formalization process) and the compilation of a truth table.

Example: If Saratov is located on the banks of the Neva, then polar bears live in Africa.

A: Saratov is located on the banks of the Neva River;

Q: Polar bears live in Africa

Definition: A formula that is true regardless of what values ​​the propositional variables included in it take is called a tautology or an identically true formula.

Definition: Formulas F 1 and F 2 are called equivalent if their equivalent is a tautology.

Definition: If the formulas F 1 and F 2 are equivalent, then the sentences P 1 and P 2 that initiate these formulas are called equivalent in propositional logic.

The basic, most frequently occurring equivalences are called the laws of logic. Let's list some of them:

• 1. X X - law of identity
• 2. XL - law of contradiction
• 3. XI - the law of exclusion of the third
• 4. X - law of double negation

• 5. laws of commutativity
• 6. X (Y Z) (X Y) Z law of associativity

X (Y Z) (X Y) Z distributive law

7. De Morgan's laws

8. laws of articulation of a variable and a constant

Using the laws of logic, you can transform formulas.

4. Of the many formulas that are equivalent to each other, let’s consider two. This is a perfect conjunctive normal form(SCNF) and perfect disjunctive normal form (SDNF). They are constructed for a given formula based on its truth table.

Construction of SDNF:

• -- rows are selected that correspond to the truth values ​​(1) of this formula;
• -- for each selected line we compose a conjunction of variables or their negations so that the sets of values ​​of the variables presented in the line correspond true values conjunctions (for this you need to take variables that took the value false (0) in this line with a negation sign, and variables that took the value truth (1) without negation);
• -- a disjunction of the resulting conjunctions is compiled.

It follows from the algorithm that for any formula it is possible to construct an SDNF, and, moreover, a unique one, if the formula is not identically false, i.e. accepting only false values.

The compilation of the SKNF is carried out according to the following algorithm:

• -- highlight those table rows in which the formula takes the value false (0);
• -- from the variables in each such line, create a disjunction that should take the values ​​- false (0). To do this, all variables must enter it with the value false, therefore those that are true (1) must be replaced with their negation;
• -- form a conjunction from the resulting disjunctions.

Obviously, any formula that is not a tautology has an SCNF.

SDNF and SCNF are used to obtain consequences from this formula.

Example: Create a truth table of SDNF and SCNF for the formula: .

Truth table of SDNF and SKNF

5. Consider the expressive form “The river flows into the Black Sea.” It contains one variable and can be represented as “River x flows into the Black Sea.”

Depending on the values ​​of the variable X, the sentence is either true or false, i.e. a mapping of a set of rivers onto a two-element set is specified. Let us denote this mapping, then:

Thus, we have a function whose all values ​​belong to the set.

Definition: A function whose all values ​​belong to a set is called a predicate.

Letters denoting predicates are called predicate symbols.

Predicates can be specified:

a) an expressive formula,

b) formula, i.e. specifying the interpretation of the predicate symbol,

c) table.

1) P - “to flow into the Black Sea.”

This formula means that “River a flows into the Black Sea.”

• 2) Predicate P is given by an expressive formula: “to be prime number on the set of the first 15 natural numbers."
• 3) In tabular form, the predicate has the form:

The domain of definition of predicates can be any set.

If a predicate loses its meaning for any set of input variables, then it is generally accepted that the value L corresponds to this set.

If a predicate contains one variable, then it is called a unary predicate, two variables - a double predicate, n variables - an n-ary predicate.

To translate texts into the language of predicates and determine their truth, it is necessary to introduce logical operations on predicates and quantifiers.

The following operations are also performed on predicates: negation, conjunction, disjunction, implication, equivalence.

Definition: A subset of the set M on which the predicate P is given, consisting of those and only those elements of M to which the value I of the predicate P corresponds, is called the truth set of the predicate P.

The truth set is designated.

Definition: The negation of the predicate P is a predicate that is false for those sets of variable values ​​that turn P into true, and true for those sets of variable values ​​that turn P into a false predicate.

Negation is indicated.

Be a student of ABiK.

Not to be a student of ABiK.

If, then the set, where M is the set on which the predicates P and Q are given.

Definition: a conjunction of predicates is a predicate that is true for those and only those values ​​of the variables included in it that make both predicates true.

Be a football player

Be a student

: to be a football player and to be a student.

Definition: a disjunction of predicates is a predicate that is false for those sets of variables included in it that make both predicates false

Be even natural number

Be an odd natural number

: be a natural number.

Definition: Predicate implication is a predicate that is false for those and only those sets of variables included in it that turn into a true predicate and into a false one.

Indicated by:

Be a prime number on the set N

Be an odd number

False for and true for other natural numbers.

Definition: Predicate equivalence is a predicate that becomes true if both predicates are true or both are false.

Indicated by:

- “to win”, i.e. x beats y

It is better to know chess history, x knows better than y

denotes that x beats y at chess if and only if he knows the theory better.

Definition: A predicate follows from a predicate if the implication is true for any values ​​of the variables included in it.

The following are indicated: .

Be a student

Go to college

There are 2 ways to turn a predicate into a statement:

1) giving a variable specific meaning

; x - student

Ivanov is a student.

2) Attaching quantifiers - any, every, every

There is, there is.

The entry where it has the property P means that every object x has the property P. Or in another way, “all x have the property P.”

The entry means that there is an object x that has property P.

Logic, created as a science by Aristotle (384-322 BC), has been used over the centuries to develop many fields of knowledge, including theology, philosophy, and mathematics.

It is the foundation on which the entire edifice of mathematics is built. Essentially, logic is the science of reasoning, which allows one to determine the truth or falsity of something. mathematical statement, based on a set of primary assumptions called axioms. Logic is also used in computer science to construct computer programs and evidence of their correctness. Concepts, methods and means of logic underlie modern information technology. One of the main goals of this work is to lay out the foundations of mathematical logic, show how it is used in computer science, and develop methods for analyzing and proving mathematical statements.

Logical representations - description of the studied system, process, phenomenon in the form of a set complex statements made up of simple (elementary) statements And logical connectives between them. Logical representations and their components are characterized by certain properties and a set of permissible transformations over them (operations, inference rules, etc.), implementing those developed in formal (mathematical) logic correct methods reasoning - laws of logic.

Concept of utterance

Statement is this a statement or declarative sentence, which can be said to be true or false. In other words, a statement about the truth or falsity of a statement must make sense. The truth or falsity attributed to a statement is called its truth value, or truth value.

For example, statements Twice two is four And The city of Chelyabinsk is located in the Asian part of Russia true and statements Three is more than five And The Don River currently flows into the Caspian Sea are false because they are not true. True statements are usually denoted T (true) or AND (true), and false, respectively, F (false) or L (lie). In computer science, truth is usually denoted by 1 (binary one), and false by 0 (binary zero).

Here are examples of sentences that are not statements:

Who are you?(question),

Read this chapter before next lesson (order or exclamation)

This statement is false(internally contradictory statement),

The area of ​​the segment is less than the length of the cube(it is impossible to say whether this sentence is true or false, because it has no meaning).

We will denote statements with letters Latin alphabet r, q, r, For example, r can mean a statement It will rain tomorrow, A q- statement The square of an integer is a positive number.

Logical connectives

In everyday speech for education complex sentence of the simple ones, connectives are used - special parts of speech that connect individual offers. The most commonly used connectives And, or, Not, If ... That, only if, And then and only then. Unlike ordinary speech, in logic the meaning of such connectives must be unambiguously determined. The truth of a complex statement is uniquely determined by the truth or falsity of its constituent parts. A statement that does not contain connectives is called simple. A statement containing connectives is called complex. Logical connectives also called logical operations over statements.

Let r And q stand for statements

r: Jane drives a car,

q: Bob has brown hair.

Complex statement

Jane drives a car and Bob has brown hair consists of two parts connected by a bond And. This statement can be symbolically written as

where the symbol represents the word And in the language of symbolic expressions. The expression is called a conjunction of propositions r And q.

The following variants of writing the conjunction are also found:

Exactly the same statement

Jane drives a car or Bob has brown hair.

symbolically expressed as

where is the word or translated into symbolic language. The expression is called a propositional disjunction r And q.

Refutation or denial of a statement p denoted by

Thus, if r there is a statement Jane drives a car, then this is a statement Jane doesn't drive a car.

If r there is a statement Joe likes computer science, That Jane doesn't drive a car and Bob has brown hair or Joe likes computer science will be symbolically written as

.

Conversely, the expression

this is a symbolic form of recording a statement Jane drives a car, Bob doesn't have brown hair, and Joe likes computer science..

Let's consider the expression. If someone says: " Jane drives a car and Bob has brown hair.", then we naturally imagine Jane driving a car and fair-haired Bob. In any other situation (for example, if Bob is not brown-haired or Jane does not drive a car), we will say that the speaker is wrong.

There are four possible cases that we need to consider. Statement r may be true ( T) or false ( F) and regardless of what truth value it takes r, statement q may also be true ( T) or false ( F). Truth table lists everything possible combinations truth and falsity of complex statements.

So, a conjunction is true if and only if both statements are true p And q, that is, in case 1.

In the same way, consider the statement Jane drives a car or Bob has brown hair, which is symbolically expressed as . If someone says: “Jane drives a car or Bob has brown hair,” then he will be wrong only if Jane cannot drive a car and Bob is not brown-haired. For the entire statement to be true, it is sufficient that one of its two components be true. Therefore it has a truth table

The disjunction is false only in case 4, when both r And q false.

The truth table for negation looks like

The truth value is always the opposite of the truth value p. In truth tables, the negation is always evaluated first, unless the negation sign is followed by a statement enclosed in parentheses. Therefore interpreted as , so the negation only applies to r. If we want to deny the entire statement, then it is written as .

The characters are called binary connectives because they connect two statements. The ~ symbol is unary connective because it applies to only one utterance.

Another binary connective is the exclusive or, which is denoted by . The statement is true when it is true p or q, but not both at the same time. This connective has a truth table

Using the word or, we can mean exclusive or. For example, when we say that r- either true or false, then, naturally, we assume that this is not true at the same time. In logic exclusive or It is used quite rarely, and in the future we, as a rule, will do without it.

Consider the statement

,

where parentheses are used to show which statements are components of each connective.

The truth table makes it possible to unambiguously indicate those situations when the statement is true; in doing so, we must be sure that all cases are taken into account. Since a complex statement contains three main statements r, q And r, then eight cases are possible

Happening	p	q	r
	T	T	T	F	F	T
	T	T	F	F	F	T
	T	F	T	T	T	T
	T	F	F	T	F	T
	F	T	T	F	F	F
	F	T	F	F	F	F
	F	F	T	T	T	T
	F	F	F	T	F	F

When finding the truth values ​​for a column, we use the columns for and r, as well as the truth table for . The truth table for shows that a statement is true only if both statements and r. This occurs only in cases 3 and 7.

Note that when determining truth values ​​for a column only the truth of statements matters p And . The truth table for shows that the only case when a statement formed using the connective or, false, is the case when both sides of the statement are false. This situation occurs only in cases 5, 6 and 8.

Another, equivalent way constructing a truth table consists of writing down the truth values ​​of the expression under the connective. Consider again the expression . First we write the truth values ​​under the variables r, q And r. The ones under the truth value columns indicate that those columns are assigned truth values ​​first. IN general case the number below the column will indicate the step number at which the corresponding truth values ​​are calculated. We then write down the truth values ​​of the statement under the symbol ~. Next, we write down the truth values ​​under the symbol. Finally, we write down the meaning of the statement under the symbol.

1.1.3. Conditional statements

Suppose someone claims that if one event happens, then another will happen. Suppose a father says to his son: " If you pass all your exams this semester with excellent marks, I will buy you a car.". Notice that the statement has the form: if p then q, Where r- statement This semester you will pass all exams with excellent marks., A q- statement I'll buy you a car. We denote a complex statement symbolically by . The question is, under what conditions does the father tell the truth? Suppose statements r And q are true. In this case, the happy student gets excellent grades in all subjects, and his pleasantly surprised father buys him a car. Naturally, no one doubts the fact that the father’s statement was true. However, there are three other cases that need to be considered. Let's say the student really achieved excellent results, but his father didn’t buy him a car.

The kindest thing that can be said about the father in this case is that he lied. Therefore, if r true, but q false, then false. Let us now assume that the student did not receive positive grades, but his father nevertheless bought him a car. In this case, the father appears to be very generous, but he cannot be called a liar. Therefore, if r false and q true, then the statement if p then q(i.e. ) is true. Finally, suppose that the student did not achieve excellent results and his father did not buy him a car.

Since the student did not fulfill his part of the agreement, the father is also free from obligation. Thus, if r And q are false, then considered true. So the only time the father lied was when he made a promise and didn't keep it.

Thus, the truth table for the statement has the form

The symbol is called implication, or conditional connective.

This may appear to be causal, but it is not necessary. To see the absence of cause and effect in implication, let us return to the example in which r there is a statement Jane drives the car, A q- statement Bob has brown hair. Then the statement If Jane drives a car, then Bob has brown hair will be written as

If p, That q or how .

The fact that Jane drives a car has nothing causally to do with the fact that Bob is brown-haired. However, it must be remembered that the truth or falsity of a binary complex statement depends only on the truth of its constituent parts and does not depend on the presence or absence of any connection between them.

Let's consider next example. You need to find the truth table for the expression

.

Using the truth table for , given above, let us first construct truth tables for and , taking into account that the implication is false only in the case when .

Now we use the table for to get for the statement

truth table

A statement of the form is denoted by . The symbol is called equivalent. Equivalence is also sometimes denoted as (not to be confused with the unary negation operator).

Among the possible truth values ​​of a linguistic variable Truth two meanings attract special attention, namely the empty set and the unit interval, which correspond to the smallest and largest elements(with respect to inclusion) of a lattice of fuzzy subsets of the interval. The importance of these particular truth values ​​is due to the fact that they can be interpreted as truth values not defined And unknown respectively. For convenience, we will denote these truth values ​​by the symbols and , understanding that and are determined by the expressions

Values unknown And not defined, interpreted as degrees of membership, are also used in the representation fuzzy sets type 1. In this case, there are three possibilities for expressing the degree of membership of a point in: 1) a number from the interval; 2) ( not defined); 3) (unknown).

Let's look at a simple example. Let

Let us take a fuzzy subset of a set of the form

In this case, the degree of membership of an element in the set is unknown, and the degree of membership is not defined. In a more general case it may be

where it is meant that the degree of membership of an element in a set is partially unknown, and the member is interpreted as follows:

. (6.56)

It is important to clearly understand the difference between and. When we say that the degree of membership of a point to a set is , we mean that the membership function not defined at point . Suppose, for example, that is the set of real numbers, and is a function defined on the set of integers, and , if - even, and , if - odd. Then the degree of membership of a number in the set is , and not 0. On the other hand, if it were defined on the set of real numbers and if and only if - even number, then the degree of membership of the number in the set would be equal to 0.

Since we can calculate the truth values ​​of statements And, or And Not given the linguistic truth values ​​of statements and , it is easy to calculate the values ​​of , , , when . Suppose, for example, that

, (6.57)

. (6.58)

Applying the generalization principle as in (6.25), we obtain

, (6.59)

After simplification, (6.59) reduces to the expression

. (6.61)

In other words, the truth value of a statement And, Where , is a fuzzy subset of the interval, the degree of membership of which the point is equal to (the membership function) on the interval.

Rice. 6.4. Conjunction and disjunction of the truth values ​​of a statement with the truth value unknown ().

Similarly, we find that the truth value of the statement or expressed as

. (6.62)

It should be noted that expressions (6.61) and (6.62) can be easily obtained using the graphical procedure described above (see (6.38) et seq.). An example illustrating this is shown in Fig. 6.4.

Turning to the case, we find

(6.63)

and similarly for .

It is instructive to observe what happens to the above relations when we apply them to a special case of two-valued logic, that is, to the case when the universal set has the form

or in a more familiar form

where means true, A - false. Since there is , we can identify the truth value unknown with meaning true or false, i.e.

The resulting logic has four truth values, , , and , and is a generalization of two-valued logic in the sense of Remark 6.5.

Since the universal set of truth values ​​consists of only two elements, it is advisable to construct truth tables for the operations , and in this four-valued logic directly, i.e., without using general formulas(6.25), (6.29) and (6.31). Thus, applying the generalization principle to the operation, we immediately obtain

whence it necessarily follows that

On this path we come to usual definition connectives ⟹ in two-valued logic in the form of the following truth table:

As the example discussed above shows, the concept of truth value unknown in combination with the principle of generalization, it helps to understand some of the concepts and relationships of ordinary two-valued and three-valued logics. These logics, of course, can be considered as degenerate cases of fuzzy logic, in which the truth value unknown is the entire unit interval, not the set 0 + 1.