logica

Cap´ ıtulo 2
L´gica Proposicional o L´gica para Programa¸ao o c˜
LEIC - Tagus Park
1o Semestre, Ano Lectivo 2007/08 c Inˆs Lynce e Bibliografia

• Martins J.P., L´gica para Programa¸ao, Cap´ o c˜ ıtulo 2.
• Ben-Ari M., Mathematical Logic for Computer Science,

Springer-Verlag, 2003, cap´ ıtulos 2 e 4 (parte)
• Huth M. e Ryan M., Logic in Computer Science, Cambridge

University Press, 2004, cap´ ıtulos 1 e 6 (parte)

L´gica Proposicional o • Em l´gica cl´ssica existem duas alternativas para a defini¸ao o a c˜ de uma linguagem:
– L´gica Proposicional, o – L´gica de Primeira Ordem. o • L´gica Proposicional ´ baseada em proposi¸oes. o e c˜ – Proposi¸oes s˜o frases declarativas que fazem afirma¸oes sobre c˜ a c˜ qualquer coisa.

Linguagem da l´gica proposicional o • S´ ımbolos da linguagem
1. S´ ımbolos de pontua¸˜o: ( ) ca 2. S´ ımbolos l´gicos: ¬ ∧ ∨ → o 2.1
2.2
2.3
2.4

o o o o s´ ımbolo s´ ımbolo s´ ımbolo s´ ımbolo ¬ corresponde a opera¸ao de nega¸ao,
`
c˜ c˜ ∧ corresponde a opera¸ao de conjun¸ao,
`
c˜ c˜ ∨ corresponde a opera¸ao de disjun¸ao,
`
c˜ c˜ → corresponde a opera¸ao de implica¸ao.
`
c˜ c˜ 3. S´ ımbolos de predicado: letras mai´sculas (P, Q, R, . . . ) ou u min´sculas (p, q, r, . . . ) que representam proposi¸oes u c˜

Frases da linguagem (fbfs)

1. Os s´ ımbolos de predicado s˜o fbfs. a 2. Se α ´ uma fbf ent˜o (¬α) ´ uma fbf. e a e 3. Se α e β s˜o fbfs ent˜o (α ∧ β), (α ∨ β) e (α → β) s˜o fbfs. a a a 4. Nada mais ´ uma fbf. e • Sempre que poss´ os parˆntesis redundantes s˜o omitidos: ıvel e a – ¬ tem prioridade sobre ∧ e ∨, e ∧ e ∨ tˆm prioridade sobre →. e – ∧ e ∨ s˜o opera¸oes associativas ` esquerda e → ´ associativa a c˜ a e
` direita. a • Exemplo: (p ∧ q) ∨ (r → (p → q)) pode ser simplificado para

p ∧ q ∨ (r → p → q).

Exemplo: Half Adder

• A e B s˜o entradas; O1 e O2 s˜o sa´ a a ıdas • O1