千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2018年8月実施 専門 B11

标签：

• Propositional-Compactness-and-Maximal-Consistency

Author

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

Description

命題変数と $\bot,\to$ からなる論理式を考える。付値は $\nu(\bot)=0$, $\nu(A\to B)=\max\{1-\nu(A),\nu(B)\}$ を満たし、$\neg A$ は $A\to\bot$ の略記とする。論理式集合のすべての有限部分集合が充足可能なとき、その集合を有限充足可能と呼ぶ。有限充足可能な集合全体を包含関係で順序付ける。

(1) その極大元 $\Gamma$ は、任意の $A$ について $A,\neg A$ の一方だけを含むことを示せ。(2) $\bot\notin\Gamma$ でこの一方だけを含む性質を満たすが、有限充足可能でない集合を構成せよ。

题目描述

考虑只含蕴涵与假常量的命题逻辑，有限可满足指每个有限子集均可满足。(1) 证明按包含关系极大的有限可满足集合，对每个公式恰包含它或其否定之一。(2) 构造不含假常量且具有该二择一性质、但并非有限可满足的公式集合。

Kai

(1) $A,\neg A$ の両方が属すると、その二元集合が充足不能になるので不可能である。

どちらも属さないと仮定する。極大性より $\Gamma\cup\{A\}$ と $\Gamma\cup\{\neg A\}$ はいずれも有限充足可能ではない。従ってある有限集合 $\Delta_1,\Delta_2\subset\Gamma$ について、$\Delta_1\cup\{A\}$ と $\Delta_2\cup\{\neg A\}$ は充足不能である。

しかし $\Delta_1\cup\Delta_2$ は有限充足可能性によりある付値で充足される。その付値では $A$ の値は $0$ または $1$ なので、上記のいずれかの充足不能性に矛盾する。

(2) 付値であることを要求しない補助写像 $v$ を、式の構成に従って次のように定める。

$$v(\bot)=0,\quad v(p)=1\ \text{（すべての命題変数）},\qquad v(A\to B)=\begin{cases}1-v(A)&B\text{ が式 }\bot,\\0&\text{それ以外}. \end{cases}$$

$\Gamma=\{A:v(A)=1\}$ とすれば $\bot\notin\Gamma$、かつ $v(\neg A)=1-v(A)$ より各 $A,\neg A$ の一方のみを含む。しかし相異なる変数 $p,q$ に対して

$$p,q,\neg(p\to q)\in\Gamma$$

であり、この有限部分集合は充足不能である。