What is the partial relationship

1. Relationship

1.1 relationship

The interrelationship between things (between objects) is called a relationship

The n-fold Cartesian product A1 × A2 × ... × An reflects the relationship between n objects, so it is an n-fold relationship.

The sequence of pairs actually reflects the relationship between the two elements, which is a binary relationship.

Note: Relationships and Cartesian Products

Any subset of the Cartesian product can define a binary relationship.

Set X = {1, 2, 3, 4}, Y = {1, 2}, then X × Y = {<1,1>, <1,2>, <2,1>, <2,2> , <1.1>, <3.2>, <4.1>, <4.2>}

R1 = { | x ∈X∧ y ∈Y ∧ x> y} = {<2, 1> , <3, 1> , <3, 2> , <4, 1> , <4, 2> , <4, 3>}

R2 = { | x ∈X∧ y ∈Y ∧ x = y2} = {<1, 1> , <4, 2>}

R2 = { | x ∈X∧ y ∈Y ∧ x = y} = {<1, 1>, <2, 2>} R1, R2, R3 are all binary relationships.

 

1.2 Order

A sequence that consists of two objects in a certain order is called a sequence pair and is called
Note: The two elements in the sequence must have a specific sequence.
That means: if a ≠ b, then 〈a, b〉 ≠ b, a〉 if 〈x, y〉 = 〈a, b〉 then (x = a ∧ y = b)
Multiple sequenced pairs: Triple sequenced pairs = << x, y>, z>
N even rearrange = <<<< x1, x2>, x3> ...>, xn>

 

Important relationship

2.1 definition

Let A × B = {〈x, y〉 | (x ∈ A) ∧ (y ∈ B)}, if the set R ⊆ A × B, then R is a binary relationship from A to B.

That is, the binary relationship R is a set with sequenced pairs as elements. If ∈ R it is recorded as x R y, otherwise it is recorded as

Note: Any subset of A × B is called a binary relationship from A to B, especially when A = B it is called a relationship to A.

 

2.2 Presentation method

2.2.1 Enumeration method (enumeration method)

The binary relationship is defined as shown in the figure:

Can be written as: R = {<1, a>, <2, b>, <3, c>, <4, d>}
From the definition it can be seen that a relationship is a set, and any method of defining a set can be used to define a relationship.

 

2.2.2 Predicate formula representation

As mentioned earlier, sets can be expressed through predicate formulas, so relationships can also be expressed through predicate formulas.
For example: The relation ">" on the set of real numbers R can be expressed as: ">" = {〈x, y〉 | x ∈ R ∧ y ∈ R ∧ x> y}

 

2.2.3 Representation of the relationship matrix

Regulations:
(a) For the successive pairs of binary relationships, the left element represents the row and the right element the column;
(b) If xi R yj, write "1" in the appropriate position, otherwise "0".
For example: Give the set A = {1, 2, 3, 4} and define the relation on AR = {⟨1,2⟩, ⟨1,3⟩, ⟨2,1⟩, ⟨2,2 ⟩, ⟨3,3⟩, ⟨4,3⟩}
Then the relationship matrix of R.

For example: Suppose X = {a, b, c}, Y = {1,2} and R1 is the relation of X → Y,
Assume that R1 is the global relationship from X → Y,

Its relationship matrix is

 

 

2.2.4 Diagram presentation

Regulations:
(a) Draw all the elements in the set X and Y in the form of points on the plane.
(b) If xi R yj Then at xi Andyj Draw a directed arc between them, otherwise don't draw a curve.

For example: known set A = {1, 2, 3, 4} and define the relationship on A.

Then R.

 

 

 

2.3 The definition and range of values ​​of the relationship

Let R be a binary relation, let the set D (R) = {x | ∃ y ( ∈R)}; set R (R) = {y | ∃ x ( ∈R)};

Then D (R) is the domain of R and R (R) is the domain of R.

