Lógica de Primeira Ordem para um Conhecimento Mais Rico

• Explicar o limite de expressividade da lógica proposicional que motiva a lógica de primeira ordem: não há como falar de objetos, relações e generalizações sem escrever uma proposição separada para cada caso individual.
• Identificar os blocos de construção da lógica de primeira ordem: constantes, variáveis, predicados, funções e os quantificadores universal (∀) e existencial (∃), já vistos como matemática pura.
• Traduzir uma frase em português para uma sentença bem formada de lógica de primeira ordem, e vice-versa.
• Explicar o que significa uma única sentença de FOL ser equivalente a infinitos fatos proposicionais.
• Distinguir a expressividade adicional da lógica de primeira ordem daquilo que ela ainda não consegue representar (relações de ordem superior sobre as próprias relações, tratadas por lógicas mais ricas não vistas aqui).

A lógica proposicional, vista nos dois conceitos anteriores, consegue representar e raciocinar sobre fatos individuais e nomeados ($P1$, $P2$, $L$), mas não tem como falar de objetos e das relações entre eles de forma geral. Para dizer "todo aluno que estuda passa" em lógica proposicional, um agente precisaria de um símbolo proposicional separado, e de uma implicação separada, para cada aluno que pudesse existir: StudiesAlice → PassesAlice, StudiesBob → PassesBob, e assim por diante, para sempre, uma sentença por indivíduo, sem que o padrão subjacente ("estudar leva a passar", para qualquer pessoa) fosse representado explicitamente em lugar nenhum.

A lógica de primeira ordem (FOL) corrige exatamente isso. Predicados e quantificadores (a mesma notação ∀, ∃, ¬, ∧, ∨, → e as mesmas regras para negar enunciados quantificados já vistas como matemática discreta pura) permitem que uma única sentença de FOL, ∀x (Studies(x) → Passes(x)), valha por todos aqueles infinitos fatos proposicionais de uma vez. Esse é o motivo real de a lógica de primeira ordem, e não a proposicional, ser a base de praticamente todo sistema sério de representação de conhecimento em IA: domínios reais estão cheios de regras gerais que se aplicam a uma quantidade ilimitada de objetos, e só uma lógica com objetos e quantificadores consegue enunciar uma regra dessas uma vez, em vez de uma vez por objeto.

Os blocos de construção da lógica de primeira ordem

• Constantes nomeiam objetos específicos (Alice, 2, RegionWA).
• Variáveis (x, y) representam um objeto não especificado, a ser ligado por um quantificador.
• Predicados expressam propriedades de objetos, ou relações entre eles, e retornam verdadeiro ou falso (Studies(x), Adjacent(WA, NT), GreaterThan(x, y)).
• Funções mapeiam objetos em objetos, e não em verdadeiro/falso (FatherOf(x), Plus(x, y)); o valor de uma função é ele próprio um objeto que pode ser argumento de um predicado.
• O quantificador universal (∀): ∀x P(x) afirma que $P$ vale para todo objeto do domínio de discurso.
• O quantificador existencial (∃): ∃x P(x) afirma que $P$ vale para pelo menos um objeto do domínio.

São exatamente os mesmos quantificadores e as mesmas regras de negação ($\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ e $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$) já vistos como matemática pura; nada no comportamento lógico deles muda quando são usados para representar o conhecimento de um agente em vez de uma afirmação matemática.

Uma sentença de FOL, infinitos fatos proposicionais

Considere ∀x (Studies(x) → Passes(x)). Para um domínio de discurso com os objetos $Alice, Bob, Carol, \ldots$, essa única sentença é logicamente equivalente à conjunção (potencialmente infinita):

text
(Studies(Alice) → Passes(Alice)) ∧
(Studies(Bob)   → Passes(Bob))   ∧
(Studies(Carol) → Passes(Carol)) ∧
  ...

Esse é o sentido preciso em que a FOL é mais expressiva que a lógica proposicional para esse tipo de enunciado: a lógica proposicional só consegue escrever à mão um conjunto fixo e finito desses fatos; o quantificador da FOL expressa o próprio padrão, cobrindo corretamente todo objeto do domínio, inclusive os ainda não nomeados ou que nem se sabia existirem quando a sentença foi escrita.

O que a FOL ainda não representa

A lógica de primeira ordem quantifica sobre objetos, e não sobre as próprias relações ou propriedades; ela não consegue expressar diretamente um enunciado como "para toda propriedade $P$, se $P$ vale para todas as aves, então..." (quantificando sobre predicados, e não só sobre objetos). Enunciados com esse formato exigem uma lógica de segunda ordem ou de ordem superior, um formalismo genuinamente mais expressivo (e computacionalmente muito mais difícil de raciocinar), não visto nesta disciplina. Na prática, a grande maioria das tarefas de representação de conhecimento em IA (as que esta disciplina e as seguintes tratam) é atendida adequadamente pela lógica de primeira ordem; o salto para a lógica de ordem superior é uma ferramenta especializada para um conjunto mais estreito de problemas.

Exemplo 1: traduzindo do português para FOL

text
Português: "Todo aluno que estuda passa."
FOL:       ∀x (Student(x) ∧ Studies(x) → Passes(x))

Português: "Algum aluno nunca reprovou em uma disciplina."
FOL:       ∃x (Student(x) ∧ ¬(∃y (Course(y) ∧ Failed(x, y))))

