Exercios 1 logica pra ciencia da computação

1º Trabalho - Lógica Proposicional

1. Considere as concatenações de símbolos do alfabeto da Lógica Proposicional dadas a seguir. Identifique aquelas que são fórmulas da Lógica Proposicional.

a) (PQ  true)

Não é uma fórmula, pois dois símbolos proposicionais não podem estar juntos sem o uso de conectivos.

b) (P  Q)  ((Q  P)   R)

Apesar de ter duas negações juntas, esta é uma fórmula, pois o símbolo de negação, é o único que pode vir acompanhado de outro símbolo de mesma classe.

c) Q

Não é uma fórmula, pois os conectivos conectam dois símbolos proposicionais ou subfórmulas.

d) (P Q)  ((Q  R))

Apesar de um jogo de parênteses a mais desnecessariamente, é uma fórmula.

2. Responda as questões a seguir:

a) Existem fórmulas sem símbolos de pontuação? Dê exemplos.

Sim.

P Q

P  Q

PQ

b) Quantos tipos de símbolos possui o alfabeto da Lógica Proposicional? Quais são estes símbolos?

Infinitos. Símbolos de pontuação: ( e ); símbolos de verdade: true e false; Símbolos proposicionais: P, Q, R, S, P¹, Q¹,R¹, S¹, P², Q²(...).

c) Qual a diferença entre sintaxe e semântica?

Sintaxe é aescrita/estrutura da fórmula e semântica é o significado de cada símbolo.

3. Seja I uma interpretação e a fórmula H = (P  Q).

a) Se I[H] = T, o que se pode concluir a respeito de I[P] e I[Q]?

Conclui que P implica - se então - em Q.

Ex: (P= está chovendo Q=a rua está molhada ) Então:

Se está chovendo, então a rua está molhada.

b) Se I[H] = T e I[P] = T, o que se pode concluir a respeito de I[Q]?

Sabendo que algo falso não pode originar de algo verdadeiro, conclui que I[Q] é T.

c) Se I[Q] = T, o que se pode concluir a respeito de I[H]?

A I[H] é verdadeira. Pois como sabemos que I[Q]=T, se I[P] = T, teremos duas verdades tornando I[H]=T; se I[P]=F, a I[H] também será verdadeira, pois podemos obter qualquer resultado de um antecedente falso.

d) Se I[H] = T e I[P] = F, o que se pode concluir a respeito de I[Q]?

Pode-se concluir que I[Q] pode ser tanto T como F; pois, se for T, podemos obter qualquer resultado de um antecedente falso, tornando assim a I[H]=T, porém, se I[Q]=F, teremos duas falsidades, então obteremos uma verdade.

e) Se I[Q] = F e I[P] = T, o que se pode concluir a respeito de I[H]?

Conclui-se que I[H] é falsa, pois não podemos ter uma falsidade com antecedente verdadeiro.

4. Seja I uma interpretação tal que: I[P  Q] = T. O que sepode deduzir a respeito dos resultados das interpretações a seguir?

a) I[P  Q]

b) I[P  Q]

Deduz que as duas afirmações são falsas.

5. Determine a tabela