ブール関数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/13 16:28 UTC 版)
効率的表現
(命題論理の)論理式で表現できるが、効率的な表現としては次のようなものがある。
- 二分決定図 (BDD)
- 否定標準形
- Propositional Directed Acyclic Graph (PDAG)
簡単化
簡単な表現に変換する手法として次のようなものがある。
- カット・アンド・トライ法
- ブール代数の定義を用い、効率的な表現に変形していく。
- ベン図
- ベン図を用いて視覚的にわかりやすい表現にする。
以上は人間の直感によるものであり「変換する手法」と言えたものではない。
- カルノー図法
- カルノー図を用い、効率的な表現に変形していく。
- クワイン・マクラスキー法
- クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。
標準形
選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。
リード-マラー標準形
リード-マラー標準形(en:Algebraic normal form)は、積(AND)の排他的論理和(XOR)による標準形である。
ここで である。
従って、列 の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの(AND)項に現われる の個数で表される。つまり、 の次数は 1(線形)であり、 の次数は 3(立方)である。
関連項目
|
|
|
- 1 ブール関数とは
- 2 ブール関数の概要
- 3 効率的表現
- ブール関数のページへのリンク