論理式と命題|基本情報技術者試験の過去問対策

目次

まずは過去問を見てみよう

過去問①:条件文と同じ意味の論理式

平成19年度 春期 基本情報技術者試験 午前 問9

過去問②:命題の真理値

平成19年度 秋期 基本情報技術者試験 午前 問9

この問題を解くために必要なキーワード

今回の学習で押さえるキーワードは、次の4つです。

① 命題と真理値
② 論理演算と条件文
③ 論理式の同値
④ 論理式の変形法則

1. 命題と真理値

命題とは、真(True)か偽(False)かを判断できる文のことです。

例えば、次のような文は命題です。

  • 「2は偶数である」→ 真
  • 「5は偶数である」→ 偽

この真・偽の値を真理値といいます。

NOT・AND・OR

試験で必要になる基本的な論理演算は、次の3つです。

演算意味真になる条件
NOT否定元の命題が偽
AND論理積両方が真
OR論理和少なくとも一方が真

例えば、Pが真、Qが偽の場合、

  • NOT P → 偽
  • P AND Q → 偽
  • P OR Q → 真

となります。

命題の真理値を求める方法

例えば、次の条件が与えられたとします。

  • Pは真
  • (NOT P) OR Q は真
  • (NOT Q) OR R は真

まず、Pが真なので、NOT Pは偽です。

したがって、

偽 OR Q = 真

となります。

ORは少なくとも一方が真でなければならないため、Qは真です。

次に、Qが真なので、NOT Qは偽です。

偽 OR R = 真

となるため、Rも真です。

試験で覚えるポイント

  • 命題:真か偽かを判断できる文
  • 真理値:真(True)または偽(False)
  • NOT:真と偽を反転する
  • AND:両方が真なら真
  • OR:少なくとも一方が真なら真
  • 複数の条件がある場合は、確定している真理値から順番に代入する

2. 論理演算と条件文

条件文とは、指定した条件が成立する場合に処理を実行する文です。

例えば、

if (A = True) then ...

は、Aが真の場合に処理を実行するという意味です。

XOR(排他的論理和)

XORは、2つの真理値が異なる場合に真になる演算です。

ABA XOR B
偽偽偽
偽真真
真偽真
真真偽

例えば、次の条件文を考えます。

if (A = True AND B = False) OR (A = False AND B = True) then ...

この条件が成立するのは、

  • Aが真、Bが偽
  • Aが偽、Bが真

の2通りです。

つまり、AとBの真理値が異なる場合です。

したがって、XORを使えば、

if ((A XOR B) = True) then ...

と表せます。

試験で覚えるポイント

  • AND:両方が真
  • OR:少なくとも一方が真
  • XOR:一方だけが真
  • 「Aが真でBが偽、またはAが偽でBが真」はXORと同じ意味

3. 論理式の同値

論理式が同値であるとは、すべての入力の組合せで結果が一致することです。

例えば、

A AND B

と、

B AND A

は同値です。

AとBの順番を入れ替えても、結果は変わりません。

同値かどうかを確認する方法

論理式が同値かどうかを判断するには、主に2つの方法があります。

方法①:真理値表を使う

すべての入力の組合せについて、それぞれの論理式を計算します。

ABA AND BB AND A
0000
0100
1000
1111

すべての結果が一致しているため、2つの論理式は同値です。

方法②:論理式を変形する

論理演算の法則を使って、同じ形になるか確認します。

試験では、選択肢に具体的な値を代入して、結果が一致しないものを除外する方法も有効です。

試験で覚えるポイント

  • 同値:すべての入力で結果が一致する
  • 真理値表を使えば同値かどうか確認できる
  • 論理式の変形法則を使っても判断できる
  • 1つでも結果が異なる入力があれば、同値ではない

4. 論理式の変形法則

論理式を変形するときは、次の法則を使います。

ここでは、・をAND、+をOR、¬をNOTとします。

交換法則

演算する順番を入れ替えても結果が変わらない法則です。

  • A・B = B・A
  • A+B = B+A

結合法則

括弧の位置を変えても結果が変わらない法則です。

  • (A・B)・C = A・(B・C)
  • (A+B)+C = A+(B+C)

分配法則

括弧を展開できる法則です。

  • A・(B+C) = A・B+A・C
  • A+B・C = (A+B)・(A+C)

吸収法則

不要な部分を取り除ける法則です。

  • A+A・B = A
  • A・(A+B) = A

例えば、

A・(A+B)

は、吸収法則を使うと、

A

になります。

補元法則

変数とその否定を組み合わせた場合の法則です。

  • A+¬A = 1
  • A・¬A = 0

ド・モルガンの法則

NOTを括弧の中に分配するときに使います。

  • ¬(A・B) = ¬A+¬B
  • ¬(A+B) = ¬A・¬B

論理式を簡単にする例

次の論理式を考えます。

A・B+A・¬B

Aでくくると、

A・(B+¬B)

となります。

補元法則から、

B+¬B = 1

なので、

A・1 = A

となります。

したがって、

A・B+A・¬B = A

です。

試験で覚えるポイント

法則覚える式
交換法則A・B = B・A
分配法則A・(B+C) = A・B+A・C
吸収法則A+A・B = A
補元法則A+¬A = 1、A・¬A = 0
ド・モルガンの法則¬(A・B) = ¬A+¬B

論理式の変形が難しい場合は、選択肢に0と1を代入して確認する方法も覚えておきましょう。

過去問の正解と解説

過去問①:条件文と同じ意味の論理式

平成19年度 春期 基本情報技術者試験 午前 問9

正解・解説

正解:エ

問題の条件文は、

if (A = True AND B = False) OR (A = False AND B = True) then ...

です。

この条件が成立するのは、

  • Aが真、Bが偽
  • Aが偽、Bが真

の2通りです。

つまり、AとBの真理値が異なる場合です。

これはXORと同じなので、

if ((A XOR B) = True) then ...

となります。

したがって、正解はエです。

過去問②:命題の真理値

平成19年度 秋期 基本情報技術者試験 午前 問9

正解・解説

正解:エ(Q=真、R=真)

問題では、次の3つの条件が与えられています。

  • Pは真
  • (NOT P) OR Q は真
  • (NOT Q) OR R は真

まず、Pが真なので、NOT Pは偽です。

(NOT P) OR Q が真になるには、Qが真でなければなりません。

したがって、

Q=真

です。

次に、Qが真なので、NOT Qは偽です。

(NOT Q) OR R が真になるには、Rが真でなければなりません。

したがって、

R=真

です。

よって、正解はエ(Q=真、R=真)となります。

まとめ

論理式と命題では、次の4つを押さえましょう。

キーワード覚えること
命題と真理値命題は真または偽で判断する
論理演算と条件文AND・OR・XORの条件を理解する
論理式の同値すべての入力で結果が一致すること
論理式の変形法則分配法則・吸収法則・補元法則・ド・モルガンの法則

特に、「確定した真理値から順番に代入する」「XORは一方だけが真」「論理式は法則を使って簡単にできる」という3点を覚えておきましょう。


出典

本記事で使用している過去問題の出典は、独立行政法人情報処理推進機構(IPA)です。

  • 平成19年度 春期 基本情報技術者試験 午前 問9
  • 平成19年度 秋期 基本情報技術者試験 午前 問9

公式サイト:IPA 基本情報技術者試験 過去問題

よかったらシェアしてね!
目次