Curso Superior em Tecnologia: Banco de dados e Sistemas para Internet
Matemática Computacional
Prof. Ulisses Cotta Cavalca
LÓGICA PROPOSICIONAL
Belo Horizonte/MG 2012
1. ELEMENTO DA LINGUAGEM INFORMAL E OUTROS TÓPICOS
FRASE é o elemento de comunicação que relaciona palavras entre si de modo a estabelecer uma mensagem com sentido completo: • • • •Declarativa: “O sol é uma estrela” Imperativa: “Não faça isto!” Interrogativa: “Onde você mora?” Exclamativa: “Parabéns!!!”
PROPOSIÇÃO é uma frase declarativa a qual pode ser atribuído, sem ambiguidade, um dos valores lógicos: Verdadeiro (V) ou Falso (F). Exemplos:
• • • • • O Japão fica na África O Brasil não é uma ilha 3+4=7 3+4 (não tem predicado) onde você vai? (interrogativa)
Não são preposições:Proposições serão representadas por letras minúsculas do nosso alfabeto:
p: O México fica na América do Norte q: O número 16 é primo.
CONECTIVOS LÓGICOS, ou operadores lógicos, são palavras ou expressões que se usam para formar novas proposições a partir de outras preposições: • • • • • não (negação) e (conjunção) ou (disjunção) se … então … (condicional) … se, e somente se …(bicondicional)
VALOR LÓGICO de uma preposição é a verdade (V) se a preposição for verdadeira e é a falsidade (F) se a proposição for falsa:
p: O sol é verde → V(p)=F q: Um hexágono tem seis lados → V(q)=V r: 2 é raiz da equação x² + 3x – 4 = 0 → V(p)=F
PRINCÍPIOS FUNDAMENTAIS DA LÓGICA Princípio da não contradição: Uma proposição não pode ser simultaneamente verdadeira (V) e falsa(F). Princípio do terceiro excluído: Toda preposição ou só é verdadeira (V) ou só é falsa (F). Logo, toda preposição admite um e um só dos valores V e F. REPRESENTAÇÃO DE PROPOSIÇÕES LÓGICAS Proposições lógicas podem ser representadas através de diagramas de árvores ou de tabelas verdade.
Seja a proposição P composta por p: P(p) Diagrama em árvore Tabela verdade
p V F · · ·
V p FSeja a proposição P composta por p e q: P(p,q) Diagrama em árvore
V F
Tabela verdade
p q V F · · · V V · F V · F F
V p F
q
V q F
2. OPERAÇÕES LÓGICAS SOBRE PROPOSIÇÕES
2.1 NEGAÇÃO Apresenta valor lógico oposto ao da proposição dada. Seja a proposição p, a negação da proposição dada será ~p, as vezes também denotada por ¬p (lê-se não p).
Tabela verdade p ~p V F F Vp: O sol é uma planeta ~p: O sol não é um planeta q: 2+3 = 5 ~q: 2+3 ≠ 5
Negar uma preposição p não é apenas afirmar algo diferente do que p afirma, ou algo com o valor lógico diferente:
A proposição “O sol é uma estrela” (que é verdadeira) não é negação da “O sol é um planeta” (que é falsa).
2.2 CONJUNÇÃO Apresenta valor lógico se, e somente se, cada componente for verdadeira. Duasproposições p e q podem ser combinadas pelo conectivo “e” para firmas uma proposição composta denominada conjunção das proposições originais. Denota-se p^q (lê-se p e q).
Tabela verdade p q p^q V V F F V F V F V F F F
p: Carlos estuda matemática; q: Calor joga xadrez p^q: Carlos estuda matemática e joga xadrez p: 2>0; q: 2 ≠ 5 p^q: 2>0 e 2 ≠ 5
2.3 DISJUNÇÃO Pode traduzir tanto a ideia de hipótesemutuamente exclusiva (ou ocorre isto ou aquilo) quanto a de que pelo menos uma das hipóteses ocorre: Sejam p e q duas proposições combinadas pelo conectivo ou, para formar uma proposição composta denominada disjunção. Denota-se p V q (lê-se p ou q). A disjunção inclusa de duas proposições (p V q) é false se, e somente se, todas as componentes forem falsas.
Tabela verdade p q pvq V V F F V F V F VV V F
Determinar o valor lógico da proposição composta P dada a seguir:
p: 3 Q (Lê-se P implica Q) Exemplo: Mostrar que (p^q) ==> p p V V F F q V F V F p ^ q V F F F (p ^ q) → p V V V V
Dadas as proposições compostas P e Q, diz-se que ocorre uma equivalência lógica entre P e Q quando suas tabelas verdade forem idênticas. Notação: P ≡ Q ou P Q (Lê-se P é equivalente a Q)....