Português: "O orientador de Alice é professor."
FOL:       Professor(AdvisorOf(Alice))
           (AdvisorOf é uma função: mapeia um aluno ao seu orientador,
            um objeto específico, que o predicado Professor então checa)

Repare no padrão da matemática discreta funcionando diretamente: uma sentença universalmente quantificada sobre "todo X" é escrita, por padrão, como uma implicação ($\forall x\, P(x) \to Q(x)$, e não $\forall x\, P(x) \wedge Q(x)$, um erro de tradução comum e fácil de cometer; a segunda forma afirmaria incorretamente que todo objeto do domínio é ao mesmo tempo aluno e aprovado, em vez de restringir a afirmação apenas aos alunos).

Exemplo 2: o erro comum de combinação entre quantificador e conectivo

text
Significado pretendido: "Todos os corvos são pretos."
FOL correta:            ∀x (Raven(x) → Black(x))
FOL incorreta:          ∀x (Raven(x) ∧ Black(x))    ← afirma que todo objeto
                                                       do domínio é AO MESMO
                                                       TEMPO corvo E preto;
                                                       quase certamente falso
                                                       e não o que se queria

Significado pretendido: "Alguma ave não voa."
FOL correta:            ∃x (Bird(x) ∧ ¬Flies(x))
FOL incorreta:          ∃x (Bird(x) → ¬Flies(x))     ← isto é VERDADEIRO desde
                                                        que exista no domínio
                                                        pelo menos um objeto
                                                        que não seja ave (já
                                                        que a implicação é
                                                        trivialmente verdadeira
                                                        para qualquer x que não
                                                        seja ave), independente
                                                        de alguma ave real não
                                                        conseguir voar

Essa convenção de combinar ∀ com → e ∃ com ∧ (e não o contrário) é o idioma padrão e correto justamente porque uma afirmação universal deve ser satisfeita trivialmente por objetos fora do escopo pretendido, enquanto uma afirmação existencial precisa afirmar positivamente que as duas propriedades valem juntas para pelo menos um objeto específico.

Exemplo 3: aplicando a regra de negação de quantificadores já vista a uma sentença de FOL

text
Original: ∀x (Student(x) → Studies(x))    ("todo aluno estuda")

Negação, passo a passo (¬∀x P(x) ≡ ∃x ¬P(x)):
  ¬∀x (Student(x) → Studies(x))
≡ ∃x ¬(Student(x) → Studies(x))
≡ ∃x ¬(¬Student(x) ∨ Studies(x))          [P→Q ≡ ¬P∨Q]
≡ ∃x (Student(x) ∧ ¬Studies(x))            [lei de De Morgan]

Final: "existe um aluno que não estuda"; exatamente a negação intuitiva de
"todo aluno estuda", derivada mecanicamente usando apenas a regra de negação
de quantificadores e a lei de De Morgan já vistas como lógica pura.

• "∀x (P(x) ∧ Q(x)) significa o mesmo que 'todo P é Q'." Como mostra o Exemplo 2, isso afirma incorretamente que todo objeto do domínio inteiro tem as duas propriedades; "todo P é Q" se escreve corretamente com uma implicação, ∀x (P(x) → Q(x)), restringindo a afirmação apenas aos objetos que satisfazem P.
• "∃x (P(x) → Q(x)) é um jeito com sentido de dizer 'algum P é Q'." Como mostra o Exemplo 2, isso é trivialmente verdadeiro sempre que o domínio contém algum objeto que simplesmente não é P, independentemente de a relação pretendida entre P e Q valer em algum lugar; "algum P é Q" precisa de uma conjunção, ∃x (P(x) ∧ Q(x)).
• "Uma função em FOL é o mesmo tipo de coisa que um predicado." Um predicado retorna verdadeiro ou falso e pode aparecer sozinho como (parte de) uma sentença; uma função retorna um objeto e só pode aparecer como argumento de um predicado ou de outra função: FatherOf(Alice) não é verdadeiro nem falso, mas Professor(FatherOf(Alice)) é.
• "A FOL consegue expressar qualquer padrão que um humano queira enunciar de forma geral." A FOL quantifica sobre objetos, e não sobre predicados ou relações em si; enunciados genuinamente de segunda ordem ("para toda propriedade...") estão fora do que a lógica de primeira ordem, como vista aqui, consegue expressar diretamente.

A lógica de primeira ordem acrescenta aos conectivos da lógica proposicional constantes, variáveis, predicados, funções e os quantificadores universal/existencial já vistos como matemática discreta pura, permitindo que uma única sentença valha por um padrão geral, verdadeiro para todo (ou algum) objeto de um domínio, em vez de exigir um fato proposicional separado por objeto. O idioma padrão combina ∀ com → e ∃ com ∧, justamente para evitar as armadilhas de verdade trivial e de generalização excessiva ilustradas acima, e as mesmas regras de negação de quantificadores e leis de De Morgan já vistas se aplicam sem mudança a sentenças de FOL. Essa expressividade adicional (infinitos fatos expressos por uma regra geral) é exatamente o motivo de a FOL, e não a lógica proposicional, ser a base padrão da representação de conhecimento em IA; o próximo conceito cobre como a inferência (unificação e resolução) de fato opera sobre sentenças escritas nessa linguagem mais rica.