For example: Set X = {1, 2, 3, 4, 5, 6}, Y = {a, b, c, d, e, f},
Let R = {<1, a> <2, b> <3, c> <4, d>},
Then R is the binary relationship of X to Y.
The domain of R is: D (R) = {1, 2, 3, 4} and the range of R: R (R) = {a, b, c, d}.

In general, you name X as R.Front DomainAnd call YRCompanion domain

 

2.4 Special binary relationships

Definition: Let R be a subset of A × A,

① If R = A × A, then R is called the global relation on A, ie R = A × A = { | x, y ∈A}.

Global relationship R1 = A × A.

Reflective, symmetrical and transferable.

 

② If R = Ø, then R is called an empty relation on A.

Empty relationship R2 = Ø

Antireflective, symmetric, antisymmetric and transitive.

 

③Identity relationship on set A: I. A. = { | x ∈A}.

The identity relationship R3 = {<1, 1> <2, 2> <3, 3>}

Reflexive, symmetric, antisymmetric, transitive

 

 

Other mutual relationships:

  

 

 

2.5 The five types of relationships

Reflective, anti-reflective, symmetrical, anti-symmetrical, passing

1. Reflexivity

Let R be a binary relation in the set X, if for every x ∈X x there is R x, then R is called reflexive.

Note: R on X is reflexive ⇔ ∀ x (x ∈ X → x R x).

For example: Put X = {a, b, c}, R = { }, then R is a reflexive relationship.

The main diagonal elements are all 1;

Each vertex on the diagram has a ring.

 

2. Anti-reflective

Let R be the binary relation in the set X if for every x ∈X there is xx, it is said that R is anti-reflective.

Note: R on X is reflexive ⇔ ∀x (x ∈X → xx).

For example: Set X = {1, 2, 3}, R1 = {<1, 2> <2, 1>}; R2 = {<1, 2>}; R3 = {<2, 1>};

Then R1, R2 and R3 are all anti-reflective.

The main diagonal elements are all 0;

For example: Set X = {1, 2, 3}, R1 = {<1, 2> <2, 1>}; R2 = {<1, 2>}; R3 = {<2, 1>};

Then R1, R2 and R3 are all anti-reflective.

Each vertex on the graph is acyclic.

For example: Set X = {1, 2, 3}, R4 = {<1, 1> <2, 1> <3, 1> <3, 2>};

Then R4 is neither reflexive nor anti-reflexive.

 

 

3. Symmetry

Let R be the binary relation in the set X. For every x and y ∈X, if there is x R y, then y must be R x, then R should have symmetry on X.

Note: R on X is symmetric ⇔ ∀x ∀y (x ∈X ∧y ∈X ∧x R y → y R x).

For example: Set X = {1, 2, 3}, R = {<1, 1> <2, 1> <1, 2> <3, 2> <2, 3>}, then R is a symmetric relationship .

Symmetrical matrix

 

If there is an edge between two vertices, there must be a pair of edges in opposite directions

 

4. Antisymmetric

Let R be a binary relation in the set X. For every x and y ∈X x = y, if there are x R y and y R x, then R on X is said to be antisymmetric.

Note: R on X is antisymmetric ⇔ ∀x ∀y (x ∈X ∧y ∈X ∧x R y ∧y R x → x = y).

Analysis: ① If the predecessor x R y ∧y R x is "T" and the following element x = y is also "T", then R is antisymmetric;

② If the predecessor x R y ∧y R x is "F" (there are three cases) and the sentence is "T", regardless of whether the latter is true or false, then R is antisymmetric.

Example 1: Let X = {a, b, c}, R1 = { }, R2 = { },

R3 = { }, then R1, R2, R3 are all antisymmetric.

 

 

5. Transitivity

Let R be the binary relation in the set X. For every x, y, z ∈ X x must be R z if there is x R y ∧ y R z.

It is said that R is transitive on X

Analysis: ① If the preceding x R y ∧y R z is "T" and the following x R z is also "T", then R is transferrable;

② If the antecedent is "F" (there are three cases), whether the latter is true or false, the sentence is "T", then R is transitive.

Example 1: Put X = {a, b, c}, then the following relationships are all transitive.

