atps

Matem´tica para Ciˆncia de Computadores a e
1 o Ano - LCC & ERSI
Lu´ Antunes ıs [e-mail]
DCC-FCUP

Luis Antunes DCC-FCUP

Complexidade 2002/03

1

Fundamentos de L´gica o No nosso dia a dia, usamos todo o tipo de frases:
• Cinco ´ menor do que dez. e • Bem vindos a FCUP
• Os porcos voam.
• Existe vida em Marte.
• O que contˆm esta piza? e • Composi¸˜o de “afirma¸˜es”. ca co
Uma afirma¸˜o ´ uma frase que ´ verdadeira ou falsa! (Mas n˜o ambos!) ca e e a
Luis Antunes DCC-FCUP

Complexidade 2002/03

2

Fundamentos de L´gica o A L´gica Matem´tica ´ uma ferramenta para trabalhar com “afirma¸˜es” o a e co compostas (complicadas!). Inclui:
• Uma linguagem para expressar “afirma¸˜es”. co • Nota¸˜o concisa para as escrever. ca • Uma metodologia para objectivamente inferir sobre a verdade ou falsidade.

Luis Antunes DCC-FCUP

Complexidade 2002/03

3

L´gica Proposicional o L´gica proposicional ´ a l´gica de “afirma¸˜es” compostas construidas a partir de o e o co “afirma¸˜es” mais simples usando conectivas Booleanas. co Algumas aplica¸˜es em CC: co • Desenho de circuitos digitais.
• Expressar condi¸˜es em programas. co • Queries a bases de dados e motores de pesquisa.

Luis Antunes DCC-FCUP

Complexidade 2002/03

4

Falso ou Verdade?

Falso ou verdade s˜o valores Booleanos B = {F, T }. a • value(5 < 10) = T
• value(“Os Porcos voam”)= F
• value(“N˜o ´ t˜o mau como parece”)-? a e a
• value(“O SLB n˜o ´ t˜o mau como parece”)= F a e a

Luis Antunes DCC-FCUP

Complexidade 2002/03

5

Operadores Booleanos

¬p p∧q p∨q p⇒q p⇔q

˜
NAO p peq p ou q
˜
SE p ENTAO q
´
p SE E SO SE q

Defini¸˜o: usando tabelas de verdade. ca Luis Antunes DCC-FCUP

NEGACAO
¸˜
CONJUNCAO
¸˜
DISJUNCAO
¸˜
IMPLICACAO
¸˜
ˆ
EQUIVALENCIA

Complexidade 2002/03

6

˜
Nega¸˜o (NAO p): ¬p ca Verdade se p ´ falso, falso se p ´ verdade e e p F
T
Exemplos:
• ¬(5 < 10)