Discrete math problem!

1. Whether the following algebraic systems are semigroups, singularities and groups.

Addition on 1. real number set r 。

2. Multiplication on real number set r 。

3. Division operation on integer set z 。

4. Union operation on power set P(A) of nonempty set A. 。

Solution: Semigroups are defined as: algebraic systems are closed and operations * can be combined.

1. It is a semigroup;

2. It is a semigroup;

3. It is not a semigroup, because division on the Z set cannot be combined;

4. It is a semigroup.

2. Are there any elements or zero elements in the following algebraic systems? If so, try to find out.

1.< r,+>, r is a real number set.

2.< r.- >, R is a set of real numbers.

3.< p (a), ∩ >, a is a nonempty set, and P(A) is a power set of a. 。

Solution: 1 If r is a real number set, then the middle addition+unary, that is, 0; There is no zero yuan.

2. If r is a real number set, there are no unary elements and zero elements.

3. If P(A) is a power set of non-empty set A, then the intermediate operation has no elements and is an empty set; There is no zero yuan.

3. Find an optimal binary tree with weights of 1, 3, 6, 9.

Solution: 19

| |

9 10

| |

4 6

| |

1 3

4. It is proved that a simple connected planar graph with less than 30 edges has a node with a degree less than or equal to 4.

Solution: reduction to absurdity: suppose that the degree of all nodes is greater than or equal to 5, because it is a simple connected plane graph and the degree of each node is greater than or equal to 5, so each face can be composed of at least 3 edges, and there is a theorem that knows M.

From the handshake theorem, we can know that 2m >: =5n means n; =30, which is different from m.

V. Symbolizing the following propositions

1. "I will go to the city when I have time."

Solution: Suppose P: I have time. Q: I'm in town, so I can write it as → Q.

2. "I only go to town when I have time."

Solution: Suppose P: I have time. Q: I'm going to town, so I can write it down as

"I watch TV or read books at home in the evening."

Suppose P: Watch TV at home in the evening. Q: Reading at home at night.

Therefore, it can be written as: (P∧┐Q)∨(Q∧┐P) 2. Find the truth table of propositional formula q→(r∧p).

6. Find the truth table of the propositional formula q→(r∧p).

Solution: Its truth table:

Q R P R∧P Q→(R∧P)