Noções básicas de programação

Na faculdade de Ciência da Computação a gente tem uma matéria chamada Circuitos Digitais, e depois outra chamada Sistemas Digitais. Nelas a gente começa aprendendo o que é uma porta lógica, e depois como usar essas portas lógicas para montar "funções" binárias quaisquer (de entrada B^n e saída B^m, em que B={0,1}) (na verdade a gente monta os circuitos dessas funções). Pra isso a gente aprende primeiro as tabelas verdade das portas lógicas, depois álgebra booleana, mapas de karnaugh, coisas assim.
Tem também que ver depois os flip-flops e outros componentes parecidos, que são componentes que possuem memória, por assim dizer, porque fazem um tipo de "loop" da sua saída voltando a interagir com a sua entrada para dar o valor seguinte. Etc.
E assim vai. Depois o objetivo final da matéria de sistemas digitais é analisar como é feito um processador simples, componente por componente. (ULA, registradores e tudo mais.)

Pois bem, aqui não vamos seguir exatamente esse roteiro, mas convém aprender de primeira o que é lógica booleana e outros aspectos relevantes ao funcionamento do computador, pois neste contexto programação significa justamente programação de computadores.

(Continua.)

Seja B um conjunto de dois elementos distintos, 0 e 1. Isto é, B = {0,1}.

Então a operação E LÓGICO, também conhecida como AND, e denotada por * ou /\ é a função de B^2 em B dada pela seguinte tabela:

a | b | a*b
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1

A operação OU LÓGICO, também conhecida como OR, e denotada por + ou \/ é a função de B^2 em B dada pela seguinte tabela:

a | b | a+b
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

A operação (unária) NÃO LÓGICO, também conhecida como NOT, e denotada por ! ou ~ é a função de B em B dada pela seguinte tabela:

a | !a
0 | 1
1 | 0

(Nota: na notação da lógica booleana costuma-se usar um overline para indicar negação, isto é, !a é denotado por [o]a[/o], mas aqui no texto digitado no fórum não vou fazer isso.)

(Também tem que no AND costuma-se apenas colocar uma variável ao lado da outra, e costuma-se usar letras maiúsculas para variáveis, etc. Esses são só detalhes.)

Álgebra de Boole então é uma álgebra (ou algo assim(???)) com um conjunto B e três operações *, + e !, isto é, "álgebra de Boole" = (B, *, +, !).
E isso define ela completamente.

Em seguida vamos usar as tabelas verdades para demonstrar algumas identidades.

Para memorizar mais fácil vale entender o 1 como "verdadeiro" e o 0 como "falso".

No NOT, a negação de algo verdadeiro é algo falso e a negação de algo falso é algo verdadeiro. Por exemplo, se eu digo "o sol é verde", o que é obviamente falso, então dizer "o sol não é verde" é verdadeiro.

No AND, se eu digo que x e y são verdade, mas x é falso, então mesmo que y seja verdade eu disse algo falso, pois eu afirmei que ambos são verdade ao mesmo tempo.

No OR, se eu digo que x ou y são verdade, e x é verdade, então mesmo que y seja falso eu disse algo verdadeiro, pois pelo menos um dos dois é verdade, que é o que foi afirmado.

Esse OR, OU LÓGICO, também é chamado de ou inclusivo, que aceita que ambos x e y sejam verdade ao mesmo tempo, diferente do ou exclusivo, que diz que um dos dois é verdade mas não ambos.

Vamos demonstrar um a um esses 20 teoremas.

1) A+0 = A
Demonstração:
Se A=0, sabemos da tabela verdade de + (ou lógico) que 0+0=0, e A=0. Portanto, para A=0, A+0=A.
Se A=1, pela tabela verdade, 1+0=1, e A=1. Portanto, para A=1, A+0=A.
Como na álgebra booleana uma variável só pode ser 0 ou 1, segue que, para todo A, A+0=A.

2) A+1=1
Demonstração:
Se A=0, temos (pela tabela verdade) que 0+1=1, ou seja, A+1=1.
Se A=1, temos que 1+1=1, ou seja, A+1=1.
Portanto, segue que, para todo A, A+1=1.

3) A+A=A
Demonstração:
Se A=0, temos 0+0=0, portanto nesse caso A+A=A.
Se A=1, temos 1+1=1, portanto A+A=A nesse caso também.
Segue que A+A=A em todos os casos possíveis.

4) A+!A=1
(Na imagem foi usado A' para denotar negação de A. Aqui usamos !A.)
Demonstração:
Se A=0, então !A=1. Se A=1, !A=0. Portanto, A+!A ou é 0+1 ou é 1+0. Mas pela tabela verdade do +, tanto 0+1=1 quanto 1+0=1.
Logo, segue que A+!A=1.

5) A*1=A
Demonstração:
Se A=0, A*1=0*1=0=A.
Se A=1, A*1=1*1=1=A.

