論理演算結果の表示について

質問

Ｃで論理演算をするプログラムを考えているのですが、少し行き詰ってしまいました。

例えば(A+B)*(A+B+C)を論理演算で考えた場合、答えはA+Bとなりますがどうすればこの結果を画面に表示させる事ができるのかが分からないのです。

ただ単に
#include <stdio.h>
int main(void)
{ int a,b,c,y ;
a = 'A';
b = 'B';
c = 'C';
y = a|b & a|b|c;
printf("%c\n",y);
}
としたら表示結果は「Ｃ」となってしまいますよね（文字を2進で計算しているからこの結果になるという事は理解しています）。
もしかしてif文を使用して総当り的に文字を調べていくしか方法がないのでしょうか？実際はもっと複雑な演算をプログラムに計算してもらいたいと考えているので、他に方法がないか考えているのですが…
どうかよろしくお願い致します。

回答No.8

venzou · ベストアンサー

(A|B)&(A|B|C)&(B|D)&(B|C|D)&(B|E)&(C|D)&(E|F)
これが、主乗法標準系で、

(B&C&E)|(A&D&E)|(B&D&E)|(B&C&F)|(B&D&F)
こっちが、主加法標準系でしょうか？

＃６のプログラムは、主乗法標準系で表された数式を、主加法標準系に変換するプログラムとなるのかな。

＃６のプログラムを更に改良し、標準入力から数式を入力できるようにしました。
例：(A|B)&(A|B|C)&(B|D)&(B|C|D)&(B|E)&(C|D)&(E|F)
構文解析はいい加減なので、上の例のような形式の数式以外の動作は保障しません。（＾＾；

#include <stdio.h>
#define BUFSIZE_STR 1024 //バッファ(適当なサイズ)
#define BUFSIZE_EXP 1024 //バッファ(適当なサイズ)
#define BUFSIZE_ANS 1024 //バッファ(適当なサイズ)
char str[BUFSIZE_STR]; //入力された数式を格納
long exp[BUFSIZE_EXP]; //ビット配列化した数式を格納
long ans[BUFSIZE_ANS]; //ビット配列化した答えを格納
int expCount = 0; //ビット配列化した数式の数
int ansCount = 0; //ビット配列化した答えの数
int maxAlpha = 0; //使用されているアルファベットの最大

void getExp(void);
int checkExp(long x);
int addAnswer(long x);
void printAnswer(void);

void main(void)
{
long x;
getExp();
for(x = 1; x < (1<<maxAlpha); x++) if(checkExp(x)) if(addAnswer(x)) return;
printAnswer();
}

//標準入力から数式を入力しビット配列化する
void getExp(void)
{
int i, j, flg;
char *c;
puts("数式を入力して下さい　例 (A|B)&(A|C)");
fgets(str,BUFSIZE_STR,stdin);
for(c = str, flg = 0; *c != '\0'; c++){
if(!flg) exp[expCount] = 0;
if(*c == '&' && flg){
expCount++;
flg = 0;
}else if('A' <= *c && *c <= 'Z'){
if((*c - 'A' + 1) > maxAlpha) maxAlpha = *c - 'A' + 1;
exp[expCount] |= (1 << (int)(*c - 'A'));
flg = 1;
}
}
if(flg) expCount++;
}

//数式を評価する
int checkExp(long x)
{
int i;
for(i = 0; i < expCount; i++) if(!(exp[i] & x)) return 0;
return 1;
}

//吸収則で不要な答えを排除しながら、答えを登録
int addAnswer(long x)
{
int i;
for(i = 0; i < ansCount; i++){
if((ans[i] & x) == ans[i]) return 0; //吸収則により排除
if((ans[i] & x) == x){ ans[i] = x; return 0; } //吸収則により排除
}
//答えの登録
ans[ansCount++] = x;
if(ansCount >= BUFSIZE_ANS){ puts("バッファが足りません。"); return -1; }
return 0;
}

//ビット配列化されている答えを、アルファベットで表示
void printAnswer(void)
{
int i, j, flg;
for(j = 0; j < ansCount; j++){
putchar('(');
for(i = 0, flg = 0; i < maxAlpha; i++){
if(ans[j] & (1 << i)){
if(flg) putchar('&');
putchar('A'+i);
flg = 1;
}
}
putchar(')');
if(j < ansCount -1) putchar('|');
}
putchar('\n');
}

