集合と論理演算

ITパスポート 無料テキスト 単元24／第7章　基礎理論とアルゴリズム／テクノロジ系／重要度 ★★★／出題箇所 テクノロジ系／読む目安 35分　登録不要で読めます

集合とベン図の基本

仕事でデータベースやネット検索を使うとき、「条件に合うものだけを絞り込む」場面がよくあります。この絞り込みの考え方を整理したものが集合です。集合とは、ある条件を満たすものの集まりのことで、例えば「東京都に住んでいる人」や「テストで80点以上を取った人」のように、条件を満たす要素をひとまとめにしたものを指します。集合どうしの関係を円を使って視覚的に表す図がベン図です。

集合には基本の演算が3つあり、検索条件でよく混同されるのでここで整理します。和集合(A∪B)は、AとBの少なくとも一方に含まれる要素の集まりで、日本語では「AまたはB」にあたります。積集合(A∩B)は、AとBの両方に共通して含まれる要素の集まりで、「AかつB」にあたります。違いは「どちらか一方でよいか、両方とも満たす必要があるか」です。例えば「東京都に住んでいる、または大阪府に住んでいる人」を探すには和集合、「東京都に住んでいて、かつ20代である人」を探すには積集合の考え方を使います。

もう一つ、補集合は全体の中である集合Aに含まれない要素の集まりで、「Aでないもの」を表します。ベン図ではAの円の外側すべてが補集合にあたり、和集合はAとBの円を合わせた範囲、積集合はAとBの円が重なる部分にあたります。

集合の考え方は、命題(正しいか正しくないかがはっきり決まる主張)を整理するときにも使われます。「Aである」という命題と「Aでない」という命題は、補集合の関係にあります。実務では、この考え方を使って会員データベースから条件を絞り込みます。例えば「都内在住(集合A)かつ20代(集合B)」という条件で顧客を抽出するとき、AとBの積集合に入る顧客だけが結果に表示されます。逆に「都内在住(集合A)ではない顧客」を除外したいときは、Aの補集合を使って絞り込みます。ベン図を頭の中でイメージしながら条件を組み立てると、複雑な検索条件でも整理しやすくなります。

人数を求める計算問題でも、集合の考え方が役立ちます。例えば「40人のクラスで、野球が好きな人が25人、サッカーが好きな人が20人、両方好きな人が15人いるとき、どちらも好きでない人は何人か」を考えてみましょう。野球またはサッカーが好きな人数(和集合)は、25+20-15=30人です。両方好きな15人を重複して数えないよう、積集合の15人を1回分だけ引くのがポイントです。クラス全体40人からこの30人を引くと、どちらも好きでない人は40-30=10人と求められます。このように、和集合の人数を求めるときは重複分を引き算する、という手順を覚えておきましょう。

論理演算(AND・OR・NOT・XOR)

集合の考え方は、プログラムの条件分岐(if文)や検索エンジンの検索条件に、そのまま応用されています。コンピュータがこうした条件を判断する仕組みを論理演算と呼び、条件が成り立つ状態を「真(true、1)」、成り立たない状態を「偽(false、0)」として扱います。

論理演算の基本はAND(論理積)とOR(論理和)で、日本語の感覚だけで判断すると混同しやすいので整理します。AND演算は二つの条件が両方とも真のときにだけ結果が真になり、「AかつB」に対応します。例えば「気温が25度以上」かつ「湿度が70%以上」を両方満たしたときだけ「蒸し暑い」と判定します。OR演算は二つの条件のうち少なくとも一方が真であれば結果が真になり、「AまたはB」に対応します。「会員である」または「クーポンを持っている」のどちらか一方でも満たせば割引を受けられる、といった使い方です。

NOT演算は、条件の真偽を反転させる演算で、「在庫がない」は「在庫がある」をNOTで反転させたものです。

もう一つ覚えておきたいのがXOR演算(排他的論理和)です。これは二つの条件のどちらか一方だけが真のときに結果が真になる演算で、両方とも真、または両方とも偽のときは結果が偽になります。ORとは「両方とも真のときの結果」が違うので、区別しておきましょう。