6) A*0=0
Demonstração:
Se A=0, A*0=0*0=0.
Se A=1, A*0=1*0=0.

7) A*A=A
Demonstração:
Se A=0, A*A=0*0=0=A.
Se A=1, A*A=1*1=1=A.

8 ) A*!A = 0
Demonstração:
Se A=0, então !A=1, e A*!A=0*1=0.
Se A=1, então !A=0, e A*!A=1*0=0.

Nota:
As propriedades 1, 2 e 3 são chamadas respectivamente de elemento neutro (o 0), absorção (pelo 1) e idempotência do ou lógico.
As propriedades 5, 6 e 7 são chamadas respectivamente de elemento neutro (o 1), absorção (pelo 0) e idempotência do e lógico.
As propriedades 4 e 8 dizem que o resultado da operação de um valor com sua negação dá sempre o elemento absorvedor da operação (1 para ou lógico, 0 para e lógico).

9) A+A*B=A
(O análogo desta propriedade em conjuntos é: A ∪ (A ∩ B) = A.)
(Aqui é entendido que a operação * (e lógico) tem precedência à operação + (ou lógico). Portanto A+A*B:=A+(A*B).)
Demonstração:
Se A=0, A+A*B=0+0*B=0+0=0=A. (Aqui usamos a propriedade 6.)
Se A=1, A+A*B=1+1*B=1+B=1=A. (Aqui usamos primeiro a propriedade 5 e depois a 2.)

Teorema extra, rapidão: + e * são comutativos, isto é, (i) A+B=B+A e (ii) A*B=B*A.
Demonstração:
i) Se A=B, temos A+B=A+A e B+A=A+A, portanto claramente a propriedade segue.
Agora considere o caso em que A=/=B. Então A=0 e B=1 ou A=1 e B=0. Nos dois casos queremos mostrar que 0+1=1+0.
Mas 0+1=1 e 1+0=1, pela tabela. Portanto, está provado.
ii) Se A=B, A*B=A*A=B*A.
Se A=/=B, 1*0=0=0*1.

10) A*(A+B)=A
(Em conjuntos,  A ∩ (A ∪ B) = A.)
Demonstração:
Se A=0, A*(A+B)=0*(0+B)=0*B=0=A. (Propriedades 1 e depois 6.)
Se A=1, A*(A+B)=1*(1+B)=1*1=1=A. (Propriedade 2.)

Pro post não ficar muito longo eu paro por aqui e demonstro os 10 teoremas seguintes no próximo post.

11) A*B + A*!B = A
Demonstração:
Se B=0, A*B+A*!B=A*0+A*1=0+A=A.
Se B=1, A*B+A*!B=A*1+A*0=A+0=A.

12) (A+B)*(A+!B) = A
Demonstração:
Se B=0, (A+B)*(A+!B)=(A+0)*(A+1)=A*1=A.
Se B=1, (A+B)*(A+!B)=(A+1)*(A+0)=1*A=A.

13) A+!A*B = A+B
(Aqui, !A*B:=(!A)*B. Negação tem precedência. Se quisermos denotar o * sendo efetuado antes escreveremos !(A*B).)
Demonstração:
Se A=0, A+!A*B=A+1*B=A+B.
Se A=1, A+!A*B=1+!A*B=1=1+B=A+B.

14) A*(!A+B) = A*B
Demonstração:
Se A=0, A*(!A+B)=0*(!A+B)=0=0*B=A*B.
Se A=1, A*(!A+B)=A*(0+B)=A*B.

As propriedades 15 e 16 a seguir são chamadas propriedades distributivas.

15) A+B*C = (A+B)*(A+C)
Demonstração:
Se A=0, A+B*C=0+B*C=B*C=(0+B)*(0+C)=(A+B)*(A+C).
Se A=1, A+B*C=1+B*C=1=1*1=(1+B)*(1+C)=(A+B)*(A+C).

16) A*(B+C) = A*B+A*C
Demonstração:
Se A=0, A*(B+C)=0*(B+C)=0=0+0=0*B+0*C=A*B+A*C.
Se A=1, A*(B+C)=1*(B+C)=B+C=1*B+1*C=A*B+A*C.

17) A*B+!A*C = (A+C)*(!A+B)
(Esse eu vou tentar demonstrar sem dividir por casos, usando as propriedades distributivas que acabamos de ver.)
Demonstração:
A*B+!A*C=(A*B+!A)*(A*B+C)=(!A+A*B)*(C+A*B)=(!A+A)*(!A*B)*(C+A)*(C+B)=1*(!A+B)*(A+C)*(B+C)=(A+C)*(!A+B)*(B+C).
Infelizmente não consegui eliminar esse B+C. (Possível argumento: Se B+C=1, a igualdade é dada. E B+C só é 0 no caso em que B e C ambos são 0. Portanto...)
Mas vamos fazer por casos que desconfio que saia mais fácil.
Se A=0, A*B+!A*C=0*B+1*C=0+C=C=C*1=(0+C)*(1+B)=(A+C)*(!A+B).
Se A=1, A*B+!A*C=1*B+0*C=B+0=B=1*B=(1+C)*(0+B)=(A+C)*(!A+B).