実際書いてみると、意外と短いプログラムになりました。

お礼

回答ありがとうございます！
言われてみて気づいたのですが、私が組みたいと思っているのは将に乗法標準系→加法標準系に直すプログラムです。
記載していただいたプログラムを使用して、いろいろシミュレーションを行ってみた所ちゃんと期待する答えが出てきました！
まだプログラムに慣れていない事もあるので、どこでどんな動作をしているかは今の所理解できてませんがこれから一つ一つ解決していきたいと思います。
（やっと見通しがつきました、本当にありがとうございます！）

回答No.9

a-saitoh

結局何をしたいのでしょうか?
論理式の簡単化をするプログラムがほしいのか、論理式を入力して値を計算するプログラムがほしいのか、あるいはそれいがいなのか。

簡単化は面倒です。値を計算するのは簡単です。コンパイラの作り方といった本の「式の評価」という章を読めばいいです。

お礼

回答ありがとうございます！
下で紹介していただいたようなプログラムを望んでいたので「論理式の簡単化」を目指している事になると思います。
望んでいた結果が得られそうなので、とりあえず見通しがたちました！

回答No.7

jacta

#6の回答のように、主加法標準系または主乗法標準系で結果を表現するのであれば、何とかなりそうですね。パラメータの個数を可変にするのがちょっと面倒そうですが。

論理圧縮まで考えるのであれば、アルゴリズムに相当知恵を絞るか、どこかから引っ張ってくる必要があるそうです。ただ、この手のアルゴリズムで既存のものは、すぐに特許を踏みそうで結構冷や冷やものですよ。

お礼

回答ありがとうございます！
よくよく考えてみると「乗法標準形→加法標準形で結果を表示したい」という事でした。これでかなり限定されていますね。
とりあえず今の所は本格的な論理圧縮までは必要なさそうなので、このあたりで留めておきたいと思います。
こういったアルゴリズムでも特許が絡んでくるんですね。

回答No.6

venzou

(A|B)&(A|B|C)&(B|D)&(B|C|D)&(B|E)&(C|D)&(E|F)

試しに、これを解くプログラムを作ってみました。

(B&C&E)|(A&D&E)|(B&D&E)|(B&C&F)|(B&D&F)

答えはこうなりました。あってるでしょうか？（＾＾；
プログラムは再起呼び出しによる総当りでチェックしています。

#include <stdio.h>
//答えを格納するバッファ
#define BUFSIZE 1024
//使用するアルファベットの数
#define MAX 6
#define A a[0]
#define B a[1]
#define C a[2]
#define D a[3]
#define E a[4]
#define F a[5]

long a[MAX]; //総当り用
long ans[BUFSIZE]; //答えを格納
int ansCount; //答えの数

void check(int dep);
void addAnswer(void);
void printAnswer(void);

int main(void)
{
int i;
ansCount = 0;
check(MAX-1);
printAnswer();
}

//再起呼び出しで、総当りチェック
void check(int dep)
{
long y;
if(dep < 0){
//ここに数式を記述してください。
y = (A|B)&(A|B|C)&(B|D)&(B|C|D)&(B|E)&(C|D)&(E|F);
if(y) addAnswer();
return;
}
a[dep] = 0;
check(dep - 1);
a[dep] = 1;
check(dep - 1);
}

//吸収則で不要な答えを排除しながら、答えを登録
void addAnswer(void)
{
long x, bit;
int i;
//答えをビット列に変換する
for(i = 0, bit = 1, x = 0; i < MAX; i++, bit <<= 1){
if(a[i]) x |= bit;
}
for(i = 0; i < ansCount; i++){
if((ans[i] & x) == ans[i]) return; //吸収則により排除
if((ans[i] & x) == x){
ans[i] = x;
return; //吸収則により排除
}
}
//答えの登録
if(x) ans[ansCount++] = x;
if(ansCount >= BUFSIZE){
puts("バッファが足りません。\n");
ansCount = 0;
}
}

//ビット列で保存されている答えを、アルファベットで表示
void printAnswer(void)
{
long bit;
int i, j, flg;
for(j = 0; j < ansCount; j++){
putchar('(');
for(i = 0, bit = 1, flg = 0; i < MAX; i++, bit <<= 1){
if(ans[j] & bit){
if(flg) putchar('&');
putchar('A'+i);
flg = 1;
}
}
putchar(')');
if(j < ansCount -1) putchar('|');
}
putchar('\n');
}

