リファクタリングブール式

Question

のは、あなたがそう

(A OR B) AND (D OR E) AND F 

あなたはとても

A AND D AND F 
A AND E AND F 
B AND D AND F 
B AND E AND F 

あなただけあるように、できるだけ多くのだけの表現に変換したいのようなブールルール/表現があるとしましょうORを減らすようにする

(A AND D AND F) OR (A AND E AND F) OR (...) 

これを行うブール代数にはプロパティがありますか？

Answer 1

hereを示すように、あなたの例では、ORのANDを超える分配性を悪用しています。

これを順番に適用するだけで済みます。たとえば、（*とを示し、+ ORを表す）x*(y+z) = (x*y)+(x*z)を使用して：

0. (A + B) * (D + E) * F 
1. Apply to the first 2 brackets results in ((A+B)*D)+((A+B)*E) 
2. Apply to content of each bracket results in (A*D+B*D)+(A*E+B*E) 
3. So now you have ((A*D+B*D)+(A*E+B*E))*F 
4. Applying the law again results in (A*D+B*D)*F+(A*E+B*E)*F 
5. Apply one more time results in A*D*F+B*D*F+A*E*F+B*E*F, QED 

Answer 2

DeMorgan's定理を見てください。このリンクは電子ゲートに関する文書を指すが、理論は同じままである。

それはそれらの相補体に我々

1. 変更のすべての変数あれば任意の論理のバイナリ表現が変わらないことを言います。
2. すべてのAND演算をORに変更します。
3. すべてのOR演算をANDに変更します。
4. 全体の表現を補完してください。私の知る限り、ブール代数は、ANDとOR演算のみで構築することはできません知っているよう
（上記リンク先のドキュメントから引用）

Answer 3

。 この2つの操作だけがある場合、NOT操作を受信することはできません。

任意の式をフルセットのブール演算に変換できます。ここで

は、いくつかの完全なセットです：あなたは、NOT演算を使用することができると仮定すると、

• ANDとNOT
• ORとNOT

Answer 4

、あなただけの論理積を持つ任意のブール式を書き換えることができますかのみOR。あなたのケースでは：

(A OR B) AND (D OR E) AND F 

私は上記の書き込みのためのエンジニアリング速記を使用する傾向がある：

• と製品として、（または何も。）
• または（+）としてのOR;
• 一重引用符（ '）ではありません。

ので：算術に

(A+B)(D+E)F 

当然の結果は、実際に条件を因数分解のために非常に便利です。De Morgan's Lawことで

：

(A+B) => (A'B')' 

ですから、としてあなたの表現を書き換えることができます。

(A+B)(D+E)F 
(A'B')'(D'E')'F 

Answer 5

あなたはおよそKarnaugh mapsを読んで興味があるかもしれません。ブール式を簡略化するためのツールですが、それらを使って個々の式をすべて判別することもできます。私はどのようにあなたがプログラムを書くことができるアルゴリズムにこれを一般化するかもしれないか分からない。

Answer 6

Conjunctive Normal formまたはその弟Disjunctive normal formに興味があります。