Lógica Matemática

Lógica Matemática

I - Introdução
A Lógica Matemática, em síntese, pode ser considerada como a ciência do raciocínio e da demonstração. Este importante ramo da Matemática desenvolveu-se no século XIX, sobretudo através das idéias de George Boole , matemático inglês (1815 - 1864), criador da Álgebra Booleana, que utiliza símbolos e operações algébricas para representar proposições e suas inter-relações.
As idéias de Boole tornaram-se a base da Lógica Simbólica, cuja aplicação estende-se por alguns ramos da eletricidade, da computação e da eletrônica.A lógica matemática (ou lógica simbólica), trata do estudo das sentenças declarativas também conhecidas como proposições , as quais devem satisfazer aos dois princípios fundamentais seguintes:
Princípio do terceiro excluído: uma proposição só pode ser verdadeira ou falsa , não havendo outra alternativa.
Princípio da não contradição: uma proposição não pode ser ao mesmo tempo verdadeira e falsa.
Diz-se então que uma proposição verdadeira possui valor lógico V (verdade) e uma proposição falsa possui valor lógico F (falso). Os valores lógicos também costumam ser representados por 0 (zero) para proposições falsas ( 0 ou F) e 1 (um) para proposições verdadeiras ( 1 ou V ).
As proposições são indicadas pelas letras latinas minúsculas: p, q, r, s, t, u, ...

II – Lógica Formal

Fornece as bases para o método de pensar organizado e cuidadoso que caracteriza qualquer atividade racional – como uma investigação criminal, uma experiência científica, um estudo sócio-lógico.

1. Proposições, Representações Simbólicas

Uma proposição (ou declaração) é uma sentença afirmativa (expressão de uma linguagem) que pode ser verdadeira ou falsa.

Exemplos: Proposições Simples:
a) Dez é maior que sete : Proposição Verdadeira
b) Como está você? : Não é proposição
c) Ela é muito talentosa: “Ela” não está especificada, assim, a sentença não é falsa nem verdadeira.

Conectivos e Valores Lógicos:

Conectivos Lógicos: O valor lógico de uma proposição composta depende dos valores lógicos de seus componentes e dos conectivos usados.
Exemplo:
a) Dez é maior que sete e três é menor que cinco.
Conectivo Lógico: e (Conjunção)
Representação:

b) Hoje é terça-feira ou hoje é quarta-feira.
Conectivo Lógico: ou (Disjunção)
Representação:

c) Ou hoje é terça-feira ou hoje é quarta-feira.
Conectivo Lógico: ou exclusivo
Representação:

d) Se eu passar na prova, então, irei ao cinema.
Conectivo Lógico: Se, então. (Condicional ou Implicação)
Representação:

e) Carlos passará no concurso, se e somente se, estudar muito.
Conectivo Lógico: Se, e somente se. (Bicondicional)
Representação:

f) Hoje não vai chover.
Conectivo Lógico: negação.
Representação: ‘ , ~,

Agora, iremos substituir cada sentença (proposição) pelas seguintes variáveis:

a) Dez é maior que sete e três é menor que cinco.
p
q

Temos: p q (Lê-se: p e q)

b) Hoje é terça-feira ou hoje é quarta-feira.
p
q

Temos: p q (Lê-se: p ou q)

c) Ou hoje é terça-feira ou hoje é quarta-feira.
p
q

Temos: p q (Lê-se: ou p ou q)

d) Se eu passar na prova, então, irei ao cinema.
p
q

Temos: p q (Lê-se; p implica em q ; Se p então q).
p é a proposição antecedente e q é a proposição consequente.

e) Carlos passará no concurso, se e somente se, estudar muito.
p
q

Temos: p q (Lê-se : p, se e somente se, q)

f) Hoje não vai chover.
p

Temos: p’ (Lê-se: não p ; p negado.)

O fato das proposições verdadeiras (valor lógico 1) ou falsas (valor lógico 0), não podem estar associadas à analogia de que zero (0) pode significar um circuito elétrico desligado e um (1) pode significar um circuito elétrico ligado? Isto lembra alguma coisa vinculada aos computadores? Pois é, isto é uma verdade, e é a base lógica da arquitetura dos computadores!
Seria demais imaginar que a proposição pÙ q pode ser associada a um circuito série e a proposição pÚ q a um circuito em paralelo?
Pois, as analogias são válidas e talvez tenham sido elas que mudaram o mundo!

