論理数学 期末試験
年
月
日実施
学生番号 氏名
命題論理式 に対して 以下のような命題論理式 を考える
このとき左の条件の下で論理式 が恒真となるときには解答欄の空欄に○を充足不能 となるときには解答欄の空欄に×をど ちらとも言えないときには解答欄の空欄に△を記 入せよ
条件
が恒真 ○ ○ ○ ○ ○ とが充足不能 ○ △ △ × ○
とが充足不能 ○ △ △ × △
とが充足不能 ○ △ ○ △ △
が恒真かつが充足不能 △ × △ × △
命題論理に関する以下の問に答えよ
かつ となることを証明せよ．
以下の真理値表より を真とする解釈は を真とし
を真とする解釈は を真とする
かつ ならば となることを証明せよ
より となる解釈に対して となる
より となる解釈に対して となる このとき なのでとを同一視できる
したがって となる解釈に対して となる すなわち となる
別証
より 任意の解釈に対して ならば である
より 任意の解釈に対して ならば である このとき なのでとを同一視できる
したがって 任意の解釈に対して ならば である すなわち となる
別証
と演繹定理より は恒真である
と演繹定理より は恒真である
このとき ではないすなわち が恒真でないと仮定する このとき となる解釈が存在する
よって かつとなる
が恒真なので つまり となる 一方 が恒真なので つまり となる これは矛盾である
半順序 に対して 以下のハッセの図式で与えられる半順序集合 を考 える
さらに および 述語 を以下のように定義する
このとき各 に対して左に与えられた論理式が真となるときには空欄に○を 偽となる ときには空欄に×を記入せよ ただし 論理式 に対して は に出現する自由変数 をすべて全称記号で束縛した式を表す
論理式
○ × ○ × ○ × 高さのパスの最大値が全体の最大値
○ × ○ ○ × × 高さのパスの最小値が全体の最小値
¼
¼
× ○ ○ × ○ × 高さのパスでと比較不能な¼が存在
¼
¼
¼
¼
¼
○ ○ ○ ○ × ○
¼
と¼が比較不能な高さのパスでは
と¼も比較不能
¼
¼
¼
¼
○ ○ ○ × ○ ○
高さのパスのと比較不能な¼が
存在するとき と比較不能な¼が存在
○ × ○ × ○ × 述語に対して最大値が存在
○ × ○ ○ × × 述語に対して最小値が存在
○ × × ○ ○ ○
述語に対して中間値が存在は前提が偽
を述語記号を関数記号を定数記号を変数とする このとき表 の左の欄に与えられた二つのアトムが単一化可能な場合はそのときのをそうでない 場合は×を表の右の欄に記入せよ
×
×
以下の節集合の線形反駁を求めよ ただし 導出に用いたを明記すること
