入力は (任意の) チェックされた構文を持つ記号の文字列で、出力は TRUE または FALSE です。
AND、XOR、TRUEで書かれた論理式を後置表現しようと考えていたのですが、後置ではパターンが認識しづらくなることにようやく気が付きました。
例:
p IMPLIES qと書くことができるTRUE XOR p (XOR (p AND q))省略形 1+p+pq
p EQUIVALENT WITH qは 1+p+q と省略して書くことができます
NOT p省略形 1+p
p または q p+q+pq の省略形
このブール環の規則は通常の代数と同じで、次の 2 つの規則があります。
- p+p=0
- pp=p
これらのルールは、交換とともに、すべての削減を担当し、文字列がトートロジーに対応する場合は '1' になります。トートロジー Modus ponens、
((p IMPLIES q) AND p) IMPLIES q ,
は、最初に上記のように代入し、次に分配的に乗算して拡張し、最後に繰り返し単純化する必要があります。IMPLIES を単純に置き換えると、次のようになります。
1+((1+f+fg)f)+((1+f+fg)f)g =
= 1+ f+ff+fgf +(f+ff+fgf)g =
= 1+ f+f+fg + fg+fg+fg =
= 1+ fg +fg+fg+fg = 1
トートロジー式がブール環の要素として記述されると、機械的に 1 に還元されます。他の式は、代数的に単純な式に還元されます。
これは良い戦略ですか？コンピュータサイエンスではどのような戦略が使用されていますか?