Logica Matematica 02

Prévia do material em texto

Lógica Matemática
Operações Lógicas
Fábio Gondim
fabio.iesp # gmail.com (#=@)
http://fabio.iesp.googlepages.com
Linguagem
Todos os homens são mortais.
Sócrates é um homem.
Portanto, Sócrates é mortal.
All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.
Para quem conhece a língua portuguesa e um 
pouco da inglesa é fácil perceber que estamos 
expondo o mesmo argumento embora utilizando 
idiomas diferentes.
2
Todos os homens são mortais.
Sócrates é um homem.
Portanto, Sócrates é mortal.
Todos os gatos gostam de peixe.
Tom é um gato.
Portanto, Tom gosta de peixe.
O que é que este conjunto de proposições têm em 
comum?
Em ambos os casos expressamos um raciocínio 
dedutivo em que caminhamos do geral para o 
particular, do todo para a parte, para concluirmos 
algo.
3
Considere agora o seguinte argumento:
Todo Pif é Paf.
Pof é um Pif.
Portanto, Pof é um Paf.
Este argumento faz sentido?
Quem respondeu que não, experimente trocar:
Pif por homem, Paf por mortal e Pof por 
Sócrates.
4
Considere agora o seguinte argumento:
Todo Pif (homem) é Paf (mortal).
Pof (Sócrates) é um Pif (homem).
Portanto, Pof (Sócrates) é um Paf (mortal).
Este argumento faz sentido?
Quem respondeu que não, experimente trocar:
Pif por homem, Paf por mortal e Pof por 
Sócrates.
Ainda acha que não faz sentido?
5
Os argumentos anteriores podem ser resumidos a forma:
Todos os elementos do tipo “A”
pertencem ao conjunto “B”.
“S” é do tipo “A”.
“S” pertence ao conjunto “B”.
Ou:
Todo A é B.
S é A.
Portanto, S é B
Está ficando claro que a forma é o que importa?
6
“Portanto, a validade ou não-validade de 
um argumento depende apenas da sua 
forma e não de seu conteúdo ...”
Edgard de Alencar Filho no livro
Iniciação à Lógica Matemática
(ver bibliografia)
7
Relembre o conceito de argumento: Raciocínio, 
indício ou prova pelo qual se tira uma conseqüência 
ou dedução. 
Agora voltemos ao argumento:
Todos os gatos gostam de peixe.
Tom é um gato.
Portanto, Tom gosta de peixe.
E se Tom é não é um gato e sim um cachorro?
Isto torna o argumento inválido?
Resposta: Não. Só podemos afirmar que um 
argumento é inválido quando todas as suas 
premissas forem verdadeiras e a conclusão for 
falsa.
8
Completando a citação anterior:
“Portanto, a validade ou não-validade de um 
argumento depende apenas da sua forma e não de 
seu conteúdo ou da verdade e falsidade das 
proposições que o integram. (...)
(...) E afirmar que uma dada forma é válida 
equivale a asseverar que não existe argumento 
algum dessa forma com premissas verdadeiras e 
uma conclusão falsa, isto é todo argumento de 
forma válida é um argumento válido.”
Edgard de Alencar Filho no livro
Iniciação à Lógica Matemática
(ver bibliografia)
9
Linguagens: Natural e Formal
Linguagens são sistemas de símbolos que servem 
como meio de comunicação.
As linguagens naturais são muito expressivas, 
porém sujeitas a imprecisões e ambigüidades. 
O formalismo foi introduzido no estudo da lógica 
para evitar a ambigüidade e garantir a precisão e 
a consistência. 
Linguagens formais são objetos matemáticos, 
cujas regras de formação são precisamente 
definidas e as quais podemos atribuir um único 
sentido, sem ambigüidade.
10
Linguagem proposicional
Neste curso utilizaremos a linguagem proposicional, que 
apesar da aparente simplicidade nos permite expressar 
uma série de importantes relações lógicas.
O alfabeto da linguagem proposicional é constituído por: 
Símbolos de pontuação: “(“ e “)”;
Símbolos de verdade: V e F (Verdadeiro e Falso);
Símbolos proposicionais: P, Q, R, ..., P1, Q1, ..., p, q, r, 
p1, q2, etc. (As letras minúsculas representam 
proposições simples e, as maiúsculas, as compostas);
Conectivos proposicionais: “~”, “^”, “v” “v”, “→” e “↔”.
Conectivos são palavras que se usam para formar novas 
proposições a partir de outras e são, geralmente, 
chamados de conectivos lógicos. 11
Valor Lógico de uma Proposição
Por definição, quando uma proposição é verdadeira o seu 
valor lógico é a verdade e quando é falsa, o seu valor 
lógico é a falsidade.
Notação: Usaremos V para verdade e F para falsidade.
Obs.: Alguns autores utilizam o algarismo “1” para a 
verdade e o algarismo “0” para a falsidade.
Lembre-se que, pelo princípio do terceiro excluído, uma 
proposição ou é verdadeira ou é falsa e que, portanto, 
não admite outras possibilidades. 
Lembre-se, ainda, que pelo princípio da não contradição 
uma proposição jamais será verdadeira e falsa ao mesmo 
tempo.
12
Valor Lógico de uma Proposição
Considerando duas proposições quaisquer P e Q temos 
que, analisadas, individualmente, cada uma delas poderá
ser ou verdadeira ou falsa:
V
P
F
V
Q
F
13
E se analisarmos as duas conjuntamente?
Teremos as seguintes possibilidades:
1. As duas são verdadeiras (V, V);
2. A primeira é verdadeira e a segunda é falsa (V, F);
3. A primeira é falsa e a segunda verdadeira (F, V);
4. As duas são falsas (F, F).
14
Representação em Árvore:
V
P
F
V (P=V, Q=V)
Q
F (P=V, Q=F)
V (P=F, Q=V)
Q 
F (P=F, Q=F)
15
Este tipo de agrupamento é definido na Análise 
Combinatória como sendo um Arranjo com Repetição. 
Arranjo porque a ordem é importante: isto significa que a 
seqüência “V F” é diferente da seqüência “F V”.
Com repetição porque o mesmo elemento pode aparecer 
mais de uma vez (ex.: “V V” e “F F”). Note que elemento 
repetido é diferente de seqüência repetida (ex.: a 
seqüência “V F” aparecer mais de uma vez, no exemplo 
anterior, não é válido).
Calculando as possibilidades:
Para uma proposição: Ar(2, 1) = 21 = 2;
Para duas proposições: Ar(2, 2) = 22 = 2 x 2 = 4;
Para três proposições: Ar(2,3) = 23 = 2 x 2 x 2 = 8;
Para n proposições: Ar(2, n) = 2n = ?. 16
Por que a base é sempre igual a 2?
Resposta: 
Os nossos arranjos têm sempre dois elementos 
possíveis em cada posição: “V” e “F”. Podemos 
dizer que se trata de um Arranjo Binário com 
Repetição.
A partir do quê conclui-se o valor de “n”?
Resposta: 
O valor de “n” representa o número de posições 
no arranjo que, neste caso, depende do número 
de proposições. 
17
p
V
F
p q
V V
V F
F V
F F
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
Uma proposição: 2 possibilidades;
Duas proposições: 4 possibilidades;
Três proposições: 8 possibilidades.
N proposições: 2N possibilidades.
18
p q r
Para garantir que nenhuma seqüência se repita 
vamos analisar um exemplo contendo três 
proposições quaisquer (p, q, r):
1) Calcule a quantidade de arranjos possíveis. 
A sua tabela deverá, então ter uma linha 
para cada arranjo e mais uma para o 
cabeçalho (neste exemplo, linhas = 23 + 1);
19
p q r
V
V
V
V
F
F
F
F
Para garantir que nenhuma seqüência se repita 
vamos analisar um exemplo contendo três 
proposições quaisquer (p, q, r):
1) Calcule a quantidade de arranjos possíveis. 
A sua tabela deverá, então ter uma linha 
para cada arranjo e mais uma para o 
cabeçalho (neste exemplo, linhas = 23 + 1);
2) Excluindo o cabeçalho, divida a primeira 
coluna na metade. Preencha a primeira 
metade com “V” e a segunda com “F”.
20
p q r
V V
V V
V F
V F
F V
F V
F F
F F
Para garantir que nenhuma seqüência se repita 
vamos analisar um exemplo contendo três 
proposições:
1) Calcule a quantidade de arranjos possíveis. 
A sua tabela deverá, então ter uma linha 
para cada arranjo e mais uma para o 
cabeçalho (neste exemplo, linhas = 23 + 1);
2) Excluindo o cabeçalho, divida a primeira 
coluna na metade. Preencha a primeira 
metade com “V” e a segunda com “F”.
3) Divida ao meio cada metade da segunda 
coluna obtendo quatro partes. Iniciando por 
“V”, preencha alternadamente cada partecom “V” e “F”;
21
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
Para garantir que nenhuma seqüência se repita 
vamos analisar um exemplo contendo três 
proposições:
1) Calcule a quantidade de arranjos possíveis. 
A sua tabela deverá, então ter uma linha 
para cada arranjo e mais uma para o 
cabeçalho (neste exemplo, linhas = 23 + 1);
2) Excluindo o cabeçalho, divida a primeira 
coluna na metade. Preencha a primeira 
metade com “V” e a segunda com “F”.
3) Divida ao meio cada metade da segunda 
coluna obtendo quatro partes. Iniciando por 
“V”, preencha alternadamente cada parte 
com “V” e “F”;
4) Proceda analogamente para a terceira 
coluna. Note que agora serão oito partes 
alternando “V” e “F”.
22
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
Para garantir que nenhuma seqüência se repita 
vamos analisar um exemplo contendo três 
proposições:
1) Calcule a quantidade de arranjos possíveis. 
A sua tabela deverá, então ter uma linha 
para cada arranjo e mais uma para o 
cabeçalho (neste exemplo, linhas = 23 + 1);
2) Excluindo o cabeçalho, divida a primeira 
coluna na metade. Preencha a primeira 
metade com “V” e a segunda com “F”.
3) Divida ao meio cada metade da segunda 
coluna obtendo quatro partes. Iniciando por 
“V”, preencha alternadamente cada parte 
com “V” e “F”;
4) Proceda analogamente para a terceira 
coluna. Note que agora serão oito partes 
alternando “V” e “F”.
23
Operações lógicas fundamentais
Quando pensamos, efetuamos muitas vezes 
certas operações sobre proposições que são 
denominadas operações lógicas. As operações 
lógicas fundamentais da lógica proposicional e 
seus respectivos símbolos são:
1. Negação (~)
2. Conjunção (∧)
3. Disjunção inclusiva (∨)
4. Disjunção exclusiva (v)
5. Implicação ou Condicional (→)
6. Dupla implicação ou Bicondicional (↔)
24
Negação
• A negação na lógica proposicional é representada 
pelo til “~” ou pelo símbolo gráfico “¬”;
• No ensino da Álgebra de Boole a negação é
representada por um apóstrofo após a proposição 
(ex.: negação de P: P’);
• Em algumas linguagens de programação é
representada pela exclamação “!” (ex.: negação 
de P: !P);
• No nosso curso utilizaremos o “~” antecedendo a 
proposição (ex.: negação de P: ~P);
• O conectivo “~” é um conectivo unário pois atua 
sobre uma única proposição. Note que é inválida a 
sentença (p ~ q). 25
Negação
• A sentença ~(p ∧ q) é válida pois a expressão (p ∧
q) representa uma proposição. A expressão dentro 
dos parênteses será resolvida primeiro e só então se 
dará a negação sobre o seu resultado.
• Note que a sentença (~p ∧ q) é válida e que a 
negação atuará apenas sobre p.
• Analogamente ao item anterior, (p ∧ ~q) é válida e a 
negação atuará apenas sobre q.
Exemplos:
p: Terminei o trabalho;
Q = ~p;
Q: Não Terminei o trabalho.
Q: Não terminei o trabalho;
R = ~Q;
R: Terminei o trabalho.
26
Tabela Verdade da Negação
P ~P
V F
F V
27
Conjunção
• A conjunção na lógica proposicional é representada pelo 
símbolo “∧” (ex.: conjunção de P e Q: P ∧ Q (lê-se P e Q);
• No ensino da Álgebra de Boole a conjunção é representada 
pelo símbolo “•” (ex.: conjunção de P e Q: P • Q);
• Em algumas linguagens de programação é representada 
por “&&” (ex.: conjunção de P e Q: P && Q);
• O conectivo “∧” é um conectivo binário pois é sempre 
aplicado sobre duas proposições (ex.: (p ∧ q) ∧ r). Note, 
portanto, que (∧ p) ou (p ∧), não são sentenças válidas na 
lógica proposicional. 
Exemplo:
p: Pedro trabalha;
q: Maria estuda;
R = p ∧
∧∧
∧ q;
R: Pedro trabalha e Maria estuda;
28
Tabela Verdade da Conjunção
P Q P ∧
∧∧
∧ Q
V V V
V F F
F V F
F F F
29
Conjunção
No ensino da Álgebra de Boole a conjunção 
é representada pelo ponto “•”, a verdade 
pelo algarismo “1” e a falsidade pelo “0”. Na 
Álgebra de Boole a conjunção é conhecida, 
também, como produto lógico pois se 
comporta como a multiplicação. Veja, no 
slide seguinte, a tabela verdade da 
conjunção utilizando a sintaxe alternativa e 
note que o resultado corresponde ao 
produto dos dois algarismos.
30
Tabela Verdade da Conjunção 
utilizando uma sintaxe alternativa
P Q P • Q
1 1 1
1 0 0
0 1 0
0 0 0
31
Disjunção Inclusiva
• Quando usamos o “ou” na língua portuguesa queremos 
representar uma alternativa única, uma coisa ou outra 
mas não ambas. É o equivalente na lógica 
proposicional a disjunção exclusiva.
• Quando utilizamos o termo disjunção isoladamente 
estamos nos referindo a disjunção inclusiva que 
significa uma coisa ou outra ou ambas que na língua 
portuguesa é, algumas vezes, representada por “e/ou”.
• O conectivo “∨” representa o ou inclusivo. Desta forma 
(p ∨ q) representa: p ou q ou ambas (normalmente 
diz-se apenas p ou q para o ou inclusivo).
• A disjunção (inclusiva) na lógica proposicional é
representada pelo símbolo “∨” (ex.: disjunção de P e 
Q: P ∨ Q, lê-se P ou Q); 32
Disjunção Inclusiva
• Na Álgebra de Boole a disjunção é representada pelo 
símbolo “+” (ex.: disjunção de P e Q: P + Q);
• Em algumas linguagens de programação é
representada por “||” (ex.: disjunção de P e Q: P || Q);
• O conectivo “∨” é um conectivo binário pois é sempre 
aplicado sobre duas proposições (ex.: (p ∨ q) ∨ r). 
Note, portanto, que (∨ p) ou (p ∨), não são 
sentenças válidas na lógica proposicional. 
Exemplo:
p: José estuda;
q: José trabalha;
R = p ∨ q;
R: José estuda e/ou José trabalha;
33
Tabela Verdade da Disjunção Inclusiva
P Q P ∨
∨∨
∨ Q
V V V
V F V
F V V
F F F
34
Disjunção Exclusiva
• A disjunção exclusiva na lógica proposicional é
representada pelo símbolo “∨” (ex.: disjunção exclusiva 
de P e Q: P ∨ Q);
• Na Álgebra de Boole a disjunção exclusiva é
representada pelo símbolo “⊕” (ex.: disjunção exclusiva 
de P e Q: P ⊕ Q);
• O conectivo “∨” é um conectivo binário pois é sempre 
aplicado sobre duas proposições (ex.: (p ∨ q) ∨ r). 
Note, portanto, que (∨ p) ou (p ∨), não são sentenças 
válidas na lógica proposicional. 
Exemplo:
p: José fala;
q: José assobia;
R = p ∨ q;
R: José fala ou José assobia;
35
Tabela Verdade da Disjunção 
Exclusiva
P Q P ∨
∨∨
∨ Q
V V F
V F V
F V V
F F F
36
Implicação ou Condicional
• A implicação também pode ser chamado de condicional, 
ou de “se então” (p implica q, ou se p então q);
• Tanto na Lógica Proposicional como na Álgebra de 
Boole a implicação, ou condicional, é representada pelo 
símbolo “→” (ex.: p implica q: p → q);
• O conectivo “→” é um conectivo binário pois é sempre 
aplicado sobre duas proposições (ex.: (p → q) → r). 
Note, portanto, que (→ p) ou (p → ), não são sentenças 
válidas na lógica proposicional. 
• A proposição que vem antes do conectivo “→” é
chamada de antecedente.
• A proposição que vem depois do conectivo “→” é
chamada de conseqüente.
37
Implicação ou Condicional
• Em uma proposição condicional do tipo (p → q), o 
antecedente p é uma condição suficiente para o 
conseqüente q, e o conseqüente q é uma condição 
necessária para o antecedente p;
Exemplo:
p: Nicolau é juiz de direito; q: Nicolau é advogado;
S: (p → q)
S: Nicolau é juiz de direito → Nicolau é advogado
Ser advogado é uma condição necessária para ser 
juiz de direito mas não é suficiente pois há outras 
condições necessárias (ex.: aprovação em exame da 
ordem, três anos de experiência profissional, 
aprovação em concurso, posse, etc.). Nicolau ser juiz 
de direito é uma condição suficiente para concluir que 
ele é advogado.
38
Implicação ou Condicional
• Quando dito que p implica q está dito que sempre que p 
for verdade, q também deve ser para que a proposição 
toda também resulte verdadeira.
Exemplo:
Se está chovendoforte então a rua está molhada.
Note que esta proposição só será falsa se estiver 
chovendo forte e a rua estiver seca. O fato de não estar 
chovendo forte e a rua estar molhada, por outro motivo, 
não falseia o que foi dito.
39
Tabela Verdade da Condicional
P Q P → Q
V V V
V F F
F V V
F F V
40
Dupla Implicação ou Bicondicional
• A dupla implicação também pode ser chamada de 
bicondicional e pode ser lida como “se e somente se” (p se 
e somente se q);
• Tanto na Lógica Proposicional como na Álgebra de Boole a 
dupla implicação, é representada pelo símbolo “↔” (ex.: p 
se e somente se q: p ↔ q);
• O conectivo “↔” é um conectivo binário pois é sempre 
aplicado sobre duas proposições (ex.: (p ↔ q) ↔ r). Note, 
portanto, que (↔ p) ou (p ↔ ), não são sentenças válidas na 
lógica proposicional. 
• Em uma bicondicional de duas proposições p e q, 
representada por p ↔ q, temos que:
a) p é condição necessária e suficiente para q;
b) q é condição necessária e suficiente para p.
41
Dupla Implicação ou Bicondicional
• Em uma dupla implicação de duas proposições p e q, 
representada por p ↔ q, temos que:
a) p é condição necessária e suficiente para q;
b) q é condição necessária e suficiente para p.
• O operador bicondicional reflete a noção de condição nos 
dois sentidos, ou seja, p ↔ q, equivale a (p → q) ∧ (q → p). 
– Assim, a proposição p ↔ q (p se e somente se q), é
interpretada da seguinte maneira:
� É verdadeira, quando p e q possuem o mesmo valor 
lógico (p=V e q=V, ou, p=F e q=F);
� É falsa, quando p e q possuem valores lógicos 
diferentes (p=V e q=F, ou, p=F e q=V).
42
Exemplos de bicondicionais:
1.É um quadrado se e somente se é um 
retângulo com os quatro lados iguais.
2.João é brasileiro nato se e somente se João 
nasceu no Brasil.
3.Será uma borboleta se e somente se é uma 
lagarta.
4.Será campeão se e somente se vencer esta 
partida.
5.Pode ser eleitor se e somente se tiver 
dezesseis anos ou mais.
43
Tabela Verdade da Bicondicional
P Q P ↔ Q
V V V
V F F
F V F
F F V
44
Tabela Verdade dos Conectivos
P Q ~P P ∧
∧∧
∧ Q P ∨
∨∨
∨ Q P ∨
∨∨
∨ Q P → Q P ↔ Q
V V F V V F V V
V F F F V V F F
F V V F V V V F
F F V F F F V V
45
Conectivos e alguns
significados na linguagem natural
~P Não P; Não é verdade que P; Não é fato 
que P; Não se tem P; etc.
(P ∧ Q) P e Q; P, mas Q; P, embora Q; P, assim 
como Q; P e, além disso, Q; Tanto P 
quanto Q; P e também Q; não só P, mas 
também Q; 
P, apesar de Q.
(P ∨ Q) P ou Q ou ambos; P e/ou Q.
(P v Q) P ou Q mas não ambos.
46
Conectivos e alguns
significados na linguagem natural
(P → Q) Se P, então Q; Se P, isto significa que Q;
Tendo-se P, então Q; Quando P, então Q;
Sempre que P, Q; Q, sempre que se tenha P;
Q, contanto que P; 
P é condição suficiente para Q;
Q é condição necessária par P;
Uma condição suficiente para Q é P;
Uma condição necessária para P é Q;
Q, se P; Q quando P; Q, no caso de P;
P, só se Q, P, somente quando Q,
P só no caso de Q; P implica Q;
P acarreta Q; Q é implicada por P.
47
Conectivos e alguns
significados na linguagem natural
(P ↔ Q) P se e só se Q;
P se e somente se Q;
P quando e somente quando Q;
P equivale a Q;
Uma condição necessária e suficiente 
para P é Q;
P é condição necessária e suficiente 
para Q.
Q é condição necessária e suficiente 
para P.
48
Bibliografia
• ABE, Jair Minoro; SCALZITTI, Alexandre; FILHO, João I. da Silva.
Introdução à lógica para a ciência da computação. São Paulo: Arte & 
Ciência, 2002.
• ALENCAR FILHO, Edgard de. Iniciação à lógica matemática. São Paulo: 
Nobel, 2002.
• AZEREDO, Vânia Dutra de. Introdução à Lógica. 3. ed. Ijuí: Unijuí, 2004.
• DAGHLIAN, Jacob. Lógica e álgebra de Boole. 4. ed. São Paulo: Atlas, 
2006.
• ROCHA, Enrique. Raciocínio lógico. Rio de Janeiro: Elsevier, 2006.
• SILVA, Flávio S. Corrêa da; FINGER, Marcelo; MELO, Ana C. Vieira de. 
Lógica para computação. São Paulo: Thompson Learning, 2006.
• SOUZA, João Nunes de. Lógica para ciência da computação.
Rio de Janeiro: Elsevier, 2002.
• Notas de Aulas do Professor Edson Holanda.
• Novo Dicionário Eletrônico Aurélio versão 5.11a.
• Pesquisas em sites voltados para o estudo da Filosofia, Lógica, Matemática 
e Computação.
49