Cap1. aspectos formais

Solu¸˜es dos Exerc´ co ıcios Propostos no Livro Introdu¸˜o aos Fundamentos da Computa¸˜o: ca ca Linguagens e M´quinas a (Ed. Thomson, 2006)
Newton Jos´ Vieira e Departamento de Ciˆncia da Computa¸˜o e ca Instituto de Ciˆncias Exatas e Universidade Federal de Minas Gerais Belo Horizonte, 30/06/2007

Pe¸o a quem encontrar erros nas solu¸˜es a seguir entrar em contato com o autor no c co endere¸o [e-mail]. Antecipadamente, agrade¸o c c

2

Cap´ ıtulo 1

Conceitos Preliminares
1.1 Representa¸˜o ca

Nesta se¸˜o n˜o h´ exerc´ ca a a ıcios.

1.2
1.

Prova de Teoremas
a) A afirmativa (α ∧ β) → α s´ ´ falsa se α ∧ β ´ verdadeira e α ´ falsa. Mas a α ∧ β oe e e n˜o pode ser verdadeira se α ´ falsa. Assim, (α ∧ β) → α n˜o pode ser falsa; logo, ´ a e a e v´lida. a b) A afirmativa α → (α ∨ β) s´ ´ falsa se α ´ verdadeira e α ∨ β ´ falsa. Mas, sendo α oe e e verdadeira, α ∨ β n˜o pode ser falsa. Assim, α → (α ∨ β) n˜o pode ser falsa; logo, ´ a a e v´lida. a c) A afirmativa (α ∧ ¬α) → β s´ pode ser falsa se α ∧ ¬α ´ verdadeira e β ´ falsa. o e e a e ca Mas a afirmativa α ∧ ¬α n˜o pode ser verdadeira, pois ´ uma contradi¸˜o. Assim, (α ∧ ¬α) → β n˜o pode ser falsa; logo, ´ v´lida. a e a

d) A afirmativa α → (β ∨ ¬β) s´ ´ falsa se α ´ verdadeira e β ∨ ¬β ´ falsa. Mas, β ∨ ¬β oe e e n˜o pode ser falsa, pois β e ¬β n˜o podem ser ambas falsas. Assim, α → (β ∨ ¬β) a a n˜o pode ser falsa; logo, ´ v´lida. a e a e) A afirmativa (α → β) ∨ α s´ pode ser falsa se ambas, α → β e α s˜o falsas. Mas, o a sendo α falsa, α → β ´ verdadeira. Assim, (α → β) ∨ α n˜o pode ser falsa; logo, ´ e a e v´lida. a f) A afirmativa (α → β) ∨ (β → α) s´ pode ser falsa se α → β e β → α s˜o falsas. Para o a α → β ser falsa, α deve ser verdadeira (e β falsa), e para β → α ser falsa, α deve ser falsa (e β verdadeira); contradi¸˜o! Assim, a afirmativa original n˜o pode ser falsa; ca a logo, ´ v´lida. e a 2. a) Suponha que α → β ´ verdadeira. Segue-se que α ´ falsa ou β ´ verdadeira. No e e e