Buscar

01-LogicaProposicional_Sintaxe

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 16 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 16 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 16 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
Lógica Proposicional
Sintaxe
José Gustavo de Souza Paiva
Lógica Proposicional
• Forma mais simples da lógica
• Fatos do mundo real representados por 
sentenças sem argumento � proposições
• Proposição
– Sentença de qualquer natureza que pode ser 
qualificada como VERDADEIRA ou FALSA
2
Lógica Proposicional
• Exemplos
– 1 + 1 = 2
– 0 > 1
Lógica Proposicional
• Se não é possível definir a interpretação 
(verdadeiro ou falso) da sentença, esta não é
uma proposição
• Exemplos
– Frases Interrogativas
• Qual o seu nome?
– Frases Imperativas
• Preste atenção!
– Paradoxos Lógicos ou ambiguidades
• Esta frase é falsa
• Toda regra tem uma exceção
• Eu vi Carlos com um relógio
3
Lógica Proposicional
• A lógica proposicional preocupa-se 
apenas com o conteúdo e significado das 
sentenças
– João comeu o bolo
– O bolo foi comido por João
OU
– João comeu o bolo
– João comerá o bolo
– João come o bolo
Exercício
• Verifique, justificando, se as expressões 
abaixo são proposições
– Brasília é a capital do Brasil
– Uberlândia fica em Goiás
– 1 + 1 = 2
– 2 + 2 = 3
– x + 1 = 2
– x + y = z
– Leia isto cuidadosamente
4
Exercício
• Verifique, justificando, se as expressões 
abaixo são proposições
– Boa sorte!
– Todas as mulheres possuem sua beleza
– Márcio não é irmão do Mário
– Não faca isso!
– Cecília é escritora
– Quantos japoneses moram no Brasil?
Linguagem
• Representação do conhecimento
• Duas partes
– Sintaxe � símbolos e notações
– Semântica � significado, entendimento
• Definição semelhante à realizada em 
outras linguagens
– Alfabeto
– Palavras
5
Alfabeto
• Conjuntos de símbolos visuais, que produzem o 
que a linguagem quer dizer
• Alfabeto da lógica proposicional
– Símbolos de pontuação
• (; )
– Símbolos de verdade
• true, false
– Símbolos proposicionais 
• P; Q; R; S; P1; Q1; R1; S1; P2; Q2; ...
– Conectivos proposicionais:
• ¬ , ∨ , ∧ , → , ↔
Fórmulas
• Representam as palavras da lógica 
proposicional
– Concatenação de símbolos do alfabeto
• Gramática
– Nem todas as combinações são válidas
• Ideia � obtenção de fórmulas complexas a 
partir de fórmulas simples
– É possível obter um conjunto infinito de fórmulas
– Diferente da língua portuguesa
• Dicionários
6
Fórmulas
• Regras
1. Todo símbolo verdade é uma fórmula
2. Todo símbolo proposicional é uma fórmula
3. Se H é uma fórmula, então (¬H) é uma fórmula
4. Se H e G são fórmulas, então (H ∨ G) é uma 
fórmula (disjunção das fórmulas H e G)
5. Se H e G são fórmulas, então (H ∧ G) é uma 
fórmula (conjunção das fórmulas H e G)
6. Se H e G são fórmulas, então (H � G) é uma 
fórmula (H é o antecedente, e G consequente)
7. Se H e G são fórmulas, então (H ↔ G) é uma 
fórmula (H é o lado esquerdo, e G o lado direito)
Fórmulas
• Fórmulas mal formadas
– PR
– (R true �)
– (true � ↔ (R true �))
7
Fórmulas
• Pode-se omitir símbolos de pontuação das 
fórmulas, em alguns casos, mantendo o 
significado original
• Também é possível usar múltiplas linhas 
para facilitar a compreensão
Fórmulas
• Exemplo
– ((( P ∨ Q) � true) ↔ (Q ∧ S))
– Pode ser escrita como
(P ∨ Q) � true
↔
Q ∧ S
– ou
(( P ∨ Q) � true) ↔ (Q ∧ S)
8
Exercício
• Dados os símbolos proposicionais P e Q, mostre 
que ((P ∧ Q) ∨ ((¬P) → (¬Q))) é uma fórmula 
proposicional
• Verifique se as fórmulas abaixo são válidas
– (P → Q) ↔ (Q → P)
– (P ∨ ¬PQ) → (Q ∧ ¬Q)
– ¬((P ∧ ¬¬Q) → ¬R)
– (P→Q) ↔ (¬ → ¬P)
– ((Q ∧ R) ∨ ¬(¬Q ∨ P) ∨ (P ∧ ¬R)) → (R ∨ ¬P)
Fórmulas
• Ordem de precedência
– Simplificam as fórmulas definindo ordem de 
aplicação dos símbolos conectivos
– Usado na linguagem matemática
– Ex
• 2 + 4 x 5 � (2 + (4 x 5))
– Em alguns casos, não há ordem de 
precedência
– Ex
• 4 x 6 / 3 � ((4 x 6) / 3) ou (4 x (6 / 3))
9
Fórmulas
• Ordem de precedência na lógica proposicional
1. ¬
2. → , ↔
3. ∨ , ∧
• Em alguns casos, não há precedência nos 
símbolos, e múltiplas interpretações são 
possíveis
– Pode se usar múltiplas linhas para facilitar a 
compreensão nesse caso
Exercício
• Elimine o maior número possível de parênteses da 
fórmula, sem alterar seu significado original
• ((¬X) ∨ ((¬(X ∨ Y)) ∨ Z))
• Identifique quais fórmulas pertencem à lógica 
proposicional. Justifique sua resposta, apresentando as 
regras de construção utilizadas ou apontando uma 
concatenação inválida
– Para as fórmulas válidas, remova os símbolos de pontuação 
sem afetar a sua interpretação 
• (P ∧ Q) → ((Q ↔ P) ∨ (¬(¬R))) 
• ∨ Q → R 
• (P ∨ R) → (Q ↔ ((¬T) ∧ R)) 
• (PQ ∨ True) 
• ((¬(¬P)) ↔ ((¬((¬(¬(P ∨ Q))) → R)) ∧ P)) 
• (¬P → (Q ∨ R)) ↔ ((P ∧ Q) ↔ (¬¬R ∨ ¬P))
10
Fórmulas
• Comprimento de uma fórmula
– Notação � comp[H]
– Definição
• Se H é um símbolo proposicional ou de verdade, então 
comp[H] = 1
• Se H e G são fórmulas da Lógica Proposicional, então
– comp[¬H] = comp[H] + 1
– comp[H ˅ G] = comp[H] + comp[G] + 1
– comp[H ˄ G] = comp[H] + comp[G] + 1
– comp[H � G] = comp[H] + comp[G] + 1
– comp[H ↔ G] = comp[H] + comp[G] + 1
– Os símbolos de pontuação não são considerados
Fórmulas
• Comprimento de fórmulas
– Usado em demonstrações por indução finita
– Ex
• (P �Q): 3
• ((P ˄ Q) ↔ R): 5
11
Fórmulas
• Sub-fórmula
– Definição
• H é sub-fórmula de H
• Se H = (¬G), então G é subfórmula de H
• Se H é uma fórmula do tipo
– (G ˅ E), (G ˄ E), (G � E) ou (G ↔ E)
• Então G e E são sub-fórmulas de H
• Se G é sub-fórmula de H, então toda sub-fórmula 
de G é sub-fórmula de H
Exercício
• Determine o comprimento e as 
subfórmulas das seguintes fórmulas 
proposicionais
– ((¬¬P ∨ Q) ↔ (P → Q)) ∧ True 
– P → ((Q → R) → ((P → Q) → (P → R))) 
– ((P → ¬P) ↔ ¬P) ∨ Q 
– ¬(P → ¬Q) 
12
Linguagem-objeto e 
Metalinguagem
• Linguagem-objeto: expressa a informação 
em sua forma original
– Ex: Ana is a student
• Metalinguagem: expressa uma informação 
contida na linguagem-objeto
– Ex: Ana é uma estudante
• O mesmo ocorre na Lógica Proposicional
– ((P ∨ Q → true)
Linguagem-objeto e 
Metalinguagem
• Variáveis
– Facilitam a expressão de leis
– Ex: (x – y)(x + y) = (x2 – y2)
– Os símbolos proposicionais podem ser 
representados por variáveis do tipo P#, com 
possíveis subíndices
• Ex.: P#1 pode representar qualquer um dos 
símbolos 
– P, Q, R, S, P1, Q1, R1, S1, P2 ...
13
Linguagem-objeto e 
Metalinguagem
• Variáveis
– As variáveis A, B, C, D, E, H e G com 
possíveis subíndices representam fórmulas
• A variável H2 pode representar, por exemplo, a 
fórmula (P � Q)
Linguagem-objeto e 
Metalinguagem
• Letras como P#, A, B, C, D, E e H são 
elementos da metalinguagem que 
representam símbolos proposicionais e 
fórmulas em geral da Lógica Proposicional
– Assim, (P#1 � P#2) não é uma fórmula da 
Lógica Proposicional
• Essa expressão é a representação de fórmulas do 
tipo (P � Q), (R � S), etc. 
14
Linguagem-objeto e 
Metalinguagem
• (H ∨ G) também não representa uma 
fórmula, mas a representação de fórmulas 
tais como ((P�Q) ∨ (R∧S))
– H é substituída por (P → Q)
– G é substituída por (R ∧ S) 
• Expressões do tipo (P#1 → P
#
2) e (H ∨ G) são 
denominadas esquemas de fórmulas
• Os esquemas de fórmulas se transformam em 
fórmulas quando as metavariáveis são 
substituídas por símbolos e fórmulas da Lógica
Exercício
• Interprete a letra sentencial “C” como 'Está
chovendo', e “N” como 'Está nevando' e 
expresse a forma de cada sentença na notação 
do cálculo proposicional
– Está chovendo
– Não está chovendo
– Está chovendo ou nevando
– Está chovendo e nevando
– Está chovendo mas não está nevando
– Não é o caso que está chovendo e nevando
– Se não está chovendo, então está nevando
– Não é o caso que se está chovendo então está
nevando
15
Exercício
• Continuação
– Está chovendo se e somente se não está nevando
– Não é o caso que está chovendo ou nevando
– Se está nevando e chovendo, então está nevando
– Se não está chovendo, então não é o caso que está
nevando e chovendo
– Ou está chovendo, ou está nevando e chovendo
– Ou está chovendo e nevando, ou está nevando mas 
não está chovendo.
Exercício
• Sejam as proposições– P: Gosto de viajar
– Q: Visitei o Chile
• Represente as seguintes proposições 
verbalmente
– P ↔ Q
– ¬Q→ ¬P
– (P ∧ ¬Q) → ¬P
– Q→ ¬P
– ¬(P → Q)
16
Exercício
• Descreva as sentenças abaixo em termos de 
proposições simples e operadores lógicos
– Se elefantes podem subir em arvores, então 3 é
número par
– π > 0 se e somente se não é verdade que π > 1
– Se as laranjas são amarelas, então os morangos são 
vermelhos
– É falso que se Montreal é a capital do Canadá, então 
a próxima copa será realizada no Brasil
– Se é falso que Montreal é a capital do Canadá, então 
a próxima copa será realizada no Brasil
Referências
• Souza, J. N., Lógica para Ciência da 
Computação, 2ª edição, Editora Campus, 
2008
• Martins, L. G. A, Apostila de Lógica 
Proposicional, FACOM, UFU.
• Neto, R., Lógica Aplicada a Computação, 
UNIVASF

Outros materiais