命題論理
(
充足可能性問題)
Dec. 27
ここでは
(p
1∨ p
2) ∧ (p
3∨ p
4)
を(p
1∨ p
2)(p
3∨ p
4)
のように∧
を省略して表記します。p
iは命題変数で0(
偽)
また は1(真)
の値をとります。また命題変数に0
または1
の値を固定することを割り当てといいます。問１．
P = (p
1∨ ¬ p
2)( ¬ p
1∨ p
2)
のときP
が1
となる割り当てがあるか。あるならばその割り当てを答えな さい。問
2． P = (p
1∨ ¬ p
2)( ¬ p
1∨ p
2)( ¬ p
1∨ ¬ p
2)(p
1∨ p
2)
のときP
が1
となる割り当てがあるか。あるならばそ の割り当てを答えなさい。問
3
．P = ( ¬ p
1∨ ¬ p
2∨ p
3)(p
1∨ p
2∨ p
3∨ ¬ p
5∨ p
6)(p
1∨ ¬ p
2∨ p
4∨ ¬ p
5∨ p
6)(p
2∨ ¬ p
4∨ p
5∨ ¬ p
6) (p
3∨ ¬ p
4∨ ¬ p
5)(p
3∨ ¬ p
4∨ p
6)(p
3∨ ¬ p
5∨ p
6)( ¬ p
3∨ ¬ p
5∨ p
6)( ¬ p
3∨ p
5∨ p
6)
のときP
が1
となる割り当てがあ るか。あるならばその割り当てを答えなさい。問
4． P = (p
1∨¬ p
2∨¬ p
4)( ¬ p
1∨ p
2∨ p
5∨¬ p
6)(p
2∨¬ p
3∨¬ p
4)( ¬ p
2∨¬ p
4∨ p
5)(p
3∨¬ p
4∨¬ p
5)(p
3∨¬ p
5∨ p
6)
のときP
が1
となる割り当てがあるか。あるならばその割り当てを答えなさい。問
5
．P = (p
1∨ ¬ p
2∨ p
3)(p
1∨ ¬ p
2∨ p
3)(p
1)(p
1∨ ¬ p
2∨ p
3)(p
1∨ ¬ p
2∨ p
3)(p
1∨ ¬ p
2∨ p
3)
のときP
が1
と なる割り当てがあるか。あるならばその割り当てを答えなさい。1
問
6． P = (p
1∨ p
2∨ p
3∨ p
4∨ ¬ p
6)( ¬ p
1∨ ¬ p
2∨ ¬ p
5∨ p
6)(p
2∨ ¬ p
3∨ p
5)(p
2∨ ¬ p
4∨ p
5∨ p
6)
(p
3∨ p
4∨ ¬ p
6)(p
3∨ ¬ p
5∨ p
6)(p
4∨ p
5∨ 6)
のときP
が1
となる割り当てがあるか。あるならばその割り当てを答 えなさい。問
7． P = (p
1∨ ¬ p
2∨ p
3)(p
1∨ ¬ p
2∨ ¬ p
5)( ¬ p
1∨ p
3∨ p
6)( ¬ p
1∨ ¬ p
3∨ p
7)(p
1∨ p
4∨ ¬ p
7)(p
2∨ p
3∨ p
4) (p
2∨¬ p
4∨ p
6)(p
2∨¬ p
5∨ p
6)(p
3∨¬ p
4∨ p
5)( ¬ p
3∨ p
5∨¬ p
7)(p
3∨ p
6∨ p
7)(p
4∨¬ p
5∨ p
6)( ¬ p
4∨¬ p
6∨ p
7)(p
5∨¬ p
6∨ p
7)
のときP
が1
となる割り当てがあるか。あるならばその割り当てを答えなさい。問
8
． 命題P
がn
変数からなるとき、P
が1
となる割り当てを総当たりで探すとすると変数の割り当ての組 合せは何通りあるか。コメント:
n
変数からなる命題P
が与えられたときに、効率よく割り当てがあるかどうかを判定できるだろうか?
