Ciencia da computação

Fundamentos Matemáticos para a Ciência da Computação
3ª Edição

Fundamentos Matemáticos para a Ciência da Computação
3ª Edição

Judith L Gersting
Indiana University — Purdue University at Indianapolis University of Hawaii at Hilo

Tradução

Lúcio Leão Fialho
Pós-graduação em Engenharia de Sistemas e Computação pela UFRJ

Manoel Martins Filho
(Participação nos Capítulos 1 e 2) Mestre em Engenharia de Sistemas e Computação pela COPPE — UFRJ

EDITORA

Título do original em inglês Mathematical Structures for Computer Science First published in the United States by W. H. Freeman and Company, New York, New York and Oxford Copyright, 1993. All rights reserved. Primeira edição nos EUA por W. H. Freeman and Company, New York, New York and Oxford Copyright, 1993. Reservados todos os direitos. Copyright © 1982, 1987, 1993 by W. H. Freeman and Company Direitos exclusivos para a língua portuguesa Copyright © 1995 by LTC - Livros Técnicos e Científicos Editora S.A. Travessa do Ouvidor, 11 Rio de Janeiro, RJ — CEP 20040-040 Reservados todos os direitos. É proibida a duplicação ou reprodução deste volume, no todo ou em parte, sob quaisquer formas ou por quaisquer meios (eletrônico, mecânico, gravação, fotocópia ou outros), sem permissão expressa da Editora.

Para Adam e Jason dois fundamentos discretos adoráveis

Prefácio

A matemática discreta continua sendo um elemento importante no ensino da Ciência da Computação. Desejamos oferecer aos estudantes os instrumentos para que desenvolvam um vocabulário preciso, recursos para notação, abstrações úteis e raciocínio formal — e queremos fazê-lo logo, desde o início de sua formação. Explicações claras e exatas são mais importantes do que nunca. Portanto, foi mantido o estilo simples que caracterizou as versões anteriores. Em termos de conteúdo, as "mudanças mínimas" previstas para esta terceira edição acabaram evoluindo para o que resultou nesta revisão maior. Assim, a primeira metade da segunda edição foi