R1 = { }

R2 = {}

R3 = { }

R4 = Ø

The following relationships are not transitive:
R5 = { }
R6 = { }

R relationship diagram: traverse each node, the nodes of the output path of the node and input path can also be connected directly, if there is only one output or one input, it is satisfied

Relationship matrix:

Compound matrix method

Idea: Let M be the relational matrix of R. If M * M is a subset of M, then R is transitive.

Assessment method: calculate M * M, M * M is a subset of M means that in the same column position of the corresponding square matrix

If M is 0, M * M must be zero, otherwise R is not transitive.

That means: If a [i] [j] == 0 in M, then c [i] [j] == 0 in M ​​* M must be

1 #include 2usingnamespace std; 3constint maxn = 100; 4int a [maxn] [maxn], c [maxn] [maxn]; 5 6int main () 7 {8int i, j, k, flag = 0; 9int n; 10 cout << "Please enter the number of rows of the square matrix (n * n) that correspond to the binary relationship: \ n"; 11 cin >> n; 12 cout << "Please enter this square matrix: \ n"; 13for (i = 0; i > a [i] [j]; 17} 18for (i = 0; i Compound matrix method

 

When using the matrix representation method to traverse this matrix and come across a position equal to 1, record the position, use the abscissa of the current next number with its ordinate, find position 1 under that abscissa, record that position and use The previous The abscissa of the number position and the ordinate of the number find a new position. If the position is 1, the number is transitive and then loops until all numbers are checked. Then it can be said that this double relationship is transitive, and there is a double relationship that does not correspond to transitivity.

1 #include 2usingnamespace std; 3constint MAXN = 100; 4int A [MAXN] [MAXN]; 5int main () 6 {7 cout << "Please enter the size of the two sentences with a binary relationship: \ n"; 8int x, y; 9 cin >> x >> y; 10 cout << "Please enter the representation of the binary relationship matrix of these two sets: \ n"; 11for (int i = 0; i > A [i] [j]; 14int p = 0; 15for (int i = 0; i Halfway point method

 

 

 

Hint: If X = Φ, then the empty relation Φ has on X.Anti-reflective, Symmetric, antisymmetric and transitive.


 

2.6 Synthesis of Relationships

 

2.6.1relationshipofcomplex

(1)Definition:

Let R be the binary relation of X → Y and S the binary relation of Y → Z, then the binary relation of X → Z can be obtained:
{ | x∈X∧z∈Z∧∃ y (y∈Y∧x R y∧y S z)}

Call this set the composite relationship of R and S, denoted as R◦S or RS.

For example: let X = {1, 2, 3, 4, 5},
R and S are both X → X and
R = {<1.2> <3.4> <2.2>}
S = {<4.2> <2.5> <3.1> <1.3>}
Then
R◦S = {<1.5> <3.2> <2.5>}
S◦R = {<4.2> <3.2> <1.4>}

R◦S ≠ S◦R, the compound relationship "◦" does not satisfy the commutative law.

to discuss:

⑴ R ◦ S is a new binary relationship;

⑵ R ◦ S ⊆ X × Z

⑶ If ∈R and ∈S, there are ∈ R ◦ S.

Note: R1R2 is defined, but R2R1 is not necessarily defined. Even if there is a definition, R1R2 = R2R1 need not necessarily be defined.

 

 

 

 

(2) Compound relationshipofMatrix display

Logical addition: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1
Boolean multiplication of the Boolean matrix: change the "+" in the matrix multiplication to ∨ and "+" to ∧, and the others are left unchanged. Mark as M.R.◦MS.

 

 

2.6.2 Relationship R.power

"Definition" For a set X, R is a binary relationship on X, n is a natural number, so the n-power of R can be defined as follows:
(1) R0 = The identity relationship in the X-set, namely R.0 ={ <x , x> | xX } = I.X

(2) Rn + 1 = Rn ◦R

Assume that X = {1, 2, 3}, the relationship on X R = {<1.2> <2.3> <3.1>}

Search R0, R2, R3, R4

