3
Lista de exercícios #1 Lógica para ciência da computação Conectivos proposicionais: ~ → ↔ ∧∨ Símbolo de implicação semântica: Símbolo de equivalência semântica: Função interpretação: I Contradomínio de I: { V, F } Convenção: na elaboração da tabela verdade, usar { V, F }, nessa ordem. NÃO USAR { 0, 1 } NEM { T, F } 1 - Qual o comprimento das fórmulas abaixo? a) P Q b) ~ ( P → Q ) ↔( R S) c) ( ~ P ~ Q) ↔ ~ ( P Q ) d) ( A ( B ( C D ) ) ) ( ~ A ( ~ B ( C D ) ) ) 2 - Indique o conjunto de subfórmulas das fórmulas da questão anterior. 3 - Dentre as concatenações de símbolos a seguir, quais são fórmulas bem formadas e quais não são? a) P → true b) P → ( ( Q → R ) → ( ( P → R ) → ( P → R ) ) ) c) ( ( P → ~ P ) ↔ ~ P ) Q d) ( P Q ) → ( ( Q ↔ ~ P ) ~ ~ R ) e) ~ ~ P f) Q g) ( P Q ) → ( Q ↔ R ) h) P ~ → Q 4 - O que se pode concluir: a') sobre I ( P Q ) se I ( P ) = V? R: I ( P Q ) = V b') sobre I ( P Q ) se I ( P ) = F? R: Nada se pode concluir. c') sobre I ( P Q ) se I ( Q ) = V? R: Nada se pode concluir. d') sobre I ( P Q ) se I ( Q ) = F? R: I ( P Q ) = F e') sobre I ( P → Q ) se I ( P ) = V? R: Nada se pode concluir. f') sobre I ( P ↔ Q ) se I ( P ) = V? R: Nada se pode concluir. a) sobre I ( P Q ) se I ( P ) = V b) sobre I ( P Q ) se I ( P ) = F c) sobre I ( P Q ) se I ( Q ) = V d) sobre I ( P Q ) se I ( Q ) = F e) sobre I ( P → Q ) se I ( P ) = F f) sobre I ( P → Q ) se I ( Q ) = V g) sobre I ( P → Q ) se I ( P ) = V h) sobre I ( P ↔ Q ) se I ( Q ) = F

lista de exercicios, lógica para computação

Embed Size (px)

DESCRIPTION

Lista de exercícios de lógica para computação

Citation preview

  • Lista de exerccios #1

    Lgica para cincia da computao

    Conectivos proposicionais: ~ Smbolo de implicao semntica: Smbolo de equivalncia semntica: Funo interpretao: IContradomnio de I: { V, F }

    Conveno: na elaborao da tabela verdade, usar { V, F }, nessa ordem. NO USAR { 0, 1 } NEM { T, F }

    1 - Qual o comprimento das frmulas abaixo?a) P Qb) ~ ( P Q ) ( R S)c) ( ~ P ~ Q) ~ ( P Q ) d) ( A ( B ( C D ) ) ) ( ~ A ( ~ B ( C D ) ) )

    2 - Indique o conjunto de subfrmulas das frmulas da questo anterior.

    3 - Dentre as concatenaes de smbolos a seguir, quais so frmulas bem formadas e quais no so?

    a) P trueb) P ( ( Q R ) ( ( P R ) ( P R ) ) )c) ( ( P ~ P ) ~ P ) Qd) ( P Q ) ( ( Q ~ P ) ~ ~ R ) e) ~ ~ Pf) Qg) ( P Q ) ( Q R )h) P ~ Q

    4 - O que se pode concluir:a') sobre I ( P Q ) se I ( P ) = V? R: I ( P Q ) = Vb') sobre I ( P Q ) se I ( P ) = F? R: Nada se pode concluir.c') sobre I ( P Q ) se I ( Q ) = V? R: Nada se pode concluir.d') sobre I ( P Q ) se I ( Q ) = F? R: I ( P Q ) = Fe') sobre I ( P Q ) se I ( P ) = V? R: Nada se pode concluir.f') sobre I ( P Q ) se I ( P ) = V? R: Nada se pode concluir.

    a) sobre I ( P Q ) se I ( P ) = Vb) sobre I ( P Q ) se I ( P ) = Fc) sobre I ( P Q ) se I ( Q ) = Vd) sobre I ( P Q ) se I ( Q ) = Fe) sobre I ( P Q ) se I ( P ) = Ff) sobre I ( P Q ) se I ( Q ) = Vg) sobre I ( P Q ) se I ( P ) = Vh) sobre I ( P Q ) se I ( Q ) = F

  • 5 - Seja I uma interpretao tal que I ( P Q ) = V. O que se pode concluir: a) sobre I ( ~ P Q )b) sobre I ( P ~ Q )c) sobre I ( P Q )d) sobre I ( ( P R ) ( Q R ) ) e) sobre I ( ( P R ) ( Q R ) )

    6 - Responda o exerccio anterior considerando que I ( P Q ) = F.

    7 - Mostre se os conjuntos de frmulas a seguir so satisfatveis ou insatisfatveis:a) { (P Q), (P Q) } b) { (P Q), (P Q) }c) { (P Q), (P Q) }d) { (P Q), (P ~ Q) }

    8 - Sejam H e G as frmulas indicadas a seguir. Identifique, justificando sua resposta, os casos em que H implica G.

    a) H = P Q, G = P.b) H = P Q, G = P.c) H = P ~ Q, G = false.d) H = false, G = P.e) H = P, G = true.

    9 - Demonstre (sem pular nenhum passo) ou d um contra-exemploa) H satisfatvel ~H satisfatvelb) H no satisfatvel H contraditriac) H satisfatvel H no contraditriad) H contraditria ~H tautologiae) H no tautologia H contraditriaf) H tautologia ~H contraditriag) H tautologia H satisfatvelh) H implica G ( H G ) tautologiai) H equivale a G ( H G ) tautologia

    10 - Demonstre se as frmulas a seguir so tautologias usando o mtodo da tabela verdade e o da rvore semntica.

    a) H = ( P Q ) ( ~P Q )b) H = ~ ( P Q ) ( ~P Q )c) H = ( ~ P ~ Q ) ~ ( P ~ Q )d) H = ( P ~ Q ) ( ~ P ~ Q )

    11 - Demonstre, sem pular nenhum passo, usando as regras de interpretao de frmulas.a) I ( P Q ) = F I ( ~ P Q ) = Fb) I ( P Q ) = V I ( ~ P Q ) = Vc) I ( P Q ) = V I ~ ( P ~ Q ) = Vd) I ( ~ P ~ Q ) = V I (~ ( ~ P Q )) = V

  • 12 - Demonstre por absurdo se as frmulas a seguir so ou no tautologias.a) ( P Q ) ( ~ P Q ) b) ( P Q ) ( ~ P Q ) c) ( P Q ) ( P ~ P ) d) ~ ( ~ H ) He) ~ ( H G ) ( ~ H G )f) ( ( H G ) ( G H ) ) ( H H )g) ( ( H G ) ( G H ) ) ( H H )h) H ( H G )