Slide 02 - Lógica para Computação

Prévia do material em texto

Lógica Proposicional
 Introdução
 Sintaxe
 Alfabeto
 Fórmulas
 Tabelas-verdade
 
Formalismo
 Alfabeto – contém símbolos que formam as palavras da 
linguagem
 Palavras (Fórmulas) – formadas pela concatenação de 
símbolos do alfabeto
 
A lógica na Ciência da Computação
■ Aplicação de métodos matemáticos rigorosos para 
resolução de problemas
■ Importância dos métodos formais, fundamentados em 
lógica formal, dentro dos diversos ramos presentes na 
Ciência da Computação
 
Alfabeto
 Símbolos de pontuação: ) , (
 Símbolos de verdade: true, false
 Símbolos proposicionais: P, Q, R, S, P1, Q1, P2, Q2...
 Conectivos proposicionais: ¬, ∨, ∧, → , ↔
 
Fórmulas
 Todo símbolo de verdade ou proposicional é uma fórmula 
da Lógica Proposicional
 Se H é fórmula então (¬H) também é 
 Se H e G são fórmulas, então (H ∨ G), (H∧G), (H→G) e 
(H↔G) também são
 
Precedência e subfórmulas
 Ordem de precedência (Segundo (**))
 Maior precedência: ¬
 Precedência intermediária: →, ↔
 Menor precedência: ∨, ∧
 Subfórmula: Se H é fórmula
 H é uma subfórmula
 Se H=(¬G), então G é subfórmula de H
 Se H é do tipo (E∨G), (E∧G), (E→G) ou (E↔G), então E e G são 
subfórmulas de H
 Se G é subfórmula de H, então toda subfórmula de G também é 
subfórmula de H
(**) SOUZA, João Nunes de. Lógica para Ciência da Computação: uma introdução 
concisa.2a. ed. rev. atual. Rio de Janeiro: Elsevier, 2008. 
 
Tabelas-verdade
 Negação: ¬
 Conjunção: ∧
 Disjunção: ∨
 Implicação: →
 Equivalencia: ↔
 
Negação
 Símbolo: ¬ (∼, , ') 
 Tabela-verdade:
 
Conjunção
 Símbolo: ∧
 Se A e B são proposições verdadeiras, então A ∧ B deve ser 
considerada verdadeira
 A tabela é formada pela combinação de todos os valores lógicos 
possíveis, referentes às proposições.
 Cada linha da tabela representa um valor lógico associado a uma proposição e 
o resultado da expressão composta
 Tabela-verdade
 
Disjunção
 Símbolo: ∨
 A tabela abaixo apresenta os valores lógicos de A∨B para todos os 
valores lógicos possíveis das proposições A e B.
 
Implicação
 Combinação de proposições na forma “se proposição A, então 
proposição B”.
 Símbolo: → 
 A proposição composta é denotada por A → B (A implica B).
 A é a proposição antecedente e B é a proposição consequente.
 A proposição composta A → B é falsa quando A é verdadeira e B é 
falsa. Caso contrário é verdadeira.
 A tabela-verdade:
 
Bi-implicação
 Símbolo: ↔
 A expressão A ↔ B é uma abreviação de (A→B) ∧ (B→A)
 De acordo com a tabela verdade apresentada abaixo, A↔B é 
verdadeira somente quando A e B têm os mesmos valores lógicos
 Tabela-verdade:
 
Resumindo...
 Para compreensão do raciocínio lógico, a tabela abaixo é essencial:
 
Fórmulas
 A partir do alfabeto da linguagem proposicional é possível construir 
palavras, que são as fórmulas lógicas
 É possível encadear letras (proposições), conectivos (¬, ∧, ∨, →, 
↔) e símbolos (parênteses) para formar novas expressões
 Exemplo: (A→B) ∧ (B→A)
 Além disso, na avaliação de uma fórmula lógica, a ordem de 
precedência dos conectivos lógicos tem que ser levada em 
consideração
 Exemplo: A ∨ ¬B = A ∨ (¬B) 
 A ∧ B → C = (A ∧ B) → C A ∧ (B → C)
 
Fórmulas
 Avaliação do valor lógico de uma fórmula
 A é falsa, B é falsa e C é verdadeira
A ∨ B ∧ C
A ∨ B → ¬C
 
Exemplo
 Sejam A, B e C as seguintes sentenças:
A: Rosas são vermelhas. 
B: Violetas são azuis. 
C: Açúcar é doce.
 Apresente as seguintes proposições compostas em notação 
simbólica:
 Rosas são vermelhas e violetas são azuis.
 Sempre que violetas são azuis, as rosas são vermelhas e açúcar é doce.
 Rosas são vermelhas e, se o açúcar for amargo, então ou violetas não 
são azuis ou o açúcar é doce.
 
Exemplo
 A: Rosas são vermelhas. 
 B: Violetas são azuis. 
 C: Açúcar é doce.
 Rosas são vermelhas e violetas são azuis.
 A ∧ B 
 Sempre que violetas são azuis, as rosas são vermelhas e açúcar é doce.
 B → A ∧ C
 Rosas são vermelhas e, se o açúcar for amargo, então ou violetas não 
são azuis ou o açúcar é doce.
 A ∧ (¬C → (¬B ∨ C))
 
Exemplo
 Determinar o valor lógico de cada proposição, sabendo que P 
e Q são verdadeiras e que as proposições R e S são falsas
 P ∧ Q → R
 P→ ¬R ∧ S
 ¬R → P ∧ Q
 ¬P ∧ Q → ¬P∨ ¬Q
 
Conceitos - Resumo
Um argumento é uma sequência de proposições 
(declarações/afirmações) na qual uma delas é a conclusão e as 
demais são premissas.
Uma proposição (ou declaração/afirmação) é uma sentença que 
pode ser verdadeira ou falsa 
O objeto de estudo da lógica é determinar se a conclusão de um 
argumento é ou não uma consequência lógica das premissas. 
Em um argumento válido, as premissas são consideradas provas 
evidentes da verdade da conclusão, caso contrário não é válido.
 
Conceitos - Resumo
 Exemplo 1: Argumento válido (a conclusão é uma decorrência 
lógica das duas premissas.)
Se eu ganhar na Loteria, serei rico. 
Eu ganhei na Loteria. 
Logo, sou rico.
 Exemplo 2: Argumento não válido (a conclusão não é uma 
decorrência lógica das duas premissas.)
Se eu ganhar na Loteria, serei rico 
Eu não ganhei na Loteria 
Logo, não sou rico
 
Conceitos - Resumo
Argumento Dedutivo: é válido quando suas premissas, se 
verdadeiras, a conclusão é também verdadeira. 
Argumento Indutivo: a verdade das premissas não basta para 
assegurar a verdade da conclusão. Argumentos deste tipo não 
pretendem que suas premissas forneçam provas cabais da 
veracidade da conclusão, mas apenas que forneçam indicações 
dessa veracidade. (possibilidade, probabilidade)
 
Conceitos - Resumo
O raciocínio Indutivo obtém conclusões baseadas em 
observações/experiências. Enquanto que um Raciocínio Dedutivo 
exige uma prova formal sobre a validade do argumento.
Verdade e Falsidade: são propriedades das proposições, nunca dos 
argumentos
Validade ou Invalidade: são propriedades dos argumentos dedutivos 
que dizem respeito a inferência ser ou não válida (raciocínio ser ou 
não correto)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22