03 Lógica Proposicional

Prévia do material em texto

Lógica Proposicional:
Sistema Formais
 
Sentenças ou 
Proposições Simples
● São frases declarativas afirmativas que devem exprimir 
um pensamento de sentido completo.
● Podem ser verdadeiras (1) ou falsas (0), nunca ambas.
● Exemplos:
3 < 7 5 > 9
 
Sentenças ou 
Proposições Compostas
● São formadas por duas ou mais proposições 
simples, relacionadas por conectivos, tais como 
“e”, “ou”, “se...então”.
● Exemplo:
● A: 3 < 7 ou 5 > 9
 
Princípios Fundamentais da 
Lógica Matemática
● Princípio da não contradição:
Uma proposição não pode ser simultaneamente 
verdadeira e falsa.
● Princípio do terceiro excluído:
Toda proposição ou é só verdadeira ou só falsa, 
nunca ocorrendo um terceiro caso.
 
Tabela Verdade
O número de linhas da tabela verdade é dado por 2n, 
sendo n o número de proposições componentes.
 
Negação
● Inverte o valor de uma proposição;
● Operação unária: envolve uma só proposição;
● A negação de uma proposição (simples ou 
composta), pode ser indicada por: 
A’ A A.
 
Negação: Porta Lógica 
“NOT”
 
Conjunção
● O conectivo “e” faz a conjunção de duas proposições: A, 
B. Elas são fatores.
● Uma proposição composta A e B, pode ser indicada por: 
A.B A^B
● O valor de A.B é verdade apenas se A e B são 
verdadeiras. 
 
Conjunção: Porta Lógica
“AND”
X Y Z
0 0 0
0 1 0
1 0 0
1 1 1
 
Disjunção Inclusiva ou
Soma Lógica
● O conceito “ou” faz a disjunção de duas proposições: 
A, B. Elas são parcelas.
● Uma proposição composta A ou B, pode ser indicada 
por: A+B AvB
● O valor de A+B é falso apenas se ambas as 
proposições são falsas. 
 
Disjunção inclusiva:Porta Lógica 
“OR”
X Y Z
0 0 0
0 1 1
1 0 1
1 1 1
 
Disjunção Exclusiva
● O conceito “ou exclusivo” faz a disjunção exclusiva de 
duas proposições: A, B.
● Uma proposição composta A ou exclusivo B, pode ser 
indicada por: A + B
● O valor de A + B é falso se as proposições são iguais. 
 
Disjunção Exclusiva: Porta Lógica 
“XOR”
X Y Z
0 0 0
0 1 1
1 0 1
1 1 0
X
 
Circuito Digital
Circuito Digital
Circuito Digital
Circuito Digital (em VHDL)
entity sum is
port( Cin : in bit;
ain0 : in bit;
bin0 : in bit;
ain1 : in bit;
bin1 : in bit;
out_0 : out bit;
out_1 : out bit;
Cout : out bit
);
end sum;
architecture sumBehave of sum is
begin
out_0 <= (ain0 xor bin0) xor Cin;
out_1 <= (ain1 xor bin1) xor ((ain0 and bin0) or ((ain0 or bin0) and Cin));
Cout<=(ain1 and bin1) or ((ain1 or bin1) and ((ain0 and bin0) or ((ain0 or bin0) and Cin)));
end sumBehave;
 
Algoritmo (já convertido em código 
fonte)#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{
int x, y;
printf("\nDigite o numero 0 ou 1, sendo '0' para indicar a ausência de enxofre e '1' para indicar a presença: ");
scanf("%d", &enxofre);
printf("\nDigite outro numero 0 ou 1, sendo '0' para indicar a ausência de metano e '1' para indicar a presença: ");
scanf("%d", &metano);
//Ressaltar o uso dos operadores lógicos.
printf("\n%d AND %d => %d", enxofre, metano, enxofre&&metano);
printf("\n%d OR %d => %d", enxofre, metano, enxofre||metano);
printf("\nNOT %d => %d", enxofre, !enxofre);
printf("\nNOT %d => %d", metano, !metano);
_getche();
}
 
Proposições Combinadas:
Condicional ou Implicação
● As proposições podem ser combinadas na forma:
 se proposição 1 então proposição 2,
indicando que a verdade da proposição 1 implica ou leva à proposição 
2.
● Indicada por: A → B, para a qual A é o antecedente e B consequente
● “A é condição suficiente para B”
● “B é consequência de A”
 
Proposições Combinadas:
Condicional ou Implicação
void main()
{
 int temperatura;
 printf("Informe a temperatura da agua: \t");
 scanf("%i", &temperatura);
 if(temperatura<20)
 {
 printf("\n\nAgua fria");
 }
 else
 {
 printf("\n\nAgua quente");
 }
 _getche();
}
Circuito Digital
Circuito Digital (em VHDL)
LIBRARY ieee;
USE ieee.std_logic_1164.all;
ENTITY dec2b IS
PORT( in_dec : IN std_logic_vector(1 downto 0);
 out_dec : OUT std_logic_vector(0 to 3)
);
end dec2b;
ARCHITECTURE dec2bBehave OF dec2b IS
BEGIN
out_dec <=
"1000" WHEN (in_dec = "00") ELSE
"0100" WHEN (in_dec = "01") ELSE
"0010" WHEN (in_dec = "10") ELSE
"0001" WHEN (in_dec = "11");
END dec2bBehave;
 
