A Notação e símbolos

Nestas páginas tentou-se usar uma notação simples e uniforme (inspirada em [1]). No entanto, a publicação dos textos em HTML obrigou a alguns compromissos. Na próxima secção apresentam-se a notação e os símbolos usados.

A.1 Notação e símbolos

Todos os pedaços de código (i.e., pedaços de texto numa linguagem de programação) e construções específicas do C++ aparecem em tipo (de letra) de largura constante (normalmente Courier). Por exemplo: main() e i++;. Em todo o restante texto usa-se um tipo proporcional. Nos comentários em C++ usa-se também um tipo proporcional.
As variáveis matemáticas aparecem sempre em itálico. Por exemplo: n = q m + r.
N é o conjunto dos números naturais.
Z é o conjunto dos números inteiros.
Q é o conjunto dos números racionais.
R é o conjunto dos números reais.
Os conjuntos podem ser indicados em extensão colocando os seus elementos entre {}.
{} é o conjunto vazio.
# é o operador cardinal, que faz corresponder a cada conjunto o respectivo número de elementos.
Os produtos matemáticos nem sempre são escritos explicitamente: p q significa o mesmo que p * q, ou seja, o produto de p por q.
O valor absoluto de um número x representa-se por |x| ou abs(x).
Os símbolos usados para as igualdades e desigualdades quando inseridos em expressões matemáticas (e não expressões C++, onde a notação do C++ é usada) são os seguintes:

= significa "igual a".
<> significa "diferente de".
> significa "maior que".
>= significa "maior ou igual a".
< significa "menor que".
<= significa "menor ou igual a".

A conjunção e a disjunção representam-se pelas palavras "e" e "ou" em negrito: e e ou (oux significa "ou exclusivo").
A pertença indica-se pela palavra "em" em negrito: em.
A implicação e a equivalência representam-se pelas palavras "implica" e "equivale" em negrito: implica e equivale.
Os valores lógicos representam-se por:

V significa verdadeiro.
F significa falso.

A operação de negação representa-se pelo símbolo ¬.
A operação de obtenção do resto da divisão inteira representa-se pelo símbolo ÷.
O símbolo usado para "aproximadamente igual" é ±=.
Os quantificadores representam-se como se segue (em todos os casos à variável i chama-se variável [muda] de quantificação):

Soma: (S i : m <= i < n : f(i)) é a soma (o somatório) dos valores que a função f() toma para todos os valores do inteiro i verificando m <= i < n. I.e., é o mesmo que f(m) + f(m+1) + ... + f(n-1).
Produto: (P i : m <= i < n : f(i)) é o produto dos valores que a função f() toma para todos os valores do inteiro i verificando 1 <= i <= n. I.e., é o mesmo que f(m)f(m+1) ... f(n-1).
Qualquer que seja: (Q i : m <= i < n : f(i)) é a conjunção dos valores (lógicos) que o predicado f() toma para todos os valores do inteiro i verificando 0 <= i < n. I.e., é o mesmo que f(m) e f(m+1) e ... e f(n-1), ou seja, é o mesmo que afirmar que "qualquer que seja i com 0 <= i < n, f(i) é verdadeira", daí que seja conhecido como o quantificador universal.
Existe um: (E i : m <= i < n : f(i)) é a disjunção dos valores (lógicos) que o predicado f() toma para todos os valores do inteiro i verificando 0 <= i < n. I.e., é o mesmo que f(m) ou f(m+1) ou ... ou f(n-1), ou seja, é o mesmo que afirmar que "existe pelo menos um i com 0 <= i < n tal que f(i) é verdadeira", daí que seja conhecido como o quantificador existencial.
Contagem: (N i : m <= i < n : f(i)) é o número dos valores (lógicos) verdadeiros que o predicado f() toma para todos os valores do inteiro i verificando 0 <= i < n. I.e., é o número de valores lógicos verdadeiros na sequência f(m), f(m+1), ... f(n-1).

Note-se que a notação x < y < z (onde em vez de < pode sugir <=) é uma forma abreviada de escrever x < y e y < z.

