Quantifiers of generality and existence. Quantifiers Meaning of predicate logic formula

In connection with the introduction of quantifiers, the following must be taken into account:

1. A predicate logic formula cannot contain the same objective variable, which would be bound in one part of the formula and free in another.

2. The same variable cannot be in the region of quantifiers that are dual to each other.

Violation of these conditions is called variable collision.

How is the truth value of a statement with a quantifier established?

To prove a statement with a general quantifier you need to make sure that when substituting each of the values X into a predicate P(x) the latter turns into a true statement. If the set X is finite, then this can be done by enumerating all cases; if the set X is infinite, then it is necessary to carry out reasoning in a general form.

Statement (x) P(x) false if such a value can be specified AX, at which P(x) turns into a false statement R(a). That's why, to refute a statement with a general quantifier It is enough to give an example.

Statement (x) P(x) true if such a value can be specified AX, at which P(x) turns into a true statement R(a). Therefore, in order verify the truth of a statement with a quantifier existence , it is enough to give an example and thus prove it.

In order to verify the falsity of a statement with quantifier existence (x) P(x), it is necessary to verify the falsity of each P(x), P(x), …, P(x). If the set X Of course, this can be done by brute force. If there are many X infinitely, then it is necessary to carry out reasoning in a general form.

Examples.

1. Find the truth value “among the numbers” 1, 2, 3, 4 there is a prime number."

Solution: The statement contains an existential quantifier and can therefore be represented as a disjunction of statements: “ 1 - prime number" or " 2 - prime number" or " 3 - prime number" or " 4 - Prime number". To prove the truth of a disjunction, the truth of at least one statement is sufficient, for example, “ 3 is a prime number that is true. Therefore, the original statement is also true.

2. Let us prove that any square is a rectangle.

Solution: The statement contains a general quantifier. Therefore, it can be presented as a conjunction: “square - rectangle” and “square - rectangle” and “square - rectangle”, etc. Since all these statements are true, then the conjunction of these statements is true, therefore, the original sentence is true.

3. “Any triangle is isosceles.” This is a false statement. To verify this, it is enough to draw a triangle that is not isosceles.a

To construct the negation of a statement with quantifiers necessary:

1) replace the quantifier of generality with the quantifier of existence, and the quantifier of existence with the quantifier of generality;

2) replace the predicate with its negation.

Example. Let us formulate a negation for the following statements:

a) all elements of the set Z even; b) some verbs answer the question “what to do?”.

Solution: a) Let us replace the quantifier of generality with the quantifier of existence, and its statement with its negation: some elements of the set Z odd.

b) Let us replace the quantifier of existence with a quantifier of generality, and its expression with negation: all verbs do not answer the question “what to do?”

Predicate (lat. praedicatum- stated, mentioned, said) - any mathematical statement in which there is at least one variable. The predicate is the main object of study in first-order logic.

A predicate is an expression with logical variables that make sense for any valid values ​​of these variables.

Expressions: x > 5, x > y – predicates.

Predicate ( n-local, or n-ary) is a function with a set of values ​​(0,1) (or “false” and “true”), defined on the set. Thus, each set of elements of the set M characterized as either "true" or "false".

A predicate can be associated with a mathematical relation: if n-ka belongs to the relation, then the predicate will return 1 on it. In particular, a unary predicate defines the relation of membership to a certain set.

A predicate is one of the elements of logic of the first and higher orders. Starting from second-order logic, quantifiers can be placed on predicates in formulas.

The predicate is called identically true and write:

if on any set of arguments it takes the value 1.

The predicate is called identically false and write:

if on any set of arguments it takes the value 0.

The predicate is called feasible, if it takes the value 1 on at least one set of arguments.

Since predicates take only two meanings, all operations of Boolean algebra are applicable to them, for example: negation, implication, conjunction, disjunction, etc.

Quantifier is a general name for logical operations that limit the domain of truth of a predicate. Most often mentioned:

Universal quantifier(designation: reads: “for everyone...”, “for everyone...” or “every...”, “any...”, “for any...”).

Existence quantifier(designation: , reads: “exists...” or “will be found...”).

Examples

Let's denote P(x) predicate " x divisible by 5." Using the general quantifier, we can formally write the following statements (false, of course):

any natural number is divisible by 5;

every natural number is a multiple of 5;

all natural numbers are multiples of 5;

in the following way:

.

The following (already true) statements use the existential quantifier:

there are natural numbers that are multiples of 5;

there is a natural number that is a multiple of 5;

at least one natural number is divisible by 5.

Their formal notation:

.Introduction to the concept

Let the predicate P(x) be given on the set X of prime numbers: “The prime number x is odd.” Let us substitute the word “any” in front of this predicate. We get the false statement “any prime number x is odd” (this statement is false, since 2 is a prime even number).

Substituting the word “exists” in front of the given predicate P(x), we obtain the true statement “There is a prime number x that is odd” (for example, x = 3).

Thus, you can turn a predicate into a statement by placing in front of the predicate the words “everything”, “exists”, etc., called quantifiers in logic.

Quantifiers in mathematical logic

The statement means that the range of the variable x included in the domain of truth of the predicate P(x).

(“For all values ​​of (x), the statement is true.”)

The statement means that the domain of truth of the predicate P(x) is non-empty.

(“There is an (x) for which the statement is true”).

Question 31 Graph and its elements. Basic concepts. Incidence, multiplicity, loop, contiguity. Types of graphs. The route in the graph and its length. Classification of routes. Adjacency matrices of directed and undirected graphs.

In mathematical graph theory and computer science, a graph is a collection of a non-empty set of vertices and a set of pairs of vertices.

Objects are represented as vertices, or nodes, of a graph, and connections are represented as arcs, or edges. For different application areas, types of graphs may differ in directionality, restrictions on the number of connections, and additional data about vertices or edges.

A path (or chain) in a graph is a finite sequence of vertices in which each vertex (except the last) is connected to the next one in the sequence of vertices by an edge.

A directed path in a digraph is a finite sequence of vertices v i, for which all pairs ( v i,v i+ 1) are (oriented) edges.

A cycle is a path in which the first and last vertices coincide. In this case, the length of a path (or cycle) is the number of its components ribs. Note that if the vertices u And v are the ends of some edge, then according to this definition, the sequence ( u,v,u) is a cycle. To avoid such “degenerate” cases, the following concepts are introduced.

A path (or cycle) is called simple if its edges are not repeated; elementary if it is simple and its vertices are not repeated. It's easy to see that:

Every path connecting two vertices contains an elementary path connecting the same two vertices.

Any simple non-elementary path contains elementary cycle.

Any simple a cycle passing through some vertex (or edge) contains elementary(sub-)cycle passing through the same vertex (or edge).

A loop is an elementary cycle.

