ブール 関数。 ブール関数とは

【ブール代数】論理式の簡単化(解き方)のコツ【練習問題付き】

ブール 関数

共通部分 A AND B(紫の部分)、和集合 A OR B(色が付いている部分全体)、A XOR B(紫以外の色が付いている部分)。 四角い外枠は「普遍集合; universe」 Xを集合としたとき:• 元(element; 要素)とは、集合のメンバーを意味する。 普遍集合(universe; 全集合)とは、集合 X であり、1 で表される場合がある。 ここで universe(通常の意味は宇宙)という言葉が使われるのは「全ての元を考慮している」ことを意味しており、必ずしも「全ての元が存在する」必要があるわけではない。 単項演算子(unary operator)は1つの集合に適用される。 単項演算子としては論理 否定( )のみがある。 をとる働きがある。 二項演算子(binary operator)は2つの集合に適用される。 基本的な演算子には論理 和( )と論理 積( )がある。 これらはとをとる。 これらから導出される二項演算子として XOR(排他的OR)などもある。 例 [ ] 集合 A には普遍集合の中の全ての偶数(2の倍数)が含まれ、集合 B には同じ普遍集合の中の全ての 3 の倍数が含まれるとする。 そのとき、これらの集合の 共通部分(A AND B の集合の全ての元)は、その普遍集合の中の全ての6の倍数が含まれる。 集合 A の補集合(NOT A に含まれる全ての元)は、その普遍集合の全ての奇数となる。 演算の連鎖 [ ] たかだか2つの集合に対してブール演算を行い、その演算によって形成された新たな集合と別の集合に対して新たなブール演算を適用することができる。 上の例で言えば、普遍集合の全ての 5 の倍数を含む集合 C を新たに定義する。 ここで「集合 A AND B AND C」は、その普遍集合の全ての30の倍数を含む。 記述を単純化するため、集合 A と B の共通部分を AB と記したり、6の倍数の集合を導入したりする。 そうすると「集合 AB AND C」は、同様に全ての30の倍数を含む。 このようなステップをさらに進めていくこともでき、この演算の結果として集合 ABC を定義することもできる。 括弧の使用 [ ] 任意個の論理積 AND の連鎖には曖昧さは全くないが、AND と OR と NOT が組み合わされると曖昧な場合が出てくる。 そのような場合に演算の順序を明確化するために括弧を使うこともある。 通常、最も内側の括弧内の演算が最初に実行され、順次外側に移っていく。 ブール代数とブール論理では以下のような法則が成り立つ。 複数の入力や他のブール演算を使った、もっと複雑な真理値表も作成できる。 記号 [ ] ブール論理の表記に使われる記号は、目的や学術分野、あるいは文化圏などによってさまざまである。 まず、英単語にもとづく AND、OR、NOT といった一群がある。 NOT は式の上に線を引いて表すこともある。 これらの記号はでの演算子として使われていることが多い。 NOT は! ()で表されることが多く、! 自然言語でのブール論理 [ ] (ブール論理に限った話ではないが)論理式をそのまま自然言語にすると、しばしば、同じ言葉の日常での意味と異なっていたり、曖昧だったりすることがあるため注意が必要である。 日本語の場合の例をいくつか挙げる。 自然言語の「朝食にはパンか御飯を食べることができる」の「パンか御飯」は、そのまま解釈すればORだが、普通はすなわち「パンか御飯のどちらかを選ぶことができる」の意味であることが多い。 曖昧な例としては「全ての輝くものが金ではない」という文は「輝くものは全て金ではない」(全否定)とも「輝くものには金でないものもある」(部分否定)とも解釈できる。 「」を参照 CG業界用語でその名も「」と呼ばれているものであるが、立体などの図形を集合としてとらえる数学的な手法をそのまま工学的に応用したもので、かつそのまま具体化される点で、直観的にわかりやすい応用のひとつである。 ディジタル回路設計 [ ] ブール論理はの設計にも使われる。 その場合、0 と 1 はでのの異なる2つの状態を表し、の高低に対応させることが、現代では多い(必ずしもそうしなければならないわけではない)。 回路は変数を含む式で表され、変数が回路の入力、式を評価した結果が回路の出力に相当する。 入力と出力の対応が完全に与えられれば、それをブール論理の式で表現することができる。 、ORゲート、NOTゲートのような基本だけを使うこともできるが、、ゲート、ゲートなども組み合わせてディジタル回路を構成することができる(なお、のごく初歩的な知識があれば、ANDやORよりNANDやNORのほうが基本的である、というのは常識だが)。 組み合わせ方は、に従ってに結合する(翻訳元にそうあったものと思われるが、何を言っているのかわからない。 回路は接続されている通りに動作するのであって、優先順位などというものは記法上の便宜的なものに過ぎない)。 データベース [ ] 等によるデータベースの操作は、各データベースを集合、クエリ結果などを部分集合、データベースに含まれる個々のデータを集合の要素とみなすと、ある種、集合の操作のようなものとみなすことができる。 特には、データベースの操作が集合代数にもとづき整理・定義されているデータベースである( )。 以下では、関係データベースの代表的なクエリ言語であるSQLの具体例を示す。 文の例を示す。 複数の表をブール演算で組み合わせることを 結合と呼ぶ。 検索エンジン [ ] に代表される、検索を行なうネットサービスでも、ブール演算にもとづく検索式が使えるものがある。 例として、検索のものを示す。 論理積には記号を使用しない。 従って、キーワードを2つ並べた場合、論理積と解釈される。 "キーワード1" "キーワード2"• 論理和には "OR" を使用する。 "キーワード1" OR "キーワード2"• マイナス記号で論理否定を表す(実際にはAND NOT)。 "キーワード1" -"キーワード2" カッコは使えない。 (面白いことに、では "OR" を使うと排他的論理和 XOR の操作が行われる) 関連項目 [ ]• (記号論理学)• 外部リンク [ ]• , by , Cambridge and Dublin Mathematical Journal Vol. III 1848 , pp. 183-98. for Windows , 論理式の取りうる値を全て計算するソフトウェア•

