Lsita 3 Logica

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Universidade Federal dos Vales do Jequitinhonha e Mucuri - UFVJM
Faculdade de Ciências Exatas – FACET
Departamento de Matemática e Estatística - DME
Introdução a Lógica Computacional (Sistemas de Informação)
Profa. Josiane Magalhães Teixeira
Exercícios – Lista 3
Questão 01. Seja I uma interpretação sobre o conjunto dos números naturais (N), tais que:
I [a] = 4	 I[x] = 1
I [ p (x) ] = T  xI < 9
I [r(x)] = T  xI é par.
I [f(x,y)] = xI - yI
Determine a interpretação da fórmula H e G a seguir.
	H = ((∀x)p(x) ^ r(x)) → (∃x) ~p(x)
	G = ~ (p(a) v (∃x)r(x))
	M = ~ ( ~ ( r (f (a ,1))) ↔ p (x+1) )
	G1= ((∀x)p(x) → r(x)) ↔ ((∃x)p(x) →(∀a)r(a))
Questão 02. Considere o conjunto dos números reais R e I uma interpretação sobre este domínio, tal que:
I[ a ] = 0 I[ q( x , y ) ] = T  xI < yI	 I[ p (x) ] = T  xI é um número primo
I [ x ] = 2	I [ y ] = 5	I [ z ] = 3 I[ r( x , y ) ] = T  xI = yI I [ f ] = produto.
Determine a interpretação das fórmulas a seguir:
	( q ( x , y ) → r ( f ( a , x ), a ) ) v p( x )
	(∀x)( ∃y)( q ( x , y ) ^ p ( y ))
	(∀x)( ∀y)( ~ r( x , a ) → r ( f ( x , z ) , y ) )
Questão 03. Sendo H = ~(∃y)p(y) e G = (∀y)~p(y) é correto afirmar que tais fórmulas sempre terão as mesmas interpretações? Justifique.
Questão 04. Para as duas fórmulas a seguir demonstre se são tautologia ou não. Justifique sua resposta em ambos os casos.
	H: (∀x)p(x) → ~(∃x)p(x)
	G: (∃x)q(x,y) v q(x,x)
Questão 05. Sejam H e G duas fórmulas da lógica de predicados. Demonstre que:
Se Objeto OLE e Objeto OLE, então E1 equivale a E2.
Questão 06. Sejam H e G duas fórmulas da lógica de predicados. Demonstre que sendo E1 = (∃x)(H v G) e E2 = (∃x)H v (∃x) G então E1 equivale a E2.
Questão 07. O que significa um argumento ser válido quando utilizamos tabela verdade para demonstrar isto? Verifique a validade do argumento a seguir por tal método.
p v ~ q , ~ p , ~ ( p ^ r ) → q ├ r
Questão 08. Utilize regras de inferência e/ou equivalências notáveis para provar a validade dos seguintes argumentos.
	( p v q ) → ~r , s → p, t → q, s v t ├ u v ~ r
	p → q, q → r, r → p, p → ~ r ├ ~ p ^ ~ r
Questão 09. Utilize regras de inferência e equivalências notáveis prove a validade do seguinte argumento.
I) y ≠ 1 ^ y ≥ 1
II) y ≤ 1 → ( y < 1 v y = 1)
III) x = 3 v x > 3
IV) x > 3 → x ≠ y
V) x = 3 → x ≠ y				Q: ~ ( x = y v y ≤ 1)
Questão 10.Utilizando regras de inferência, prova e validde do seguinte argumento:
p → q, p v ( ~ ~ r ^ ~ ~ q), s → ~ r, ~ ( p ^ q ) ├ ~s v ~ q
Questão 11. Seja G uma fórmula na qual a variável x não ocorre livre. Demonstre que o par de formulas a seguir são equivalentes.
Objeto OLE e Objeto OLE