Skip navigation

Monthly Archives: setembro 2014

Atribuição de Significado a um Símbolo (ou objeto) Sintático

A (P ^ Q), o significado está intrinsicamente ligado à interpretação atribuída aos símbolos P e Q.

Assim, I[(P^Q)] = I[P] ^ I[Q]

Nesse caso, a Interpretação nos trará os valores (lógicos) referentes à sentença e ao contexto.

Esses valores podem assumir duas propriedades, já vistas nas aulas anteriores: Verdadeiro (T) ou Falso (F)

É possível representar fatos como:

“Meu Tio Mora em São Paulo”

Mas não como:

“Essa Sentença é Falsa” (paradoxo de Epimênides)

Esse último, devido à auto-referência, é representado por outra competência da lógica, mas não pela preposicional.

Na língua portuguesa podemos ter mais de um significado (ou interpretação) para uma sentença
Na lógica proposicional há apenas um significado (ou interpretação) e ela se resume a um valor de Verdadeiro ou a um valor de Falso

A interpretação dos símbolos da lógica é definida a seguir:

Função Binária: Uma função é dita binária se seu contradomínio possuir apenas dois elementos
Interpretação: Uma interpretação I na lógica preposicional é uma função binária tal que:
O domínio de I é constituido pelo conjunto das fórmulas da lógica proposicional
O contradomínio de I é o conjunto formado pelos valores verdade {T,F}
Os valores dos símbolos de verdade (true, false) recuperados através da interpretação I[true]=T e I[false]=F
Dado um símbolo proposicional P, então I[P] pertence a {T,F}
Interpretação de Fórmulas

Fórmulas: Símbolos do alfabeto concatenados utilizando-se uma regra específica
Interpretação das Fórmulas é obtida através da interpretação desses símbolos
Procedimentos para se interpretar fórmulas:
Definição de Interpretação de fórmulas:
Dada uma fórmula E e uma interpretação I, o significado de E, indicado por I[E] é obtido através das seguintes regras:
se E=P, onde P é um símbolo proposicional, então I[E]=I[P] e I[P] pertence a {T,F}
se E=true, então I[E]=I[true]=T. Se E=false, então I[E]=I[false]=F
seja H uma fórmula. Se E=(¬H), então
I[E]=I[(¬H)]=T se I[H]=F
I[E]=I[(¬H)]=F se I[H]=T
Sejam H e G duas fórmulas. Se E=(HvG), então
I[E]=I[(HvG)] = F se I[H]=F e I[G]=F
I[E]=I[(HvG)] = T se I[H]=T e/ou I[G]=T
Sejam H e G duas fórmulas. Se E=(H^G), então
I[E]=I[(H^G)] = T se I[H]=T e I[G]=T
I[E]=I[(H^G)] = F se I[H]=F e/ou I[G]=F
Sejam H e G duas fórmulas. Se E=(H→G), então
I[E]=I[(H→G)]=T se I[H]=F e/ou I[G]=T
I[E]=I[(H→G)]=F se I[H]=T e I[G]=F
Sejam H e G duas fórmulas. Se E=(H←→G), então
I[E]=I[(H←→G)]=T se I[H]=I[G]
I[E]=I[(H←→G)]=T se I[H]<>I[G]
As regras semânticas determinam o significado de (H^G) a partir de I[H] e I[G], não a partir de I[^], que seria o significado do conectivo ^
Na lógica proposicional não existe o significado dos conectivos isoladamente
Para simplificar o significado de (H^G) é denotado o significado de ^.
As regras semânticas também são apresentadas em tabelas, denominadas tabela verdade
Considere H e G fórmulas da lógica proposicional, a tabela a seguir apresenta o significado das formulas obtidas através do processo de construção e dos conectivos utilizando essas duas fórmulas

(apresentar a tabela verdade separada dos símbolos considerando o significado da interpretação das fórmulas)

H G ¬H ¬G (HvG) (H^G) (H→G) (H←→G)
F F T T F F T T
F T T F T F T F
T F F T T F F F
T T F F T T T T

Exemplo: Tabela verdade da fórmula:

(((¬P)vQ)→(PvQ))

Explicar a causalidade e a semântica do conectivo →, indicando que não há necessariamente a causalidade do elemento antecedente ao consequente.
Ex:
(H)=O sol é redondo
(G)=A mídia é imparcial

Interpretações podem ser limitadas:

Considere:

E=(((¬P)^Q) → (RvP))

I[P]=T ,I[Q]=F , I[R]=T
J[P]=F ,J[Q]=T , J[R]=F

