Equivalence relation and quotient set. Equivalence relations. Factor sets Equivalence relations. Factor sets
(that is, which has the following properties: each element of the set is equivalent to itself; if x equivalent y, That y equivalent x; If x equivalent y, A y equivalent z, That x equivalent z ).
Then the set of all equivalence classes is called factor set and is designated . Partitioning a set into classes of equivalent elements is called its factorization.
Display from X into the set of equivalence classes is called factor mapping.
Examples
It is reasonable to use set factorization to obtain normed spaces from semi-normed ones, spaces with an inner product from spaces with an almost inner product, etc. To do this, we introduce, respectively, the norm of a class, equal to the norm of an arbitrary element, and the inner product of classes as an inner product of arbitrary elements of classes. In turn, the equivalence relation is introduced as follows (for example, to form a normalized quotient space): a subset of the original seminormed space is introduced, consisting of elements with zero seminorm (by the way, it is linear, that is, it is a subspace) and it is considered that two elements are equivalent if their difference belongs to this very subspace.
If, to factorize a linear space, a certain subspace is introduced and it is assumed that if the difference of two elements of the original space belongs to this subspace, then these elements are equivalent, then the factor set is a linear space and is called a factor space.
Examples
see also
Wikimedia Foundation. 2010.
See what “Factorset” is in other dictionaries:
The logical principle underlying definitions through abstraction (See Definition through abstraction): any Relation of the type of equality, defined on some initial set of elements, splits (divides, classifies) the original... ...
A form of thinking that reflects the essential properties, connections and relationships of objects and phenomena in their contradiction and development; a thought or system of thoughts that generalizes, distinguishes objects of a certain class according to certain general and in the aggregate... ... Great Soviet Encyclopedia
Galois group cohomology. If M is an Abelian group and a Galois group of an extension acting on M, then Galois cohomology groups are cohomology groups defined by a complex consisting of all maps, and d is a coboundary operator (see Cohomology of groups).... ... Mathematical Encyclopedia
The construction, to paradise, first appeared in set theory, and then became widely used in algebra, topology and other areas of mathematics. An important special case of an I. p. is an I. p. of a directed family of mathematical structures of the same type. Let be … Mathematical Encyclopedia
Points although relative to the group G acting on the set X (on the left), the set Set is a subgroup of G and is called. stabilizer, or stationary subgroup of a point with respect to G. The mapping induces a bijection between G/Gx and the orbit G(x). ABOUT.… … Mathematical Encyclopedia
This article has too short an introduction. Please add an introductory section that briefly introduces the topic of the article and summarizes its contents... Wikipedia
This article is about the algebraic system. For the branch of mathematical logic that studies statements and operations on them, see Algebra of Logic. Boolean algebra is a non-empty set A with two binary operations (analogous to a conjunction), ... ... Wikipedia
Let an equivalence relation be given on a set. Then the set of all equivalence classes is called the factor set and is denoted. Partitioning a set into classes of equivalent elements is called its factorization. Mapping from to... ... Wikipedia
In geometry, a directed segment is understood as an ordered pair of points, the first of which, point A, is called its beginning, and the second, B, its end. Contents 1 Definition ... Wikipedia
In various branches of mathematics, the kernel of a mapping is a certain set kerf, which in a sense characterizes the difference between f and an injective mapping. The specific definition may vary, but for the injective mapping f... ... Wikipedia
Set theory. Basic Concepts
Set theory is the fundamental definition of modern mathematics. It was created by Georg Cantor in the 1860s. He wrote: “Multiple is many, conceived as a single whole.” The concept of set is one of the basic, undefined concepts of mathematics. It cannot be reduced to other, simpler concepts. Therefore, it cannot be defined, but can only be explained. Thus, a set is a unification into one whole of objects that are clearly distinguishable by our intuition or our thought; a collection of certain objects defined by a common characteristic.
For example,
1. Many residents of Voronezh
2. Set of plane points
3. Set of natural numbers ℕetc.
Sets are usually denoted in capital Latin letters( A, B, C etc.). The objects that make up a given set are called its elements. Elements of a set are denoted by small Latin letters( a, b, c etc.). If X– set, then record x∈X means that X is an element of the set X or what X belongs to the set X, and the entry x∉X that element X does not belong to the set X. For example, let ℕ be the set of natural numbers. Then 5 ℕ , A 0,5∉ℕ .
If the set Y consists of elements of the set X, then they say that Y is a subset of the set X and denote Y⊂Х(or Y⊆Х). For example, a set of integers ℤ is a subset of rational numbers ℚ .
If for two sets X And Y two inclusions occur simultaneously X Y And Y X, i.e. X is a subset of the set Y And Y is a subset of the set X, then the sets X And Y consist of the same elements. Such sets X And Y are called equal and write: X=Y.
The term empty set is often used - Ø - a set that does not contain a single element. It is a subset of any set.
The following methods can be used to describe sets.
Methods for specifying sets
1. Enumeration of objects. Used only for finite sets.
For example, X=(x1, x2, x3… x n). Y entry ={1, 4, 7, 5} means that the set consists of four numbers 1, 4, 7, 5 .
2. Indication of the characteristic property of the elements of the set.
To do this, a certain property is set R, which allows you to determine whether an element belongs to a set. This method is more universal.
X=(x: P(x))
(a bunch of X consists of such elements X, for which the property holds P(x)).
An empty set can be specified by specifying its properties: Ø=(x: x≠x)
You can construct new sets using already defined ones using operations on sets.
Set Operations
1. A union (sum) is a set consisting of all those elements, each of which belongs to at least one of the sets A or IN.
A∪B=(x: x A or x B).
2. An intersection (product) is a set consisting of all elements, each of which simultaneously belongs to the set A, and many IN.
A∩B=(x: x A and x B).
3. Set difference A And IN is a set consisting of all those elements that belong to the set A and do not belong to the multitude IN.
A\B=(x: x A and x B)
4. If A– a subset of a set IN. That's a lot B\A called the complement of a set A to many IN and denote A'.
5. The symmetric difference of two sets is the set A∆B=(A\B) (B\A)
N- the set of all natural numbers;
Z- the set of all integers;
Q- the set of all rational numbers;
R- the set of all real numbers;
C- the set of all complex numbers;
Z 0- the set of all non-negative integers.
Properties of operations on sets:
1. A B=B A (commutativity of the union)
2. A B=B A (commutativity of intersection)
3. A(B C)=(A IN) C (union associativity)
4. A (IN C)=(A IN) C (intersection associativity)
5. A (IN C)=(A IN) (A C) (1st law of distributivity)
6. A (IN C)=(A IN) (A C) (2nd law of distributivity)
7. A Ø=A
8. A U=U
9. A Ø= Ø
10. A U=A
11. (A B)'=A' B' (de Morgan's law)
12. (A B)'=A' B' (de Morgan's law)
13. A (A B)=A (absorption law)
14. A (A B)=A (absorption law)
Let's prove property No. 11. (A B)'=A' IN'
By definition of equal sets, we need to prove two inclusions 1) (A B)’ ⊂A’ IN';
2) A' B’⊂(A IN)'.
To prove the first inclusion, consider an arbitrary element x∈(A B)’=X\(A∪B). It means that x∈X, x∉ A∪B. It follows that x∉A And x∉B, That's why x∈X\A And x∈X\B, which means x∈A’∩B’. Thus, (A B)’⊂A’ IN'
Back if x∈A’ IN', That X simultaneously belongs to sets A', B', which means x∉A And x∉B. It follows that x∉ A IN, That's why x∈(A IN)'. Hence, A' B’⊂(A IN)'.
So, (A B)'=A' IN'
A set consisting of two elements, in which the order of the elements is defined, is called an ordered pair. To write it, use parentheses. (x 1, x 2)– a two-element set in which x 1 is considered the first element, and x 2 is the second. Couples (x 1, x 2) And (x 2, x 1), Where x 1 ≠ x 2, are considered different.
A set consisting of n elements, in which the order of the elements is defined, is called an ordered set of n elements.
A Cartesian product is an arbitrary set X 1, X 2,…,X n ordered sets of n elements, where x 1 X 1 , x 2 X 2 ,…, x n Xn
X 1 Xn
If the sets X 1, X 2,…,X n match (X 1 = X 2 =…=X n), then their product is denoted Xn.
For example, ℝ 2 – a set of ordered pairs of real numbers.
Equivalence relations. Factor sets
Based on a given set, new sets can be constructed by considering the set of some subsets. In this case, we usually talk not about a set of subsets, but about a family or class of subsets.
In a number of questions, the class of such subsets of a given set is considered A, which do not intersect and whose union coincides with A. If this set A can be represented as a union of its pairwise disjoint subsets, then it is customary to say that A divided into classes. The division into classes is carried out on the basis of some characteristic.
Let X is not an empty set, then any subset R from the work X X is called a binary relation on the set X. If a couple (x,y) included in R, they say that the element x is in the relation R With at.
For example, relationships x=y, x≥y are binary relations on the set ℝ.
Binary relation R on a set X is called an equivalence relation if:
1. (x,x) R; X X (reflexivity property)
2. (x,y) R => (y, x) R (symmetry property)
3. (x,y) R, (y,z) R, then (x,z) R (transitivity property)
If a couple (x,y) entered into equivalence relations, then x and y are called equivalent (x~y).
1.Let ℤ – a set of integers, m≥1– an integer. Let us define the equivalence relation R on ℤ so that n~k, If n-k divided by m. Let's check whether the properties are satisfied on this relation.
1. Reflexivity.
For anyone n∈ℤ ℤ such that (p,p)∈R
р-р=0. Because 0∈ ℤ , That (p,p)∈ℤ.
2. Symmetry.
From (n,k) ∈R it follows that there is such a thing р∈ℤ, What n-k=mp;
k-n =m(-p), -p∈ ℤ, hence (k,n) ∈R.
3. Transitivity.
From what (n,k) ∈R, (k,q) ∈R it follows that there are such p 1 And р 2 ∈ ℤ, What n-k=mp 1 And k-q=mp 2. Adding these expressions, we get that n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. That's why (n,q) ∈ ℤ.
2. Consider the set X all directed segments of space or plane . =(A, B). Let us introduce the equivalence relation R on X.
Let G=(p 0 =e, p 1, …, p r) be a certain group of permutations defined on the set X = (1, 2, …, n) with the unit e=p 0 identical permutation. Let us define the relation x~y by putting x~y equivalent to the fact that there exists p belonging to G(p(x)=y). The introduced relation is an equivalence relation, that is, it satisfies three axioms:
1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;
Let A be an arbitrary set.
Definition: A binary relation δ=A*A is an equivalence relation (denoted by a ~ b) if it satisfies the following axioms:
∀ a, b, c ∈ A
1) a ~ a – reflexivity;
2) a ~ b ⇒ b ~ a – commutativity;
3) a ~ b & b ~ c → a ~ c - transitivity
denoted by a ~ b, σ(a,b), (a,b) ∈ σ, a σ b
Definition: A partition of a set A is a family of pairwise disjoint subsets of A, which in the union (in total) give all A.
А= ∪А i, А i ∩А j = ∅, ∀i ≠ j.
Subsets A i are called cosets of the partition.
Theorem: every equivalence relation defined on A corresponds to some partition of the set A. Every partition of the set A corresponds to some equivalence relation on the set A.
Briefly: there is a one-to-one correspondence between the classes of all equivalence relations defined on set A and the class of all partitions of set A.
Proof: let σ be an equivalence relation on the set A. Let a ∈ A.
Let's construct a set: K a =(x ∈ A,: x~a) – all elements equivalent to a. The set (notation) is called the equivalence class with respect to the equivalence σ. Note that if b belongs to K a , then b~a. Let us show that a~b⇔K a =K b . Indeed, let a~b. Take an arbitrary element c belonging to K a . Then c~a, a~b, c~b, c belongs to K b and therefore K b belongs to K a . The fact that K a belongs to K b is shown in a similar way. Therefore, K b =K a.
Let now K b =K a . Then a belongs to K a = K b , a belongs to K b , a~b. That's what needed to be shown.
If 2 classes K a and K b have a common element c, then K a = K b. In fact, if c belongs to K a and K b , then b~c, c~a, b~a => K a = K b .
Therefore, different equivalence classes either do not intersect or intersect and then coincide. Every element c of A belongs to only one equivalence class K c. Therefore, a system of disjoint equivalence classes at intersection gives the entire set A. And therefore this system is a partition of the set A into equivalence classes.
Converse: Let A = sum over or A i is a partition of A. Let us introduce the relation a~b on A, as a~b ⇔ a,b belong to the same partition class. This relation satisfies the following axioms:
1) a ~ a (are in the same class);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, i.e. the introduced relation ~ is an equivalence relation.
Comment:
1) a partition of a set A into single-element subsets and a partition of A consisting only of the set A are called trivial (improper) partitions.
2) Partitioning A into single-element subsets corresponds to an equivalence relation which is equality.
3) Partitions A, consisting of one class A, correspond to an equivalence relation containing A x A.
4) a σ b → [a] σ = [b] σ - any equivalence relation defined on a certain set divides this set into pairwise disjoint classes called equivalence classes.
Definition: The set of equivalence classes of a set A is called the quotient set A/σ of the set A by equivalence σ.
Definition: The mapping p:A→A/σ, for which p(A)=[a] σ, is called the canonical (natural) mapping.
Any equivalence relation defined on a certain set partitions this set into pairwise disjoint classes called equivalence classes.
If the attitude R has the following properties: reflexive symmetrical transitive, i.e. is an equivalence relation (~ or ≡ or E) on the set M , then the set of equivalence classes is called the factor set of the set M regarding equivalence R and is designated M/R
There is a subset of elements of the set M equivalent x , called equivalence class.
From the definition of a factor set it follows that it is a subset of a Boolean: .
The function is called identification and is defined as follows:
Theorem. Factor algebra F n /~ is isomorphic to the algebra of Boolean functions B n
Proof.
The required isomorphism ξ : F n / ~ → B n is determined by the following rule: equivalence class ~(φ) function is matched f φ , having a truth table for an arbitrary formula from the set ~(φ) . Since different equivalence classes correspond to different truth tables, the mapping ξ injective, and since for any Boolean function f from In p there is a formula representing the function f, then the mapping ξ surjective. Store operations, 0, 1 when displayed ξ is checked directly. CTD.
By the theorem on the functional completeness of every function that is not a constant 0 , corresponds to some SDNF ψ , belonging to the class ~(φ) = ξ -1 (f) formulas representing a function f . The problem of being in the classroom arises ~(φ) disjunctive normal form, which has the simplest structure.
End of work -
This topic belongs to the section:
Course of lectures on the discipline discrete mathematics
Moscow State University of Civil Engineering.. Institute of Management Economics and Information Systems in Construction.. IEEE..
If you need additional material on this topic, or you did not find what you were looking for, we recommend using the search in our database of works:
What will we do with the received material:
If this material was useful to you, you can save it to your page on social networks:
| Tweet |
All topics in this section:
Subject of discrete mathematics
The subject of discrete (finite, finite) mathematics is a branch of mathematics that studies the properties of discrete structures, while classical (continuous) mathematics studies the properties of objects
Isomorphism
The science that studies algebraic operations is called algebra. This concept will become more specific and deepen as you study the course. Algebra is only interested in the question of HOW to act
Exercises
1. Prove that an isomorphic mapping is always isotone, and the converse is not true. 2. Write your group in the language of sets. 3. Write down in the language of sets the objects that
Set and elements of set
Currently, existing set theories differ in the paradigmatics (system of views) of the conceptual basis and logical means. So, as an example, we can cite two opposite
Finite and infinite sets
That which the set consists of, i.e. The objects that make up a set are called its elements. The elements of a set are distinct and distinct from each other. As can be seen from the given example
Power of set
The cardinality for a finite set is equal to the number of its elements. For example, the cardinality of the universe B(A) of a set A of cardinality n
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
A finite set A has cardinality k if it is equal to the segment 1.. k;:
Subset, proper subset
After the concept of a set is introduced, the task arises of constructing new sets from existing ones, that is, defining operations on sets. Set of M",
Symbolic language of meaningful set theories
In the process of studying the course, we will distinguish between the object language of set theory and the metalanguage, by means of which the object language is studied. By the language of set theory we understand relational
Proof
The set B is infinite, which means
Adding and removing elements
If A is a set, and x is an element, and then the element
Bounded sets. Set boundaries
Let a numerical function f(x) be given on some set X. The upper bound (boundary) of the function f(x) is such a number
Exact upper (lower) limit
The set of all upper boundaries E is denoted by Es, and all lower boundaries by Ei. In case
The exact upper (lower) bound of the set
If an element z belongs to the intersection of the set E and the set of all its upper boundaries Es (respectively lower r
Basic properties of upper and lower bounds
Let X be a partially ordered set. 1. If, then
Set from an attributive point of view
The aggregate point of view, unlike the attributive point of view, is logically untenable in the sense that it leads to paradoxes of the type of Russell and Cantor (see below). Within the framework of attributive t
Structure
A partially ordered set X is called a structure if it contains any two-element set
Covering and partitioning sets
A partition of a set A is a family Ai
Binary relationships
A sequence of length n, the terms of which are a1, .... an, will be denoted by (a1, .... a
Properties of binary relations
A binary relation R on the set Ho has the following properties: (a) reflexive if xRx
Ternary relations
Cartesian product XY
N-ary relations
By analogy with the Cartesian product of two sets X,Y, we can construct the Cartesian product X
Displays
Mappings are some connections between elements of sets. The simplest examples of relations are the relations of membership x
Correspondence
A subset S of a Cartesian product is called an n-ary correspondence of elements of sets Mi. Formally
Function
All branches of discrete mathematics are based on the concept of function. Let X -
Representing a function in terms of relations
A binary relation f is called a function if from and
Injection, surjection, bijection
When using the term “mapping”, a distinction is made between the mapping XbY and the mapping X onto Y
Inverse function
For arbitrary ones, we define
Partially ordered sets
A set S is called partially ordered (PUM) if it is given a reflexive, transitive and antisymmetric binary partial order relation
Set representation minimization
Using these laws, we consider the problem of minimizing the representation of the set M using the operations
Rearrangements
Given a set A. Let A be a finite set consisting of n elements A = (a1, a2, …, a
Permutations with repetitions
Let set A have identical (repeating) elements. Permutation with repetitions of composition (n1, n2, … ,nk
Placements
Tuples of length k (1≤k≤n), consisting of different elements of the n-element set A (the tuples differ in
Placements with repetitions
Let set A have identical (repeating) elements. Placements with repetitions of n elements of k names
Orderly placement
Let us place n objects into m boxes so that each box contains a sequence, and not, as before, a set of objects placed in it. Two
Combinations
From an m-element set A we construct an ordered set of length n, the elements of which are arrangements with the same themes
Combinations with repetitions
The resulting formulas are valid only when there are no identical elements in the set A. Let there be elements of n types and from them a tuple of
Function generating method
This method is used to enumerate combinatorial numbers and establish combinatorial identities. The starting point is the sequence (ai) combinator
Algebraic system
An algebraic system A is a collection ‹M,O,R›, the first component of which M is a non-empty set, the second component O is a set
Closure and subalgebras
A subset is said to be closed under the operation φ if
Algebras with one binary operation
Let one binary operation be given on the set M. Let us consider the algebras it generates, but first we will consider some properties of binary operations. Binary o
Groupoid
Algebra of the form<М, f2>called a groupoid. If f2 is an operation like multiplication (
Integers modulo m
Given a ring of integers
Congruences
Congruence on algebra A =
Elements of graph theory
Graphs are mathematical objects. Graph theory is used in areas such as physics, chemistry, communication theory, computer design, electrical engineering, mechanical engineering, architecture, research on
Graph, vertex, edge
By an undirected graph (or, in short, a graph) we mean such an arbitrary pair G =
Correspondence
Another, more often used description of a directed graph G consists of specifying a set of vertices X and a correspondence Г, to
Undirected graph
If the edges have no orientation, then the graph is called undirected (undirected duplicate or unoriented
Incidence, mixed graph
If the edge e has the form (u, v) or<и, v>, then we will say that the edge e is incident ver
Reverse Match
Since it represents a set of such vertices
Graph isomorphism
Two graphs G1 =
Path oriented route
A path (or directed route) of a directed graph is a sequence of arcs in which
Adjacent arcs, adjacent vertices, vertex degree
Arcs a = (xi, xj), xi ≠ xj, having common end vertices, n
Connectivity
Two vertices in a graph are called connected if there is a simple path connecting them. A graph is called connected if all its vertices are connected. Theorem.
Weighted arc graph
A graph G = (N, A) is called weighted if some function l: A → R is defined on the set of arcs A such that
Strong connectivity matrix
Strong connectivity matrix: put 1 along the diagonal; fill in the line X1 - if the vertex is reachable from X1 and X1 d
Trees
Trees are important not only because they find applications in various fields of knowledge, but also because they have a special position in graph theory itself. The latter is caused by the extreme simplicity of the structure of the tree
Any non-trivial tree has at least two hanging vertices
Proof Consider the tree G(V, E). A tree is a connected graph, therefore
Theorem
The center of a free tree consists of one vertex or two adjacent vertices: Z(G) = 0&k(G) = 1 → C(G) = K1
Directed, ordered and binary trees
Directed (ordered) trees are an abstraction of hierarchical relationships that are very often encountered both in practical life and in mathematics and programming. Tree (orientation)
Proof
1. Each arc enters some node. From clause 2 of definition 9.2.1 we have: v
Ordered trees
The sets T1,..., Tk in the equivalent definition of orderev are subtrees. If the relative order of the subtrees T1,...,
Binary trees
A binary (or binary) tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees - left and right. Binary tree not in java
Free Tree Representation
To represent trees, you can use the same techniques as for representing general graphs - adjacency and incidence matrices, adjacency lists, and others. But using the special properties of
End for
Rationale The Prüfer code is indeed a free tree representation. To verify this, let us show that if T" is a tree
Representation of binary trees
Any free tree can be oriented by designating one of its nodes as the root. Any order can be ordered arbitrarily. For descendants of one node (brothers) of an ordered order, it is defined relative
Basic logic functions
Let us denote by E2 = (0, 1) a set consisting of two numbers. The numbers 0 and 1 are basic in a discrete mat
Boolean function
A Boolean function of n arguments x1, x2, … ,xn is a function f from the nth power of the set
Two-element Boolean algebra
Let's consider the set Во = (0,1) and define operations on it, according to the tables of sources
Boolean Function Tables
A Boolean function of n variables can be specified by a table consisting of two columns and 2n rows. The first column lists all sets from B
F5 – repeat in y
f6 – sum modulo 2 f7
Order of operations
If there are no parentheses in a complex expression, then the operations must be performed in the following order: conjunction, disjunction, implication, equivalence, negation. Conventions regarding the arrangement of shannon's first theorem
To solve the problem of finding the SDNF and SCNF equivalent to the original formula φ, we first consider the expansions of the Boolean function f(x1, x2
Shannon's second theorem
By virtue of the principle of duality, Theorem 6.4.3 (Shannon’s second theorem) holds for Boolean algebras. Any Boolean function f(x1, x2,...
Functional completeness
Theorem (about functional completeness). For any Boolean function f there is a formula φ representing the function f
Algorithm for finding sdnf
To find the SDNF, this formula must first be reduced to the DNF, and then transform its conjuncts into constituents of the unit using the following actions: a) if the conjunct includes some
Quine's method
Consider Quine's method for finding the MDNF representing a given Boolean function. Let us define the following three operations: - complete gluing operation -
Canonical representation of logical functions
Canonical forms of logical (formulas) functions are expressions that have the standard form of a Boolean formula such that it uniquely represents a logical function. In algebra
Boolean function systems
Let Boolean functions f(g1, g2, …, gm) and g1(x1, x2, …, xn), g2(x1
Zhegalkin basis
Let's try it out. Let's look at the system. It is complete, since any function from the standard basis is expressed in terms
Post's theorem
Post's theorem establishes necessary and sufficient conditions for the completeness of a system of Boolean functions. (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu
Proof
Necessity. From the opposite. Let it be
Zhegalkin algebra Propositional logic Definition of a predicate Application of predicates in algebra Boolean predicate algebra F↔G=(F→G)(G→F), F→G=not FG Predicate calculus Following and equivalence Accepted notations Meta designations Let R be a binary relation on the set X. The relation R is called reflective
, if (x, x) О R for all x О X; symmetrical
– if from (x, y) О R it follows (y, x) О R; the transitive number 23 corresponds to option 24 if (x, y) О R and (y, z) О R imply (x, z) О R. Example 1 We will say that x О X has in common
with element y О X, if the set Equivalence relation on X is a reflexive, transitive and symmetric relation. It is easy to see that R Í X ´ X will be an equivalence relation if and only if the inclusions hold: Id X Í R (reflexivity), R -1 Í R (symmetry), R ° R Í R (transitivity). In reality, these three conditions are equivalent to the following: Id X Í R, R -1 = R, R ° R = R. By splitting of a set X is the set A of pairwise disjoint subsets a Í X such that UA = X. With each partition A we can associate an equivalence relation ~ on X, putting x ~ y if x and y are elements of some a Î A. Each equivalence relation ~ on X corresponds to a partition A, the elements of which are subsets, each of which consists of those in the relation ~. These subsets are called equivalence classes
. This partition A is called the factor set of the set X with respect to ~ and is denoted: X/~. Let us define the relation ~ on the set w of natural numbers, putting x ~ y if the remainders from dividing x and y by 3 are equal. Then w/~ consists of three equivalence classes corresponding to the remainders 0, 1 and 2. Order relation A binary relation R on a set X is called antisymmetric
, if from x R y and y R x it follows: x = y. A binary relation R on a set X is called order relation
, if it is reflexive, antisymmetric and transitive. It is easy to see that this is equivalent to the following conditions: 1) Id X Í R (reflexivity), 2) R Ç R -1 (antisymmetry), 3) R ° R Í R (transitivity). An ordered pair (X, R) consisting of a set X and an order relation R on X is called partially ordered set
. Example 1 Let X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)). Since R satisfies conditions 1 – 3, then (X, R) is a partially ordered set. For elements x = 2, y = 3, neither x R y nor y R x is true. Such elements are called incomparable
. Usually the order relation is denoted by £. In the example given, 0 £ 1 and 2 £ 2, but it is not true that 2 £ 3. Example 2 Let< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество. Elements x, y О X of a partially ordered set (X, £) are called comparable
, if x £ y or y £ x. A partially ordered set (X, £) is called linearly ordered
or chain
, if any two of its elements are comparable. The set from example 2 will be linearly ordered, but the set from example 1 will not. A subset A Í X of a partially ordered set (X, £) is called bounded above
, if there is an element x О X such that a £ x for all a О A. The element x О X is called the largest
in X if y £ x for all y О X. An element x О X is called maximal if there are no elements y О X different from x for which x £ y. In example 1, elements 2 and 3 will be the maximum, but not the largest. Similarly defined lower limit
subsets, smallest and minimum elements. In example 1, element 0 will be both the smallest and the minimum. In Example 2, 0 also has these properties, but (w, £) has neither the largest nor the maximum element.
The sum modulo 2, the conjunction and the constants 0 and 1 form a functionally complete system, i.e. form an algebra - Zhegalkin algebra. A=
Mathematical logic studies the basic concepts of syntax (form) and semantics (content) of natural language. Let's consider three major areas of research in mathematical logic - logic
Let X1, X2, ..., Xn be arbitrary variables. We will call these variables subject variables. Let the variable sets you
Let's consider predicates in which only one variable is free, which we denote by x, and discuss the use of predicates in algebra. A typical example
Since logical operations can be applied to predicates, the basic laws of Boolean algebra are valid for them. Theorem. (Properties of logical operations for predicates). Mn
2. Use the law not not F=F, de Morgan's laws: not (F
Predicate calculus is also called first-order theory. In the predicate calculus, as well as in the propositional calculus, the first most important place is the problem of solvability.
The propositional form Q2 follows from the propositional form Q1 if the implication Q1→Q2 becomes true
Symbols of "order no more". When comparing the growth rate of two functions f(n) and g(n) (with non-negative values), the following are very convenient
Symbols Contents Example OR
x Ç y is not empty. The relation to have in common will be reflexive and symmetrical, but not transitive.
