論理和と論理積の結合則、交換則を推論規則から演繹しようと思って挑戦。やりながら論理式と括弧が気になってきました。
そういえばどんなルールがあるのだろうと。
論理式と二項演算と括弧
論理式の定義
Wikipediaには以下のように説明されています。
論理式は次のように再帰的に定義される。
Wikipedia
命題変数は、単独でも論理式である。
『φ』が論理式であるとき『¬φ』も論理式である。
『φ』と『ψ』が論理式であるとき、二項結合子を『•』で表すとすると『(φ•ψ)』も論理式である。一般には、『∨』『∧』『→』『↔』といった記号が二項結合子として使われる。
この定義をバッカス・ナウア記法で形式文法として記述することもできる。変数の種類は有限とすると、次のようになる。
⟨alpha set⟩ ::= p|q|r|s|t|u|…（命題変数の有限集合）
⟨form⟩ ::= ⟨alpha set⟩ | ¬ ⟨form⟩ | (⟨form⟩ ∧ ⟨form⟩) | (⟨form⟩ ∨ ⟨form⟩) | (⟨form⟩ → ⟨form⟩) | (⟨form⟩ ↔ ⟨form⟩)
この文法を使って次のような記号列が記述できる。
論理式である為の要請は思ったより少ない。
命題変数だけでも論理式だし、またはそれに否定の演算を施したものも論理式。定義した二項演算を施したもの、またはそれらを組み合わせたものも論理式。
()は二項演算
()は論理演算の最小単位で、演算なしの(p)のように命題変数一つだけを区切ることはできず(¬p)、(p→q)のように区切ります。
()を外していいのはそれを外しても論理式全体の意味が変わりない場合に限ります。
例えば
(p∧q)∧r
の()を外して
p∧q∧r
にはできません。
意味が変わります。
また(p(q))という区切りも意味がないのでできません。()で区切った演算が一つの単位になるので、
(p→q)→r
の場合は(p→q)を先に演算しその結果を元にrとの二項演算を行います。
基本的には論理式の左端から演算を行います。
p,¬p,p∧q
は論理式ですが
p∧,p→,(p)
は定義を満たさないので論理式ではありません。
今日はこんなもんで。
コメント