Assim, I interpreta E (I[E]) diferentemente de J (J[E])

*** Demonstrar utilizando tabela ***

(Exercícios Capitulo 2)

+ Alfabeto
– Símbolos Proposicionais
P, Q, R, P1, Q1, R1, P2, Q2, R2, …
– Símbolos de Pontuação
(  )
– Símbolos de Verdade
True, False
Verdadeiro, Falso
– Conectivos Lógicos
v  ou Disjunção (também encontrada com o símbolo + )
^ ou Conjunção (também encontrada com o símbolo . )
¬ ou negação (não)
→ também conhecido como implicação ou se-então
←→  também conhecido como “iff”, “se e somente se” ou bi-implicação

+ Fórmulas

– Conjunto de símbolos do alfabeto da lógica proposicional concatenados seguindo um conjunto específico de regras:
– Todo Símbolo de Verdade é uma Fórmula
– Todo Símbolo proposicional é uma fórmula
– Se H é uma fórmula, (¬H) (a negação de H) é uma fórmula
– Se H e G são fórmulas, então (HvG) (a disjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H^G) (a conjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H→G) é uma fórmula e é dito que H é o antecedente e G é o consequente da fórmula
– Se H e G são fórmulas, então (H←→G) é uma fórmula e é dito que H é o lado (ou componente) esquerdo e G é o lado (ou componente) direito da fórmula

Cada item acima define uma regra para a construção de fórmulas.
Observe a obrigatoriedade do uso dos símbolos de pontuação ( e )

Exemplos de Fórmulas

P
Q
True

(PvQ)
((PvQ)→True)

Símbolos de pontuação
– São utilizados para eliminar ambiguidades nas fórmulas
– Quando não há possibilidade de ambiguidade tais símbolos podem ser omitidos
– Ambiguidade surge devido à precedência dos operadores (conectivos lógicos) na álgebra de boole
Ordem de precedência (maior para menor):
¬
→, ←→
v,^

Exemplo de Ambiguidade:

PQ←→R

Pode ser interpretada como

(P→(Q←→R)) ou ((P→Q)←→R)

Pode-se utilizar várias linhas para eliminar ambiguidade:

P→Q
←→
R

Não se considera o significado dos símbolos. A manipulação é puramente simbólica e avalia-se o  relacionamento entre eles

+ Comprimento de uma Fórmula

Comp(H) define-se como:

– Se H é um símbolo de verdade ou um símbolo preposicional, então Comp[H]=1
– Se H é um símbolo de verdade, então Comp[¬H] = Comp[H]+1
– Se H e G são fórmulas, então Comp[HvG]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H^G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H→G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H←→G]=Comp[H]+Comp[G]+1

Lógica Proposicional: Sintaxe e Semântica. Álgebra de Boole. Portas Lógicas. Circuitos Lógicos.

BIBLIOGRAFIA BÁSICA
NUNES DE SOUZA, J. Lógica para Ciência da Computação. 1ª ed. São Paulo: Elsevier, 2002.
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação. 5ª ed. Rio de Janeiro: LTC, 2004.
MENEZES, P.B.; Matemática discreta para Computação e Informática. Porto Alegre, Sagra-Luzzatto. Instituto de Informática da UFRGS, Série Livros Didáticos, número 16, 2004.
BIBLIOGRAFIA COMPLEMENTAR
Daghlian, Jacob. Lógica e álgebra de Boole. São Paulo: Atlas, 1995.
SKVARCIUS, Romualdes; ROBINSON, William B.. Discrete Mathematics with Computer Science Applications. Redwood City: Benjamin/Cummings, 1986.
EVARISTO, Jaime. Introdução à álgebra com aplicações à ciência da computação.EdUFAL, 1999.
SCHEINERMAN, E.R.. Matemática discreta: uma introdução. São Paulo. Thomson Learning
Ltda. 2003.
SCHEINERMAN, Edward R.: Matemática Discreta Uma Introdução. Thomson Pioneira, 2003.
BEZERRA, L.H; BARROS, P.H.V.; TOMEI. C.; WILMER, C.; Introdução à Matemática. Florianópolis. Editora da UFSC, 1995.

Olá alunos.

 

Como uma ferramenta de comunicação entre eu e vocês, esse espaço está destinado a agregar as notas de sala de aula e conteúdos de exercícios ou fontes de informação e pesquisa que vocês poderão usar, bem como artigos que julgar interessante para auxiliar nas disciplinas que vocês cursam.

Espero que façam bom proveito e bons estudos.

 

Prof. MSc. Rodrigo de Godoy Domingues