計算システム論第一のバックアップ(No.1) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

講義日程-2007年度冬学期

計算システム論

論理関数
- $2 = {0,1}$
  $n$ 変数論理関数、 $f:2^n\to2$ ブール関数・スイッチング関数とも呼ばれる。
  表現形式としては、論理式・真理値表・キューブ表現・BDDがある。
  定義域の $2^n$ 全てについて値が定義されているものを、完全定義関数。
  値が未定義の組み合わせがあり、「渡してはいけない値」があるものを、不完全定義関数と呼ぶ。
- 論理式の表現には真理値表が最も簡単。
  ROMの入力値に対応する論理値を書き込んで
  真理値表を作れば、簡単に論理回路を作れる。
  ただし、入力変数が増えると表の行数が急激に増える。
- 論理式による表現。
  論理関数は必ず論理式で書けるか？Yes.
  - ブール展開
    $F(x,y,z) = x F(1,y,z)+\lnotx F(0,y,z)$ と展開すれば、２変数論理関数２つに分解できる。
    同様に展開を進めると、引数の積と否定からなる項の和からなる形の論理式として、この論理関数を表現できる。
    ある項を真にする論理変数の組み合わせが唯一であるとき、その項は極小項と呼ばれる。
    全ての論理変数の積を取ったものと、そのうちいくつかの論理変数を否定したものが極小項。
    極小項の和で書かれた論理式は、真理値表と一対一対応。