桜技録

🐈🐈🐈🐈🐘

ノート: 情報科学における論理③

数学 情報科学における論理

間が空いてしまったけれど小野寛晰『情報科学における論理』の読書ノート。なるべく練習問題も解いてく。（→前回）

2021-11-13 読み返してて気になる点があったので一部を訂正

第2章 述語論理

述語論理の論理式

言語

述語論理を記述するのに必要な以下の記号の集まりを言語（language）という。

  • 論理結合子 : \land , \lor , \rightarrow , \lnot

  • 量化記号　 : \forall , \exists

  • 対象変数　 : 議論対象の「もの」の集合を動く変数

  • 対象定数　 : 議論対象の「もの」の集合のうち特定の要素を表す記号

  • 関数記号　 : 議論対象の「もの」の集合上に定義された関数を表す記号

  • 述語記号　 : 議論対象の「もの」の集合上に定義された述語を表す記号　

  • 補助記号　 : 括弧やカンマなど

これらはあくまで記号であって、その記号が表す「もの」と同一視してはならない。関数 f と「 f 」という記号（文字）は別のものだと意識する。

項

  • 対象変数、対象定数は項（term）

  • f が m 変数の関数記号、 t_i が項のとき、 f ( t_1 , \cdots , t_m ) は項

論理式

  • P が n 変数の述語記号、 t_i が項のとき、 P ( t_1 , \cdots , t_n ) は論理式（formula）。この形を特に原子論理式（atomic formula）という

  • A , B が論理式のとき、 A \land B , A \lor B , A \rightarrow B , \lnot A は論理式

  • A が論理式、 x が対象変数のとき、 \forall x A , \exists x A は論理式

束縛変数と自由変数

論理式 \forall x A , \exists x A に於いて変数 x の出現（occurrence）を束縛された出現といい、 x を束縛変数（bound variable）という。反対に束縛されていない出現を自由な出現といい、その変数を自由変数（free variable）という。

自由変数のない論理式を閉じた論理式（closed formula）といい、論理式 A のすべての自由変数 x_1 , \cdots , x_n を全称記号で束縛した論理式 \forall x_1 \cdots \forall x_n A を A の閉包（universal closure）という。

代入

論理式 A の自由変数 x を項 t で置き換えた論理式を A [ t / x ] と表し、 x への t の代入（substitution）という。特に複数回の代入を順序を設けず同時に実施する際は A [ t_1 / x_1 , \cdots , t_n / x_n ] のように表す。

構造

言語 \mathscr{ L } に対して次の U , I からなる2つ組を \mathscr{ L } の構造（structure）という。

  • U は \mathscr{ L } の対象変数が動く空でない集合。対象領域（domain）

  • I は \mathscr{ L } の対象定数を U の要素に、関数記号を U 上の関数に、述語記号を U 上の述語に対応させる写像。解釈（interpretation）

解釈 I による像は I ( x ) ではなく x^{ I } と表記するのが一般的な模様。

論理式 A が構造 \mathfrak{ A } で正しいことを \mathfrak { A } \vDash A で表す。

構造により「記号」と「記号が表す『もの』」とが関連付けられる。つまり記号列であった論理式に具体的な意味が生まれる。

言語 \mathscr{ L } とそれに対する構造 \mathfrak{ A } = ( U , I ) があるとき、 U の各要素 u に対応する各記号 \underline{ u } を \mathscr{ L } の対象定数に追加して新しい言語を定義できる。この言語を \mathscr{ L } [ \mathfrak { A } ] で表す。

恒真な論理式

ある言語上の論理式 A が任意の構造に於いて正しいとき A は恒真である（valid）といい、 \vDash A と表す。

練習問題

問2.1

1)-1 「ある学生が存在し、すべての教師が好きだ」すなわち「教師を好む学生がいる」

1)-2 「すべての怠け者はすべての教師が好きでない」すなわち「怠け者は教師を好きではない」

2) \lnot \forall x ( T ( x ) \rightarrow L ( x ) )

問2.2

1) 「任意の実数 x , y について、 x \lt y ならば x \lt z かつ z \lt y を満たす実数 z が存在する」すなわち「実数は稠密である」

2) 「任意の実数 x , y , z について、 x \lt z かつ z \lt y ならば x \lt y 」すなわち「関係 \lt は推移律を満たす」

問2.3

s に x が出現しない、かつ t に y が出現しないこと

問2.4

等しいとはいえない。以下いずれをも満たす必要がある

  • t に x が出現しないこと

  • B_z を \forall z C または \exists z C としたとき、 C に自由変数 x の出現する B_y 、 自由変数 x の出現する B_t 、 自由変数 y の出現する B_t がいずれも A の部分論理式でないこと