Solution: R.= {<1.1> <2.2> <3.3>} = I.XR.2  = { <1,3> <2,1> <3,2> }

R.3 = R2 ◦ R = {<1.1> <2.2> <3.3>} = I.X R.4 = R3 ◦ R = R

"Theorem" Let R be the binary relation on A, and then m and n are natural numbers

(1) RmR.n = Rm + n

(2) (Rm)n = Rmn .

Let A = {a, b, c, d}, R = {<a, b> a> ), find R.2, R3 , R4, R5

Solution: R.2  = { <a, a>  < a, c >  < b, b > < b, d > }

R.3 = R2 ◦ R = {<a, b> < a, d > a> }

R.4 = R3 ◦ R = {<a, a>   <a, c> } = R2 .

R5 = R4 ◦ R = R2 ◦ R = R3.

Note: If | X | = n, the power value of the binary relationship R in X is limited. In general, there is no need to find the baseline performance of more than X.

 

2.6.3 Reverse relationship

definition: With two sets X and Y R, if the relationship X → Y, the relationship of Y → X is called the inverse relationship of R, which is recorded asOr R.-1, which is

⑴ As long as all the elements in each sequence pair in R are interchanged, the inverse relationship of R can be obtained

(2)The relationship matrix is

⑶ In the R relationship graph, just change any arrows to change the direction you can getDiagram. (It doesn't matter if the loop arrow changes or not)

 

 

 Sentence:Let R, R.1, R2Then is the binary relationship on the set A and B.

(1) (R.-1)-1= R ;

(2) (R.1∪R2)-1= R1-1∪R2-1
(3) (R.1∩R2)-1= R1-1∩R2-1  ;           

(4) (R.1-R2)-1= R1-1 -R2-1 

(5) (A × B)-1= B × A;

(6) Ø -1= Ø ;

(7) R.⊆ R2Then R.1-⊆ R2-1

 

Sentence:Let R be the binary relation in X, then R is symmetric if and only if R =

 

2.6.4 The formation of relationships

Given the set X, R is a binary relationship in X. If there is another relationship, R ¢ satisfies the following conditions:

⑴ R 'is reflexive (symmetric and transitive);

⑵ R ′ ⊇ R ;

⑶ For every reflexive (symmetrical, transitive) relationship R ", R² must be R R 'if R" ⊇ R;

It is said that R 'is the reflexive (symmetric and transitive) shutter of R, which in turn is represented by r (R), s (R) and t (R).

 

Discussion definition:

⑴ If a binary relationship R is given in a set, then r (R), s (R), t (R) are unique and they are the smallest reflexive (symmetric, transitive) relationship that R contains;

⑵ If R is reflexive (symmetric and transitive), then r (R), s (R), t (R) are R themselves;

(3) If R is not reflexive (symmetric, transitive) we can add the least-order pair to make it a reflexive (symmetric, transitive) relationship and get r (R), s (R), t ( R).

 

"Theorem" Given a set X, then R is a binary relation on X.

⑴ R is reflexive if and only if r (R) = R;

⑵ R is symmetric if and only if s (R) = R;

⑶ R is passable if and only if t (R) = R.

 

"Sentence1AcceptR.YesXThe double relationship onI.xYesXThe identity relationship on r (R) = R U Ix  .

"Sentence2AcceptR.YesXThe binary relationship on the s (R) = R U R-1

"Sentence3AcceptR.YesXThe binary relationship on the t (R) = R U R2 U R3 U ··· =

 

 

 

2.6.5 Order relationship

2.6.5.1 Partly ordered sets

Definition:

Let R be a binary relationship on X. If R is reflexive, antisymmetric, and transitive, then R is the partial order (or partial order) relationship in X and is represented by the symbol "≤" and ordered pairs are considered partial called ordered sets.

⑴ "≤" does not simply mean the ≤ -relationship in real numbers, but represents a more general relation (reflexive, antisymmetric and transitive relation);

⑵ When x, y∈ X, "x ≤ y" is pronounced: "x is less than or equal to y";

⑶ R is the partial order relationship in the set X, then R is also the partial order relationship in X, if R is represented by "≤", R is represented by "≥";

⑷ If is a partially ordered set, then must also be a partially ordered set, and the partially ordered set is an ordered pair, the left element is the set X and the right element is the partial orderly relationship.

Definition: In the partially ordered set , x and y are considered comparable if x, y∈X, x ≤ y or y ≤ x, otherwise x and y are not comparable. Comparison of.

Example 1:
(1) The "relationship between the leader and the led" in the group of leading institutions is a partial order relationship;
(2) In the set I (integer) "≤" and "≥" are both partial relationships;
(3) The inclusion relation "⊆" in the power set ρ (A) is a partial order relation;
(4) The divisibility relationship on the set of positive integers Z + is a partial order relationship;

 

2.6.5.2 Special

Quasi orderly set

Definition: R is a binary relationship in the set X. If R is antireflective, antisymmetric, and transitive, then R is denoted as a quasi-order relationship in X (serial order) and is represented by the symbol "<". The ordered pair is called a pseudo-ordered set.

Discussion: (1) Quasi-order relationships must be antisymmetric; (2) Quasi-order relationships can also be defined by partial order relationships:

 

 

Total ordered set

Definition: Let 〈X, ≤〉 be a partially ordered set, if for every x, y ∈ X or x ≤ y or y ≤ x, then

∀x ∀y (x ∈X ∧ y ∈ X → x ≤ y∨y ≤ x), then the partial order relationship "≤" is called the overall order relationship,

And is called a totally ordered set (line-ordered set).

 

In the partially ordered set , x and y are considered comparable if for x, y∈ X, x ≤ y or y ≤ x.

Otherwise x and y should be incomparable.

In a partially ordered set, it generally has to be: some elements are comparable, others are not.

In the overall order relationship, all elements are comparable.

 

Well ordered set

Definition: If the binary relation R on the set X is an overall order relation and every non-empty subset of X has a minimal element,

R is called an ordered relation, and is an ordered set.

Hint: ⑴ Well-ordered relations have one more condition than relations of total order, ie in relations of total order every non-empty subset of X has a minimal element;

⑵ The overall order relationship for every finite set X must be an ordered relationship.

Example: Set A = {1,2,3,4} to define the overall order relationship for A:
“≤” = { <1,1><1,2><1,3><1,4><2,2>
<2,3><2,4><3,3><3,4><4,4> }.
Then "≤" is also an ordered relationship.

 

2.6.5.3 Partly ordered sets and Hass diagrams

2.6.5.3.1 Definition

In the partially ordered set , if anyx, y∈ X andx ≤ y but x≠ y

And there are no other elements that z can dox ≤ z z ≤ y

elementy Home pagex, The lid set is recorded as COV (X) = {<x, y >| x, y ∈ X ;yHome pagex }.

For a partially ordered set , its coverage set is unique.

We can draw a relational graph that covers the set, called a Hass diagram of a partially ordered set .

 

2.6.5.3.2How to draw a Hass diagram of a partially ordered set

⑴ Use "◦" to denote the knot in X (which indicates reflexivity);

⑵ Ifx, y∈ X andx ≤ y Withx y Then putx Recordy Below

⑶ If y covers x, draw a line between x and y with the arrow pointing up. If y does not cover x but has a "≤" relationship, it must pass through the other center between x and y. The knot connects x and y;

⑷ The direction of all sides is upwards, so the arrow can be omitted when drawing.

 

 

 

 

 

 

2.6.5.3.3The smallest (large) element, the smallest (large) element in a partially ordered set

"Definition" gives a partially ordered set and a subset B ⊆ A,

(1) If ∃ b∈ B such that ∀x x ∈B → x ≤ b) is true, then b is the largest element of B, i.e. b is larger than all other elements in B.