Graph or undirected graph G is an ordered pair G: = (V,E

V

E this is a set of pairs (in the case of an undirected graph, unordered) of vertices, called edges.

V(and therefore E, otherwise it would be a multiset) are usually considered finite sets. Many good results obtained for finite graphs are not true (or differ in some way) for infinite graphs. This is because a number of considerations become false in the case of infinite sets.

The vertices and edges of a graph are also called graph elements, the number of vertices in the graph | V| - order, number of edges | E| - the size of the graph.

Peaks u And v are called the terminal vertices (or simply ends) of an edge e = {u,v). An edge, in turn, connects these vertices. Two end vertices of the same edge are called adjacent.

Two edges are said to be adjacent if they have a common end vertex.

Two edges are called multiple if the sets of their end vertices coincide.

An edge is called a loop if its ends coincide, that is e = {v,v}.

degree deg V peaks V call the number of edges incident to it (in this case, the loops are counted twice).

A vertex is said to be isolated if it is not the end of any edge; hanging (or leaf) if it is the end of exactly one edge.

Directed graph (abbreviated digraph) G is an ordered pair G: = (V,A), for which the following conditions are met:

V is a non-empty set of vertices or nodes,

A it is a set of (ordered) pairs of distinct vertices, called arcs or directed edges.

Arc is an ordered pair of vertices (v, w), where is the vertex v called the beginning, and w- the end of the arc. We can say that the arc leads from the top v to the top w.

Mixed graph

Mixed graph G is a graph in which some edges can be directed and some can be undirected. Written as an ordered triple G: = (V,E,A), Where V, E And A defined the same as above.

Directed and undirected graphs are special cases of mixed graphs.

Isomorphic graphs(?)

Graph G is called isomorphic to the graph H, if there is a bijection f from the set of graph vertices G to the set of vertices of the graph H, which has the following property: if in the graph G there is an edge from the vertex A to the top B, then in the graph H f(A) to the top f(B) and vice versa - if in the graph H there is an edge from the vertex A to the top B, then in the graph G there must be an edge from the vertex f − 1 (A) to the top f − 1 (B). In the case of a directed graph, this bijection must also preserve the orientation of the edge. In the case of a weighted graph, the bijection must also preserve the weight of the edge.

Graph adjacency matrix G with a finite number of vertices n(numbered from 1 to n) is a square matrix A size n, in which the element value a ij equal to the number of edges from i th vertex of the graph in j-th peak.

Sometimes, especially in the case of an undirected graph, a loop (an edge from i th vertex into itself) is counted as two edges, that is, the value of the diagonal element a ii in this case equal to twice the number of loops around i th peak.

The adjacency matrix of a simple graph (containing no loops or multiple edges) is a binary matrix and contains zeros on the main diagonal.

Question32 Function. Methods of assignment. Classification of functions. Basic elementary functions and their graphs. Composition of functions. Elementary functions.

Function is a mathematical concept that reflects the relationship between elements of sets. We can say that a function is a “law” according to which each element of one set (called domain of definition ) is put into correspondence with some element of another set (called range of values ).

The mathematical concept of a function expresses the intuitive idea of ​​how one quantity completely determines the value of another quantity. So the value of the variable x uniquely defines the meaning of an expression x 2, and the value of the month uniquely determines the value of the month following it, also any person can be compared with another person - his father. Similarly, some pre-conceived algorithm produces certain output data based on varying input data.

Methods for specifying a function

Analytical method

A function is a mathematical object that is a binary relation that satisfies certain conditions. A function can be specified directly as a set of ordered pairs, for example: there is a function . However, this method is completely unsuitable for functions on infinite sets (which are the usual real functions: power, linear, exponential, logarithmic, etc.).

To specify a function, use the expression: . Wherein, x is a variable that runs through the domain of definition of the function, and y- range of values. This entry indicates the presence of a functional relationship between the elements of sets. X And y can run through any sets of objects of any nature. These can be numbers, vectors, matrices, apples, colors of the rainbow. Let's explain with an example:

Let there be a set apple, plane, pear, chair and many man, locomotive, square. Let's define the function f as follows: (apple, person), (plane, locomotive), (pear, square), (chair, person). If we introduce a variable x running through the set and a variable y running through the set, the specified function can be specified analytically as: .

Numerical functions can be specified similarly. For example: where x runs through the set of real numbers and defines some function f. It is important to understand that the expression itself is not a function. A function as an object is a set of (ordered pairs). And this expression as an object is the equality of two variables. It defines a function, but is not one.

However, in many branches of mathematics, it is possible to denote by f(x) both the function itself and the analytical expression that defines it. This syntactic convention is extremely convenient and justified.

Graphic method

Numerical functions can also be specified using a graph. Let be a real function of n variables.

Let's consider some (n+1)-dimensional linear space over the field of real numbers (since the function is real). Let us choose any basis () in this space. Each point of the function is associated with a vector: . Thus, we will have a set of linear space vectors corresponding to the points of a given function according to the specified rule. The points of the corresponding affine space will form a certain surface.

If we take the Euclidean space of free geometric vectors (directed segments) as a linear space, and the number of arguments of the function f does not exceed 2, the specified set of points can be visually depicted in the form of a drawing (graph). If, in addition, the original basis is taken to be orthonormal, we obtain the “school” definition of the graph of a function.

For functions of 3 arguments or more, this representation is not applicable due to a person’s lack of geometric intuition of multidimensional spaces.

However, for such functions one can come up with a visual semi-geometric representation (for example, each value of the fourth coordinate of a point can be associated with a certain color on the graph)

Proportional quantities. If the variables y And x are directly proportional

y = k x ,

Where k- constant value ( proportionality factor).

Schedule direct proportionality– a straight line passing through the origin of coordinates and forming a line with the axis X angle whose tangent is equal to k: tan = k(Fig. 8). Therefore, the proportionality coefficient is also called slope. Figure 8 shows three graphs for k = 1/3, k= 1 and k = 3 .

Linear function. If the variables y And x are related by the 1st degree equation:

A x + B y = C ,

where at least one of the numbers A or B is not equal to zero, then the graph of this functional dependence is straight line. If C= 0, then it passes through the origin, otherwise it does not. Graphs of linear functions for various combinations A,B,C are shown in Fig.9.

Inverse proportionality. If the variables y And x are inversely proportional, then the functional relationship between them is expressed by the equation:

y = k / x,

Where k- constant value.

Inverse proportional graph – hyperbola(Fig. 10). This curve has two branches. Hyperbolas are obtained when a circular cone intersects with a plane (for conic sections, see the “Cone” section in the “Stereometry” chapter). As shown in Fig. 10, the product of the coordinates of the hyperbola points is a constant value, in our example equal to 1. In the general case, this value is equal to k, which follows from the hyperbola equation: xy = k.

Main characteristics and properties of a hyperbola:

x 0, range: y 0 ;

The function is monotonic (decreasing) at x< 0and at x> 0, but not

monotonic overall due to the break point x = 0);