次の

真理値表を分かりやすく解説!

ブール 関数

真偽値 Boolean、bool を返す関数は、is で始めるのが一般的かと思います。 ただし、英語的に、is 始まりが難しい場合もあります。 is で始められない関数名の名付け方を考えました。 以下の内容は、そのルールを破ってまで適用すべきものではありません。 今回は英語的な正しさを重要視していますが、どんな場合も英語的な正しさを優先すべきとは限りません。 他の人が書いた関数名に合わせたり、関数の関係性を重要視する場合は英語的な正しさを二の次にすることは正しい判断になると思います。 存在するか? 一番やりがちな失敗が「存在するか?」を is で始めようとするパターンです。 気持ちは分かります。 真偽値を返す関数が is で始まるのは気持ち良いですからね。 しかし、「存在するか?」という関数はどうしても is で始められないと思うのです。 isExist という表現を見かけることが多いですが、個人的には使いません。 exist は動詞なので is と組み合わせることは英語的に有り得ません。 ただし、英語的な正しさよりも、真偽値がisで始まることが重要だと考える場合は、間違った名前ではないと思います。 十分意味も伝わります。 isExistence だと「存在するか?」というより「存在か?」という感じで、意味が分かりません。 isExisted もダメです。 exist は自動詞なので、英語的に有り得ません。 過去形になってしまっているので、分かりやすさという意味では isExist の方がマシです。 isExisting や isExistent は微妙なところですが、やっぱりおかしい気がします。 私は以前、「真偽値を返す関数名は is で始めないと死んでしまう病」という奇病にかかっていたため、 isExisting を使っていました。 今となっては黒歴史です。 ということで、exist に関しては is で始めるのを諦めましょう。 無理です。 ではどんな表現にすべきかといいますと・・・ exists です。 世の中の API がこの表現を使っています。 PHP では boolean exists みんな exists を使ってます。 納得できようができまいが、 exists なのです。 ソフトウェアの世界では、Apple と Microsoft と Google が黒と言ったら黒です。 黙って従いましょう。 このように、関数名の表現に困ったら、世の中の API を参考にすると良いです。 非ネイティブの我々では思いつかないような的確な表現が見つかることもあります。 関数の名付け方 真偽値を返す関数は if 文で使われることが多いので、頭に if を置いて最もしっくり来る表現が良いと思います。 個人的には、真偽値を返す関数名を考えるときは以下のフォーマットに当てはめるようにしています。 if オブジェクト名 関数名 「項目が選択中だったら」なら "if item is selected" なので関数名は item. isSelected となります。 同様に「項目が存在したら」なら "if item exists" なので item. exists となります。 「リストに項目が含まれていたら」なら "if list contains item" なので list. contains item または list. containsItem item となりますし、 「リストの項目を削除できるなら」なら "if list can remove item" なので list. canRemove item または list. canRemoveItem item となります。 最後の例はちょっと怪しいですが、こんな感じで関数名を考えています。 こうすると、関数名が exist ではなく exists になっていることも納得できます。 isEnabled は一般的な関数名ですが "if is enabled" は英語的に変です。 "if this is enabled" なら違和感はありません。 また、Item クラスで isItemEnabled という関数名にすると "if this Item is item enabled" という違和感のある英語になってしまい、関数名が不適切だということが分かると思います。 もちろん、このフォーマットが当てはまらないケースも 多々あります。 例えば、Item クラスのメンバ変数に name という文字列があり、その文字列が空かどうか判断する場合は isNameEmpty という名前を付けると思います。 フォーマットに当てはめると "if this is name empty" となり、おかしいです。 this を省略しても "if is name empty" となり、これもおかしいです。 それでも、関数名は isNameEmpty が一般的だと思います。 それだと "if this has empty name" になるのでフォーマットにも当てはまります。 is で始まらない表現 is 以外で始める場合は、動詞か助動詞を使いましょう。 それ以外の品詞で始まるのは変です。 動詞始まりで真偽値を返す表現の例:• exists 存在するか• contains 含まれているか• has 持っているか• needs 必要か 助動詞始まりで真偽値を返す表現の例:• can できるか• should すべきか• canRemoveItem item• canUpdate• canStartTimer timer しかし、英語的には can は is 〜able に置き換えることもできます たぶん。 isItemRemovable item• isUpdatable• isTimerStartable timer 「真偽値を返す関数名は is で始めないと死んでしまう病」の方は、こういう表現を使うという手もあります。 私も一時期、この表現を使っていました。 しかし、目的語は関数の最後にあった方が気持ちがいいので、個人的には isUpdatable 以外は can の方の表現を使いたいです。 あと、〜able は造語になってしまうので、辞書に載ってない英単語になることもあります。 英語が得意な人なら意味を理解できるかもしれませんが、英語が苦手な日本人にとっては理解が難しくなります。 is以外のbe動詞を使いたい場合 「全てのアイテムが削除済みかどうか」を確認する関数を作成した場合、どんな名前にすべきでしょうか? 深く考えずにパッと思いつくのは以下の2つです。 isAllItemsRemoved• isで始まっており真偽値を返す関数名としては気持ちいいですが、名詞が複数形なので英語的には間違っています。 areAllItemsRemoved• 英語的に正しいですが、areで始まることに違和感があります。 「関数名的に気持ち良い表現を優先するか」「英語的に正しい表現を優先するか」ということに関しては意見が分かれると思います。 私個人としては、英語的な正しさを優先するので、上記2つのどちらかを選ぶとすれば are の方です。 ただ実際には、「全アイテムが削除済みかどうか」を関数にする場合、上記2つではなく以下の関数名にすると思います。 isEveryItemRemoved• 細かいことを言えば、all と every は英語的にニュアンスが違うとは思いますが、is始まりだし、英語的にも正しいので分かりやすいです。 ただし、Every が「全ての」という意味だということは、All ほど認知されていないような気もします。 itemExists• 「存在するか」に表現を変えることで、気持ちいい関数名にします。 こんな感じで、関数名に迷ったら別の表現を検討するのも良い手だと思います。 is vs are の議論は以下でも行われています。 真偽値を設定する関数 今までは真偽値を返す関数 以下、getter のことを書いてきましたが、最後に真偽値を設定する関数 以下、setter についても書いておきます。 基本的に is を set に変えるだけです。 getter が isSelected なら、setter は setSelected とします。 必ず isXXX と setXXX がペアになるようにしましょう。 その方が分かりやすいです。 is で始まらない場合は、頭に set を付けます。 canRemove なら setCanRemove とします。 exists なら setExists とします。 英語的にはおかしい表現になりますが、英語の正確さよりも関数の関係性の分かりやすさを優先します。 この辺のルールは Apple の Naming Guidelines を参考にしています。 というか、私が関数や変数の名前を真面目に考えるようになったのが、iOSアプリ開発に携わるようになってからなので、私のネーミング思想は Apple の影響が強いです。 ということで、Apple の Naming Guidelines オススメです! Objective-C なので注意.

