跳到主要内容

電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2024年8月実施 選択問題 離散数学とオートマトン

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

1. α\alpha と β\beta は命題を表し、P(x)P(x) は xx を変数とする述語論理式を表す。

（1）論理式 α∧β\alpha\land\beta、α∨β\alpha\lor\beta、α→β\alpha\to\beta、α↔β\alpha\leftrightarrow\beta の真理値表を書け。なお、真は 1、偽は 0 で表すこと。

（2）以下の（i）〜（iii）の論理式に対し、常に真偽が一致する論理式を直後の選択肢より一つ選び、（a）〜（d）の記号で答えよ。

（i）α→β\alpha\to\beta

（a）（b）（c）（d）
β→α\beta\to\alphaβ→¬α\beta\to\neg\alpha¬β→α\neg\beta\to\alpha¬β→¬α\neg\beta\to\neg\alpha

（ii）¬(α∧β)\neg(\alpha\land\beta)

（a）（b）（c）（d）
¬α∧¬β\neg\alpha\land\neg\beta¬α∨¬β\neg\alpha\lor\neg\beta¬(¬α∧¬β)\neg(\neg\alpha\land\neg\beta)¬(¬α∨¬β)\neg(\neg\alpha\lor\neg\beta)

（iii）∀x¬P(x)\forall x\neg P(x)

（a）（b）（c）（d）
¬(∀xP(x))\neg(\forall xP(x))¬(∀x¬P(x))\neg(\forall x\neg P(x))¬(∃xP(x))\neg(\exists xP(x))¬(∃x¬P(x))\neg(\exists x\neg P(x))

2. 集合 A={1,2,3}A=\{1,2,3\}、A2=A×AA^2=A\times A 上の関係 R1R_1 と R2R_2 について以下の問に答えよ。

（1）

R1={((a,b),(c,d))∈A2×A2∣a+b=c+d}\begin{gathered} R_1=\{((a,b),(c,d))\in A^2\times A^2\mid a+b\\ =c+d\} \end{gathered}

とすると、R1R_1 は同値関係である。A2A^2 の R1R_1 による同値類をすべて書け。各同値類の要素もすべて記述すること。

（2）

R2={((a,b),(c,d))∈A2×A2∣((a=c)∧(b=d))∨((a<c)∧(b<d))}\begin{aligned} R_2=\{((a,b),(c,d))\in A^2\times A^2\mid{}&((a=c)\land(b=d))\\ &\lor((a<c)\land(b<d))\} \end{aligned}

とすると、R2R_2 は半順序である。半順序集合 (A2,R2)(A^2,R_2) のハッセ図を描け。

3. 以下の（1）〜（9）で示す各々の言語 L1∼L9L_1\sim L_9 に対し、正則（すなわちそれを受理する有限オートマトンが存在する）ならば ○、正則でないならば × で答えよ。なお、どれも入力記号集合は Σ={0,1}\Sigma=\{0,1\} とし、任意の語 w∈Σ∗w\in\Sigma^* に対し、ww の含む “1” の数と “0” の数を各々 ∣w∣1|w|_1 と ∣w∣0|w|_0 で表現する。

（1）L1={w∈Σ∗∣(∣w∣1−∣w∣0) は偶数}L_1=\{w\in\Sigma^*\mid (|w|_1-|w|_0)\text{ は偶数}\}

（2）L2={w∈Σ∗∣∣w∣1≤2100}L_2=\{w\in\Sigma^*\mid |w|_1\le2^{100}\}

（3）L3={w∈Σ∗∣∣w∣1≤∣w∣0}L_3=\{w\in\Sigma^*\mid |w|_1\le|w|_0\}

（4）L4=L1∪L2L_4=L_1\cup L_2

（5）L5=L1∩L2L_5=L_1\cap L_2

（6）L6=L1∪L3L_6=L_1\cup L_3

（7）L7=L1∩L3L_7=L_1\cap L_3

（8）L8=L2∪L3L_8=L_2\cup L_3

（9）L9=L2∩L3L_9=L_2\cap L_3

