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

学習環境

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

初期段階。

任意の命題pに対して、

p

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

帰納段階。

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

このとき、

\begin{array}{l} (p \land q) \\ (p \lor q) \\ (p \Rightarrow q) \\ (p \Leftrightarrow q) \end{array}

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

m + n + 1

また、論理式

(\neg p)

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

m + 1

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

（証明終）