18) (A+B)*(!A+C) = A*C+!A*B
Demonstração:
Pela propriedade anterior (17), temos que
A*C+!A*B = (A+B)*(!A+C).
(E a igualdade é uma relação simétrica.)
(É um simples trocar o B e o C de lugar.)

19) A*B + !A*C + B*C = A*B + !A*C
(A expressão da direita é como um "switch": o valor de A escolhe se a expressão vai valer B ou C. Quando A é 1, vale B. Quando A é 0, vale C.)
Demonstração:
Vou tentar um jeito alternativo.
Se B*C = 0, então a igualdade claramente vale, pois no ou lógico o 0 é elemento neutro, que é eliminado.
Isto é,  A*B + !A*C + 0 = A*B + !A*C.
Se B*C=1, então B=1 e C=1.
Assim, A*B + !A*C + B*C = A*B + !A*C + 1 = 1 = A + !A = A*1+!A*1 = A*B+!A*C.

20) (A+B)*(!A+C)*(B+C) = (A+B)*(!A+C)
(O lado direito nesse caso também é uma "switch", mas uma switch inversa: quando A é 0 o B é escolhido e quando A é 1 o C é escolhido.)
Demonstração:
Se B+C=1, então (A+B)*(!A+C)*(B+C) = (A+B)*(!A+C)*1 = (A+B)*(!A+C).
Se B+C=0, então B=0 e C=0, e (A+B)*(!A+C)*(B+C)=(A+B)*(!A+C)*0=0=A*!A=(A+0)*(!A+0)=(A+B)*(!A+C).

Esse foi o último teorema dos 20 propostos pela imagem.
A próxima coisa a fazer acho que vai ser enunciar e demonstrar as leis de De Morgan.

Leis de De Morgan

Elas básicamente dizem que a negação da conjunção é a disjunção inclusiva das negações e que a negação da disjunção inclusiva é a conjunção das negações.
(Em lógica a operação e lógico que vimos é chamada de conjunção e a operação ou lógico que vimos é chamada de disjunção inclusiva.)

Em símbolos,
!(A*B) = !A + !B;
!(A+B) = !A * !B.

Vamos demonstrar essas leis.

1) !(A*B) = !A + !B
Demonstração:
Se A*B=0, ou A=0 ou B=0 (pelo menos um). Assim, !A=1 ou !B=1, e !A+!B=1+!B=1 ou !A+!B=!A+1=1. Isto é, !A+!B=1.
Mas !(A*B)=!0=1 também. Logo, !(A*B)=!A+!B.
Se A*B=1, então ambos A e B são 1.
!(A*B)=!1=0=0+0=!1+!1=!A+!B.

2) !(A+B) = !A * !B
Demonstração:
Se A+B=0, então ambos A e B são 0.
!(A+B)=!0=1=1*1=!0*!0=!A*!B.
Se A+B=1, ou A=1 ou B=1 (pelo menos um). Sem perda de generalidade, assuma que A=1.
Assim, !A*!B=!1*!B=0*B=0=!1=!(A+B).

(Não perdemos generalidade na demonstração anterior porque a operação * é comutativa.)

Essas são as leis de De Morgan.

Se você for parar pra pensar é meio óbvio, ou lógico, isso daí.
Negar que pelo menos uma das afirmações x e y é verdadeira é afirmar que ambas são falsas.
E negar que ambas as afirmações x e y são verdadeiras é afirmar que pelo menos uma é falsa.

Todas essas coisas que vimos provavelmente concordam com nossas intuições.

É possível generalizar De Morgan fácilmente, usando indução.

Por exemplo, !(A+B+C)=!((A+B)+C)=!(A+B)*!C=!A*!B*!C
e
!(A*B*C)=!((A*B)*C)=!(A*B)+!C=!A+!B+!C

Agora vamos introduzir uma notação.
Para o ou-tório lógico (analogia com somatório, produtório, união de muitos conjuntos e intersecção de muitos conjuntos), vamos usar
\/_{i=1}^n A_i = A_1 \/ A_2 \/ A_3 \/ ... \/ A_{n-1} \/ A_n
Aqui tô recorrendo à notação da lógica convencional pro ou inclusivo pra não confundir com somatório (cujo símbolo é um sigma maiúsculo).
Daria pra chamar ele de disjuntório inclusivo, também.
E para e-tório lógico (ou conjuntório) vamos usar
/\_{i=1}^n A_i = A_1 /\ A_2 /\ A_3 /\ ... /\ A_{n-1} /\ A_n
Por exemplo, \/_{i=1}^2 A_i = A_1 \/ A_2, e /\_{i=1}^3 A_i = A_1 /\ A_2 /\ A_3.
Para não misturar notações vou usar ~ para denotar negação também.