命題：proposition、変数：variable、述語論理式：predicate logic expression、論理式：logic expression、真理値表：truth table、真：true、偽：false、集合：set、関係：relation、同値関係：equivalence relation、同値類：equivalence class、半順序：partial order、半順序集合：partially ordered set、ハッセ図：Hasse diagram、言語：language、正則：regular、受理：accept、有限オートマトン：finite automaton、入力記号集合：input alphabet set、語：word、偶数：even number。

题目描述​

1. α,β\alpha,\beta 表示命题，P(x)P(x) 表示以 xx 为变量的谓词逻辑式。

（1）写出 α∧β\alpha\land\beta、α∨β\alpha\lor\beta、α→β\alpha\to\beta、α↔β\alpha\leftrightarrow\beta 的真值表，用 1 表示真、0 表示假。

（2）对下列（i）～（iii），从各自的（a）～（d）中选择一个与所给式子始终具有相同真值的逻辑式，回答字母。

（i）α→β\alpha\to\beta：

（a）β→α\beta\to\alpha；（b）β→¬α\beta\to\neg\alpha；（c）¬β→α\neg\beta\to\alpha；（d）¬β→¬α\neg\beta\to\neg\alpha。

（ii）¬(α∧β)\neg(\alpha\land\beta)：

（a）¬α∧¬β\neg\alpha\land\neg\beta；（b）¬α∨¬β\neg\alpha\lor\neg\beta；（c）¬(¬α∧¬β)\neg(\neg\alpha\land\neg\beta)；（d）¬(¬α∨¬β)\neg(\neg\alpha\lor\neg\beta)。

（iii）∀x¬P(x)\forall x\neg P(x)：

（a）¬(∀xP(x))\neg(\forall xP(x))；（b）¬(∀x¬P(x))\neg(\forall x\neg P(x))；（c）¬(∃xP(x))\neg(\exists xP(x))；（d）¬(∃x¬P(x))\neg(\exists x\neg P(x))。

2. 设 A={1,2,3}A=\{1,2,3\}、A2=A×AA^2=A\times A，回答关于 A2A^2 上关系 R1,R2R_1,R_2 的问题。

（1）定义

R1={((a,b),(c,d))∈A2×A2∣a+b=c+d},\begin{gathered} R_1=\{((a,b),(c,d))\in A^2\times A^2\mid a+b\\ =c+d\}, \end{gathered}

则 R1R_1 是等价关系。写出 A2A^2 关于 R1R_1 的全部等价类，须列出每个等价类的全部元素。

（2）定义

R2={((a,b),(c,d))∈A2×A2∣((a=c)∧(b=d))∨((a<c)∧(b<d))},\begin{aligned} R_2=\{((a,b),(c,d))\in A^2\times A^2\mid{}&((a=c)\land(b=d))\\ &\lor((a<c)\land(b<d))\}, \end{aligned}

则 R2R_2 是偏序。画出偏序集 (A2,R2)(A^2,R_2) 的 Hasse 图。

3. 判断以下（1）～（9）的语言 L1∼L9L_1\sim L_9 是否为正则语言，即是否存在接受它的有限自动机。正则填 ○，非正则填 ×。所有语言的输入字母表均为 Σ={0,1}\Sigma=\{0,1\}。对任意单词 w∈Σ∗w\in\Sigma^*，其中 “1” 与 “0” 的数量分别记为 ∣w∣1,∣w∣0|w|_1,|w|_0。

（1）L1={w∈Σ∗∣(∣w∣1−∣w∣0) 为偶数}L_1=\{w\in\Sigma^*\mid (|w|_1-|w|_0)\text{ 为偶数}\}

（2）L2={w∈Σ∗∣∣w∣1≤2100}L_2=\{w\in\Sigma^*\mid |w|_1\le2^{100}\}

（3）L3={w∈Σ∗∣∣w∣1≤∣w∣0}L_3=\{w\in\Sigma^*\mid |w|_1\le|w|_0\}

（4）L4=L1∪L2L_4=L_1\cup L_2

