2021 国考

数学

一，用逻辑符号表达下列语句

1．任何计算设备都可以求解某个问题。

设：

• C(x)：x 是计算设备
• P(y)： y 是问题
• S(x, y)：计算设备x 可以求解问题 y

则“任何计算设备都可以求解某个问题”可以表达为：

$$\forall x(C(x)\to \exists y(P(y)\wedge S(x,y)))$$

解释：

• 对于所有 x ，如果 x 是计算设备 C(x)，那么存在一个问题 $y$（$\exists y(P(y))$），使得 x 可以求解 y S(x, y) 。

二，填空题

1．设集合 \mathrm{A}={1,2,3,4} ，则集合 A 上有（）种等价关系。

集合 ( A = {1, 2, 3, 4} ) 上的等价关系数目等于其不同划分方式的数量，即贝尔数 ( B_4 )。通过斯特林数（第二类）计算如下：

1. 斯特林数分解：

   • ( S(4,1) = 1 )（全部元素在一个子集）。
   • ( S(4,2) = 7 )（分成两个非空子集，例如通过公式 $(2^4-2)/2=7$。
   • ( S(4,3) = 6 )（分成三个非空子集，对应选2个元素组合成一对，共$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 种）。
   • ( S(4,4) = 1 )（每个元素单独成子集）。

2. 贝尔数计算：
   $$B_4=S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15.$$

结论：集合 ( A ) 上有 15 种等价关系。

$$\boxed{15}$$

2．A 上的二元关系， R= { < x , y > ∣ x 是 y 的父亲 } \{<x, y>\mid x 是 y 的父亲 \} {<x,y>∣x是y的父亲}, S= { < x , y > ∣ x 是 y 的母亲 } \{<x, y>\mid x 是 y 的母亲 \} {<x,y>∣x是y的母亲} 。当 Q 为＿时，满足 x 和 y 是夫妻关系。一「国考－2021」

解答

逆： ${\mathrm{R}}^{-1}=\{⟨\mathrm{y},\mathrm{x}⟩\mid <\mathrm{x},\mathrm{y}>\in \mathrm{R}\}$
合成： RoS ⁡ = { < x , z > ∣ ∃ y ( < x , y > ∈ R ∧ < y , z > ∈ S ) } \operatorname{RoS}=\{<x, z>\mid \exists y(<x, y>\in R \wedge<y, z>\in S)\} RoS={<x,z>∣∃y(<x,y>∈R∧<y,z>∈S)}
要构造关系 ( Q ) 使得 ( x,Q,y ) 表示“( x ) 和 ( y ) 是夫妻”，需通过父亲关系 ( R ) 和母亲关系 ( S ) 的复合关系来定义。

---

1. 夫妻关系的逻辑：

   • ( x ) 是 ( y ) 的妻子，当且仅当存在一个共同子女 ( z )，使得：
     • ( x ) 是 ( z ) 的母亲（即 ( $⟨x,z⟩\in S$ )），
     • ( y ) 是 ( z ) 的父亲（即 ( $⟨y,z⟩\in R$ )）。
   • 同理，( y ) 是 ( x ) 的丈夫需通过逆关系构造。

2. 复合关系构造：

   • 妻子关系：( $S\circ R^{-1}$ )
     表示“存在 ( z )，使得 ( x ) 是 ( z ) 的母亲，且 ( y ) 是 ( z ) 的父亲”。
   • 丈夫关系：( $R\circ S^{-1}$ )
     表示“存在 ( z )，使得 ( y ) 是 ( z ) 的母亲，且 ( x ) 是 ( z ) 的父亲”。
   • 夫妻关系的并集：
     $$Q=(R\circ S^{-1})\cup (S\circ R^{-1}),$$
     覆盖所有可能的夫妻对。

---

验证复合关系

