logica

L´gica para Computa¸˜o o ca
Primeira lista de exerc´ ıcios Entrega: 17 de agosto de 2014
1. Determine o tamanho das f´rmulas abaixo e o conjunto de subf´rmulas o o
(a) (p → (q → p))
(b) (p ∨ (q ∧ r))
(c) ((p ∨ q) ∧ (p ∨ r))
(d) (¬((¬p) ∧ (¬q)))
2. Especifique os seguintes conceitos por meio de defini¸˜es recursivas: co (a) Defina uma fun¸˜o c : LLP → N que calcula o n´mero de ocorrˆncias ca u e de conectivos bin´rios (∧, ∨, →, ↔) em uma f´rmula. a o
(Por exemplo, a f´rmula (p ∨ (q → (¬q))) tem duas ocorrˆncias de o e conectivos bin´rios, ou seja, c ((p ∨ (q → (¬q)))) = 2.) a (b) Defina uma fun¸˜o c : LLP → N que calcula o n´mero de ocorrˆncias ca u e de conectivos (¬, ∧, ∨, →, ↔) em uma f´rmula. o (Por exemplo, a f´rmula (p ∨ (q → (¬q))) tem trˆs ocorrˆncias de o e e conectivos, ou seja, s((p ∨ (q → (¬q)))) = 3.)
(c) Defina uma fun¸˜o s : LLP → N que calcula o n´mero de ocorrˆncias ca u e de proposi¸˜es atˆmicas em uma f´rmula. co o o (Por exemplo, a f´rmula (p → (q → p)) tem trˆs ocorrˆncias de o e e proposi¸˜es atˆmicas, ou seja, s((p → (q → p))) = 3.) co o
(d) Defina uma fun¸˜o sp : LLP × AP → N que calcula o n´mero de ca u ocorrˆncias de uma dada proposi¸˜o atˆmica em uma f´rmula. e ca o o
(Por exemplo, a f´rmula (p → (q → p)) tem duas ocorrˆncias do o e
´tomo p, ou seja, sp ((p → (q → p)), p) = 2.) a (e) Defina uma fun¸˜o ||s : LLP → N que calcula o tamanho do conjunto ca de subf´rmulas de uma dada f´rmula. o o
(Por exemplo, a f´rmula (p → (q → p)) tem quatro subf´rmulas, ou o o seja, |((p → (q → p))|s = 4.)

1

3. Demonstre por meio de indu¸˜o que as seguintes propriedades s˜o verdaca a deiras:
(a) Seja φ uma f´rmula em LLP , mostre que s(φ) = c (φ) + 1. Por o exemplo, se φ ´ (p → ¬q) ent˜o s(φ) = 2, c (φ) = 1, e portanto e a s(φ) = c (φ) + 1 ´ verdadeiro. e (b) Mostre que o n´mero de ocorrˆncia de um dado ´tomo em uma u e a f´rmula ´ sempre menor ou igual ao n´mero total de