Capítulo 01: Lógica Matemática, Álgebra Booleana e Circuitos Lógicos

Módulo 01: Fundamentos da Computação • Ciência da Computação Formal

🗺️ 1. Mapa Conceitual da Lógica e Circuitos

flowchart TD
    A["Proposições e Conectivos Lógicos"] --> B["Tabelas-Verdade"]
    B --> C["Álgebra Booleana (Leis de De Morgan)"]
    C --> D["Portas Lógicas Digitais (AND, OR, NOT, XOR)"]
    D --> E["Minimização: Mapas de Karnaugh"]
    E --> F["Circuitos Integrados e ALUs"]

    style A fill:#e1f5fe,stroke:#03a9f4,stroke-width:2px
    style C fill:#ede7f6,stroke:#7e57c2,stroke-width:2px
    style D fill:#e8f5e9,stroke:#4caf50,stroke-width:2px
    style F fill:#fff3e0,stroke:#ff9800,stroke-width:2px

🏛️ 2. Fundamentação Teórica e Formal

A Lógica Proposicional e a Álgebra Booleana (desenvolvida por George Boole em 1854 e aplicada a circuitos elétricos por Claude Shannon em 1937) constituem o fundamento matemático de toda a computação digital. Na máquina binária, toda informação e processamento são expressos por meio de estados discretos de tensão: $1$ (Verdadeiro / High) e $0$ (Falso / Low).

2.1 Conectivos Lógicos Fundamentais

Sejam $P$ e $Q$ duas proposições lógicas:

Operação Símbolo Booleano Notação Lógica Expressão em Código Descrição Formal
Negação (NOT) $\overline{A}$ ou $A’$ $\neg P$ !P ou not P Inverte o valor lógico.
Conjunção (AND) $A \cdot B$ $P \land Q$ P && Q ou P and Q Verdadeiro apenas se ambos forem 1.
Disjunção (OR) $A + B$ $P \lor Q$ P || Q ou P or Q Verdadeiro se pelo menos um for 1.
Disjunção Exclusiva (XOR) $A \oplus B$ $P \oplus Q$ P ^ Q Verdadeiro se as entradas forem distintas.
Não-Conjunção (NAND) $\overline{A \cdot B}$ $\neg(P \land Q)$ !(P && Q) Porta universal: 0 apenas se ambos forem 1.
Não-Disjunção (NOR) $\overline{A + B}$ $\neg(P \lor Q)$ !(P || Q) Porta universal: 1 apenas se ambos forem 0.
Implicação $\overline{A} + B$ $P \to Q$ !P || Q Falso apenas quando $P=1$ e $Q=0$.
Bicondicional $A \odot B$ $P \leftrightarrow Q$ P == Q Verdadeiro quando $P$ e $Q$ possuem o mesmo valor.

2.2 Postulados e Leis da Álgebra Booleana

As identidades fundamentais permitem otimizar expressões lógicas para reduzir a quantidade física de transistores em um chip:

  1. Elemento Neutro: $A + 0 = A \quad \text{e} \quad A \cdot 1 = A$
  2. Elemento Nulo: $A + 1 = 1 \quad \text{e} \quad A \cdot 0 = 0$
  3. Idempotência: $A + A = A \quad \text{e} \quad A \cdot A = A$
  4. Complementaridade: $A + \overline{A} = 1 \quad \text{e} \quad A \cdot \overline{A} = 0$
  5. Comutatividade: $A + B = B + A \quad \text{e} \quad A \cdot B = B \cdot A$
  6. Associatividade: $(A + B) + C = A + (B + C) \quad \text{e} \quad (A \cdot B) \cdot C = A \cdot (B \cdot C)$
  7. Distributividade: $A \cdot (B + C) = (A \cdot B) + (A \cdot C) \quad \text{e} \quad A + (B \cdot C) = (A + B) \cdot (A + C)$
  8. Teoremas de De Morgan: \(\overline{A \cdot B} = \overline{A} + \overline{B}\) \(\overline{A + B} = \overline{A} \cdot \overline{B}\)

2.3 O Princípio da Universalidade das Portas NAND e NOR

Na engenharia de semicondutores e fabricação de circuitos integrados (VLSI), construir transistores CMOS que realizam a operação NAND ou NOR é fisicamente mais simples e rápido do que fabricar portas AND ou OR diretas. Pelo Teorema da Universalidade:

  • Qualquer função booleana concebível pode ser sintetizada utilizando exclusivamente portas NAND (ou exclusivamente NOR).
  • Exemplo: $\text{NOT}(A) = A \text{ NAND } A$.
  • $\text{AND}(A, B) = \text{NOT}(A \text{ NAND } B) = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)$.

2.4 Síntese de Circuitos: Somador Completo (Full Adder)

Um computador realiza somas binárias encadeando blocos de Somador Completo, que computa a soma de dois bits ($A, B$) mais o bit de transporte de entrada ($C_{in}$):

\(\text{Soma } (S) = A \oplus B \oplus C_{in}\) \(\text{Transporte de Saída } (C_{out}) = (A \cdot B) + (C_{in} \cdot (A \oplus B))\)

A propagação do sinal $C_{out}$ através de somadores em série constitui a base do Ripple-Carry Adder, elemento nuclear da Unidade Lógica e Aritmética (ALU).

💻 3. Implementação e Simulação Computacional

Abaixo está um simulador em Python que gera tabelas-verdade completas, valida as Leis de De Morgan e emula o circuito de um Somador Completo de 8 bits com detecção de overflow:

def full_adder(a: int, b: int, cin: int) -> tuple[int, int]:
    """Emula uma unidade funcional de somador completo de 1 bit."""
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def adder_8bit(x: int, y: int) -> tuple[int, int]:
    """Soma dois inteiros de 8 bits usando portas lógicas bit a bit."""
    soma = 0
    cin = 0
    for i in range(8):
        bit_a = (x >> i) & 1
        bit_b = (y >> i) & 1
        s, cin = full_adder(bit_a, bit_b, cin)
        soma |= (s << i)
    return soma, cin

def validar_de_morgan() -> bool:
    """Verifica exaustivamente as Leis de De Morgan para todas as combinações binárias."""
    for a in [0, 1]:
        for b in [0, 1]:
            # Lei 1: !(a & b) == !a | !b
            if (not (a and b)) != ((not a) or (not b)):
                return False
            # Lei 2: !(a | b) == !a & !b
            if (not (a or b)) != ((not a) and (not b)):
                return False
    return True

if __name__ == "__main__":
    print("=== SIMULAÇÃO DE CIRCUITO DIGITAL SOMADOR 8-BIT ===")
    x, y = 45, 27
    resultado, overflow = adder_8bit(x, y)
    print(f"Entrada A : {x:3d} (binário: {x:08b})")
    print(f"Entrada B : {y:3d} (binário: {y:08b})")
    print(f"Soma      : {resultado:3d} (binário: {resultado:08b})")
    print(f"Carry-Out : {overflow} (Overflow: {'SIM' if overflow else 'NÃO'})")
    assert resultado == x + y, "Erro no circuito somador!"
    print(f"Validação Formal De Morgan: {'APROVADA' if validar_de_morgan() else 'FALHA'}")