离散数学复习题
一.  有两个小题
1．分别说明联结词、∧、∨、→和的名称，再分别说明它们在自然语言中表示什么含义。
解：(1) undefined叫做否定 。 (2) ∧ 叫做合取。(3) ∨叫做析取。
    (4) undefined叫做蕴涵。  (5) undefined 叫做等价。
“undefined”表示“…不成立”，“不…”。
“∧”表示“并且”、“不但…而且...”、“既…又 ...”等。
“∨”表示“或者”， 是可兼取的或。
“undefined”表示 如果… ，则 …；只要… ，就 …； 只有… ,  才…；  仅当 … 。
“undefined”表示“当且仅当”、“充分且必要”。
2．分别列出undefinedP、PundefinedQ、PundefinedQ、PundefinedQ、PundefinedQ的真值表(填下表)。
P
Q
undefinedP
PundefinedQ
PundefinedQ
PundefinedQ
PundefinedQ
解：
P
Q
undefinedP
PundefinedQ
PundefinedQ
PundefinedQ
PundefinedQ
F
F
T
F
F
T
T
F
T
T
F
T
T
F
T
F
F
F
T
F
F
T
T
F
T
T
T
T
二. 将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。)
1.如果小张去，则小王与小李都不去，否则小王与小李不都去。
解：设P：小张去。Q：小王去。R：小李去。
    此命题的表达式为：
    (P→(undefinedQ∧undefinedR))∧(undefinedP→undefined(Q∧R))
2.我们不能既划船又跑步。
解：令 P:我们划船。Q:我们跑步。 
      此命题的表达式为undefined(P∧Q)
3.有些运动员是大学生。(L(x): x是运动员，S(x): x是大学生。)
解：undefinedx(L(x)∧S(x))
4.每个运动员都钦佩一些教练。
( L(x):x是运动员，A(x,y):x钦佩y，J(x):x是教练。)
解：undefinedx(L(x)→undefinedy(J(y)∧A(x,y)))
三.  有三个问题
1.先说明什么叫永真式(也叫重言式)。
解：A(P1,P2,…,Pn) 是含有命题变元P1,P2,…, Pn的命题公式，如不论对P1,P2,…, Pn作任何指派，都使得二叉树公式A(P1,P2,…,Pn) 为真，则称之为重言式，也称之为永真式。
2.指出下面的命题公式中哪些是永真式(只写题号即可)。
(1). (P∨Q)→P              (2). P→(P∨Q)
  (3). (P∧(P→Q))→Q          (4). (P∧Q)→Q
解:(2),(3),(4)为永真式。
3.然后对上面的永真式任选其中一个给予证明(方法不限)。
证明 (4). (P∧Q)→Q
  设前件(P∧Q)为真，则得Q为真。所以(P∧Q)→Q是永真式。
四. 写出命题公式 (Q→undefinedP)→Q 的主合取范式。（要求有解题过程）
解：
方法1：等价变换
(QundefinedundefinedP)undefinedQ
  undefinedundefined(undefinedQ∨undefinedP)∨Q       ( 去    )
    undefined (Q∧P)∨Q          ( 摩根定律 )
    undefined  Q                  ( 吸收律  )
  undefined (P∧undefinedP)∨Q        （互补、同一律 ）
    undefined (P∨Q)∧(undefinedP∨Q)     ( 分配律  )
方法2：真值表法
先列(QundefinedundefinedP)undefinedQ的真值表如下：
P
Q
undefinedP
QundefinedundefinedP
(QundefinedundefinedP)undefinedQ
F
F
T
T
F
F
T
T
T
T
T
F
F
T
F
T
T
F
F
T
从真值表看出，该命题公式的主合取范式含有大项M0和M2，即(P∨Q)和
(undefinedP∨Q)。于是此命题公式的主合取范式为：
(QundefinedundefinedP)undefinedQ undefined (P∨Q)∧(undefinedP∨Q)
五. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。
  undefinedxP(x), undefinedx(Q(x)undefinedundefinedR(x)), undefinedx(undefinedP(x)undefinedR(x)) undefined undefinedxundefinedQ(x)