(2) If∃ b∈ B such that ∀x x ∈B → b ≤ x) If found, then b is the smallest element of B, i.e. b is smaller than all other elements in B.

"Definition" gives a partially ordered set and a subset B ⊆ A,

(1) If ∃ b∈ B such that ¬ ¬x x ∈B ∧ x ≤ b) is true, then b is called the minimal element of B. That is, there is no element smaller than b in B.

(2) If ∃ b∈ B such that ¬ ¬x x ∈B ∧ b ≤ x) If found, then b is called the maximum element of B. That is, there is no element greater than b in B.

 

Note: According to the definition:

⑴ The largest (small) element and the maximum (small) element of set B, if any, must be in B.

⑵ The largest (small) element is to be compared for all elements in B, while the largest (small) element is for the elements in B that can be compared with it.

(3) The largest (small) element does not necessarily exist, if it does exist it must be unique, while the largest (small) element must exist and does not necessarily have to be unique.

 

 

2.6.5.3.4The upper (lower) limits of the partial order, the upper (lower) limits

definition

For a partially ordered set and a subset B ⊆ A,

(1) If ∃ a∈ A such that ∀x x ∈B → xa) Is then seta If the upper limit of B is the smallest upper limit,

Called B.supremacy, Referred to asLUB

(2) If ∃ a∈ A so that∀x x ∈B → ax) Is then seta Is the lower bound of B, the largest of which is the lower bound,

