1.(4 points) Finding toe-in conjunctive normal form is logically equivalent to the following formula:

2.(8 points) For propositional formulas P, Q and R, prove the following equivalence relations:

3.(8 points)

(1) defines the binary relation r 1 = {< i, j>| j = i or j = I/2}, R2 = {

(2) Write the graph and matrix of R2, and point out whether it is reflexive, reflexive, symmetric, antisymmetric and transitive.

4.(8 points) Settings

It is proved that if any one of A and B ∈ h satisfies a*b- 1∈H, then

5.(6 points) Prove that graph G is connected and the degree of each node is even, then for any node V, W (G-V).

6.(6 points) Let G be a connected graph, and any node v∈V(G) has W (G-V)?