Proposições Combinadas:
Bicondicional ou Equivalência
● O bicondicional é obtido com a conjunção de 
dois condicionais.
● Indicado por: A ↔ B
● “A se, e somente se B”
 
Precedência das
Operações Lógicas
● É possível encadear sentenças usando operadores e 
parênteses;
● Expressões que formam sentenças válidas são 
consideradas: well-formed formulas (wff);
● Ordem de Precedência:
● ( )
● ‘ 
● . , +, 
● → 
● ↔ 
Exemplo: C + A . B . (A’ + B . C’ + B’)
 
Well-Formed Formulas (wff’s)
● Expressões que formam sentenças válidas são 
consideradas: well-formed formulas (wff);
● Exemplos de well-formed formulas (wff’s):
X = A’.B.C + A.B’.C + A.B.C’ + A.B.C
Y = AB + AC + BC
 
Tabela Verdade e
Mapa de Karnaugh
 
Lógica Proposicional:
Teorema
● É aquilo que se objetiva verificar;
● Exemplo:
Seja:
 X = A’.B.C + A.B’.C + A.B.C’ + A.B.C
 Y = AB + AC + BC
 Z = X  Y
 W = (X  Y)’
Então: X  Y? (X é equivalente a Y?)
 
Lógica Proposicional:
Deduções
● Para provar teoremas, devem ser usadas wff’s 
conhecidas (premissas) e argumentos válidos;
● Estas são usadas para obter outras wff’s 
válidas até que se obtenha a wff final;
● Esta estratégia é chamada “Prova Direta”.
 
Lógica Proposicional:
Axiomas
● Um axioma é uma wff cuja verdade é evidente;
● Exemplo: a disjunção exclusiva (ou exclusivo) 
entre duas proposições (wff’s) resulta em falso, 
se ambas são iguais, ou verdadeira, se elas 
são diferentes
 
Disjunção Exclusiva: Porta Lógica 
“XOR”
X Y Z
0 0 0
0 1 1
1 0 1
1 1 0
X
 
Tautologia
● Quando todos os valores de uma proposição 
composta resultam em verdade.
A B P
0 0 1
0 1 1
1 0 1
1 1 1
 
Contradição
● Quando todos os valores de uma proposição 
composta resultam em falsos.
A B P
0 0 0
0 1 0
1 0 0
1 1 0
 
Lógica Proposicional:
Regra de Inferência
● É uma convenção que permite a uma nova wff ser inferida de 
outras wff’s;
● Inferir: fazer inferência sobre; concluir, deduzir;
● Exemplo:
Seja,
 X = A’.B.C + A.B’.C + A.B.C’ + A.B.C
 Y = AB + AC + BC
 Z = X  Y
Então,
Z é uma contradição.
 
Contradição e Tautologia
Seja:
 X = A’.B.C + A.B’.C + A.B.C’ + A.B.C
 Y = AB + AC + BC
 Z = X  Y
 W = (X  Y)’
Então:
– A afirmação “X não equivale a Y” pode ser refutada 
por Contradição;
– A afirmação “X equivale a Y” pode ser demonstrada 
por Tautologia.
 
Contradição e Tautologia
Seja:
 X = A’.B.C + A.B’.C + A.B.C’ + A.B.C
 Y = AB + AC + BC
 Z = X  Y
 W = (X  Y)’
Então:
X  Y
A B C X Y Z W
0 0 0 0 0 0 1
0 0 1 0 0 0 1
0 1 0 0 0 0 1
0 1 1 1 1 0 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 1 0 1 1 0 1
1 1 1 1 1 0 1
 
Equivalências Tautológicas
● Leis de De Morgan;
● Idempotência;
● Contrapositivo;
● Dupla Negação;
● Etc.
 
Lógica Proposicional:
Argumentos Válidos
● Um argumento é uma sequência de sentenças 
que pode ser representada por P1, P2, …, Pn, 
seguida de uma conclusão Q.
P1, P2, …, Pn → Q
 
Lógica Proposicional:
Argumentos Válidos
● Exemplo:
Seja:
 X = A’.B.C + A.B’.C + A.B.C’ + A.B.C,
 Y = AB + AC + BC,
 Z = X Y, uma contradição e
 W = (X  Y)’, uma tautologia,
Então:
X  Y
 
Lógica Proposicional:
Deduções
● Para provar teoremas da forma P → Q, (para 
os quais P é chamado “Hipótese” e Q é a 
“Tese”), supõem-se a hipótese como sendo 
verdadeira e tenta-se concluir que a tese é 
verdadeira;
Esta estratégia é chamada “Prova 
Condicional”.
 
Tabela Verdade e
Mapa de Karnaugh
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37