Eletrônica Digital/Lógica

Introdução

As pessoas costumam pensar na matemática como uma série de regras e operações que são aplicadas sempre à números com o objetivo de simular ações da vida real, como dividir uma maçã entre três pessoas, dobrar a velocidade de um veículo ou aplicar um desconto de 30% a uma mercadoria.

Entretanto, esta definição é uma definição errônea. A matemática não lida apenas com números que representam quantidades. A matemática é uma ferramenta que serve para lidar com absolutamente qualquer coisa que segue uma lógica clara e bem-definida. Matemática é a aplicação pura de lógica.

A lógica vem do grego clássico λόγος (logos), é uma ciência de índole matemática e fortemente ligada à Filosofia. Já que o pensamento é a manifestação do conhecimento, e que o conhecimento busca a verdade, é preciso estabelecer algumas regras para que essa meta possa ser atingida. Assim, a lógica é o ramo da filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar. A aprendizagem da lógica não constitui um fim em si. Ela só tem sentido enquanto meio de garantir que nosso pensamento proceda corretamente a fim de chegar a conhecimentos verdadeiros. Podemos, então, dizer que a lógica trata dos argumentos, isto é, das conclusões a que chegamos através da apresentação de evidências que a sustentam.

Toda a matemática é construída de forma lógica. Isso significa que em cada ramo da matemática existe um certo número limitado de proposições que são reconhecidos como verdadeiros. À partir de um raciocínio dedutivo, buscamos sempre extrair novos teoremas que sempre são conseqüências dos axiomas iniciais.

Por exemplo: Considere como verdadeiros os seguintes axiomas definidos sobre o conjunto de números T={0, 1}:

Axioma 1: 1 é maior do que 0
Axioma 2: Existe uma operação denominada "v" tal que quando à usamos em um número pertencente à T, obtemos como resposta o maior número usado como operando
Axioma 3: Existe uma operação denominada "^" tal que quando à usamos em um número pertencente à T, obtemos como resposta o menor número usado como operando
Teorema 1: Se $x\in T$ , então x^1=1.

No exemplo acima, as três primeiras afirmações são axiomas, pois nós assumimos à priori que elas são verdadeiras. Nós não nos preocupamos em encontrar provas de que elas são verdadeiras. Elas são afirmações arbitrárias consideradas verdadeiras. Já a quarta afirmação não é um axioma, mas um teorema. Afinal, ele é uma conseqüência do Axioma 1 e do Axioma 3.

Tradicionalmente, também chamamos de lógica a designação para o estudo de sistemas prescritivos de raciocínio, ou seja, sistemas que definem como se "deveria" realmente pensar para não errar, usando a razão, dedutivamente e indutivamente. A forma como as pessoas realmente raciocinam é estudado noutras áreas, como na psicologia cognitiva.

Como ciência, a lógica define a estrutura de declaração e argumento e elabora fórmulas através das quais estes podem ser codificados. Implícita no estudo da lógica está a compreensão do que gera um bom argumento e de quais os argumentos que são falaciosos.

A lógica filosófica lida com descrições formais da linguagem natural. A maior parte dos filósofos assumem que a maior parte do raciocínio "normal" pode ser capturada pela lógica, desde que se seja capaz de encontrar o método certo para traduzir a linguagem corrente para essa lógica.

Outra coisa que é importante de ser mencionada é que existe mais de um tipo de lógica. A lógica clássica é chamada de Lógica Booleana. Esta é a lógica que costuma ser mais usada na matemática, computação clássica, na filosofia e no nosso dia-a-dia. Entretanto, existem outros modelos de lógica que são bastente úteis em outras áreas de conhecimento. Por exemplo, existe a Lógica Difusa (também chamada de Lógica Fuzzy) que é bastante usada na Computação Quântica. Mas ao longo deste wikilivro, nos limitaremos apenas à Lógica Booleana justamente por ser a mais simples, intuitiva e também a mais usada de todas.

Limitações da Lógica

Como você pode ter reparado, a lógica e a matemática tem algumas limitações. A principal delas é que elas não tem nenhuma pretensão de ser uma representação fiel do nosso universo ou da realidade. Elas buscam ser apenas um modelo coerente, mas não necessariamente um modelo fiel ao nosso universo.

Veja por exemplo, a frase "Esta frase é falsa.". Ela é verdadeira ou falsa? Se for verdadeira, então concluímos que ela é falsa. Mas isso é uma contradição! Por outro lado, se ela for falsa, concluímos que ela é verdadeira, o que também é uma contradição! Este é um exemplo de uma afirmação que pode ocorrer em nosso universo que não obedece à lógica clássica.