Unbounded function, discontinuous at a point x= 0, odd, non-periodic;

- The function has no zeros.

Quadratic function. This is the function: y = ax 2 + bx + c, Where a, b, c- permanent, a b=c= 0 and y = ax 2. Graph of this function square parabola - OY, which is called the axis of the parabola.Dot O the vertex of the parabola.

Quadratic function. This is the function: y = ax 2 + bx + c, Where a, b, c- permanent, a 0. In the simplest case we have: b=c= 0 and y = ax 2. Graph of this function square parabola - a curve passing through the origin of coordinates (Fig. 11). Every parabola has an axis of symmetry OY, which is called the axis of the parabola.Dot O the intersection of a parabola with its axis is called the vertex of the parabola.

Graph of a function y = ax 2 + bx + c- also a square parabola of the same type as y = ax 2, but its vertex lies not at the origin, but at a point with coordinates:

The shape and location of a square parabola in the coordinate system depends entirely on two parameters: the coefficient a at x 2 and discriminant D:D=b 2 – 4ac. These properties follow from the analysis of the roots of a quadratic equation (see the corresponding section in the chapter “Algebra”). All possible different cases for a square parabola are shown in Fig. 12.

Main characteristics and properties of a square parabola:

Function scope:  < x+ (i.e. x R), and the area

values: … (Please answer this question yourself!);

The function as a whole is not monotonic, but to the right or left of the vertex

behaves as monotonous;

The function is unbounded, continuous everywhere, even when b = c = 0,

and non-periodic;

- at D< 0 не имеет нулей.

