教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

命題論理における部分論理式

目次

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

部分論理式

命題変数\(P,Q\)に関する式\(((\lnot P)\wedge Q)\)が論理式であることを論理式の定義から確認しましょう。まず、命題変数\(P,Q\)はいずれも論理式です。\(P\)が論理式であるならば\(\left( \lnot P\right) \)は論理式です。\(\left( \lnot P\right) \)と\(Q\)が論理式であるならば\(\left( \left( \lnot P\right) \wedge Q\right) \)は論理式です。

さて、この論理式\(((\lnot P)\wedge Q)\)を生成する過程で登場したすべての論理式\(P,Q,(\lnot P)\)に\(((\lnot P)\wedge Q)\)自身を加えたものを\(((\lnot P)\wedge Q)\)の部分論理式(subformula)と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。ただし、論理式自身をその論理式の部分論理式とみなします。

論理式の部分論理式を以下のように再帰的に定義します。

定義(部分論理式)
  1. 論理式\(A\)自身は\(A\)の部分論理式である。
  2. 論理式\(A\)が論理式\(B\)を用いて\(\left( \lnot B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式でもある。
  3. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\wedge C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
  4. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\vee C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
  5. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\veebar C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
  6. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\rightarrow C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
  7. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\leftrightarrow C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。

いくつか例を挙げます。

例(部分論理式)
命題変数\(P\)に関する論理式\(\left( \lnot P\right) \)の部分論理式を特定します。まず、\(P\)自身は\(P\)の部分論理式です。\(P\)の部分論理式である\(P\)は\(\left( \lnot P\right) \)の部分論理式です。また、\(\left( \lnot P\right) \)自身は\(\left( \lnot P\right) \)の部分論理式です。したがって、\(\left( \lnot P\right) \)の部分論理式は\(P\)と\(\left( \lnot P\right) \)です。
例(部分論理式)
命題変数\(P,Q\)に関する論理式\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式を特定します。先に確認したように、\(\left( \lnot P\right) \)の部分論理式は\(P\)と\(\left( \lnot P\right) \)です。また、\(Q\)自身は\(Q\)の部分論理式です。また、\(\left( \lnot P\right) \)の部分論理式\(P,\left( \lnot P\right) \)と\(Q\)の部分論理式\(Q\)はいずれも\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式です。また、\(\left( \left( \lnot P\right) \rightarrow Q\right) \)自身は\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式です。したがって、\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式は\(P,\ \left( \lnot P\right) ,\ Q,\ \left( \left( \lnot P\right) \rightarrow Q\right) \)です。

 

演習問題

問題(部分論理式)
以下の論理式の部分論理式をすべて列挙してください。ただし、\(P,Q,R\)はいずれも命題変数です。

  1. \(\left( \lnot P\right) \)
  2. \(\left( \left( \lnot P\right) \rightarrow Q\right) \)
  3. \(\left( \left( \lnot P\right) \rightarrow Q\right) \vee R\)
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回からは論理式の解釈について学びます。

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

RELATED KNOWLEDGE
命題論理