Called B.Infimum, Referred to asGLB

 

Note: According to the definition:

(1) The upper (lower) limits are compared to all elements in B.

(2) The upper (lower) bound of B does not necessarily exist, and if it does exist it does not necessarily have to be unique.

(3) B's LUB (GLB) does not necessarily exist, if it does exist it must be unique.

(4) If the upper (lower) boundaries of B and LUB (GLB) exist, they can be in B,

It can't be in B, but it has to be in A.

 

"Theorem" sets the subset , B is a subset of A, then:

(1) If b is the largest element of B, then b is also the largest element of B.

(2) If b is B's largest yuan, then b is B's Lub.

(3) If b is an upper bound of B and b ∈ B, then b is the largest element of B.

 

 

2.6.5 Equivalence

2.6.5.1 Definition

Let R be a binary relation on X if R is reflexive, symmetric, and transitive,

It is said that R is an equivalent relationship to X.

If ∈ R, it is recorded as x ~ y.

Analysis: The directed graph of the equivalence relation R satisfies: reflexive, symmetric and transitive.

Example 1: The following relationships are equivalent relationships
(1) The relation "=" on the set of real numbers;
(2) Same surname relationship in {human};
(3) equivalence relations on the set of sentences;
(4) The congruent relationship of triangles and the similarity relationship of triangles are equivalent relationships;
(5) The ratio of "same age" in a class is equivalent;

 

2.6.5.2 Equivalence class

Definition: Let R be the equivalent relation on X for ∀x∈ X, define a subset of X.

[x]R. = { y | y ∈ X∧ x R. y }

Subsetx]R.By x The generated equivalence class around R is abbreviated with [x],

And saidx Is the equivalence class [x] Represents the element.

Note: ⑴ Equivalent class [x]R.Is a lot and [x]R. ⊆ X.

  ⑵ [x]R.The elements in are: all andx A set consisting of elements with the equivalence relation R and [x]R.≠ Ø.

 

 

 

2.6.5.3 Division

Definition: Let X be a non-empty set, A.1, A2 , ..., Am Is a non-empty subset of it and is fulfilled

⑴ Ai ∩ Aj = Ø (i ≠ j) ;

⑵ A1 U A2 U ... U Am = X ;

It is called the collective family π = {A.1, A2 , ..., Am } Is a division of set X.

And the subsets A1, A2, ..., Am are called this divided block.

 

 

Theorem: Let X be a non-empty set and R the equivalence relation in X,

The set of equivalence classes of R {[x]R. | x∈ X} is a division of X,

And call this set the quotient set of X under R, denoted as X / R = {[x]R. | x∈ X}.

 

 

 

 

Pass 1: https: //blog.csdn.net/qq_41705423/article/details/79503938

 

 

 

Reprinted at: https://www.cnblogs.com/ZanderZhao/p/11019629.html