計算機科学のブログ

帰納的定義と証明技法 論理式、括弧の組の数と論理結合子の数

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、章末問題の問3.8の解答を求めてみる。

初期段階。

任意の命題pに対して、

p

なので論理結合子がが0個、括弧が0組で数は等しい。

帰納段階。

任意の命題p、 q に対して、 pの括弧の組の数、論理結合子の数とm、 qの括弧の組の数をnと仮定する。

このとき、

( p q ) ( p q ) ( p q ) ( p q )

のいずれの論理式の括弧の組の数、論理結合子の数は

m + n + 1

また、 論理式

( ¬ p )

の括弧の組の数、論理結合子の数は

m + 1

よって帰納法により、括弧の組の数と論理結合子の数は同じである。

(証明終)