次の

ブール論理

ブール 関数

実質上位互換な記事を書いてしまったのでこちらをどうぞ「」 本記事は「」10日目の記事です.前後の記事は以下の通りです.• 9日目: 氏による「」• 11日目: 氏による「」です. えー、割と良くない体調の中で書いたので色々と多めにみていただきたく… あ,図も書いてないですね…手元にいい感じに図を描けるものが無いので後日…とりあえず Wikipedia で代用… はじめに 本記事で扱うトピックは Binary Decision Diagram BDD ,および Zero-suppressed Binary Decision Diagram ZDD というデータ構造です.これらはそれぞれ,計算機科学でしばしば議論されている ブール関数,および 集合族を効率良く扱うことができるデータ構造です.具体的には,• 圧縮: ブール関数の主加法標準形,および集合族のリスト表現の長さよりも真に大きくはならず,指数的に小さくなる事例が多い 実メモリ的には定数倍を除いて考えています .• クエリ応答: メンバーシップクエリ,要素数のカウント,ランダムサンプリング,ある種の確率に関する数値計算,ある種の目的関数に対する最適解探索,etc... を高速に処理できる.• 演算: ブール関数,および集合族に関する様々な二項演算 三項以上の演算もあり を圧縮されたデータ構造上で計算する.これらの演算を総称して Apply 演算と呼ぶ. などの性質,機能を備えたリッチなデータ構造となっています. BDD はブール関数を圧縮処理することに特化しています.Bryant による効率的なアルゴリズム 圧縮技法,Apply 演算 の発見 [文献 1,1986] を期に大きく発展してきました.応用としては VLSI 設計,制約充足問題,システムの故障解析などが挙げられます.本記事では,構造の説明と BDD 上での Apply 演算の紹介,確率計算に関する解説をします. ZDD は BDD の派生系で集合族を圧縮処理することに特化しています.湊により考案され [文献 2,1993] , BDD の改良技術として注目を浴びています.特に,Knuth の著書 The Art of Computer Programming に,1つの章として取り上げられています.略記はもともと ZBDD だったらしいのですが,考案者が Knuth に ZDD の方が良いよと言われて以降,ほとんどの場合で ZDD と略されているようです.VLSI 設計,組合せ問題,データマイニングの分野などに応用があります.本記事では,構造の説明と ZDD 上での Apply 演算の紹介,組合せ最適化に関する解説をします. 準備 準備をしっかり書こうかなとも思いましたが,そんなに必要ない気がしたので簡潔に書きます.• Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, C-35 8 :677—691, 1986. Shin-ichi Minato. "Zero Suppressed BDDs for Set Manipulation in Combinatorial Problems", 1993. Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura and Shin-ichi Minato. "Counterexamples to the long-standing conjecture on the complexity of BDD binary operations", Information Processing Letters, 2012.

次の