（5）L5=L1∩L2L_5=L_1\cap L_2

（6）L6=L1∪L3L_6=L_1\cup L_3

（7）L7=L1∩L3L_7=L_1\cap L_3

（8）L8=L2∪L3L_8=L_2\cup L_3

（9）L9=L2∩L3L_9=L_2\cap L_3

Kai​

1.​

(1)​

α\alphaβ\betaα∧β\alpha\land\betaα∨β\alpha\lor\betaα→β\alpha\to\betaα↔β\alpha\leftrightarrow\beta
000011
010110
100100
111111

(2)​

対偶、De Morgan の法則、量化否定より、

(i) (d),(ii) (b),(iii) (c).\boxed{\text{(i) (d)},\qquad \text{(ii) (b)},\qquad \text{(iii) (c)}}.

対応する同値式は順に ¬β→¬α\neg\beta\to\neg\alpha、¬α∨¬β\neg\alpha\lor\neg\beta、¬(∃xP(x))\neg(\exists xP(x)) である。

2.​

(1)​

R1R_1 の同値類は成分和ごとに分かれ、すべて書くと

{(1,1)},{(1,2),(2,1)},{(1,3),(2,2),(3,1)},{(2,3),(3,2)},{(3,3)}.\boxed{ \begin{aligned} &\{(1,1)\},\\ &\{(1,2),(2,1)\},\\ &\{(1,3),(2,2),(3,1)\},\\ &\{(2,3),(3,2)\},\\ &\{(3,3)\} \end{aligned} }.

(2)​

R2R_2 の被覆関係を下から上へ結ぶと、Hasse 図は次のようになる。

ここで (1,3)(1,3) と (3,1)(3,1) は孤立点である。

3.​

N=2100N=2^{100} とおく。判定結果は

L1L2L3L4L5L6L7L8L9正則か∘∘×∘∘×××∘.\boxed{ \begin{array}{c|ccccccccc} &L_1&L_2&L_3&L_4&L_5&L_6&L_7&L_8&L_9\\ \hline \text{正則か}&\circ&\circ&\times&\circ&\circ&\times&\times&\times&\circ \end{array} }.

  • L1L_1：∣w∣1−∣w∣0|w|_1-|w|_0 の偶奇は ∣w∣|w| の偶奇に等しいので正則である。

  • L2L_2：11 の個数が固定上限 NN 以下なので、有限状態で数えられ、正則である。

  • L3L_3：L3∩1∗0∗={1m0n∣m≤n}L_3\cap1^*0^*=\{1^m0^n\mid m\le n\} はポンピング補題に反するので、正則でない。

  • L4,L5L_4,L_5：正則言語 L1,L2L_1,L_2 の和と共通部分なので正則である。

  • L6L_6：正則と仮定すると、その補集合と 1∗0∗1^*0^* の共通部分

    {1m0n∣m>n, m−n は奇数}\{1^m0^n\mid m>n,\ m-n\text{ は奇数}\}

    も正則となるが、1p+10p1^{p+1}0^p にポンピング補題を適用すると矛盾する。

  • L7L_7：

    L7∩1∗0∗={1m0n∣m≤n, m−n は偶数}L_7\cap1^*0^*=\{1^m0^n\mid m\le n,\ m-n\text{ は偶数}\}

    に対し、1p0p1^p0^p をポンプアップすると矛盾するので、正則でない。

  • L8L_8：正則と仮定すると、その補集合と 1∗0∗1^*0^* の共通部分

    {1m0n∣m>N, m>n}\{1^m0^n\mid m>N,\ m>n\}

    も正則となるが、1N+p+10N+p1^{N+p+1}0^{N+p} をポンプダウンすると矛盾する。

  • L9L_9：

    L9=⋃k=0N{w∣∣w∣1=k}∩{w∣∣w∣0≥k}L_9= \bigcup_{k=0}^{N} \{w\mid |w|_1=k\}\cap\{w\mid |w|_0\ge k\}

    は正則言語の有限和なので正則である。

Reference​

本页目录