計算機科学のブログ

命題論理 論理式の標準形 CNFとDNF 変換手順

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版 )の第1章(命題論理)、1.4(論理式の標準形)、1.4.1(CNFとDNF)、問題1.14の解答を求めてみる。

( p ¬ q ) ( r s )
= ¬ ( p ¬ q ) ( r s )
= ¬ ( ¬ p ¬ q ) ( r s )
= ( p q ) ( r s )
= ( ( p q ) r ) ( ( p q ) s )
= ( p r ) ( q r ) ( p s ) ( q s )

コード(Wolfram Language)

Table[
    Table[
        Table[
            Table[
                Implies[
                    Implies[p, !q],
                    r && s
                ] == ((p || r) && (q || r) && (p || s) && (q || s)),
                {p, {True, False}}
            ],
            {q, {True, False}}
        ],
        {r, {True, False}}
    ],
    {s, {True, False}}
]
Output