A combinação das proposições simples formadas por p e q pode ser considerada verdadeira ou falsa. Assim, as diversas combinações possíveis entre p e q são distribuídas na tabela-verdade:

Tabela-Verdade para p q (Lê-se: p e q)

p
q
p q
V
V
V
V
F
F
F
V
F
F
F
F

Tabela-Verdade para p q (Lê-se: p ou q)

p
q
p q
V
V
V
V
F
V
F
V
V
F
F
F


Tabela-Verdade para p q (Lê-se: ou p ou q; p ou q, mas não ambos)

p
q
p q
V
V
F
V
F
V
F
V
V
F
F
F


Tabela-Verdade para p q (Lê-se: p implica em q; Se p então q)

p
q
p q
V
V
V
V
F
V
F
V
F
F
F
V

“Por convenção, p q é considerada verdadeira se p for falsa , independentemente do valor lógico de q”
p é a proposição antecedente e q é a proposição consequente.

Tabela-Verdade para p q (Lê-se: p, se e somente se, q)

p
q
p q
V
V
V
V
F
F
F
V
F
F
F
V

Podemos notar que p q é verdadeira somente quando p e q têm os mesmos valores lógicos.

A relação p q (p q) (q p) é verdadeira, prove:

p
q
p q
q p
(p q) (q p)
p q


























Tabela-Verdade para p’ (Lê-se: não p, p negado)

P
P’
V
F
F
V


Expressão em Português
Conectivo Lógico
Expressão Lógica
e, mas, também, além disso
Conjunção
- p q
ou
Disjunção
- p q
Se p, então, q
Condicional ou Implicação
- p q
p, se e somente se, q
Bicondicional
- p q
não p (não é verdade que p)
Negação
- p’

Podemos encadear proposições e conectivos para formar novas expressões:

Cálculo Proposicional:

Exemplo:
1) (p q) (q p)
Conectivo principal:

2) p (q r)’
Conectivo principal:

3) ((p q) r) (q r’)
conectivo principal:

Escrevemos a tabela-verdade para qualquer expressão composta:

a) (p q’) (q q’)



























b) [(p q’) r’]’














































Tautologia:

Uma tautologia é “intrinsicamente verdadeira” por sua própria estrutura.
Ela é verdadeira, independentemente, dos valores lógicos atribuídos às suas proposições.
Exemplo: Hoje vai ter sol ou hoje não vai ter sol. – Sempre é uma tautologia. Sempre será verdadeira, pois uma das duas coisas tem que acontecer.

Contradição:

Uma contradição é “intrinsicamente falsa” pela sua própria estrutura.
Exemplo: Hoje é segunda-feira e hoje não é segunda-feira. – Sempre será falsa!

Quando p q representam uma tautologia, os valores lógicos de p e q são iguais em todas as linhas da tabela-verdade. Nesse caso, dizemos que p e q são expressões equivalentes, denotamos essa propriedade por p q. Assim, p q enuncia o fato de p q ser uma tautologia.
Assim, (p q) (q’ p’). Prove.







Prove também que p q (p q)’






Algumas Equivalências Tautológicas:

1a. p q q p
1b. p q q p
Comutatividade
2a. (p q) r p (q r)
2b. (p q) r p (q r)
Associatividade
3a.p (q r) (p q) (p r)
3b.p (q r) (p q) (p r)
Distributividade
4a. p 0 p
4b.p 1 p
Elementos neutros
5a .p p’ 1
5b.p p’ 0
Complementares

Duas equivalências adicionais muito importantes:

1) Leis de DeMorgan (Augusto DeMorgan – matemático – século XIX)

(p q)’ p’ q’
(p q)’ p’ q’

2) Negação da condicional(p® q)’ = pÙ q’
Todas as propriedades acima podem ser verificadas com a construção das tabelas verdades. Vamos exemplificar verificando a propriedade dos itens (1 e 2):Para isto, vamos construir as tabelas verdades de 1 e 2:




Exercícios:

01. Escreva a sentença em notação simbólica e, em seguida, sua negação.


a) O processador é rápido, mas a impressora é lenta.


b) O processador é rápido ou a impressora é lenta.


