計算機科学のブログ

命題論理 論理式の標準形 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