中央大学 理工学研究科 情報工学専攻 2024年8月実施 問題V

标签：

• 中央大学
• 命题逻辑

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

問題 I は必答。問題 II～V のうち，2 問を選んで解答すること。

10 次元の論理値を 10 個のビットの並置（例：1011010011）として定め，さらに 10 次元の論理変数を，10 次元の論理値をとりうる変数として定めたうえで，真理関数 $T$ を，10 次元の論理値に対し，ビット 1 の個数を次元 10 で割った実数値をとる関数として定める（例：$T(1011010011)=0.6$）。論理値 $p$ に対しビットごとの否定の並置を $\neg p$ と表記するとともに，10 次元の論理値 $p$ と $q$ に対しビットごとの論理積の並置を $p\land q$ と表記し，さらに論理和 $\lor$ と含意 $\to$ についても同様に表記する。これらの論理演算を論理値または論理変数に適用して得られる式を論理式とよび，論理演算子を再び論理式に適用して得られる式もまた論理式とよぶ。

1. 命題 $b$ “ある脊椎動物は鳥類（birds）である” と命題 $f$ “ある脊椎動物は飛ぶ（fly）” に対し，“ある脊椎動物が飛ばないならどちらかといえば鳥類ではない” を表す式を記せ。また，これより $T(b\to f)=0.6$ すなわち “ある脊椎動物が鳥類ならどちらかといえば飛ぶ” を導く証明の呼称を，日本語（または英語）にて記せ。
2. $T(x\land\neg y)$ の値が既知である任意の論理式 $x$ と $y$ に対し，De Morgan の法則などを利用して $T(x\to y)$ の値を得る式を記せ。
3. 命題 $m$ “ある脊椎動物は哺乳類（mammals）である” と命題 $v$ “ある脊椎動物は胎生（viviparity）である” に対し少なくとも，哺乳類の一例であるカモノハシ（duckbill）は胎生ではないので $T(m\land\neg v)>0$ といえる。この式より $T(m\to v)$ の値域を見積もる式 (＊) が導け，ある脊椎動物が哺乳類だからといって必ずしも胎生とは限らないことが証明できる。この (＊) を記せ。また，証明の呼称を日本語（または英語）にて記せ。
4. 任意の論理式 $x$ と $y$ に対し，論理式を構成する論理変数のとりうる論理値にかかわらず恒等的に $T(((x\to y)\land\neg y)\to\neg x)=1$ が成立することを，$(x\to y)\land\neg y\Rightarrow\neg x$ と表記する。この式の呼称を，日本語（またはラテン語ないし英語）にて記せ。また，$T(x\to y)$ の値と $T(\neg y)$ の値が既知のとき，$T(\neg x)$ の値域を見積もれ。
5. 命題 $r$ “ある脊椎動物は爬虫類（reptiles）である” と命題 $o$ “ある脊椎動物は卵生（oviparity）である” に対し，“ある脊椎動物が爬虫類ならほぼ卵生である” を $T(r\to o)=0.9$ とおき，さらに “ある脊椎動物がまったく卵生ではない” を $T(\neg o)=1$ とおくとする。以上より $T(\neg r)$ の値域を見積もる式 (†) が導け，その脊椎動物はほぼ爬虫類ではないことが証明できる。この (†) を記せ。また，証明の呼称を日本語（またはラテン語ないし英語）にて記せ。
6. 飛ぶものを観察してはそれが亀ではないことの確認を繰り返すことにより亀は飛ばないことへの確信を高めていく帰納推論は妥当かについて，端的に解説せよ。なお，問題文の冒頭に与えられていない用語等（ただし，ブール論理に関連するものに限る）を用いてもよい。

题目描述

问题 I 必答；问题 II～V 中选答 2 题。

将 10 维逻辑值定义为 10 个比特的排列，例如 1011010011；10 维逻辑变量是可以取这种逻辑值的变量。定义真值函数 $T$：对一个 10 维逻辑值，将其中比特 1 的个数除以维数 10，得到一个实数，例如 $T(1011010011)=0.6$。对逻辑值 $p$，逐位取否定得到的排列记为 $\neg p$；对 10 维逻辑值 $p,q$，逐位取逻辑与得到的排列记为 $p\land q$，逻辑或 $\lor$ 和蕴含 $\to$ 也采用同样的逐位定义。将这些逻辑运算施加于逻辑值或逻辑变量所得的式子称为逻辑式，将逻辑运算再次施加于逻辑式所得的式子仍称为逻辑式。