• 举例：
  • 若 ( $⟨x,y⟩\in S\circ R^{-1}$ )，则存在 ( z ) 使得 ( x ) 是 ( z ) 的母亲，( y ) 是 ( z ) 的父亲，故 ( x ) 是 ( y ) 的妻子。
  • 若 ( $⟨x,y⟩\in R\circ S^{-1}$ )，则存在 ( z ) 使得 ( y ) 是 ( z ) 的母亲，( x ) 是 ( z ) 的父亲，故 ( y ) 是 ( x ) 的妻子（即 ( x ) 是 ( y ) 的丈夫）。
• 对称性：夫妻关系是双向的，需通过并集确保对称性。

---

最终答案

$$\boxed{Q=(R\circ S^{-1})\cup (S\circ R^{-1})}$$
即用题目中的符号表示为 ROS⁻¹ ∪ SOR⁻¹。

3．有 5 个男同学和 3 个女同学站成一排，如果没有 2 个女同学相邻，共有（）种不同的排法。

4．设 G 是有 10 个顶点的无奇圈的简单连通图，则 G 的着色数是（）（简单图的着色数是指相邻的顶点着不同的颜色所需的最少颜色的个数）。

5．如果 $\frac{1}{[f0]}(1-2x{)}^2={\sum }_{k=0}^{\infty }(\genfrac{}{}{0ex}{}{n}{k})a_k{x}^k$ ，则 $a_k$= （）

三，解答题

1，用逻辑符号表示 $\forall xF(x)\to \exists yG(y)$ 。论域为 { a , b , c } \{a, b, c\} {a,b,c} ,设个体域为 { a , b , c } \{\mathrm{a}, \mathrm{b}, \mathrm{c}\} {a,b,c} ，试写出公式 $(\exists \mathrm{x})\mathrm{P}(\mathrm{x})\to (\forall \mathrm{y})\mathrm{Q}(\mathrm{y})$ 的命题逻辑表达。

2，（5分）求$(\neg P\vee Q)\to (Q\wedge \neg R)\vee P$的主合取范式和主析取范式。（用简洁表示法，如 ${\mathbf{M}}_2,{\mathrm{m}}_3$ 等。）

3，有4对夫妻围坐一个圆桌，至少有一对不相邻的坐法有多少种。

4，把 6 个相异的球放进 5 个不同的盒子里，不允许空盒，有多少种放法。
5．设某单位安排 A，B，C，D，E 和 F 六人从周二到周六值班。每天有且仅有一人值班，条件是 A 不能周一值班， B 不能周二值班， C 不能周三值班，求共有多少种安排值班的方法。

四，解答题。

A= { 1 , 2 , 3 , 4 , 5 , 6 } \{1,2,3,4,5,6\} {1,2,3,4,5,6}

（1）找一个既满足等价关系，又满足偏序关系的例子。
（2）证明（1）中例子既是偏序关系又是等价关系。

解答

1) 例子：恒等关系

在集合 ( A = {1,2,3,4,5,6} ) 上，定义关系：
[
R = { (a, a) \mid a \in A },
]
即每个元素仅与自身相关。

2) 证明

步骤1：验证 ( R ) 是等价关系

• 自反性：对任意 ( a \in A )，有 ( (a, a) \in R )，满足自反性。
• 对称性：若 ( (a, b) \in R )，则 ( a = b )，因此 ( (b, a) = (a, a) \in R )，满足对称性。
• 传递性：若 ( (a, b) \in R ) 且 ( (b, c) \in R )，则 ( a = b ) 且 ( b = c )，故 ( a = c )，即 ( (a, c) \in R )，满足传递性。

步骤2：验证 ( R ) 是偏序关系

• 自反性：同上，满足自反性。
• 反对称性：若 ( (a, b) \in R ) 且 ( (b, a) \in R )，则 ( a = b )，满足反对称性。
• 传递性：同上，满足传递性。

结论：恒等关系 ( R ) 同时满足等价关系和偏序关系的所有条件。

最终答案

1. 例子：
   [
   \boxed{R = { (a, a) \mid a \in A }}
   ]
2. 证明：恒等关系 ( R ) 是等价关系（满足自反、对称、传递）和偏序关系（满足自反、反对称、传递）。