問2.5

1)-1 成り立たない。最大元は存在しない

1)-2 成り立つ。 x = a_4 のとき y = a_4 とし、それ以外は y = a_5 とすればよい

2)-3 成り立つ。 ( y , z ) = ( a_4 , a_5 ) のときなど

2)-4 成り立たない。 ( x , y , z ) = ( a_1 , a_2 , a_3 ) のときなど

問2.6

1) \forall s \forall t ( ( A [ s / x ] \land A [ t / x ] ) \rightarrow s = t )

2) \forall s \forall t ( ( A [ s / x ] \land A [ t / x ] ) \rightarrow s = t ) \land \exists s A [ s / x ]

3) \exists s \exists t ( ( A [ s / x ] \land A [ t / x ] ) \land \lnot ( s = t ) )

問2.7

1) \exists x \forall y ( x \leq y ) （自然数に最小元は存在するが整数には存在しない）

2) \exists x \exists y ( \lnot ( y \leq x ) \land \forall z ( \lnot ( x \leq z ) \lor \lnot ( z \leq y ) ) ) （「間にどんな要素も挟まらない異なる2要素が存在する」の意。整数では正しいが有理数では正しくない）

問2.9

8) 構造 \mathfrak{ A } = ( \mathbf{ N } , I ) をとる。但し D を x R y とし、 R^{ I } に大小関係 \gt をとる。このとき任意の自然数に対して真に大きい自然数は存在するが、すべての自然数より真に大きな自然数は存在しない。つまり \mathfrak{ A } \vDash \forall y \exists x ( x R y ) かつ \mathfrak{ A } \nvDash \exists x \forall y ( x R y ) 、従って \mathfrak{ A } \nvDash \forall y \exists x ( x R y ) \rightarrow \exists x \forall y ( x R y ) 。

9) 構造 ( \{ 0 , 1 \} , I ) をとればよい。但し B を P ( x ) とし、 P^{ I } に「1である」をとる。

14) 構造 \mathfrak{ A } = ( \mathbf{ N } , I ) をとる。但し ( B , C ) を ( P ( x ) , Q ( x ) ) とし、 P^{ I } , Q^{ I } にそれぞれ「偶数である」、「奇数である」をとる。このとき明らかに \mathfrak{ A } \nvDash \forall x P ( x ) 、よって \mathfrak{ A } \vDash \forall x P ( x ) \rightarrow \forall x Q ( x ) 。一方これもまた明らかに \mathfrak{ A } \nvDash \forall x ( P ( x ) \rightarrow Q ( x ) ) 。従って \mathfrak{ A } \nvDash ( \forall x P ( x ) \rightarrow \forall x Q ( x ) ) \rightarrow \forall x ( P ( x ) \rightarrow Q ( x ) ) 。

15) 構造 ( \{ 0 , 1 \} , I ) をとればよい。但し ( B , C ) を ( P ( x ) , Q ( x ) ) とし、 P^{ I } , Q^ { I } にそれぞれ「0または1である」、「1である」をとる。

問2.10

恒真でない。 \mathfrak{ A } \nvDash \exists x P ( x ) となるような構造 \mathfrak{ A } を示せばOK。

問2.11

1) \exists x R ( x , y ) \rightarrow \forall y ( P ( y ) \land \lnot \forall z Q ( z ) ) \\ \sim \forall x ( R ( x , y ) \rightarrow \forall y ( P ( y ) \land \lnot \forall z Q ( z ) ) ) \\ \sim \forall x \forall t ( R ( x , y ) \rightarrow ( P ( t ) \land \lnot \forall z Q ( z ) ) ) \\ \sim \forall x \forall t \exists z ( R ( x , y ) \rightarrow ( P ( t ) \land \lnot Q ( z ) ) )

2) \exists x ( \forall y ( P ( y ) \rightarrow Q ( x , z ) ) \lor \exists z ( \lnot \exists u R ( z , u ) \land Q ( x , z ) ) ) \\ \sim \exists x \forall y ( ( P ( y ) \rightarrow Q ( x , z ) ) \lor \exists z ( \lnot \exists u R ( z , u ) \land Q ( x , z ) ) ) \\ \sim \exists x \forall y \exists t ( ( P ( y ) \rightarrow Q ( x , z ) ) \lor ( \lnot \exists u R ( t , u ) \land Q ( x , t ) ) ) \\ \sim \exists x \forall y \exists t \forall u ( ( P ( y ) \rightarrow Q ( x , z ) ) \lor ( \lnot R ( t , u ) \land Q ( x , t ) ) )

（→次回）