A quantificação é central para explicar as inferências em língua natural. A
teoria aristotélica apresentada em Um Motor de Inferência
trata sentenças com um único quantificador. Ela não permite combinar
quantificadores na mesma sentença nem abrange expressões como
most, half of e at least five. Além disso, algumas de suas
inferências pressupõem que a restrição tenha elementos.
Na lógica de Frege, os quantificadores \forall e \exists ligam variáveis
em fórmulas arbitrárias, permitindo combinar várias quantificações. Eles podem
ser definidos um pelo outro com a negação: \exists x\,P(x) equivale a
\neg\forall x\,\neg P(x). As quatro formas do quadrado das oposições recebem
representações nessa lógica. Por exemplo, «todo A é B» é
\forall x\,(A(x)\to B(x)), e «algum A é B» é \exists x\,(A(x)\land B(x)).
Essas fórmulas não pressupõem que a extensão de A seja não vazia. Se nenhum
elemento satisfaz A, a universal é verdadeira e a existencial é falsa. Nesse
caso, «todo A é B» e «nenhum A é B» são ambas verdadeiras, enquanto as duas
particulares são falsas. As relações de contrariedade, subcontrariedade e
subalternação do quadrado exigem, portanto, a pressuposição existencial. As
diagonais continuam sendo contraditórias. Esse é também o motivo pelo qual uma
inferência como Darapti pode falhar na lógica de primeira ordem.
Com a igualdade, podemos expressar quantidades fixas na lógica de primeira
ordem. Para dizer que pelo menos dois elementos são A e B, quantificamos duas
variáveis e exigimos que seus valores sejam distintos:
\exists x\exists y\,(x\neq y\land A(x)\land A(y)\land B(x)\land B(y)).
A função atLeastTwo recebe os nomes dos dois predicados e constrói uma fórmula
de tipo LF. O termo .neg (.eq tx ty) exprime a desigualdade entre as
variáveis. A função check avalia a fórmula no modelo do fragmento. Nesse
modelo, há três pessoas que riem, das quais duas são meninas.
As funções atLeastTwo e atMostTwo constroem fórmulas. É
importante acompanhar os dois níveis envolvidos: Lean é a metalinguagem em que
escrevemos o programa, e FOL é a linguagem objeto cujas fórmulas o programa
produz.
Para cada número natural fixo, podemos construir uma fórmula que conte até ele.
Também podemos combinar essas fórmulas por conjunção, disjunção e negação. Isso
não fornece à linguagem objeto uma operação única de contagem com limite
arbitrário. Cada fórmula resultante é finita e tem sua própria quantidade de
variáveis e quantificadores.
Exercício★★★(at-least-n)
Defina atLeast n a b, a fórmula de "pelo menos n A são B", e atMost n a b,
a de "no máximo n A são B". Nenhuma fórmula sozinha serve para todo n, mas
uma única função Lean pode gerar, para cada n, a fórmula correspondente.
Dicas: as n variáveis distintas podem sair do índice de Variable, pois
⟨"x", [i]⟩ é a variável xi. "No máximo n" é a negação de "pelo menos n +
1". Para atLeast, uma função auxiliar recursiva pode carregar a lista dos
termos já quantificados, para exigir que cada nova variável seja diferente de
todos eles.
Combinar quantificadores torna visíveis diferenças de escopo.
Every prince sang a ballad pode afirmar que cada príncipe cantou
alguma balada, possivelmente uma diferente para cada um. Com o escopo invertido,
existe uma balada que todos os príncipes cantaram. As fórmulas de primeira ordem
distinguem as leituras
\forall x\,(Prince(x)\to\exists y\,(Ballad(y)\land Sang(x,y))) e
\exists y\,(Ballad(y)\land\forall x\,(Prince(x)\to Sang(x,y))). A sentença
passiva A ballad was sung by every prince também permite examinar esse
contraste.
Como em Formas Linguísticas e Traduções para Lógica, a estrutura da
fórmula pode diferir da estrutura sintática da sentença. Os sintagmas nominais
deixam de aparecer como unidades na representação. Queremos preservar suas
contribuições semânticas como componentes da composição e obter um procedimento
sistemático para combiná-las. Também queremos incluir quantificadores como
most no mesmo tratamento. A perspectiva relacional e os significados tipados
permitirão desenvolver esses três objetivos.
Na perspectiva relacional, um determinante relaciona dois subconjuntos de um
domínio: a restrição e o escopo. Essa abordagem foi desenvolvida por Mostowski
(Mostowski, 1957)Marginal noteAndrzej Mostowski (1957). “On a generalization of quantifiers”. Fundamenta Mathematicae.44. e, para a língua natural, por Barwise e Cooper
(Barwise and Cooper, 1981)Marginal noteJon Barwise and Robin Cooper (1981). “Generalized quantifiers and natural language”. Linguistics and Philosophy.4..
Em Every princess laughed, a restrição é o conjunto das princesas, e o escopo
é o conjunto dos que riram. A sentença é verdadeira quando o primeiro conjunto
está contido no segundo. A função every verifica essa condição percorrendo as
entidades do modelo.
A composição pode ser acompanhada pelos tipos. O determinante recebe duas
propriedades e tem tipo OnePlacePred → OnePlacePred → Bool. Depois de receber
princess, a expressão every princess ainda espera uma propriedade. Ao
receber laugh, produz um valor de verdade. Assim, o significado do
sintagma nominal continua sendo uma unidade que participa da composição. Em
lfDET, restrição e escopo serviam para construir uma fórmula; aqui,
eles são interpretados diretamente no modelo.
Uma propriedade como princess pode ser vista como a função
característica de um conjunto de entidades, conforme
Conjuntos e Relações. Aplicamos a mesma ideia às propriedades:
every princess é a função característica do conjunto das propriedades que
todas as princesas têm.
Se q é uma dessas propriedades, o conjunto das princesas está contido no
conjunto das entidades que satisfazem q. A avaliação abaixo restringe essa
consulta a três propriedades do modelo. Apenas laugh é aceita, por isso
o resultado contém somente o nome dessa propriedade.
A sentença Every dwarf defeated a giant contém dois sintagmas quantificados.
Para compor o significado do objeto, começamos pelo determinante a. A função
a p q é verdadeira quando existe uma entidade que satisfaz tanto p quanto
q. Em termos de conjuntos, a interseção entre restrição e escopo deve ser não
vazia.
Depois de receber a propriedade giant, a expressão a giant espera a
propriedade que será fornecida pela relação verbal.
Precisamos distinguir a palavra da gramática, sua interpretação no modelo e a
função usada na composição. O construtor TV.defeated representa a
palavra. A função defeat é a relação binária entre entidades. Já
defeated combinará essa relação com o significado de um sintagma nominal.
O objeto a giant espera uma propriedade, mas a relação de derrotar recebe duas
entidades. Fixando um sujeito y, obtemos a propriedade fun z => defeat y z.
Aplicar o objeto a essa propriedade verifica se y derrotou algum gigante.
Abstraindo sobre y, obtemos a propriedade denotada por defeated a giant.
A avaliação lista as entidades que têm essa propriedade. O resultado, [B, R],
contém precisamente os dois anões do modelo.
Para completar a sentença, aplicamos every dwarf à propriedade
defeated (a giant). O cálculo verifica se cada anão derrotou algum gigante.
As duas avaliações diferem apenas na presença dos parênteses e realizam a mesma
aplicação de funções.
Nessa composição, o objeto está no escopo do sujeito. O gigante pode variar
conforme o anão. A leitura em que um único gigante está no escopo mais amplo
exigiria outra composição.
9.2.2. Condições sobre as Relações Quantificadoras🔗
Nem toda relação entre conjuntos se comporta como um quantificador de
quantidade. Usaremos três condições para delimitar essa noção: a extensão, EXT,
a conservatividade, CONS, e a invariância por isomorfismo, ISOM. Cada uma exclui
um tipo de dependência, que veremos em many, em only e no possessivo
Alice's. Chamaremos de quantificadores as relações que satisfazem as três
condições.
Para enunciar e provar as condições, usamos proposições sobre conjuntos. O tipo
GQ.Det α abrevia Set α → Set α → Set α → Prop. Em D E A B, E é o
universo, A é a restrição e B é o escopo. Como o tipo não impõe inclusões
entre esses conjuntos, as condições recebem explicitamente as hipóteses A ⊆ E
e B ⊆ E. A categoria sintática DET e o tipo GQ.Det têm funções
distintas: a primeira representa palavras, e o segundo permite representar
relações semânticas, inclusive as que não satisfazem as condições de
quantificador.
A relação GQ.all expressa a inclusão da restrição no escopo. Ela
corresponde à função every quando representamos cada propriedade pelo
conjunto das entidades em que ela é verdadeira.
O teorema estabelece essa correspondência nas duas direções. A prova usa
mem_entities, que garante que toda entidade do tipo Entity
aparece na lista usada pela avaliação de every.
Em Quantificação vimos que, sem a pressuposição
existencial, "todo A é B" não implica "algum A é B". Prove as duas coisas: a
subalternação vale quando A tem um elemento, e falha em geral.
A condição EXT compara universos E e E' com E ⊆ E'. Se a restrição e o
escopo já estão contidos em E, aumentar o universo não deve mudar o valor da
relação. Podemos, portanto, considerar apenas um universo que contenha A ∪ B.
A condição CONS compara D E A B com D E A (A ∩ B). Ela permite descartar
todos os elementos do escopo que estão fora da restrição. Depois dessa redução,
as regiões relevantes são os A que satisfazem B e os A que não satisfazem B.
As relações GQ.all e GQ.some satisfazem EXT e CONS. Para EXT, as
provas usam rfl, pois ambas as definições ignoram o argumento do universo. Os
dois lados da equivalência são, assim, a mesma proposição.
Para CONS, a inclusão A ⊆ B equivale a A ⊆ A ∩ B. No caso existencial, um
elemento pertence simultaneamente a A e B exatamente quando pertence a A e
a A ∩ B. As provas abaixo explicitam essas duas correspondências.
Uma leitura de many pode depender do tamanho do universo. Vamos representar
uma versão simples em que «muitos A são B» significa que os elementos de A ∩ B
são mais da metade dos elementos de E. Ao aumentar E sem alterar A e B,
a relação pode deixar de valer, violando EXT.
Usamos Set.ncard para expressar as cardinalidades finitas.
Em Only dwarfs sing during work, todos os que cantam durante o trabalho devem
ser anões. A relação GQ.only exige, portanto, B ⊆ A.
Exercício★★(only-not-cons)
Prove que only não é conservativo. Basta escolher uma restrição e um escopo
para os quais as duas leituras da definição de Cons dão resultados
diferentes.
A condição ISOM formaliza a independência em relação à identidade dos elementos.
Se f leva o universo E bijetivamente em E', a relação que vale entre A
e B deve valer entre suas imagens. A notação f '' A denota o conjunto dos
valores f x com x ∈ A, e Set.BijOn expressa a bijeção entre os
universos.
Com EXT, CONS e ISOM, uma relação sobre conjuntos finitos depende somente das
quantidades nas regiões A - B e A ∩ B. Isso inclui artigos. A tem a
condição existencial de some. Na leitura de Russell, the exige que A tenha
um único elemento e que ele pertença a B, isto é, |A-B|=0 e
|A\cap B|=1.
Na leitura de Verificação de Modelos com Lógica de Primeira Ordem, The dwarf laughed diz
que há exatamente um anão e que ele riu. Como relação entre conjuntos,
the E A B diz que A tem um único elemento e que ele está em B. Mostre que
the satisfaz EXT, CONS e ISOM. Assim, o artigo the é, no sentido técnico
desta seção, um quantificador.
O possessivo Alice's, como em Alice's daggers are sharp, ocupa a posição de
um determinante: poss owns a A B diz que todo A que a possui é B. A
relação de posse owns é um parâmetro. Mostre que poss satisfaz EXT e CONS,
mas não ISOM. Assim, EXT e CONS não bastam para fazer de um determinante
um quantificador.
Dica: para ISOM, basta um exemplo pequeno em Bool, em que false
possui só true, e a bijeção not.
Para representar os casos finitos, escrevemos m=|A-B| e n=|A\cap B|. O
par (m, n) descreve quantos elementos da restrição deixam de satisfazer o
escopo e quantos o satisfazem. As condições estudadas permitem ignorar o
restante do universo e a identidade dos elementos.
Organizamos esses pares em uma árvore de linhas. Na linha k, a restrição tem
k elementos e, portanto, m + n = k. Da esquerda para a direita, diminuímos
m e aumentamos n. A posição (1, 2) da linha três, por exemplo, representa
uma restrição com três elementos, dos quais dois satisfazem o escopo. A função
row enumera as posições de uma linha.
A função tree k reúne as linhas de zero até k. Cada linha acrescenta os
casos para mais um tamanho de restrição. A árvore matemática tem infinitas
linhas, mas sua representação por uma lista do Lean é finita. O parâmetro k
fixa o trecho que queremos examinar ou desenhar.
Para desenhar a árvore, transformamos cada par em um texto. A função
labelTree k cell aplica cell aos dois números de cada posição, e
drawTree w distribui os textos em linhas, usando a largura w para calcular o
recuo.
A função numberTree escreve o próprio par em cada posição. Até a linha nove,
os dois números têm um algarismo cada e, separados por vírgula, cabem na largura
de três caracteres usada no desenho.
Um quantificador numérico seleciona as posições em que é verdadeiro. A função
patternTree usa a mesma organização da árvore numérica, mas escreve + para
uma posição aceita e - para uma posição recusada. Chamamos esse desenho de
padrão do quantificador.
Os exemplos mostram três condições sobre as contagens.
At least three exige n ≥ 3, less than half exige
2 * n < m + n, e an even number of exige que n seja par. A comparação dos
desenhos permite observar como cada condição seleciona regiões diferentes da
árvore.
Também podemos dar um quantificador como uma função que recebe uma lista de
objetos e uma propriedade. O tipo ListQuant usa naturais como objetos para que
possamos montar universos de teste. As funções List.all e
List.any verificam se todos ou algum dos elementos da lista satisfazem a
propriedade.
Essa apresentação toma a própria restrição como universo da consulta, usando as
reduções permitidas por CONS e EXT.
abbrevListQuant:=ListNat→(Nat→Bool)→Bool
Exercício★★(gen-tree)
Defina genTree q k, a lista dos pares (m, n) de tree k para os quais q
é verdadeiro num universo de m + n objetos dos quais exatamente n têm a
propriedade. Por exemplo, (0, 3) está na lista de List.all, porque se
todos os A são B, os 3 objetos de um A de 3 objetos têm a propriedade B.
9.2.4. Representações Lógicas para Quantificadores🔗
Os padrões podem ser descritos diretamente por expressões aritméticas nas duas
contagens. O tipo NumQuant dá nome às funções Nat → Nat → Bool, já usadas
como argumento de patternTree. Um valor desse tipo decide quais pares
pertencem ao padrão.
Por exemplo, all exige m = 0, no exige n = 0,
at least k exige n ≥ k, e at most k exige n ≤ k.
As definições abaixo permitem combinar e estudar essas condições sem construir
conjuntos ou listas de entidades a cada consulta.
A função toNum constrói uma representação numérica a partir de um
ListQuant. Para cada par (m, n), fornece à função uma lista dos
naturais de um até m + n e a propriedade «ser menor ou igual a n». Nessa
lista, exatamente n elementos têm a propriedade.
Se a função representa um quantificador invariante por isomorfismo, essa
consulta depende apenas das contagens. As igualdades abaixo comparam os padrões
de List.all e de sua condição numérica, bem como os de no, até a linha
cinco.
Podemos formar quantificadores compostos aplicando operações lógicas a seus
valores em cada posição. A negação troca + por - e - por +. A conjunção
aceita uma posição quando os dois quantificadores a aceitam, e a disjunção a
aceita quando pelo menos um deles a aceita.
A expressão at least three but not all combina n ≥ 3 com a negação de
m = 0. Seu padrão conserva as posições de
at least three que ficam fora da borda direita da árvore.
As funções notNum, andNum e orNum implementam essas operações.
Defina someNum, notAllNum e exactlyNum k, as expressões de some,
not all e exactly k. Use patternTree para ver os padrões de all, some,
no e not all, e os de at least three, at most three e exactly
three. Depois, prove as relações entre eles: some é a negação de no,
not all é a negação de all, exactly k é a conjunção de at least k e
at most k, e at most k é a negação de at least k + 1.
Dica: depois de funext m n, rw [Bool.eq_iff_iff] transforma a igualdade
entre dois Bool numa equivalência entre proposições. Em seguida, simp
com as definições simplifica a meta, e omega resolve o que sobrar de
aritmética.
Como quantificadores são relações entre conjuntos, podemos perguntar se são
reflexivos, simétricos ou monótonos. Cada propriedade pode ser enunciada para as
relações de tipo GQ.Det e estudada nos padrões numéricos
correspondentes.
A reflexividade exige que Q A A valha para toda restrição A. Isso vale para
all, pois todo conjunto está contido em si mesmo. Para some, a interseção de
A consigo mesmo precisa ter um elemento.
Na consulta Q A A, nenhum elemento da restrição fica fora do escopo. Logo,
m = 0, e a posição correspondente é (0, |A|). Variando o tamanho da
restrição, percorremos a borda direita da árvore. Um quantificador reflexivo tem
+ em toda essa borda, incluindo o topo (0, 0).
O topo é o caso da restrição vazia. O padrão de all o aceita, enquanto o de
some o recusa. A definição ReflNum expressa a condição da borda por uma
proposição sobre funções numéricas.
Not all é irreflexivo: sua borda direita é toda -. No não é: o topo,
com A vazio, é +, porque "nenhum A é A" é verdadeiro. E o resto da borda é
-, então no não é reflexivo nem irreflexivo.
Uma relação quantificadora é simétrica quando trocar restrição e escopo conserva
seu valor. Some é simétrico porque a existência de um elemento em A ∩ B
também garante um elemento em B ∩ A. Assim, Alguma menina riu tem o mesmo
valor de verdade que
Alguém que riu era menina.
A troca altera o significado de all. Toda princesa riu permite que outras
pessoas também tenham rido; Todos os que riram eram princesas exige que não
haja essas outras pessoas. As avaliações mostram a diferença no modelo.
A simetria também ajuda a estudar as construções existenciais do inglês. Nos
exemplos considerados aqui, There are some dwarfs,
There are no dragons e There are three wizards aceitam
quantificadores simétricos. As leituras existenciais neutras de
There are all dwarfs e There are most dragons não apresentam
a mesma aceitabilidade. Usaremos esse contraste como uma aplicação da análise
relacional dos quantificadores.
A monotonicidade no escopo descreve o que acontece quando variamos B,
mantendo a restrição. Um quantificador é MON↑ se uma consulta verdadeira
permanece verdadeira quando o escopo aumenta. Se todos os A pertencem a B,
também pertencem a qualquer conjunto que contenha B. O mesmo crescimento
preserva some e
at least three.
Um quantificador é MON↓ se a verdade é preservada quando o escopo diminui. Se
nenhum A pertence a B, nenhum pertence a um subconjunto de B. Essa propriedade
vale para no e para not all. As definições abaixo enunciam os dois sentidos
sobre conjuntos.
Compare os padrões de all e de at least three, que são MON↑. Que forma tem o
padrão de um quantificador MON↑? E o de um MON↓?
Show solution
Acrescentar a B um elemento de A tira esse elemento de A - B e o põe em
A \cap B: a posição passa de (m + 1, n) para (m, n + 1), uma casa à
direita na mesma linha. Então, num padrão MON↑, à direita de um + na mesma
linha só há +. Num padrão MON↓, o mesmo vale à esquerda.
As definições MonUpNum e MonDownNum escrevem essas formas como proposições
sobre NumQuant.
O padrão de an even number of alterna entre + e - nas linhas. Acrescentar
ou retirar um elemento do escopo pode mudar a paridade.
A monotonicidade também permite estudar contrastes linguísticos. Em all men and
some women, a coordenação reúne dois sintagmas MON↑. Em many English but no
Dutch, a conjunção but marca um contraste entre orientações de inferência.
Expressões como any e lift a finger são itens de polaridade negativa. Um
escopo MON↓ pode licenciá-las, como em
No dwarf liked any of the elves. A troca por Every dwarf
retira esse ambiente decrescente e torna a leitura pretendida inaceitável. Esses
contrastes motivam o estudo da monotonicidade, sem esgotar as condições
linguísticas de licenciamento.
Há também contrastes associados à polaridade positiva.
Some people could hardly believe it é aceitável na leitura
considerada, enquanto Nobody could hardly believe it é marcada como
inaceitável nessa mesma leitura. A comparação muda a orientação do sintagma que
toma a expressão em seu escopo.
Exercício★★(mon-not)
Prove que a negação troca MON↑ por MON↓, e MON↓ por MON↑.
Mostre que, combinando um quantificador MON↑ com um MON↓, nada se pode garantir:
nem a conjunção nem a disjunção são sempre MON↑ ou MON↓.
Dica: para a conjunção, use at least one e at most three; para a disjunção,
at least three e at most one. Antes de provar, desenhe os padrões da
conjunção e da disjunção com patternTree.
Também podemos variar a restrição e manter o escopo. Um quantificador é ↑MON se
a verdade é preservada ao aumentar A, e ↓MON se é preservada ao diminuir A.
Some e not all são crescentes na restrição; all e no são decrescentes
nela.
Por exemplo, se algum A é B, aumentar A conserva esse elemento. Se todo A é B,
restringir A conserva a inclusão. Na árvore, acrescentar um elemento a A aumenta
n quando ele está em B e aumenta m quando está fora de B.
A orientação na restrição também aparece em fenômenos de polaridade.
All dwarfs who liked any of the elves were mistrusted coloca
a oração relativa em uma restrição decrescente. A substituição de all por
some altera essa orientação e o licenciamento pretendido de any.
Exercício★★(left-mon-pattern)
Defina UpMonNum q e DownMonNum q, as formas do padrão de um quantificador
↑MON e de um ↓MON. Depois, prove que some e not all são ↑MON, e que
all e no são ↓MON.
Dica: acrescentar um elemento a A aumenta em um n, se o elemento está em
B, ou m, se não está.
9.2.6. Quantificadores, Autômatos e Definibilidade🔗
Podemos registrar uma situação de quantificação como uma palavra sobre o
alfabeto binário. Percorremos os elementos de uma lista que representa A e
escrevemos 1 quando satisfazem B e 0 quando não satisfazem. No código, esses
símbolos são os valores booleanos true e false. Para que as contagens
representem cardinalidades, a lista deve enumerar os elementos de A sem
repetições, como ocorre nos exemplos obtidos de entities.
A função wordOf produz a palavra. A função accepts conta zeros e uns e
consulta o quantificador numérico nessa posição. A linguagem langOf q reúne
todas as palavras aceitas por q. Usamos LanguageBool, do Mathlib,
para representar esse conjunto de palavras e suas operações.
No exemplo com as meninas do modelo, a palavra contém dois zeros e dois uns. Por
isso, All girls laughed é falsa e
Some girl laughed é verdadeira.
Reordenar os elementos conserva as duas contagens. O teorema abaixo usa
List.Perm.count_eq para mostrar que uma permutação de uma palavra aceita
também é aceita. A linguagem de um quantificador numérico é, portanto, fechada
por permutação, refletindo nas palavras a independência da identidade dos
elementos.
As operações lógicas sobre quantificadores também se expressam nas linguagens
que eles aceitam. Negar um quantificador aceita exatamente as palavras que ele
recusava. Assim, a linguagem de notNum é o complemento, indicado por ᶜ,
da linguagem original.
O teorema verifica essa correspondência palavra por palavra.
O quantificador all exige que a palavra não contenha nenhum zero. Suas
palavras são sequências de uns, incluindo a palavra vazia. Essa linguagem é o
fecho de Kleene da linguagem formada apenas pela palavra [true].
A notação ∗ permite concatenar zero ou mais palavras da linguagem.
Um autômato que aceita exatamente a linguagem de um quantificador computa esse
quantificador nas palavras que representam as situações. Como a decisão depende
somente das contagens, a linguagem aceita deve ser invariante por permutação.
Para quantificadores sobre conjuntos finitos, a caracterização de van Benthem
relaciona a definibilidade em primeira ordem a autômatos finitos invariantes por
permutação cujo grafo de transições não tem ciclos entre estados distintos.
Laços de um estado para ele mesmo são permitidos. A lógica considerada usa
apenas igualdade e os predicados da restrição e do escopo, além dos
quantificadores usuais.
Um teste de paridade precisa alternar entre estados de quantidade par e ímpar.
Já most exige comparar quantidades arbitrariamente grandes de zeros e uns, o
que excede a memória de um autômato finito. Esses quantificadores ficam fora
dessa lógica de primeira ordem. Na interpretação direta sobre o modelo finito,
entretanto, podemos implementá-los por funções que calculam as contagens
necessárias.