A exemplo de qualquer outra ciência, a Ciência da Computação depende da Matemática para obter um vocabulário preciso, uma notação poderosa, abstrações úteis e um raciocínio rigoroso. O objetivo deste livro é melhorar nosso entendimento da linguagem, das ferramentas e dos processos de raciocínio da Matemática que são usados na Ciência da Computação. Este capítulo introduz a Lógica Formal, que delineia o método organizado e cuidadoso de pensar que caracteriza qualquer investigação científica ou qualquer outra atividade de raciocínio. Além disso, a lógica formal tem aplicações diretas na Ciência da Computação. A última seção deste capítulo explora uma linguagem baseada na lógica e no uso da Lógica Formal objetivando verificar a correção de programas de computadores. Ainda, a lógica de circuitos (a lógica que rege os circuitos de computadores) é um análogo direto da lógica de sentenças deste capítulo. Estudaremos este tipo de lógica no Cap. 7.

Geralmente nos expressamos, em português, através de interrogações e exclamações, mas, para comunicar fatos ou informações, usamos sentenças. Tecnicamente, uma sentença (ou proposição) é uma frase que pode ser apenas verdadeira ou falsa.

Conectivos Lógicos e Programação


Os conectivos lógicos E, OU e NÃO (ou, mais comumente seus equivalentes em inglês AND, OR e NOT) são oferecidos pela maioria das linguagens de programação. Esses conectivos, de acordo com as tabelas-verdade que definimos, agem sobre combinações de expressões verdadeiras e falsas a fim de produzir um valor-verdade final. Desses valores provém a capacidade de tomada de decisão fundamental ao controle do fluxo de programas de computadores. Desta forma, em um desvio condicional de um programa, se o valor-verdade de uma determinada expressão for verdadeiro, o programa irá executar um trecho de seu código; se o valor for falso, o programa executa, em seguida, outro trecho de seu código. Se a expressão condicional for substituída por uma expressão mais simples equivalente, o valor-verdade da expressão e, portanto, o controle do fluxo do programa não serão afetados, mas o novo código torna-se mais simples de ser entendido e poderá ser executado mais rapidamente.

Esse código é usualmente chamado de Algoritmo. Um algoritmo é um conjunto de instruções que pode ser executado mecanicamente em uma quantidade finita de tempo e que resolve algum problema. Os algoritmos são normalmente descritos em uma forma intermediária entre uma descrição puramente verbal na forma de parágrafos (tal como a que demos para decidir se é ou não uma tautologia) e um programa de computador (que, se executado, iria realizar os passos do algoritmo) escrito em uma linguagem de programação. Esta forma intermediária para descrição de algoritmos é chamada de pseudocódigo.

a) Qual é a expressão lógica definida da tabela verdade dada acima.

b) Usando mapa de Karnaugh, qual é a expressão lógica mais simplificada da tabela dada.

c) Qual é o diagrama de Venn da expressão lógica.

d) Qual é o circuito lógico definido da expressão lógica.