Como conseqüência desta limitação da matemática, os axiomas que escolhemos em cada área da matemática são bastante arbitrários. É perfeitamente possível criar modelos lógicos e matemáticos conflitantes. A lógica clássica afirma que uma proposição só pode ser verdadeira ou falsa - mas não ambos. Já a Lógica Difusa afirma que uma proposição pode ser verdadeira, falsa ou pode ser algo intermediário entre verdadeiro e falso (35% verdadeira e 65% falsa, por exemplo). Qual das duas lógicas seria a verdadeira? A resposta é que não existe uma lógica verdadeira que tem a pretensão de descrever o nosso universo. Cada uma das lógicas tem as suas vantagens e desvantagens. Ao analizarmos o universo ou o funcionamento de um computador, por exemplo, devemos escolher qual das duas usar (a clássica é melhor para computadores clássicos e a difusa é melhor para computadores quânticos) ou se desejamos criar uma lógica completamente nova.

Exercícios

1. Analize as seguintes afirmações: "Sabemos que se uma cidade é capital de um país, ela fica dentro deste país. Também sabemos que a cidade de Tóquio fica dentro do Japão. Com estas duas informações, podemos concluir que Tóquio é a capital do Japão." O raciocínio mostrado nas frases indicadas está correto? Porque?

2. Assuma como verdadeiros os três axiomas dados no texto sobre o conjunto de números T={0,1}. Você acha que se $X,Y,Z\in T$ , a afirmação $X$ ^ $(Y$ v $Z)=(X$ ^ $Y)$ v $(X$ ^ $Z)$ é verdadeira ou falsa?

3. E se substituírmos o primeiro axioma por "1 é igual à 0"? Você acha que o Teorema 1 mostrado no texto ainda seria válido?

Resposta dos Exercícios

1. Não. Apesar da conclusão à qual ele chega ser verdadeira, a lógica usada para se chegar até ela é falha. Afinal, se uma cidade é capital de um país, ela fica dentro do país. Mas isso não significa que se uma cidade está dentro de um país, ela é a sua capital. Uma cidade pode estar dentro de um país sem ser a sua capital (Kyoto fica no Japão, mas não é sua capital). Com isso, podemos notar que o fato da conclusão obtida por um raciocínio ser correta, não prova que o raciocínio empregado foi correto.

2. É verdadeira. Deixemos para provar isso mais adiante no livro.

3. Sim. Se 1=0, podemos usar o mesmo símbolo para escrever os dois números. No teorema x^1=1, se x=1, então obtemos 1^1=1, que é verdadeiro segundo o Axioma 3. Se x=0, então obtemos 0^1=1. Se 0=1, podemos substituir 0 por 1 e obtemos 1^1=1, o que é verdadeiro.

Cálculo proposicional

Cálculo proposicional é um sistema da lógica matemática que representa os princípios e operações da lógica proposicional .

Proposição

Proposição é uma sentença declarativa afirmativa que pode assumir um valor de Verdadeiro (V) ou Falso (F).

Como exemplo de proposições temos:

A terra é redonda.

O dado é quadrado.

As proposições de acordo com a lógica clássica devem seguir os seguintes princípios:

Princípio da não-contradição: uma proposição não pode ser verdadeira ou falsa ao mesmo tempo.
Princípio do terceiro excluído: uma proposição deve obrigatoriamente ser verdadeira ou falsa, mas não ter uma terceira possibilidade.

Símbolos

Variáveis proposicionais

Podemos representar proposições através de frases como fizemos logo acima. Entretanto, a partir de agora, passaremos a representar proposições através de letras minúsculas a partir do p. (Por exemplo. p, q e outros).

Dentro da lógica proposicional cada proposição é considerado um elemento simples (átomo). Representá-los por letras ao invés de frases é útil porque:

É mais rápido e prático de escrever.
Isso permite que nos concentremos apenas na lógica empregada. Se usássemos frases como "O céu é azul", os nossos conhecimentos à priori sobre a cor do céu iriam induzir o nosso raciocínio e a nossa conclusão a respeito do valor da proposição.

Conectivos lógicos

As fórmulas atômicas podem ser combinadas entre si utilizando-se os conectivos lógicos. Utilizam-se os parênteses para delimitar o alcance de cada conectivo. Uma cadeia que forma uma expressão válida (isto é que ofereça um valor F [falso] ou V [verdadeiro] de retorno) é chamado de fórmula bem-formulada (fbf).