解：⑴ undefinedxP(x)                    P
    ⑵ P(a)                      ES ⑴
    ⑶ undefinedx(undefinedP(x)undefined R(x))          P
    ⑷ undefinedP(a)undefinedR(a)              US ⑶
    ⑸  R(a)                      T⑵⑷  I
    ⑹ undefined x(Q(x)undefinedundefinedR(x))          P
    ⑺  Q(a)undefinedundefinedR(a)              US ⑹
    ⑻ undefinedQ(a)                      T ⑸ ⑺ I
    ⑼ undefinedxundefinedQ((x)                  EG ⑻
六. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 
  undefinedxC(x), undefinedx(A(x)undefinedB(x)), undefinedx(B(x)undefinedundefinedC(x)) undefined undefinedxA(x)
解：    ⑴ undefinedx(A(x)undefinedB(x))        P
        ⑵ A(a)undefinedB(a)              ES ⑴
        ⑶ undefinedxC(x)                P     
        ⑷ C(a)                  US ⑶ 
        ⑸ undefinedx(B(x)→undefinedC(x))      P
        ⑹ B(a)→undefinedC(a)            US ⑸
        ⑺ undefinedB(a)                  T  ⑷ ⑹ I
        ⑻ A(a)                    T  ⑵ ⑺ I
        ⑼ undefinedxA(x))                EG ⑻
七.  令集合A={1,{1}},B={1}，P(A)表示A的幂集。
1.判断下面命题的真值。并说明原因，否则不给分。
      (1)  B∈A,            (2)  P(B)undefinedP(A)
      (3)  {Φ}undefinedP(A)      (4)  {{1}}∈P(B)
解：P(A)＝{Φ,{1},{{1}}, {1,{1}}
  P(B)＝{Φ,{1}}
⑴：真值为T；因为A={1,{1}},  B={1}, B是A中一个元素，所以B∈A。
⑵：真值为T；因为P(B)＝{Φ,{1}}，P(B)中两个元素Φ和{1}都属于P(A),所以P(B)undefinedP(A)。
⑶：真值为T；因为集合{Φ}中只有一个元素Φ，而P(A)中也有元素Φ，所以{Φ}undefinedP(A)。
⑷：真值为F。因为{{1}}不是P(B)中元素，故真值为F。
2.分别计算:  （注意：要求要有计算过程，不能直接写出计算结果！）
  (1)  A×P(B)
  (2)  A⊕B
  (3)  P(A)－P(B)
解： A={1,{1}}, B={1}，
⑴ A×P(B)＝{1,{1}}× {Φ,{1}}
    ＝{<1,Φ>,<1,{1}>,<{1},Φ>,<{1},{1}>}
⑵ A⊕B＝(AundefinedB)－(AundefinedB)
  =({1,{1}}undefined{1})－ ({1,{1}} undefined {1})＝{1,{1}}－{1}＝{{1}}。
⑶ P(A)－P(B)＝{Φ,{1},{{1}}, {1,{1}}－{Φ,{1}}
  ＝{{{1}}, {1,{1}}}
八. 令全集E={1,2},A={1}, P(A)表示集合A的幂集。
（注意：要求要有计算过程，不能直接写出计算结果！）
    1. 指出 P(E)和P(A)各有多少个元素。即求|P(E)|和|P(A)|.
解：因为P(E)＝{Φ,{1},{2}, {1,2}} 所以P(E)有4个元素。即|P(E)|＝4。
P(A)＝{Φ,{1}}  所以P(A)有2个元素。即|P(A)|＝2。
    2. 计算～AundefinedE
解：因为～A＝E－A={1,2}-{1}={2}
～AundefinedE＝{2} undefined{1,2}＝({2}undefined{1,2})－({2}undefined{1,2})＝{1,2}－{2}＝{1}
九. 令集合A={1},B＝{1,2}, P(A)表示集合A的幂集。
（注意：要求要有计算过程，不能直接写出计算结果！）
  1．计算A与B的对称差AundefinedB。
解：AundefinedB＝(AundefinedB)－(AundefinedB)
  ＝({1}undefined{1,2})－({1}undefined{1,2})＝{1,2}－{1}＝{2}
2．计算 P(B)－P(A)
解： P(B)－P(A)＝P({1,2})－P({1})
  ＝{Φ,{1},{2},{1,2}}－{Φ,{1}}＝{{2},{1,2}}
十. 给定集合A={1,2,3},定义A上的关系如下：
    R={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。