離散数学-述語論理

Predicate Logic 変数を含む命題である述語を扱います。

述語論理–定義

述語は、特定のドメインで定義された1つ以上の変数の式です。変数を含む述語は、変数に値を割り当てるか、変数を定量化することによって命題にすることができます。

以下は述語のいくつかの例です-

  • E(x、y)が「x = y」を表すとします。
  • X(a、b、c)が「a + b + c = 0」を表すとします。
  • M(x、y)が「xはyと結婚している」ことを表すとします

論理式

論理式(wff)は、次のいずれかを保持する述語です。

  • すべての命題定数と命題変数はwffsです

  • xが変数で、Yがwffの場合、$ \ forall x Y $と$ \ exists x Y $もwffです。

  • 真理値と偽値はwffsです

  • 各原子論理式はwffです

  • wffsを接続するすべての接続詞はwffsです

定量化子

述語の変数は、数量詞によって数量化されます。述語論理には、全称記号と存在記号の2種類の量化子があります。

全称記号

全称記号は、そのスコープ内のステートメントが特定の変数のすべての値に当てはまると述べています。記号$ \ forall $で示されます。

$ \ forall x P(x)$は、xのすべての値と同様に読み取られ、P(x)は真です。

Example −「人は死ぬ」は、命題形式$ \ forall x P(x)$に変換できます。ここで、P(x)は、xが死ぬことを示す述語であり、論議領界はすべて人です。

存在記号

存在記号は、そのスコープ内のステートメントが特定の変数の一部の値に当てはまると述べています。記号$ \ exists $で示されます。

$ \ exists x P(x)$は、xの一部の値について読み取られ、P(x)は真です。

Example −「一部の人々は不正直である」は命題形式$ \ exists x P(x)$に変換できます。ここで、P(x)は、xが不正直であり、論議領界が一部の人々であることを示す述語です。

ネストされた数量詞

別の数量詞のスコープ内に表示される数量詞を使用する場合、それはネストされた数量詞と呼ばれます。

Example

  • $ \ 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 $

Note − $ \ forall \:a \:\ exists b \:P(x、y)\ ne \ exists a \:\ forall b \:P(x、y)$