Valor lógico	Símbolo	Expressão	Observação
Negação	$\not$ , ¬ , ~ ou '	não, é falso, não é verdade que	inverte o valor da proposição
Conjunção	$\land$	e, mas , também, além disso	nenhuma
Disjunção	$\lor$	ou	não confundir com o ou exclusivo
Condicional	$\to$	se...então, implica, logo, somente se	nenhuma
Bi-condicional	$\leftrightarrow$	...se, e somente se...; ...é condição necessária que ...	nenhuma

Tabelas-verdades

Tabelas-verdades sao matrizes de V ou F que uma proposição assume de acordo com o conectivo lógico associado a ele. Utilizaremos a letra p para representar o uso de conectivos sobre apenas uma proposição, e p e q quando o conectivo age sobre duas proposições.

Negação

p	¬ p
V	F
F	V

Conjunção

p	q	p $\land$ q
V	V	V
F	V	F
V	F	F
F	F	F

Disjunção

p	q	p $\lor$ q
V	V	V
V	F	V
F	V	V
F	F	F

Condicional

p	q	p $\to$ q
V	V	V
V	F	F
F	V	V
F	F	V

Bi-condicional

p	q	p $\leftrightarrow$ q
V	V	V
V	F	F
F	V	F
F	F	V

Disjunção-exclusiva

p	q	p $\lor$ q
V	V	F
V	F	V
F	V	V
F	F	F

Proposições compostas

Uma proposição composta é um conjunto de proposições simples com seus conectivos, representada por uma letra maiúscula. Ex: P: p $\land$ q ou P (p,q):p,q. Para n proposições simples com possibilidades V e F, considera-se que a tabela-verdade que os combina terá $2^{n}$ linhas.

Tautologia

Tautologia é uma proposição composta onde todas as suas combinações finais são V.

Contradição

Contradição é uma proposição composta onde todas as suas combinações finais são F.

Contigência

Contingência é uma proposição composta onde os valores F e V aparecem pelo menos uma vez nas combinações finais.

Implicação

Uma proposição implica logicamente outra quando, e somente quando, para cada atribuição de valores verdade que torna uma proposição verdadeira, também tornam sua implicação verdadeira. Ou seja, dadas duas proposições P e Q, P implica Q todas as vezes que ambos os lados aparecerem V.

p	q	(P) p $\land$ q	(Q)p $\lor$ q	(R) p $\leftrightarrow$ q
V	V	V	V	V
V	F	F	V	F
F	V	F	V	F
F	F	F	F	V

Equivalência lógica

Uma proposição composta é logicamente equivalente a outra se suas tabelas-verdades são idênticas. A equivalência lógica é representada por ( $\Longleftrightarrow$ ).

Resumo

Cálculo proposicional é um sistema da lógica matemática que representa os princípios e operações da lógica proposicional .
Proposição é uma sentença declarativa afirmativa que pode assumir um valor de Verdadeiro (V) ou Falso (F).Uma proposição não pode ser verdadeira ou falsa ao mesmo tempo e uma proposição deve obrigatoriamente ser verdadeira ou falsa, mas não ter uma terceira possibilidade.
As fórmulas atômicas podem ser combinadas entre si utilizando-se os conectivos lógicos.Utilizam-se os parênteses para delimitar o alcance de cada conectivo.
Uma proposição composta é um conjunto de proposições simples com seus conectivos, representada por uma letra maiúscula.
Tautologia é uma proposição composta onde todas as suas combinações finais são V.
Contradição é uma proposição composta onde todas as suas combinações finais são F.
Contingência é uma proposição composta onde os valores F e V aparecem pelo menos uma vez nas combinações finais.
Uma proposição implica logicamente outra quando, e somente quando, para cada atribuição de valores verdade que torna uma proposição verdadeira, também tornam sua implicação verdadeira.
Uma proposição composta é logicamente equivalente a outra se suas tabelas-verdades são idênticas.

Exercícios

p->q,~q|-~q

Bibliografia

Klement, Kevin C. (2006), "Propositional Logic", in James Fieser and Bradley Dowden (eds.), Internet Encyclopedia of Philosophy, Eprint.
Introduction to Mathematical Logic
Elements of Propositional Calculus
forall x: an introduction to formal logic, por P.D. Magnus, covers formal semantics and proof theory for sentential logic.
Lógica/Cálculo Proposicional Clássico