練習問題

練習問題
問１
• ３この論理式を要素とする集合Mがある。
いま、Mのどの２つの要素をとっても、それ
らのモデルが存在するが、３つすべてに対
するモデルは存在しないという。Mの例を
１つ作れ。
問２
• 次の節集合で表される論理式は充足可能
か？（モデルは存在するか？）
M={{A1,A2}, {~A2,~A3}, {A3,A4},
{~A4,~A5}, {A5,A6},
…}
問３
•
次の式の真理値表を作成せよ。
1. ((A∧B)∧(~B∨C))
2. ~(~A∨~(~B∨~A))
3. (A↔(B↔C))
問４
• 次の関係が成り立つことを示せ。
((A∨(B∨C))∧(C∧~A))
=
((B∧~A)∨C)
問５
• 次の真理値表で与え
られる論理式Ｆを
– Conjunctive normal
formで
– Disjunctive normal
form で
書きなさい。
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
1
0
0
0
1
1
0
0
問6
• 次の式を
– Conjunctive normal formで
– Disjunctive normal form で
書きなさい。
F = ((~A→B)∧((A∧~C) ↔B))
問７
• F=(~B∧~C∧D)∨(~B∧~D)∨(C∧D)∨B
がトートロジー（恒真式）であることを示せ。
問
• 次の演繹定理を証明せよ。
 |    iff   {} |  ,
where  is a set of formulas
and  is a formula.
問
• 論理式   xP(x), 論理式   P(a) とする。
1.  は  のskolem standard formである
ことを示せ。
2. 次のような解釈を考えるとき、この２つの
論理式は等価でないことを示せ。
 D  { 1, 2 }

a  2
 I  {P (1)}

問

Download Report