←【情報学基礎Ａ】シラバスへ

第２２回講義内容へ→

←講義のツボメニューへ

情報学基礎Ａ

【第２０／２１回】【2001.1.11,16】【野村美穂】

関数モデル
（８）（９）
論理型計算モデル

一階述語論理

定義１）項

1. 変数は項である。
2. 定数は項である。
3. 関数は項である。
   ・・・t₁,t₂,...,t_nが項ならばn変数関数fによって作られたf(t₁,t₂,...,t_n)は項である。

定義２）命題
「〜は〜である」のような形の文において、真または偽のどちらか一方をとるもの。
「〜は〜である」のような文を言明という。
また、変数を含む命題を「述語」という。

定義３）論理式

1. t₁,t₂,...,t_nが項ならば、n変数述語Pによって作られたP(t₁,t₂,...,t_n)は論理式である。
2. P、Qが論理式ならば、以下のものは論理式である。

   ¬P	Pの否定（否定）
   P∧Q	PかつQ（論理積）
   P∨Q	PまたはQ（論理和）
   P→Q	PならばQ（含意）→条件文
   P⇔Q	PとQは同値→必要十分条件

3. Pを論理式、xが実数ならば、次のものは論理式である。

   ∀xＰ	任意の（全ての）xについてＰ、あるいは、各xについてＰ。
   ∃xＰ	あるxが存在してＰ、あるいはＰを満たすxが存在する。

   ∀は全称記号（allの意）、∃は存在記号（existの意）である。
   ∀xのxを、束縛変数という。このとき、xは限量または束縛されているという。

定義４）開（閉）論理式
開論理式・・・論理式の全ての変数が∀または∃によって束縛されていない関数。
閉論理式・・・論理式の全ての変数が∀または∃によって束縛されている関数。

優先順位・・・（）省略の場合

高い	¬、∀、∃
・・	∧
・・	∨
低い	⇒、⇔

論理式の解釈

解釈・・・論理式に含まれる項（定数、関数）や述語に適当な意味を定めること。

1. ある集合Ｕ（領域）を定め、各定数にＵの要素を割り当てる。
2. n変数関数fをＵ上の関数Ｕⁿ→Ｕとして定める。
3. n変数述語ＰをＵ上の関数Ｕⁿ→｛真、偽｝として定める。

恒真な論理式

充足可能	ある解釈のもとで真となることができる論理式
充足不可能	充足可能でない論理式

充足可能・・・真となる解釈が１つのみ

恒真（妥当）	どの解釈のもとでも常に真となる論理式
恒偽	どの解釈のもとでも常に偽となる論理式
等価	２つの論理式ＦとＱの審議値が任意の解釈のもとで同じであること（Ｆ＝Ｑと表す）

←【情報学基礎Ａ】シラバスへ

第２２回講義内容へ→