Ciência da Computação first-order-logic
Perguntas com a marcação «first-order-logic»
Recentemente, eu estava pensando sobre a validade da prova por contradição. Eu li nos últimos dias coisas sobre lógica intuicionista e teoremas de Godel para ver se eles me dariam respostas para minhas perguntas. No momento, ainda tenho perguntas pendentes (talvez relacionadas ao novo material que li) e esperava obter …
19 logic first-order-logic propositional-logic incompleteness
Por que a solidez implica consistência?
Eu estava lendo a pergunta Consistência e integridade implicam solidez? e a primeira afirmação diz: Entendo que a solidez implica consistência. O que me deixou bastante intrigado porque pensei que a consistência era uma afirmação mais fraca que a consistência (ou seja, pensei que sistemas consistentes deviam ser sólidos, mas …
12 terminology logic first-order-logic propositional-logic incompleteness
Reescrita de termos; Computar pares críticos
Tentei resolver o exercício a seguir, mas fiquei preso ao tentar encontrar todos os pares críticos . Tenho as seguintes perguntas: Como sei qual par crítico produziu uma nova regra? Como sei que encontrei todos os pares críticos? Seja onde é binário, é unário e é uma constante. ∘ i …
10 logic first-order-logic
Eu pensei que qualquer FOT é um subconjunto de FOL, mas isso não parece ser o caso, porque FOL está completo (todas as fórmulas são válidas ou inválidas), enquanto alguns FOT (como aritmética inteira linear) não estão completos. Então, o FOL é mais expressivo que o FOT? Ou incomparável? Além …
8 logic first-order-logic
Algoritmo para decidir a equivalência alfa de termos em idiomas com ligações
Estou interessado na relação de equivalência alfa em idiomas com ligações variáveis, como: t := x:y 'x belong to y' | bot 'False' | t -> t 'implication' | Ax.t 'forall x, t' Ou o cálculo lambda puro: t := x 'variable' | (t t) 'application ' | Lx.t 'abstraction: …
7 logic lambda-calculus first-order-logic
Por que a VALIDIDADE da lógica de primeira ordem (sem aritmética) é apenas recursivamente enumerável e não recursiva?
A "Complexidade Computacional" de Papadimitriou afirma que VALIDITY, o problema de decidir se uma fórmula de lógica de primeira ordem (sem aritmética) é válida, é recursivamente enumerável. Isso decorre dos teoremas da completude e da solidez, que igualam VALIDITY e THEOREMHOOD, sendo este último o problema de encontrar uma prova …
7 complexity-theory undecidability first-order-logic
Eu tenho lido o excelente livro Representação e Raciocínio do Conhecimento, de Ronald Brachman e Hector Levesque. No início da Seção 3.2 "Vocabulário" do Capítulo 3 "Expressando conhecimento", eles afirmam: Ao criar uma KB (Base de Conhecimento), é uma boa idéia começar com o conjunto de predicados e funções dependentes …
7 terminology logic knowledge-representation first-order-logic reasoning
A resolução está completa ou apenas a refutação concluída?
Passando por alguns tutoriais de representação do conhecimento sobre resolução no momento, deparei-me com o slide 05.KR, no77 . Lá é mencionado que "o procedimento também está completo". Eu acho que essa completude não pode significar que, se uma sentença for envolvida por KB, ela será derivada por resolução. Por …