Tutorial de Introdução à Lógica e Algoritmia
Este tutorial tem o objectivo de dar algumas bases nestas duas disciplinas para iniciantes à programação. Sendo que a programação está assente na algoritmia, e a algoritmia está assente na lógica, como se verá ao longo deste pequeno tutorial, este torna-se de extrema importância para se entender muitos "porquês" da programação que os beginners muitas vezes colocam.
Lógica
De forma resumida, a lógica é o ramo da filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar.1
Nesta parte vamos entender os operadores lógicos básicos - E, OU e OU... OU... - recorrendo às Tabelas de Verdade.
Proposições e condições
De forma muito resumida, seguem-se três exemplos simples e perceptíveis:
- Sentença: O João gosta de ir à praia.
- Proposição: O João gosta de ir à praia e ao campo.
- Condição: O João gosta de ir à praia se estiver bom tempo.
Tabela de Verdade
Numa Tabela de Verdade são analisadas todas as hipóteses de resposta a um problema lógico, desde o mais simples ao mais complexo, sendo mesmo a base das bases da investigação criminal forense. São lançadas as hipóteses de forma lógica, unindo as sentenças em proposições e relacionando estas últimas em condições. Um exemplo simples e sem fundamentação forense: O João é culpado se a arma do crime tiver as impressões digitais dele. Ou a arma é uma faca se as impressões digitais forem as dextras, ou então é uma pistola se ele praticar carreira de tiro. A Tabela de Verdade tem a seguinte estrutura básica:
proposição 1 (p) | proposição 2 (q) | Resultado com o operador lógico X (p X q) |
---|---|---|
V | V | V X V |
V | F | V X F |
F | V | F X V |
F | F | F X F |
Havendo duas proposições, há quatro hipóteses de conjugação conforme os valores lógicos da proposição. Havendo N proposições num enunciado lógico como o anterior, vão existir \(2^N\) combinações. Neste caso, havendo 2 proposições, existem \(2^2=4\) combinações. Nota: Valor lógico: Verdadeiro, Falso. Uma proposição só pode tomar um valor lógico - não pode ser V e F ao mesmo tempo!
Operadores lógicos
E - Conjunção
O João gosta de praia e do campo.
Ou seja, o João gosta de ambas as coisas, a praia e o campo.
p | q | \(p~\wedge~q\) |
---|---|---|
V | V | V |
V | F | F |
F | V | F |
F | F | F |
Só é verdadeiro quando ambas as proposições são verdadeiras.
OU - Disjunção
Também denominada de Disjunção inclusiva.
O João gosta de praia ou do campo.
Isto é, o João gosta ou da praia, ou do campo, ou de ambos.
p | q | \(p~\vee~q\) |
---|---|---|
V | V | V |
V | F | V |
F | V | V |
F | F | F |
Só é falso quando ambas as proposições são falsas.
OU... OU... - Disjunção exclusiva
O João ou gosta de praia, ou gosta de campo.
Ou seja, o João gosta de um só destes ambientes, e não dos dois ao mesmo tempo: ou um ou outro.
p | q | p ⊕ q |
---|---|---|
V | V | F |
V | F | V |
F | V | V |
F | F | F |
É falso quando as proposições têm o mesmo valor lógico.
Condições
Implicação
Se* o João gosta de ir à praia, então* gosta do mar.
p | q | \(p\Rightarrow~q\) |
---|---|---|
V | V | V |
V | F | F |
F | V | V |
F | F | V |
Nota: "Verdadeiro implica falso" é falso. Mas "Falso implica verdadeiro" é uma condição verdadeira.
Equivalência
Também chamada de Implicação dupla ou bi-implicação.
O João gosta de praia se e só se gosta de mar.
p | q | \(p~\Leftrightarrow~q\) |
---|---|---|
V | V | V |
V | F | F |
F | V | F |
F | F | V |
Ou seja, só é verdade quando ambas as proposições tiverem o mesmo valor lógico – só assim as proposições equivalem uma à outra.
Outras operações lógicas
Negação
Esta é uma operação muito básica que, simplesmente, nega o resultado lógico de uma proposição ou condição.
p | ~\(p\) |
---|---|
V | F |
F | V |
O João não gosta de ir à praia e gosta de mar.
- ~\(p~\wedge~q\)
Nota: Dupla negação: ~~\(p~\Leftrightarrow~p\)
Igualdade e diferença
Sem negação:
- \(2+2~=~4\): verdadeiro
- \(2-5~\neq~-3\): falso
Com negação:
- ~\((5+6~=~11)\): falso
- ~\((3-1~\neq~2)\): verdadeiro
Maior do que, menor do que, maior ou igual que, menor ou igual que
- \(5~>~9\): falso
- \(3~<~8\): verdadeiro
- ~\(( (3+pi)~\geq~6)\): falso
- ~\(( (1/e)~\leq~(1/pi) )\): verdadeiro
Principais Leis de De Morgan
- ~\((p~\wedge~q)~\Leftrightarrow~\)~\(p~\vee~\)~\(q\)
- ~\((p~\vee~q)~\Leftrightarrow~\)~\(p~\wedge~\)~\(q\)
Algoritmia
Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais pode ser executada mecanicamente num período de tempo finito e com uma quantidade de esforço finita.2 Ou seja, um algoritmo é um caminho bem definido para se resolver um determinado problema. Por exemplo:
Problema | Algoritmo Geral |
---|---|
Multiplicar 36 por 2 | Alg. da Multiplicação: \(\matrix{2}{2}{~ 36 ~*~ 2} / \matrix{1}{2}{~ 72}\) |
Ordenar lista de forma crescente: \({7,~3,~6}\) | Alg. de Ordenação (Crescente): \({3,~6,~7}\) |
Representação de Algoritmos
Um algoritmo tem uma representação para que possa ser facilmente interpretado. Antes de se programar, os problemas devem ser estudados para se chegar a um algoritmo-solução. Este será representado num esquema, chamada Fluxograma, ou então escrito na linguagem-mãe (no nosso caso, Português) ou numa mistura desta com a linguagem de programação a que nos propomos resolver o dito problema. Vamos então analisar um algoritmo muito simples que resolve o seguinte problema: Dados dois números, inteiros, inseridos pelo utilizador, dizer qual é o maior, ou então se são iguais.
Fluxograma
Vamos resolver o problema anterior segundo o algoritmo tradicional: análise caso-a-caso, que com este problema é totalmente viável, pois basta analisar duas situações, segundo esta ordem:
- Se num1 é maior que num2, mostra num1...
- Caso contrário, se num2 é que é maior que num1, então mostra num2...
- Por fim, se num1 não é o maior e num2 também o não é, conclui-se que só podem ser iguais.
Um fluxograma respeita uma norma geral que pode ser adaptada por cada pessoa. A imagem seguinte mostra o algoritmo de resolução do problema proposto seguindo a norma geral dos fluxogramas. No canto superior direito da imagem está uma pequena legenda, que inclui símbolos não incluídos no esquema.
De notar que cada "caminho" é chamado de fluxo, e no final do programa reconhecem-se três fluxos que são unidos antes de se dar o fim do programa: o símbolo é um círculo e denomina-se conector de fluxos. Na prática, na programação não se nota esta conexão de fluxos, mas na teoria, havendo a um determinado ponto vários caminhos possíveis, eles unem-se sempre, pelo menos no fim do programa. Esta união pode ocorrer noutro ponto e pode reunir apenas alguns dos N fluxos que existam - vários conectores podem existir. Pontos em que um fluxo se divide são quase sempre Condições, excepto nos Ciclos que, em si, têm dois fluxos: o fluxo das acções a processar dentro do ciclo e um fluxo de retoma do ciclo no caso da condição de paragem não for satisfeita. Esta é a teoria básica de fluxos nas Estruturas de Repetição.
Pseudo-código
Início Programa
Ler num1
Ler num2
Se (num1>num2) Então
Escrever "O maior é: " & num1
SeNão
Se (num1<num2) Então
Escrever "O maior é: " & num2
SeNão
Escrever "São iguais."
Fim Se
Fim Se
Fim Programa
Alguns algoritmos
Algoritmo de ordenação
Ver o Capítulo 5 da Parte II do nosso Tutorial de Pascal: Ordenação crescente de uma lista. Aproveita e vê como pode ser programado recorrendo a Pascal. ;-)
Grafos
Ver o artigo da Revista PROGRAMAR: Parte 1 e Parte 2.
Algoritmos de pesquisa
Ver o documento completo Algoritmos de pesquisa.