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.