命題論理と真理値表とは？

命題論理と真理値表の意味

「真」か「偽」のいずれかに定まる文（命題）を対象に、論理演算の組み合わせでできる複合命題の真偽を、すべての入力パターンについて一覧表にしたものが真理値表。論理式の等価性の確認や、論理回路の動作検証に使われる。

命題論理と真理値表の具体例

「A→B」（AならばB）という命題は、Aが偽のときは常に真になるという直感に反する性質があり、真理値表を書いて確認すると理解しやすい。

命題論理と真理値表は試験でどう引っ掛けられる？

「AならばB」はAが偽ならBの真偽に関わらず真になる。この行の見落としが定番の誤り。逆・裏・対偶のうち元の命題と必ず真偽が一致するのは対偶だけ。入力がn個なら真理値表の行数は2のn乗になる。

命題論理と真理値表と関連する用語

• ブール代数と論理式の簡略化

命題論理と真理値表が出た過去問

• 真理値表に示す3入力多数決回路はどれか。

  正解：2入力ANDゲート3個（A・B、B・C、C・A）の出力を、ORゲート2段で束ねてYを得る回路。

  要点：3入力多数決はAB＋BC＋CA。ANDを3個並べてORで束ねる

  3入力多数決は、3つのうち2つ以上が1のとき出力が1になる。これは2入力ずつの積を取って和にした AB＋BC＋CA という論理式で表せるため、2入力ANDを3個作りその出力をORで束ねる回路が該当する。真理値表の1になる4行がちょうどこの3つの積項で覆われることを確かめればよい。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問23（IPA）

• 図の論理回路と等価な回路はどれか。

  正解：AとBを入力とするXOR回路（Y出力）

  要点：NAND4個の定番構成は排他的論理和（XOR）と等価

  この回路は4個のNAND素子でできた定番の構成である。まず両入力のNAND出力をNとし、上側でAとN、下側でNとBのNANDをとり、その二つをさらにNANDで結んでいる。真理値表を作ると、AとBが同じ値のときは出力が0、異なるときだけ1になり、排他的論理和と一致する。

  出典：平成28年度 春期 基本情報技術者試験 午前 問23（IPA）

• 真理値表に示す3入力多数決回路はどれか。

  正解：回路図ア

  要点：3入力多数決はAB＋BC＋CAで表せる

  3入力多数決回路の出力は、入力のうち2つ以上が1のときに1となるので、論理式は A・B ＋ B・C ＋ C・A で表せる。したがって、2入力の論理積を3つ作り、それらの論理和をとる構成が正しい。

  出典：平成30年度 春期 基本情報技術者試験 午前 問23（IPA）

• P, Q, Rはいずれも命題である。命題Pの真理値は真であり、命題(not P) or Q及び命題(not Q) or Rのいずれの真理値も真であることが分かっ…

  正解：Q：真、R：真

  要点：not X or Y は含意 X→Y と同じ意味

  「not X or Y」は含意X→Yと同値であり、前件が真なら後件も真でなければ全体が真にならない。Pが真なので、not Pは偽となり、(not P) or Qが真であるためにはQが真しかない。次にQが真だとnot Qは偽なので、(not Q) or Rが真であるにはRも真である必要がある。

  出典：令和1年度 春期 基本情報技術者試験 午前 問3（IPA）

• P, Q, Rはいずれも命題である。命題Pの真理値は真であり、命題（not P）or Q及び命題（not Q）or Rのいずれの真理値も真であることが分かってい…

  正解：Q：真　R：真

  要点：（not X）or Y は「XならばY」。前提の連鎖で真理値が決まる

  「not X or Y」は「XならばY」と同値である。Pが真なので、第1の命題が真であるためにはQが真でなければならない。次にQが真と定まったので、第2の命題が真であるためにはRも真でなければならない。よってQ・Rともに真となる。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問3（IPA）