これらの演算は組み合わせて複雑な条件を表現することもできます。「AかつBでない」のように、ANDとNOTを組み合わせれば、より細かい条件を表せます。例えば検索エンジンで「東京」というキーワードを含み、「賃貸」というキーワードを含まないページを探すときは、この考え方が使われています。プログラムの条件分岐(if文)や、検索エンジンのキーワード検索は、こうした論理演算の組み合わせによって成り立っています。仕組みが分かっていれば、複雑に見える条件式も「どの演算がどの順番で使われているか」を一つずつ分解して読み解けます。

論理演算の結果は、真理値表を使って一つずつ確認すると確実です。例えば「AかつBでない」という条件を、A=1・B=0のときとA=1・B=1のときで比べてみましょう。A=1・B=0のとき、Bでない(NOT B)は1なので、Aかつ(Bでない)は1(真)です。A=1・B=1のとき、Bでない(NOT B)は0なので、Aかつ(Bでない)は0(偽)になります。このように、条件を一段階ずつ分解して真偽を確かめれば、複雑に見える条件式でも間違いなく答えを出せます。

論理回路と真理値表

論理演算の考え方を、実際の電子回路として実現したものが論理回路です。コンピュータの内部では電気信号のオン・オフで0と1を表現し、この回路を無数に組み合わせて複雑な処理を実現しています。論理演算に対応する基本の回路を論理ゲートと呼び、AND演算に対応する回路をANDゲート、OR演算に対応する回路をORゲート、NOT演算に対応する回路をNOTゲートと呼びます。

ANDゲートとORゲートは、真理値表(入力の組み合わせと出力の関係を一覧にした表)で比べると違いがはっきりします。入力A・Bがともに1のときは、ANDもORも出力は1です。ここでA=1、B=0のときを見ると、ANDの出力は0(両方とも1ではないため)ですが、ORの出力は1(どちらか一方が1であるため)になります。A=0、B=0のときは、ANDもORも出力は0です。この「A=1、B=0のときの出力が違う」という点が、両者を見分ける最も確実な手がかりです。

基本ゲートを組み合わせると別のゲートも作れます。ANDゲートの出力にNOTゲートをつなげると、両方とも真のときにだけ偽を出力するNANDゲートになります。同様にORゲートの出力にNOTゲートをつなげるとNORゲートになります。試験では図記号からどの演算に対応するかを答えさせる問題が出ます。

真理値表は、入力が2つのときは組み合わせが4通り(1と1、1と0、0と1、0と0)、入力が3つのときは8通りというように、入力の数に応じて行数が増えていきます。行数が増えても考え方は同じで、それぞれの入力の組み合わせについて、ゲートの種類ごとの出力を一つずつ確認していけば答えにたどり着けます。パソコンやスマートフォンの内部にあるCPU(中央処理装置)は、こうした論理ゲートを数十億個という単位で組み合わせてできています。基本のANDゲート・ORゲート・NOTゲートの動きを確実に区別できるようにしておくことが、複雑な回路を読み解く土台になります。

XOR演算に対応する回路はXORゲートと呼ばれ、二つの入力のどちらか一方だけが1のときに1を出力します。ORゲートと図記号が似ていますが、A=1・B=1のときの出力が違います。ORゲートはこのとき1を出力しますが、XORゲートは0を出力します。図記号を見て「この形は何ゲートか」を素早く判断できるようにしておくと、試験の回路問題を短時間で解けるようになります。

この単元の確認問題

答えを見る前に、まず自分の言葉で答えてみてください。言葉にできないところが、そのまま本試験で止まるところです。

「第7章　基礎理論とアルゴリズム」の他の単元

• 単元23　基数変換と情報量
• 単元25　確率・統計とデータ分析
• 単元26　アルゴリズムとフローチャート
• 単元27　プログラミングと擬似言語

← 単元一覧へ