陕西省网站建设_网站建设公司_Redis_seo优化

三、计算题（第3题及之后）

3. 假设集合 A = {1, 2, 3, 4} 上的关系 R = {<1, 2>, < 3, 4>, < 3, 2>, < 2, 2>} 和 S = {<4, 2>, <2, 3>, < 3, 1>, <1, 3>} ，利用关系矩阵求 R ∘ S。

解答：

1. 写出关系矩阵：

   • 关系 R 的矩阵 M_R（行为前驱，列为后继）：

        1  2  3  4
     1 [0, 1, 0, 0]
     2 [0, 1, 0, 0]
     3 [0, 1, 0, 1]
     4 [0, 0, 0, 0]
     

   • 关系 S 的矩阵 M_S：

        1  2  3  4
     1 [0, 0, 1, 0]
     2 [0, 0, 1, 0]
     3 [1, 0, 0, 0]
     4 [0, 1, 0, 0]
     

2. 计算复合关系 R ∘ S 的矩阵 M_{R∘S}：

   • 复合关系 R ∘ S 的定义是：如果存在元素 y，使得 <x, y> ∈ R 且 <y, z> ∈ S，则 <x, z> ∈ R ∘ S。
   • 在矩阵运算上，M_{R∘S} = M_R · M_S（使用布尔运算，即乘法中“与”代替乘，“或”代替加）。
   • 计算过程（以第1行第1列为例）：(M_R的第1行) 与 (M_S的第1列) 进行布尔乘加。
     • (0∧0) ∨ (1∧0) ∨ (0∧1) ∨ (0∧0) = 0 ∨ 0 ∨ 0 ∨ 0 = 0
   • 最终得到 M_{R∘S}：

        1  2  3  4
     1 [0, 1, 0, 0]  // <1,2>∈R 且 <2,3>∈S → <1,3>∈R∘S? 检查：<1,2>∈R，但<2,3>∈S，所以<1,3>∈R∘S。矩阵中第1行第3列应为1。让我们重新计算。
     

   • 重新精确计算（手工逻辑推导）：
     • 对于有序对 <x, z>，检查是否存在 y ∈ A，使得 <x, y> ∈ R 且 <y, z> ∈ S。
     • x=1: R中有<1,2>。S中，以2为第一元素的有<2,3>。所以存在y=2，使得<1,2>∈R且<2,3>∈S，因此<1,3> ∈ R∘S。
     • x=2: R中有<2,2>。S中，以2为第一元素的有<2,3>。所以<2,3> ∈ R∘S。
     • x=3: R中有<3,4>和<3,2>。
       • 对于<3,4>：S中，以4为第一元素的有<4,2>。所以<3,2> ∈ R∘S。
       • 对于<3,2>：S中，以2为第一元素的有<2,3>。所以<3,3> ∈ R∘S。
     • x=4: R中无任何以4为第一元素的有序对。所以R∘S中无任何以4为第一元素的有序对。
   • 因此，R ∘ S = {<1, 3>, <2, 3>, ❤️, 2>, ❤️, 3>}。
   • 对应的关系矩阵为：

        1  2  3  4
     1 [0, 0, 1, 0]
     2 [0, 0, 1, 0]
     3 [0, 1, 1, 0]
     4 [0, 0, 0, 0]
     

答案： R ∘ S = {<1, 3>, <2, 3>, ❤️, 2>, ❤️, 3>}。其关系矩阵如上所示。

4. 选择适当的例子将下列谓词公式描述成汉语：
   （1） ∀x ( p(x) → q(x) )
   例子： 设论域为“所有人”，p(x)：x是学生，q(x)：x需要学习。
   汉语描述： 对于所有人来说，如果某人是学生，那么这个人就需要学习。（即：所有学生都需要学习。）

   （2） ∃x ( p(x) ∧ q(x) )
   例子： 设论域为“所有动物”，p(x)：x是猫，q(x)：x是白色的。
   汉语描述： 存在一个动物，它既是猫又是白色的。（即：存在白色的猫。）

