離散数学-述語論理
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）$