1. 设命题 $b$ 为“某脊椎动物是鸟类”，命题 $f$ 为“某脊椎动物会飞”。写出表示“如果某脊椎动物不会飞，则较倾向于认为它不是鸟类”的式子。再写出由此推出 $T(b\to f)=0.6$，即“如果某脊椎动物是鸟类，则较倾向于认为它会飞”的证明方法名称，可用日语或英语。
2. 对任意逻辑式 $x,y$，已知 $T(x\land\neg y)$ 的值，利用 De Morgan 定律等写出求 $T(x\to y)$ 的公式。
3. 设命题 $m$ 为“某脊椎动物是哺乳类”，$v$ 为“某脊椎动物是胎生”。至少存在鸭嘴兽这一哺乳动物不为胎生的例子，因而可以说 $T(m\land\neg v)>0$。由此可以推导出估计 $T(m\to v)$ 取值范围的式子 (＊)，从而证明脊椎动物即使是哺乳类，也不一定为胎生。写出 (＊)，并用日语或英语写出证明方法名称。
4. 对任意逻辑式 $x,y$，无论其中的逻辑变量取何种逻辑值，恒有 $T(((x\to y)\land\neg y)\to\neg x)=1$，将此记为 $(x\to y)\land\neg y\Rightarrow\neg x$。用日语、拉丁语或英语写出该式的名称。当 $T(x\to y)$ 和 $T(\neg y)$ 已知时，估计 $T(\neg x)$ 的取值范围。
5. 设命题 $r$ 为“某脊椎动物是爬虫类”，$o$ 为“某脊椎动物是卵生”。用 $T(r\to o)=0.9$ 表示“如果某脊椎动物是爬虫类，则几乎可以认为它是卵生”，再用 $T(\neg o)=1$ 表示“某脊椎动物完全不是卵生”。由这些条件可推得估计 $T(\neg r)$ 取值范围的式子 (†)，从而证明该脊椎动物几乎可以认为不是爬虫类。写出 (†)，并用日语、拉丁语或英语写出证明方法名称。
6. 反复观察会飞的对象并确认它不是龟，以此提高对“龟不会飞”的确信程度，这种归纳推理是否妥当？请简要解释。允许使用题干开头未给出的术语，但须限于与布尔逻辑相关的术语。

Kai

各ビットで通常のブール論理を用いるので，任意の論理式 $z$ に対して $T(\neg z)=1-T(z)$ である。また，$T$ の値は $0,0.1,\ldots,1$ に限られる。

1. 対偶

求める式は

$$\boxed{T(\neg f\to\neg b)=0.6}.$$

含意の定義と二重否定より，各ビットで

$$\neg f\to\neg b=f\lor\neg b=\neg b\lor f=b\to f$$

となるため，$T(b\to f)=0.6$ が得られる。この証明は 対偶による証明（contraposition） である。

2. 含意が偽となる場合

含意の定義と De Morgan の法則から，

$$x\to y=\neg x\lor y=\neg(x\land\neg y).$$

従って，

$$\boxed{T(x\to y)=1-T(x\land\neg y)}.$$

3. 反例による反証

第 2 問の式より，

$$T(m\to v)=1-T(m\land\neg v)<1.$$

10 ビットのうち少なくとも 1 ビットで $m\land\neg v$ が真なので，その真理関数の値は少なくとも $0.1$ である。従って，より具体的には

$$\boxed{0\le T(m\to v)\le0.9<1}\tag{＊}$$

となる。方法の名称は 反例による反証（disproof by counterexample） である。普遍的に真であるためには全ビットで真でなければならず，一つの反例だけでもこれを否定できる。

4. 後件否定と真理関数の範囲

この推論形式は 後件否定（modus tollens） である。実際，

$$(x\to y)\land\neg y =(\neg x\lor y)\land\neg y =\neg x\land\neg y$$

なので，前件が真である各ビットで必ず $\neg x$ も真となる。

$a=T(x\to y)$，$b=T(\neg y)$ とおく。各ビットにおける $(x,y)$ の値で分類すると，次の表を得る。

$(x,y)$	全ビットに占める割合
$(1,0)$	$1-a$
$(0,0)$	$a+b-1$
$(0,1)$	$q$
$(1,1)$	$1-b-q$

ここで，$y=0$ の割合が $b$ であることから，$(0,0)$ の割合は $b-(1-a)=a+b-1$ と決まる。一方，$y=1$ のビットにおける $x$ の値は未定なので，$0\le q\le1-b$。従って

$$T(\neg x)=a+b-1+q$$

となり，求める最良の上下界は

$$\boxed{\begin{gathered} T(x\to y)+T(\neg y)-1\\ \le T(\neg x)\le T(x\to y) \end{gathered}}.$$

実際の論理式から得られる $a,b$ は必ず $a+b\ge1$ を満たす。この範囲内の $0.1$ 刻みの値は，$y=1$ のビットのうち $x=0$ とする個数を選ぶことですべて実現できる。

5. 卵生でないという情報を用いた後件否定

第 4 問に $a=0.9$，$b=1$ を代入すると，

$$0.9\le T(\neg r)\le0.9.$$

従って，

$$\boxed{T(\neg r)=0.9}\tag{†}$$

である。$T(\neg o)=1$ は全ビットで $o=0$ であることを意味し，この場合 $r\to o=\neg r\lor o=\neg r$ となるため，等号を直接確認することもできる。推論形式は 後件否定（modus tollens） である。

6. 対偶の検証と帰納推論

亀であることを $t$，飛ぶことを $f$ とすれば，「亀は飛ばない」は $t\to\neg f$，「飛ぶものは亀ではない」は $f\to\neg t$ である。両者は対偶であり，各ビットで同値である。

したがって，飛ぶものの中に亀という反例がないかを調べることは，亀が飛ばないという仮説を検証する方法として妥当である。ただし，有限回の観察で反例が見つからなかったことから，全ての亀についての普遍命題を演繹的に確定することはできない。観測対象の偏りもあり得るため，確信がどれだけ高まるかはブール論理の同値性だけでは決まらない。

Reference

• 中央大学 2025年度 夏季一般入学試験・情報工学 公式問題（冊内 p.78／PDF 第79頁）