- 538 名前：デフォルトの名無しさん [2007/08/03(金) 15:50:40 ]
- 初めまして、いきなりで申し訳ないんですが教えてください(_ _)
入力された論理式の充足可能性を判定するプログラムを作成せよ。
論理式は， 充足可能性判定の計算量を考慮し， 最大10変数までにする。
という問題です。
以下は注釈です。
「論理式」とは論理変数 x0，x1，x2，・・・に， 論理演算「¬（否定）」，「∧（論理積）」，「∨（論理和）」を有限回適用したものである。
論理式 F(x1,...,xn) が「充足可能である」とは， F(a1,...,an) = true となる変数割当て (a1,...,an)∈{true, false}n が存在することをいいます。
作成するプログラムには， 以下の機能を付加すること。
１：入力された論理式を，通常の式のように表示する機能
「x1∨x2」， 「¬x0」， 「(x2∨¬x3)∧x1」など
２：論理式が true となる（すべての）変数値割当てを表示する機能
例
「F = x1∨x2 が true になるのは
x1=true, x2=true のとき
x1=true, x2=false のとき
x1=false, x2=true のとき
よって F は充足可能である」
ちなみに入力方法はキーボードで直接入力です。
例として、
例えば， (x1∧x2)∨x3， x1∧¬x1 などはいずれも論理式です。
例えば， F1 = (x1∧x2)∨x3 とすると， x1 = true， x2 = false， x3 = true のとき F1 = true となるので， 論理式 F1 は充足可能です。 一方， F2 = x1∧¬x1 とすると， どのような x1 に対しても F2 = false となるので， F2 は充足可能ではありません。
お願いします(_ _)
|
 |
