Mat Disc AULA03

Prévia do material em texto

Matemática Discreta - AULA03 - Prof. Rafael Matos 
 
Bibliografia utilizada: 
ROSEN, K. H. Matemática Discreta e suas aplicações. 
Capítulo I. 
 
Tema: 
Lógica Proposicional. Argumentos Válidos. Seqüência de demonstração. 
 
Notas: 
 
Lógica Proposicional 
 
Sistema formal no qual as fórmulas representam proposições formadas pela combinação de 
proposições atômicas, através de conectivos lógicos e um sistema de regras de derivação, 
permitindo que fórmulas sejam teoremas. 
 
Argumentos são as asserções matemáticas (regras de inferência), preservadoras da verdade, 
usadas para derivar fórmulas, representando asserções verdadeiras. 
 
A linguagem de um cálculo proposicional consiste em: 
 
● Um conjunto de símbolos primitivos, definidos como fórmulas atômicas, proposições 
atômicas, ou variáveis; 
● Um conjunto de operadores ou conectivos lógicos; 
 
Um dos principais usos de um cálculo proposicional, em aplicações lógicas, é na determinação 
de relações de equivalência lógica entre fórmulas proposicionais. Sequências de regras 
estabelecem o que chamamos "derivação" ou "demonstração". 
 
Demonstração: sequência de linhas enumeradas, em que cada linha consiste em uma única 
fórmula, seguida por uma ​razão ou ​justificativa para introduzir esta fórmula. Cada premissa do 
argumento, é listada no começo da sequência e é justificada simplesmente como uma 
"premissa". Uma demonstração é completa se cada linha segue das anteriores pela aplicação 
correta de uma regra de inferência. 
Exemplo de demonstração: 
Demonstrar que é uma tautologia (sempre verdadeira).p ) p )( ⋀ q → ( ⋁ q 
 
p ) p )( ⋀ q → ( ⋁ q ¬(p ) p )≡ ⋀ q ⋁ ( ⋁ q Através de tabela verdade 
¬p q) p )≡ ( ⋁ ¬ ⋁ ( ⋁ q Primeira Lei de Morgan 
¬p ) ¬q )≡ ( ⋁ p ⋁ ( ⋁ q Propriedades associativas e comutativas 
≡ V ⋁ V Por tabela verdade e Propriedade 
comutativa 
≡ V Por dominação 
 
 
Mostre que: 
a) p ) ¬p q)p ↔ q ≡ ( ⋀ q ⋁ ( ⋀ ¬ 
b) p q ) p )¬ → ( → r ≡ q → ( ⋁ r