c) Se o processador é rápido, então a impressora é lenta.


d) Se o arquivo não está danificado e o processador é rápido, então a impressora é lenta.



02. Escreva cada uma das proposições compostas a seguir em notação simbólica usando letras de proposição para denotar os componentes.

a) Se os preços subirem, então haverá muitas casas para vender e elas serão caras, mas se as casas não forem caras, então, ainda assim, haverá muitas casas para vender.

b) Tanto ir dormir como ir nadar é uma condição suficiente para a troca de roupa, no entanto, mudar a roupa não significa que se vai nadar.

c) Vai chover ou nevar mas não ambos.

d) Se Jane vencer ou perder, vai ficar cansada.

e) Ou Jane irá vencer ou, se perder, ela ficará cansada.

f) Uma economia forte virá se Anita ganhar as eleições. (ver quem é o antecedente e quem é o consequente).

g) Uma economia permanecerá forte se, e somente se, Anita ganhar a eleição e os impostos forem reduzidos.
Conectivos Lógicos no Mundo Real


Os programas de busca na rede permitem a exploração de recursos imensos disponíveis, porém cuidado. Se você escrever carros usados, você pode obter de volta referências na rede contendo todas as buscas com as palavras carros e usados. Se você escrever entre aspas “carros usados”, você está restringindo a busca às páginas contendo exatamente essa frase. Para restringir ainda mais a sua pesquisa, você poderia colocar, por exemplo:
“carros usados” E (Ford ou Fiat)
Muitos programas de busca usam + no lugar de E (ou AND) e – no lugar de ENÃO (ou AND NOT).
Os conectivos E (AND), ou (OR) e NÃO (NOT) estão disponíveis em muitas linguagens de programação ( , ,‘). Esses conectivos, de acordo com as tabelas verdade que definimos, agem em combinação de expressões verdadeiras ou falsas para produzir um valor lógico final.
Tais valores lógicos fornecem a capacidade de decisão fundamental ao fluxo de controle em programas de computadores. Assim, em uma ramificação condicional de um programa, se o valor lógico da expressão condicional for verdadeiro, o programa executará a seguir um trecho de seu código; se o valor for falso, ele executará um trecho diferente de seu código. Se a expressão condicional for substituída por outra expressão equivalente mais simples, o valor lógico da expressão, e, portanto, o fluxo de controle do programa, não será afetado, mas o novo código será mais fácil de ser entendido e poderá ser executado mais rapidamente.
3) Considere uma proposição em um programa de computador da forma:

Sendo A: “Fluxo De Saída > Fluxo De Entrada”
B : “Pressão < 1000”

If (( Fluxo De Saída > Fluxo De Entrada)
And not ((Fluxo De Saída > Fluxo De Entrada)
And (Pressão < 1000)))

Do Alguma Coisa;

Else

Do Outra Coisa.


Observação: Se V: o programa executa uma linha de seu código), se F: o programa executa um trecho diferente de seu código, até que seja encontrado o valor V.

Escreva a expressão condicional do algoritmo acima:




Essa expressão pode ser simplificada, substituindo a fórmula por outra equivalente. Escreva todas as equivalências tautológicas encontradas. Vamos testar.
4) Escreva uma expressão lógica para que um programa de busca na rede encontre todas as páginas sobre:

a) cachorros que não são de caça.
b) pinturas à óleo de Van Gogh ou de Rembrandt, mas não de Vermeer.




5) Suponha que A, B e C representam condições que serão verdadeiras ou falsas quando um certo programa é executado. Suponha, ainda, que você quer que o programa realize uma determinada tarefa, somente quando A ou B for verdadeira (mas não ambas) e C falsa. Usando A, B, e C e os conectivos E, Ou e NÃO, escreva uma proposição que será verdadeira apenas nessas condições.




6) Quatro máquinas A, B, C e D estão conectadas em uma rede de computadores. Receia-se que um vírus de computador possa ter infectado a rede. Seu grupo de segurança de rede faz as seguintes afirmações:

- Se D estiver infectado, C também está.
- Se C estiver infectado, A também está.
- Se D estiver limpo, então B está limpo, mas C está infectado.
- Se A estiver infectado, então ou B está infectado, ou C está limpo.

Supondo todas essas proposições verdadeiras, o que você pode concluir?