Assim, vamos à indução. Ela é um axioma matemático que diz basicamente que se algo vale para o número 1 e, valendo pra k inteiro positivo qualquer também vale pra k+1, então esse algo vale pra todos os inteiros positivos, sem limite.

Queremos mostrar as duas leis de De Morgan para o caso geral, isto é, que para qualquer n inteiro positivo, ~(\/_{i=1}^{n} A_i) = (/\_{i=1}^{n} ~A_i) e ~(/\_{i=1}^{n} A_i) = (\/_{i=1}^{n} ~A_i).


De Morgan já mostramos valer pra n=2 e n=3, e o caso n=1 é trivial, pois ~A=~A. Então o passo básico já foi.
Agora vamos ao passo indutivo.

1) Suponha que, para certo k, ~(\/_{i=1}^k A_i) = /\_{i=1}^k ~A_i.
Então ~(\/_{i=1}^{k+1} A_i) = ~((\/_{i=1}^{k} A_i) \/ A_{k+1}), que, por De Morgan para o caso n=2, é igual a ~(\/_{i=1}^{k} A_i) /\ ~A_{k+1}.
Agora, utilizando a hipótese, temos que isso é igual a (/\_{i=1}^k ~A_i ) /\ ~A_{k+1} = /\_{i=1}^{k+1} ~A_i.

2) Suponha que, para certo k, ~(/\_{i=1}^k A_i) = \/_{i=1}^k ~A_i.
Então ~(/\_{i=1}^{k+1} A_i) = ~((/\_{i=1}^{k} A_i) /\ A_{k+1}), que, por De Morgan para o caso n=2, é igual a ~(/\_{i=1}^{k} A_i) \/ ~A_{k+1}.
Agora, utilizando a hipótese, temos que isso é igual a (\/_{i=1}^k ~A_i ) \/ ~A_{k+1} = \/_{i=1}^{k+1} ~A_i.

Esses dois passos indutivos, um para cada lei, concluem a nossa prova.

Já vimos a tabela verdade para a operação E e a operação OU, que são operações que tomam dois argumentos.

Podemos generalizar isso para operações binárias quaisquer, montando a tabela verdade dela e depois simplificando a expressão obtida usando nossos resultados de álgebra booleana.

Primeiro dois exemplo simples, a operação chamada PRIMEIRO e a operação chamada SEGUNDO, são dadas pelaa seguintes tabelas verdade:

a | b | primeiro(a,b)
0 | 0 | 0
0 | 1 | 0
1 | 0 | 1
1 | 1 | 1


a | b | segundo(a,b)
0 | 0 | 0
0 | 1 | 1
1 | 0 | 0
1 | 1 | 1


Podemos achar uma expressão algébrica, em termo de Es OUs e NÃOs, para o que nos informa uma tabela verdade, da seguinte forma: onde no resultado houver 1, olhamos para o a e o b (nesse caso de dois argumentos) e onde for zero negamos e onde for 1 não negamos, juntamos com E e fazemos o OU de todos. Assim capturamos todos os casos em que resulta em 1 e o OU deles será 1 sempre que pelo menos um deles for satisfeito e será 0 sempre que nenhum deles for satisfeito. Exemplo:

Para a operação primeiro, obtemos a expressão,
primeiro(a,b) = a*(~b) + a*b ((a E (NÃO b)) OU (a E b))
Podemos usar a propriedade distributiva e outras que vimos acima para simplificar a expressão.
primeiro(a,b) = a*(~b) + a*b = a*(~b + b) = a*1 = a

Similarmente para a operação segundo,
segundo(a,b) = (~a)*b + a*b = (~a + a)*b = 1*b = b

Agora vou fazer o xor e o iff.

a | b | a xor b
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0


a | b | a iff b
0 | 0 | 1
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1



a xor b = (~a)*b + a*(~b)
Não é possível simplificar mais que isso.
a iff b = (~a)*(~b) + a*b
Não é possível simplificar mais que isso.

Note que, por De Morgan, a iff b = ~(a xor b). (Também podemos ver isso na tabela.)
De fato, 
~(a xor b) = ~((~a)*b + a*(~b)) = ~((~a)*b)*~(a*(~b)) = (a+(~b))*((~a)*b) = a*(~a) + a*b + (~b)*(~a) + (~b)*b = 0 + a*b + (~a)*(~b) + 0 = a*b + (~a)*(~b) = (~a)*(~b) + a*b = a iff b .