5. 求命题公式 ( p ∨ (q ∧ r) ) → ( p ∨ q ∨ r ) 的主合取范式与主析取范式。
   解答：

   1. 构造真值表：

      p	q	r	q∧r	p∨(q∧r)	p∨q∨r	(p∨(q∧r))→(p∨q∨r)
      0	0	0	0	0	0	1
      0	0	1	0	0	1	1
      0	1	0	0	0	1	1
      0	1	1	1	1	1	1
      1	0	0	0	1	1	1
      1	0	1	0	1	1	1
      1	1	0	0	1	1	1
      1	1	1	1	1	1	1

   2. 分析结果： 由真值表可知，原公式在所有赋值下均为真（永真式）。

   3. 主析取范式： 永真式的主析取范式包含所有可能的小项（2^n个，n=3）。即：
      (¬p∧¬q∧¬r) ∨ (¬p∧¬q∧r) ∨ (¬p∧q∧¬r) ∨ (¬p∧q∧r) ∨ (p∧¬q∧¬r) ∨ (p∧¬q∧r) ∨ (p∧q∧¬r) ∨ (p∧q∧r)

   4. 主合取范式： 永真式的主合取范式为空（即没有大项合取，或表示为1）。

   答案：

   • 主合取范式： 1 （或为空，表示没有成假赋值的大项合取式）。
   • 主析取范式： (¬p∧¬q∧¬r) ∨ (¬p∧¬q∧r) ∨ (¬p∧q∧¬r) ∨ (¬p∧q∧r) ∨ (p∧¬q∧¬r) ∨ (p∧¬q∧r) ∨ (p∧q∧¬r) ∨ (p∧q∧r)

四、证明题（本题共2小题，每小题8分，满分16分）

1. 证明蕴含式 ( p ∨ q) → (r ∧ s), (s ∨ u) → v ⇒ ¬p ∨ v 。
   证明：
   我们可以采用构造性证明或反证法。这里使用构造性证明（前提推结论）：

   1. 假设前提成立：(p ∨ q) → (r ∧ s) 为真，且 (s ∨ u) → v 为真。
   2. 要证明的结论是 ¬p ∨ v。我们考虑其等价形式：若 p 为真，则需证 v 为真。
   3. 假设 p 为真。则根据前提1 (p ∨ q) → (r ∧ s)，由于 p 真导致 (p ∨ q) 真，因此可推出 (r ∧ s) 为真。
   4. 由 (r ∧ s) 为真，可知 s 为真。
   5. 由于 s 为真，则 (s ∨ u) 为真。根据前提2 (s ∨ u) → v，可推出 v 为真。
   6. 因此，在 p 为真的假设下，我们推出了 v 为真。这恰好满足了 ¬p ∨ v（因为当 p 真时，v 真使得整个析取式为真；当 p 假时，¬p 为真，析取式也为真）。
   7. 综上，由前提 (p ∨ q) → (r ∧ s) 和 (s ∨ u) → v 可有效推出结论 ¬p ∨ v。证明完毕。

2. 设 R 是集合 X 上的二元关系，证明 I_X ∪ R ∪ R⁻¹ 是 X 上的相容关系。（要求有详细证明过程）
   证明：
   要证明一个关系是相容关系，需证明其满足自反性和对称性。

   • 记关系 S = I_X ∪ R ∪ R⁻¹，其中 I_X 是 X 上的恒等关系，R⁻¹ 是 R 的逆关系。

   1. 证明自反性： 对于任意 x ∈ X，根据恒等关系的定义，有 (x, x) ∈ I_X。因为 S = I_X ∪ R ∪ R⁻¹，所以 (x, x) ∈ S。因此，S 是自反的。

   2. 证明对称性： 对于任意 (x, y) ∈ S，我们需要证明 (y, x) ∈ S。

      • 根据 S 的定义，(x, y) 可能来自三个部分：
        a. 若 (x, y) ∈ I_X，则 x = y。那么显然 (y, x) = (x, x) ∈ I_X ⊆ S。
        b. 若 (x, y) ∈ R，则根据逆关系的定义，(y, x) ∈ R⁻¹。因为 R⁻¹ ⊆ S，所以 (y, x) ∈ S。
        c. 若 (x, y) ∈ R⁻¹，则根据逆关系的定义，存在 (y, x) ∈ R。因为 R ⊆ S，所以 (y, x) ∈ S。
      • 综上所述，无论 (x, y) 来自 S 的哪个部分，都有 (y, x) ∈ S。因此，S 是对称的。

   由于关系 S 同时满足自反性和对称性，根据相容关系的定义，I_X ∪ R ∪ R⁻¹ 是 X 上的相容关系。证明完毕。