Exponential function. Function y = a x, Where a- a positive constant number is called exponential function.Argument x accepts any valid values; functions are considered as values only positive numbers, since otherwise we have a multi-valued function. Yes, the function y = 81x has at x= 1/4 four different values: y = 3, y = 3, y = 3 i And y = 3 i(Check, please!). But we consider as the value of the function only y= 3. Graphs of the exponential function for a= 2 and a= 1/2 are presented in Fig. 17. They pass through the point (0, 1). At a= 1 we have a graph of a straight line parallel to the axis X, i.e. the function turns into a constant value equal to 1. When a> 1 the exponential function increases, and at 0< a < 1 – убывает. Основные характеристики и свойства показательной функции:

Function scope:  < x+ (i.e. x R);

range: y> 0 ;

The function is monotonic: it increases with a> 1 and decreases at 0< a < 1;

- The function has no zeros.

Logarithmic function. Function y= log a x, Where a– a constant positive number not equal to 1 is called logarithmic. This function is the inverse of the exponential function; its graph (Fig. 18) can be obtained by rotating the graph of the exponential function around the bisector of the 1st coordinate angle.

Main characteristics and properties of the logarithmic function:

Function scope: x> 0, and range of values:  < y+

(i.e. y R);

This is a monotonic function: it increases as a> 1 and decreases at 0< a < 1;

The function is unlimited, continuous everywhere, non-periodic;

The function has one zero: x = 1.

Trigonometric functions. When constructing trigonometric functions we use radian measure of angles. Then the function y= sin x is represented by a graph (Fig. 19). This curve is called sinusoid.

Graph of a function y=cos x presented in Fig. 20; this is also a sine wave resulting from moving the graph y= sin x along the axis X to the left by 2

From these graphs, the characteristics and properties of these functions are obvious:

Domain:  < x+ range of values: 1 y +1;

These functions are periodic: their period is 2;

Limited functions (| y| , continuous everywhere, not monotonic, but

having so-called intervals of monotony, inside which they are

behave like monotonic functions (see graphs in Fig. 19 and Fig. 20);

Functions have an infinite number of zeros (for more details, see section

"Trigonometric Equations").

Function graphs y= tan x And y=cot x are shown in Fig. 21 and Fig. 22, respectively.

From the graphs it is clear that these functions are: periodic (their period ,

unlimited, generally not monotonic, but have intervals of monotonicity

(which ones?), discontinuous (what discontinuity points do these functions have?). Region

definitions and range of values ​​of these functions:

Functions y= Arcin x(Fig.23) and y= Arccos x(Fig. 24) multi-valued, unlimited; their domain of definition and range of values, respectively: 1 x+1 and  < y+ . Since these functions are multi-valued, do not

considered in elementary mathematics, their main values ​​are considered as inverse trigonometric functions: y= arcsin x And y= arccos x; their graphs are highlighted in Fig. 23 and Fig. 24 with thick lines.

Functions y= arcsin x And y= arccos x have the following characteristics and properties:

Both functions have the same domain of definition: 1 x +1 ;

their range of values:  /2 y/2 for y= arcsin x and 0 y For y= arccos x;

(y= arcsin x– increasing function; y= arccos x – decreasing);

Each function has one zero ( x= 0 for function y= arcsin x And

x= 1 for function y= arccos x).

Functions y= Arctan x(Fig.25) and y= Arccot x(Fig. 26) - multi-valued, unlimited functions; their domain of definition:  x+ . Their main meanings y= arctan x And y= arccot x are considered as inverse trigonometric functions; their graphs are highlighted in Fig. 25 and Fig. 26 with bold branches.

Functions y= arctan x And y= arccot x have the following characteristics and properties:

Both functions have the same domain of definition:  x + ;

their range of values:  /2<y < /2 для y= arctan x and 0< y < для y= arccos x;

Functions are limited, non-periodic, continuous and monotonic

(y= arctan x– increasing function; y= arccot x – decreasing);

Function only y= arctan x has a single zero ( x= 0);

function y= arccot x has no zeros.

Composition of functions

If two maps are given and , where , then the “end-to-end map” from to , given by the formula , makes sense, which is called the composition of functions and and is denoted by .

Fig. 1.30. End-to-end display from to