Lista 1 - 2014.1

Prévia do material em texto

Lo´gica para Computac¸a˜o
Primeira lista de exerc´ıcios
Entrega: 17 de agosto de 2014
1. Determine o tamanho das fo´rmulas abaixo e o conjunto de subfo´rmulas
(a) (p→ (q → p))
(b) (p ∨ (q ∧ r))
(c) ((p ∨ q) ∧ (p ∨ r))
(d) (¬((¬p) ∧ (¬q)))
2. Especifique os seguintes conceitos por meio de definic¸o˜es recursivas:
(a) Defina uma func¸a˜o c� : LLP → N que calcula o nu´mero de ocorreˆncias
de conectivos bina´rios (∧,∨,→,↔) em uma fo´rmula.
(Por exemplo, a fo´rmula (p ∨ (q → (¬q))) tem duas ocorreˆncias de
conectivos bina´rios, ou seja, c�((p ∨ (q → (¬q)))) = 2.)
(b) Defina uma func¸a˜o c : LLP → N que calcula o nu´mero de ocorreˆncias
de conectivos (¬,∧,∨,→,↔) em uma fo´rmula.
(Por exemplo, a fo´rmula (p ∨ (q → (¬q))) tem treˆs ocorreˆncias de
conectivos, ou seja, s((p ∨ (q → (¬q)))) = 3.)
(c) Defina uma func¸a˜o s : LLP → N que calcula o nu´mero de ocorreˆncias
de proposic¸o˜es atoˆmicas em uma fo´rmula.
(Por exemplo, a fo´rmula (p→ (q → p)) tem treˆs ocorreˆncias de
proposic¸o˜es atoˆmicas, ou seja, s((p→ (q → p))) = 3.)
(d) Defina uma func¸a˜o sp : LLP × AP → N que calcula o nu´mero de
ocorreˆncias de uma dada proposic¸a˜o atoˆmica em uma fo´rmula.
(Por exemplo, a fo´rmula (p→ (q → p)) tem duas ocorreˆncias do
a´tomo p, ou seja, sp((p→ (q → p)), p) = 2.)
(e) Defina uma func¸a˜o ||s : LLP → N que calcula o tamanho do conjunto
de subfo´rmulas de uma dada fo´rmula.
(Por exemplo, a fo´rmula (p→ (q → p)) tem quatro subfo´rmulas, ou
seja, |((p→ (q → p))|s = 4.)
1
3. Demonstre por meio de induc¸a˜o que as seguintes propriedades sa˜o verda-
deiras:
(a) Seja φ uma fo´rmula em LLP , mostre que s(φ) = c�(φ) + 1. Por
exemplo, se φ e´ (p → ¬q) enta˜o s(φ) = 2, c�(φ) = 1, e portanto
s(φ) = c�(φ) + 1 e´ verdadeiro.
(b) Mostre que o nu´mero de ocorreˆncia de um dado a´tomo em uma
fo´rmula e´ sempre menor ou igual ao nu´mero total de a´tomos desta
fo´rmula.
(c) Mostre que uma fo´rmula com n conectivos tem tamanho de no ma´ximo
2n+ 1.
2