calculop

C´lculo proposicional a Proposi¸˜o ca Proposi¸˜es s˜o senten¸as afirmativas declarativas que n˜o sejam amb´ uas e que possuem co a c a ıg¨ a propriedade de serem ou verdadeiras ou falsas, mas n˜o ambas. a Exemplos:
. “Gatos tˆm quatro patas” e · “1 + 2 = 3”
. “A Terra ´ quadrada” e . “3 ´ um n´mero primo” e u
Exemplos de senten¸as que n˜o s˜o proposi¸˜es: c a a co . “O que estou dizendo agora ´ mentira” e . “Ir´ chover amanh˜” a a
. “Onde est´ a chave ?” a C´lculo proposicional a ´
E uma sub-´rea da l´gica simb´lica que estuda um conjunto formal de regras que pera o o mitem a an´lise e manipula¸˜o de proposi¸˜es. Algumas referˆncias para este assunto a ca co e s˜o [Ross and Wright, 1992], [Garnier and Taylor, 1992], cap´ a ıtulo 1 de [Mendelson, 1977].
Conectivos l´gicos o ˜
Proposi¸˜es simples podem ser concatenadas atrav´s de conectivos l´gicos E, OU, NAO co e o para formar novas proposi¸˜es compostas. co Exemplos: Das proposi¸˜es “Fulano est´ cansado” e “Ciclano est´ cozinhando”, pode-se co a a formas as proposi¸˜es “Fulano est´ cansado E Ciclano est´ cozinhando”, ou “Fulano est´ co a a a
˜ est´ cansado”. cansado OU Ciclano est´ cozinhando”, ou “Fulano NAO a a
Nota¸˜es
co
Proposi¸˜es ser˜o representadas por letras como x, y, z, p, q, etc. Em geral, as letras que co a representam proposi¸˜es simples s˜o denominadas vari´veis (l´gicas). co a a o
Proposi¸˜es tˆm valor l´gico ou V (VERDADEIRO) ou F (FALSO). co e o Utilizaremos os seguintes s´ ımbolos para representar os conectivos l´gicos: o 1

Nina S. T. Hirata (DCC/IME-USP) — Notas de aula de MAC0329 (2007)

Conectivo
E
OU
˜
NAO

s´ ımbolo ∧
∨
¬

Os conectivos implica¸˜o condicional (→) e bicondicional ↔ ca Em adi¸˜o aos trˆs conectivos vistos acima, ´ comum tamb´m a utiliza¸˜o dos condicionais ca e e e ca ˜
SE-ENTAO (→) e SE-E-SOMENTE-SE (↔).
˜
Para proposi¸˜es x e y quaiquer, express˜es do tipo “SE x