Discrete-mathematics-predicate-logic
離散数学-述語論理
- 述語ロジック*は、変数を含む命題である述語を扱います。
述語論理–定義
述語は、特定のドメインで定義された1つ以上の変数の式です。 変数を含む述語は、変数に値を割り当てるか、変数を定量化することにより命題にすることができます。
以下は、述語のいくつかの例です-
- E(x、y)が「x = y」を示すものとします
- X(a、b、c)が「a+ b+ c = 0」を示すものとする
- M(x、y)が「xはyと結婚している」ことを示すとします
整形式
整形式(wff)は、次のいずれかを保持する述語です-
- すべての命題定数と命題変数はwffです
- xが変数でYがwffの場合、$ \ forall x Y $および$ \ exists x Y $もwffです
- 真理値と偽値はwffです
- 各アトミック式はwffです
- wffを接続するすべての接続詞はwffです
数量詞
述語の変数は、数量詞によって数量化されます。 述語論理には2種類の量指定子があります-Universal QuantifierとExistential Quantifier。
汎用数量詞
汎用数量詞は、そのスコープ内のステートメントが特定の変数のすべての値に当てはまると述べています。 記号$ \ forall $で示されます。
$ \ forall x P(x)$はxのすべての値について読み取られ、P(x)はtrueです。
例-"Man is mortal"は命題形式$ \ forall x P(x)$に変換できます。ここで、P(x)はxが致命的であり、談話の世界はすべて男性であることを示す述語です。
実存量指定子
存在量指定子は、そのスコープ内のステートメントが特定の変数のいくつかの値に対して真であると述べています。 記号$ \ exists $で示されます。
$ \ exists x P(x)$はxのいくつかの値に関して読み取られ、P(x)はtrueです。
例-「一部の人々は不誠実」は命題形式$ \ exists x P(x)$に変換できます。ここで、P(x)はxが不誠実であり、談話の宇宙が一部の人々であることを示す述語です。
ネストされた量指定子
別の数量詞のスコープ内に現れる数量詞を使用する場合、それはネストされた数量詞と呼ばれます。
例
- $ \ forall \ a \:\ exists b \:P(x、y)$ここで、$ P(a、b)$は$ a + b = 0 $を示します
- $ \ forall \ a \:\ forall \:b \:\ forall \:c \:P(a、b、c)$ここで、$ P(a、b)$は$ a (b + c)=( a + b) c $
注-$ \ forall \:a \:\ exists b \:P(x、y)\ ne \ exists a \:\ forall b \:P(x、y)$