回答No.5

venzou

＃２～４ですが、集合の演算になってました。失礼しました。

論理演算だと(A|B)&(A|C) の答えは A|(B&C) ですか？
これを求めるのはかなり面倒ですね。

お礼

再び回答ありがとうございます！

やはり面倒になってきますか…
ややこしくなるので書いていませんでしたが、実際に私が演算したいのは
(A|B)&(A|B|C)&(B|D)&(B|C|D)&(B|E)&(C|D)&…&(E|F)＝？
or結合された項をすべてand結合した式を演算して、その答えを表示してくれるプログラムを目指しています（各項の文字は別のプログラムから求められるものとしてます）。
とても手計算ではやっていられないし、いずれ必要になってきそうなプログラムなので取り掛かったのですが…詰まってしまいました。
これらの論理演算を解く方法がどこかで話題に挙がっていないかなぁと思い検索かけてみましたが、全然見当たりませんでした。少しくらいは話題に挙がっていてもいいような気がするのですが…

回答No.4

venzou

>y = (A|B)&(A|C)　も起こり得るという事を想定しています。
これの答えは A と出ましたが、間違ってますか？

>上記方法だとごく限られた演算のみになってしまうような気がします。
確かに、そんな気もします。（＾＾；

>汎用性のあるプログラムになるのでしょうか？
数式をプログラム中に埋め込むのではなく、数式を入力して答えを求めるプログラムにしたいって事でしょうか？

回答No.3

venzou

>実際はもっと複雑な演算をプログラムに計算してもらいたいと考えているので、他に方法がないか考えているのですが…

#include <stdio.h>
#define MAX 26
#define A a[0]
#define B a[1]
#define C a[2]
//中略
#define Z a[25]

int main(void)
{
long a[MAX],y,bit;
int i;
for(bit = 1,i = 0; i < MAX; i++, bit<<=1) a[i] = bit;

y = (A|B)&(A|B|C);

for(i = 0; i < MAX; i++) if(y&a[i]) putchar('A'+i);
putchar('\n');
}

A-Zの26文字対応版
基本的には＃２と同じですが、配列を使っています。

お礼

ありがとうございます。

下でも述べさせていただいたのですが、今組みたいと考えているプログラムではy = (A|B)&(A|C)　も起こり得るという事を想定しています。
もしかしたら提案していただいた方法を応用さえすれば、汎用性のあるプログラムになるのでしょうか？

回答No.2

venzou

#include <stdio.h>
int main(void)
{ int a,b,c,y ;
a = 1; // 2進数で 0001
b = 2; // 2進数で 0010
c = 4; // 2進数で 0100
y = (a|b)&(a|b|c);
if(y&a) putchar('A');
if(y&b) putchar('B');
if(y&c) putchar('C');
putchar('\n');
}

y の計算の括弧は必要です。

こんな感じでどうでしょう。

お礼

ありがとうございます。

上ではy=(a|b)&(a|b|c)を例に挙げましたが、他にもy=(a|b)&(a|c)といった論理演算にも対応したプログラムを書きたいと思っています。
せっかく提案していただいたのですが、上記方法だとごく限られた演算のみになってしまうような気がします。
（提案していただいた方法すらも思いつかなかった自分が生意気言ってすみません）

回答No.1

jacta

C言語の演算子は、数値の演算子か行うことができません。質問者さんは数式の処理を行おうとしているので、これを直接記述することはできないわけです。

たとえば、論理演算と考えると難しいのであれば、普通の算術演算を考えてみましょう。

(A + B)*2

は 2*A + 2*B になりますが、同じようにやっても期待した結果は得られませんよね。それと同じことです。
これを解決するためには、数式を展開するための処理を別途作成する必要があります。総当たり的になる必要はありませんが、ちょっと面倒です。

お礼

ありがとうございます。

>数式を展開するための処理を別途作成する必要があります。総当たり的になる必要はありませんが、ちょっと面倒です。
展開する処理が必要になってくるわけですね。if文を使い各項に含まれる文字を順次調べていくのかなぁと考えていますが…まだあまりプログラムに慣れていない自分にとってはちょっと難しそうですね。