計算機科学のブログ

命題論理 論理式、命題の種類数、真理値表の行数

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版 )の第1章(命題論理)、章末問題1.1の解答を求めてみる。

命題が1つの場合、TとFの2行。

命題がn種類の場合にその真理値表が

2 n

行と仮定する。

このとき命題が

n + 1

種類のとき、n種類の命題の真理値表の各行に残り1つの種類のTの場合とEの場合を考えればいいから、

2 n · 2 = 2 n + 1

よって、帰納法により n種類の命題が含まれている論理式の真理値表は

2 n

行である。

証明終

コード(Wolfram Language)

Table[
    Table[
        Table[
            Table[
                Table[{p1, p2, p3, p4, p5}, {p5, {True, False}}],
                {p4, {True, False}}
            ],
            {p3, {True, False}}
        ],
        {p2, {True, False}}
    ],
    {p1, {True, False}}
]
Output
t = Flatten[t, 4]
Output
% // Column
Output
Length[t]

32
2^5

32