論理式( a && b ) ( とaは両方ともbブール値を持ちます) は、たとえば のように記述できます!(!a || !b)。 これは、 が「不要」であることを意味しているのではないですか。これは、すべての論理式が と のみを使用して作成できる&&ことを意味しますか。||!
ベストアンサー1
はい、他の回答者が指摘したように、およびからなる演算子の集合||は!機能的に完全以下は、その構成的証明であり、ブール変数と間の 16 個の可能な論理接続詞すべてをこれらを使用して表現する方法を示していAますB。
- 真実:
A || !A - NANDB:
!A || !B - BはAを意味する:
!B || A - AはBを意味する:
!A || B - A または B:
A || B - Bではない:
!B - ではない:
!A - A 排他的論理和 B:
!(!A || B) || !(A || !B) - A XNOR B:
!(!A || !B) || !(A || B) - あ:
A - B:
B - A または B:
!(A || B) - AはBを意味しない:
!(!A || B) - BはAを意味しない:
!(!B || A) - AとB:
!(!A || !B) - 間違い:
!(A || !A)
NAND と NOR はどちらもそれ自体が機能的に完全であることに注意してください (これは上記と同じ方法を使用して証明できます)。したがって、演算子のセットが機能的に完全であることを確認する場合は、NAND または NOR のいずれかをそれを使用して表現できることを示すだけで十分です。
これはグラフで示したものですベン図上記の各接続詞について:
[ソース]
