Short answer questions (25%):
Solution: The relation matrix of R is expressed as:
Reflexive closure: r (r) = {
Symmetric closure s (r) =
Transitive closure t (r) =
Solution:
⑴(P∨？ P)→？ The truth table of q is as follows:
PQP∨？ P(P∨？ P)→？ Q
0 0 1 1
0 1 1 0
1 0 1 1
1 1 1 0
Is a satisfiable formula.
⑵(P→Q)(？ Q→？ The truth table of p) is as follows:
PQ(P→Q)(？ Q→？ P)(P→Q)(？ Q→？ p)
0 0 1 1 1
0 1 1 1 1
1 0 0 0 1
1 1 1 1 1
This is an eternal formula.
⑶G=(P∨Q)∧(？ P∨Q)∧(P∨？ Q)∧(？ P∨？ Q) The truth table is as follows:
PQ(P∨Q)(？ P∨Q)(P∨？ Q) (? P∨？ q)G
0 0 0 1 1 1 0
0 1 1 1 0 1 0
1 0 1 0 1 1 0
1 1 1 1 1 0 0
This is a formula that is always wrong.
⑷G=(P∧Q)∨(？ P∧Q)∨(P∧？ Q)∨(？ P∧？ Q) The truth table is as follows:
PQ(P∧Q)(？ P∧Q)(P∧？ Q) (? P∧？ q)G
0 0 0 0 0 1 1
0 1 0 1 0 0 1
1 0 0 0 1 0 1
1 1 1 0 0 0 1
This is an eternal formula.
Solutions;
It's not a lattice. There are two elements that have no lower bounds.
Is a lattice, and any two elements have a minimum upper bound and a maximum lower bound.
This is the same reason as (b).
It's not a lattice. There are two elements that have no lower bounds.
True or false (25%):
1. solution:
The (1) proposition is false. R∩S is reflexive, but ROS is not necessarily reflexive. For example, r = {
(2) The proposition is false. R∩S is transitive, but ROS is not necessarily transitive. For example: set A={ 1, 2, 3, 4, 5}, r = {
(3) The proposition is true.
(4) The proposition is false. For example, let A={a, b, c} and r = {
2. solution: because for any x, y∈R, |x-y|=|y-x|, so x*y=y*x, so * is interchangeable. For 1, 2,3 ∈ r, (1* 2) * 3 = ||1-2 |-3 | = 2, while1* (2 * 3) = |/kloc-. Because for every x∈R, it is impossible to make x*y=y hold for any y∈R, so there is no unitary about * in R.
3. Which of the following pictures have Euler paths?
Euler path
Euler path
There is no Euler path.
There is no Euler path.
Proof problem (35%):
Prove:
∵fOg=IA is bijective, ∴f is injective, g is surjective,
∵gOf=IB is bijective, ∴g is injective and F is surjective.
So g and f are bijective, so g and f are reversible.
gOfOf- 1 =(gOf Of- 1 = IBOf- 1 = f- 1
Gofof-1= go (fof-1) = goia = g, so g=f- 1.
Foog- 1 = (fog) og-1= iaog-1= g-1
Foog-1= f o (gog-1) = foib = f, so f = g- 1.
Prove:
P∨Q P
p→QT，①，E
q→SP
p→ST，②，③，I
s→PT，④，E
p→RP
s→RT，⑤，⑥，I
SVRT，⑦，E
Prove:
Q(x)P
(x)(？ P(x))P
(x)(？ q(x))T，①，E
(x)(？ P(x))∧(x)(？ q(x))T，②，③，I
(x)(？ P(x)∧？ q(x))T，④，E
P(y)∧？ Ask (y) us, ⑤
p(y)∨Q(y))T，⑥，E
(x)(P(x)∨Q(x))P
p(y)∞Q(y)US，⑧
(P(y)∨Q(y))∧？ (P(y)∨Q(y))T，⑦，⑨，I
Prove:
known
For any a, b∈G, there is (a * b) * (a * b) = e.
a*(b*(a*b))=a*a
b*(a*b)=a
Then b * (b * (a * b)) = b * a a.
e*(a*b)=b*a
a*b=b*a
So as to satisfy the exchange law.
So < g; *> This is an Abelian group.
Comprehensive questions (15%):
Solution:
⑴ P→(P∧(Q→P)) P→(P∧(？ Q∨P))
? P∨(P∧(P∨？ Q)
? P∨P 1
∴ p→ (p ∧ (the main conjunctive normal form of Q→ p)) is empty.
The main disjunctive paradigm is (? P∧Q)∨(P∧？ Q)∨(P∧Q)∨(？ P∧？ Q)
⑵ (Q→P)∧(？ P∧Q)(？ Q∨P)∧(？ P∧Q)
(? Q∨P)∧？ (? Q∨P) 0
∴(Q→P)∧(？ The principal disjunctive normal form of P∧Q) is empty.
Lord conjunctive normal form is (? P∨Q)∧(P∨？ Q)∧(P∨Q)∧(？ P∨？ Q)
Solution: The picture below shows what may happen in the game. In the picture, those marked with A represent the first victory, and those marked with B represent the second victory. This is a complete binary tree.