A notação para os quantificadores divide-se em três partes: (a : b : c). A parte a indica o tipo de quantificador e as respectivas variáveis mudas bem como o respectivo conjunto base. Por exemplo, (P i,jem N : ...) indica um produto para todos os i e j inteiros. A parte b consiste num predicado que restringe os valores possíveis das variáveies mudas. Esse predicado pode ser omitido se for sempre V. Na realidade, portanto, as variáveis mudas tomam apenas valores que tornam o predicado verdadeiro. Por exemplo, (P i em N : i ÷ 2 <> 0 : ...) indica um produto para todos os inteiros ímpares. O mesmo efeito poderia ser obtido escrevendo (P i em {j em N : j ÷ 2 <> 0} : V : ...), onde o predicado é sempre verdadeiro e se restringe à partida o conjunto base do quantificador. A parte c indica os termos do quantificador.

O conjunto de valores que a variável muda de um quantificador pode tomar pode ser indicado implicitamente ou explicitamente. Em qualquer dos casos a indicação é feita através de um predicado que será verdadeiro para todos os valores que se pretende que a variável muda tome e falso no caso contrário. O conjunto base da variável muda pode ser indicado na primeira parte do quantificador quando a indicação for implícita. Quando o conjunto base não for indicado assume-se que é Z (conjunto dos números inteiros). Exemplos:

(Q i : i em N : ...), (Q iem N: V : ...), (Q i em Z: i > 0 : ...) ou (Q i : i > 0 : ...): para todos os naturais.
(Q i em N : i ÷ 2 = 0 : ...) ou, menos formalmente, (Q i em N : i par : ...): para todos os naturais pares.
(Q i : m < i <= n : ...): para todos os inteiros entre m (inclusive) e n (exclusive).
(Q i em {1, 4, 5}: V : ...): para todos os elementos do conjunto {1, 4, 5}.

Os quantificadores têm, por definição, os seguintes valores quando o conjunto de valores possíveis para a variável de quantificação é vazio:

(S i : F : ...) = 0, a soma de zero termos é nula.
(P i : F : ...) = 1, o produto de zero termos é 1.
(Q i : F : ...) = V, a conjunção de zero predicados é verdadeira.
(E i : F : ...) = F, a disjunção de zero predicados é falsa.
(N i : F : ...) = 0, a contagem de zero predicados é nula.

Em geral, o valor destes quantificadores quando o conjunto de variação da variável muda é vazio é o elemento neutro da operação utilizada no quantificador. Assim, para a soma é 0, para o produto é 1, para a conjunção é V e para a disjunção é F.

Existem (pelo menos) as seguintes equivalências entre quantificadores:

(Q i em A : p(i) : f(i)) = ¬(E i em A : p(i) : ¬f(i)).
(E i em A : p(i) : f(i)) = ¬(Q i em A : p(i) : ¬f(i)).
(Q i em A : p(i) : ¬f(i)) = ¬(E i em A : p(i) : f(i)) é o mesmo que (N i em A : p(i) : f(i)) = 0.
(Q i em A : p(i) : f(i)) = ¬(E i em A : p(i) : ¬f(i)) é o mesmo que (N i em A : p(i) : f(i)) = # {i em A : p(i)}.

Predicado: expressão matemática envolvendo variáveis que, de acordo com o valor dessas variáveis, pode ter valor lógico verdadeiro ou falso. Por exemplo, x > y é um predicado. Se x = 1 e y = 0 o predicado tem valor lógico V (verdadeiro).

A.2 Abreviaturas e acrónimos

e.g. - (do latim exempli gratia) por exemplo (também se pode usar v.g., de verbi gratia).
i.e. - (do latim id est) isto é.
vs. - (do latim versus) versus, contra.
cf. - (do latim confer) conferir, confrontar, comparar.
viz. - (do latim videlicet) nomeadamente.

A.3 Referências

[1] David Gries, "The Science of Programming", volume da série "Texts and Monographs in Computer Science", editada por David Gries, Springer-Verlag, Nova Iorque, 1981 [1989]. *

* Existe na biblioteca do ISCTE.