Matemática Discreta - Lógica Predicada

Predicate Logic lida com predicados, que são proposições contendo variáveis.

Lógica de Predicados - Definição

Um predicado é uma expressão de uma ou mais variáveis definidas em algum domínio específico. Um predicado com variáveis pode ser proposto atribuindo um valor à variável ou quantificando a variável.

A seguir estão alguns exemplos de predicados -

Deixe E (x, y) denotar "x = y"
Deixe X (a, b, c) denotar "a + b + c = 0"
Deixe M (x, y) denotar "x é casado com y"

Fórmula Bem Formada

Well Formed Formula (wff) é um predicado contendo qualquer um dos seguintes -

Todas as constantes e variáveis proposicionais são wffs
Se x é uma variável e Y é um wff, $ \ forall x Y $ e $ \ existe x Y $ também são wff
O valor verdadeiro e os valores falsos são wffs
Cada fórmula atômica é um wff
Todos os conectivos conectando wffs são wffs

Quantificadores

A variável dos predicados é quantificada por quantificadores. Existem dois tipos de quantificador na lógica de predicado - Quantificador Universal e Quantificador Existencial.

Quantificador Universal

O quantificador universal afirma que as afirmações dentro de seu escopo são verdadeiras para cada valor da variável específica. É denotado pelo símbolo $ \ forall $.

$ \ forall x P (x) $ é lido como para todo valor de x, P (x) é verdadeiro.

Example - "O homem é mortal" pode ser transformado na forma proposicional $ \ forall x P (x) $ onde P (x) é o predicado que denota x é mortal e o universo do discurso são todos os homens.

Quantificador Existencial

O quantificador existencial afirma que as afirmações dentro de seu escopo são verdadeiras para alguns valores da variável específica. É denotado pelo símbolo $ \ exists $.

$ \ existe x P (x) $ é lido como para alguns valores de x, P (x) é verdadeiro.

Example - "Algumas pessoas são desonestas" pode ser transformado na forma proposicional $ \ existe x P (x) $ onde P (x) é o predicado que denota que x é desonesto e o universo do discurso são algumas pessoas.

Quantificadores Aninhados

Se usarmos um quantificador que aparece no escopo de outro quantificador, ele é chamado de quantificador aninhado.

Example

$ \ forall \ a \: \ exists b \: P (x, y) $ onde $ P (a, b) $ denota $ a + b = 0 $
$ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ onde $ P (a, b) $ denota $ a + (b + c) = ( a + b) + c $

Note - $ \ para todos \: a \: \ existe b \: P (x, y) \ ne \ existe a \: \ para todos b \: P (x, y) $