Matematyka dyskretna - logika predykatów

Predicate Logic zajmuje się predykatami, które są zdaniami zawierającymi zmienne.

Logika predykatów - definicja

Predykat to wyrażenie jednej lub więcej zmiennych zdefiniowanych w określonej dziedzinie. Predykat ze zmiennymi można złożyć jako propozycję, przypisując wartość zmiennej lub określając ją ilościowo.

Oto kilka przykładów predykatów -

Niech E (x, y) oznacza „x = y”
Niech X (a, b, c) oznacza „a + b + c = 0”
Niech M (x, y) oznacza „x jest żonaty z y”

Dobrze uformowana formuła

Dobrze uformowana formuła (wff) jest predykatem zawierającym dowolne z poniższych -

Wszystkie stałe zdaniowe i zmienne zdaniowe są wffs
Jeśli x jest zmienną, a Y jest wff, $ \ dla wszystkich x Y $ i $ \ istnieje x Y $ są również wff
Wartość prawdy i wartości fałszywe to wffs
Każda formuła atomowa to wff
Wszystkie łączniki łączące wffs są wffs

Kwantyfikatory

Zmienna predykatów jest określana ilościowo za pomocą kwantyfikatorów. Istnieją dwa rodzaje kwantyfikatorów w logice predykatów - kwantyfikator uniwersalny i kwantyfikator egzystencjalny.

Uniwersalny kwantyfikator

Uniwersalny kwantyfikator stwierdza, że instrukcje w jego zakresie są prawdziwe dla każdej wartości określonej zmiennej. Jest oznaczony symbolem $ \ forall $.

$ \ forall x P (x) $ jest czytane jak dla każdej wartości x, P (x) jest prawdziwe.

Example - „Człowiek jest śmiertelny” można przekształcić w formę zdaniową $ \ forall x P (x) $, gdzie P (x) jest orzeczeniem oznaczającym, że x jest śmiertelny, a wszechświatem dyskursu są wszyscy ludzie.

Kwantyfikator egzystencjalny

Kwantyfikator egzystencjalny stwierdza, że instrukcje w jego zakresie są prawdziwe dla niektórych wartości określonej zmiennej. Jest oznaczony symbolem $ \ istnieje $.

$ \ istnieje x P (x) $ jest odczytywane jako dla niektórych wartości x, P (x) jest prawdziwe.

Example - „Niektórzy ludzie są nieuczciwi” można przekształcić w formę zdaniową $ \ istnieje x P (x) $, gdzie P (x) jest orzeczeniem oznaczającym, że x jest nieuczciwy, a wszechświat dyskursu to niektórzy ludzie.

Zagnieżdżone kwantyfikatory

Jeśli użyjemy kwantyfikatora, który pojawia się w zakresie innego kwantyfikatora, nazywamy go kwantyfikatorem zagnieżdżonym.

Example

$ \ forall \ a \: \ istnieje b \: P (x, y) $ gdzie $ P (a, b) $ oznacza $ a + b = 0 $
$ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ gdzie $ P (a, b) $ oznacza $ a + (b + c) = ( a + b) + c $

Note - $ \ forall \: a \: \ istnieje b \: P (x, y) \ ne \ istnieje a \: \ forall b \: P (x, y) $