P PCS2214 — Fundamentos de Engenharia de Computação I

Lógica

Professores:

Anarosa Alves Franco Brandão,

Anna Helena Reali Costa,

Ricardo Luís de Azevedo da Rocha, Ricardo Nakamura

Sumário

1 Introdução

2 Lógica proposicional

Proposições Operadores ¬, ∧, ∨ e Tabela Verdade Operadores →, ↔ e Equivalência Propriedades dos operadores

3 Lógica de predicados

Predicados e relações Quantificadores

4 Provas e Inferência

Prova de teoremas Regras de inferência Indução matemática

Introdução O que é lógica

Derivada do estudo dos processos fundamentais de raciocínio e argumentação. (dialética e retórica)

Do grego lógos: palavra, argumento, discurso, pensamento, idéia, razão, raciocínio.

Estudada desde a era clássica ( Aristóteles), continua em evolução.

Muito útil em matemática, computação, direito, mas tem aplicação em muitas outras áreas.

Introdução Aplicações e limitações

A lógica se foca na relação entre declarações, ao invés do conteúdo de declarações particulares.

Ela permite compor provas de argumentos.

No século XVII Leibniz começou a transformar a lógica em uma forma de cálculo, algo puramente sintático, ou “mecânico”. Daí o nome cálculo proposicional.

Seguiram Boole, De Morgan, Frege, Russel e Wittgenstein nos séculos XIX e X.

Introdução Aplicações e limitações

Exemplo:

p : Todos engenheiros usam óculos. q : Pessoas de óculos gostam de computadores. ∴ Todos engenheiros gostam de computadores.

A lógica nos garante que se p e q forem verdadeiras, a última declaração também o será.

Observe que a conclusão é correta, mas as premissas não são verdadeiras, e nem dizem tudo:

Nem todos engenheiros usam óculos. Há pessoas que usam óculos e que não gostam de computadores.

Lógica Proposicional Proposições

Uma das lógicas formais mais simples é a lógica proposicional, ou cálculo proposicional.

Ela lida com declarações, que são sentenças com valor verdadeiro ou falso, nomeadas por variáveis representadas com letras minúsculas, como:

s : Sócrates era mortal. p : Leila matou Odete Roitman. q : 2 + 2 = 5 r : 2 é um número par e primo.

Lógica Proposicional Proposições

Na lógica proposicional, apenas o valor verdade das proposições importa, e não o significado.

s, p, q e r são chamados símbolos de proposição, variáveis proposicionais, ou simplesmente átomos, e podem assumir os valores verdade V (verdadeiro) ou F (falso).

Lógica Proposicional Linguagem de L

A linguagem de L, também chamada de conjunto de fórmulas bem-formadas, (fbf ou wff), é definida recursivamente:

(1) Qualquer elemento de um conjunto finito de átomos (ou símbolos) é uma fbf de L.

(2) Se p é uma fbf, então ¬p é uma fbf.

Lógica Proposicional Sintaxe em BNF: Backus normal form ou Backus-Naur form

Símbolo inicial: <sentença>

<sentença>::= <sentença atômica> | <sentença complexa>

<sentença atômica>::= V | F | <símbolo>

<símbolo>::= p | q | r | s |

<sentença complexa>::= (<sentença>) | ¬ <sentença> | <sentença> ∧ <sentença> |

<sentença> ∨ <sentença> |

<sentença> → <sentença> |

<sentença> ↔ <sentença>

Lógica Proposicional Operadores ∧ e ∨

Sejam p e q proposições.

A conjunção de p e q, denotada por p ∧ q, é a proposição p e q (“and”). A disjunção de p e q, denotada por p ∨ q, é a proposição p ou q (“or”).

Um operador binário sobre um conjunto X associa cada par de elementos em X a um elemento de X. O operador ∧ associa o par de proposições p e q à proposição p ∧ q. Então, ∧ é um operador binário sobre proposições. O operador ∨ também é um operador binário sobre proposições.

Lógica Proposicional Tabela verdade

Os valores verdade possíveis de uma proposição podem ser listados exaustivamente em uma tabela verdade.

Cada linha é uma combinação de valores verdade dos átomos que compõem cada proposição. As colunas correspondem às proposições e seus valores verdade resultantes. (V é verdadeiro, F é falso.)

A tabela verdade define formalmente as proposições p ∧q e p ∨q:

p q p ∧q p ∨q

Lógica Proposicional Operador de Negação

A negação de p, denotada por ¬p, é a proposição não p.

Um operador unário sobre um conjunto X associa cada elemento em X a um elemento de X. O operador ¬ associa a proposição p à proposição ¬p. Então, ¬ é um operador unário sobre proposições.

A tabela verdade define formalmente as proposições ¬p:

Lógica Proposicional Exercícios

Sejam as proposições: p: João le Veja. q: João le IstoÉ. r: João le Época. Escreva em lógica proposicional:

João le Veja ou IstoÉ, mas não a Época. João le Veja e IstoÉ, ou ele não le nem Veja nem Época. Não é verdade que João le Veja mas não a Época. Não é verdade que João le ou IstoÉ ou Época, mas não a Veja.

Escreva a tabela verdade para as seguintes fbfs:

Considere que p é V e q é F. Escreva os valores verdade das sentenças do item anterior.

Lógica Proposicional Proposição condicional

O operador de implicação indica condição, consequência ou causação. Exemplo:

r : Se a porta estiver aberta, o cachorro entra.

É representado por p → q, e significa “se p, então q”.

p é a hipótese, premissa, condição ou antecedente. q é chamada de conclusão ou consequente.

Uma implicação q → r pode ser verdadeira (ou falsa) sem que sua recíproca r → q o seja.

Lógica Proposicional Operador de Implicação

A tabela verdade define o valor verdade da proposição condicional:

p q p → q

O operador de implicação → é um operador binário.

Lógica Proposicional Operador de Implicação

Justificativa para p → q ser V quando p é F:

Todos concordam que ela é verdadeira, certo? Isto é, para qualquer número real que se atribua a x, p → q é V, com p denotando x > 0 e q denotando x2 > 0.

Verifique: a proposição é verdadeira para quando, por ex., (i) x = 3, quando então p é V e q também é V; ou quando (i) x = −2, quando então p é F (pois −2 > 0 é falso) e q é V (pois (−2)2 > 0 é verdade), ou ainda quando (i) x = 0, quando então p é F (pois 0 > 0 é falso) e q é F (pois (0)2 > 0 é falso).

Lógica Proposicional Condição Necessária e Condição Suficiente

Uma condição necessária precisa ser verdadeira para que a condicionada também o seja. Ela não garante o outro termo, mas se não for verdadeira, este outro termo também não poderá ser verdadeiro.

u : Maria necessita ir à Itália para visitar a Torre de Pisa.

Uma condição suficiente basta para garantir uma consequência. Se a condição não for verdadeira, a proposição consequente pode não vir a sê-lo, ou ainda pode se tornar verdadeira por outros meios.

v : Se Maria está na Torre Eiffel, então ela está em Paris. (Isto não equivale a “Se Maria está em Paris, então ela está na Torre Eiffel.”) p︸︷︷︸ suficiente para q → q︸︷︷︸ necessária para p

Lógica Proposicional Proposição bicondicional

Se uma condição for simultaneamente necessária e suficiente, temos uma proposição bicondicional.

Neste caso, a relação entre as variáveis p e q pode ser lida como “se e somente se” (sse, iff)

Exemplo:

Lógica Proposicional Proposição bicondicional

A tabela verdade define o valor verdade da proposição bicondicional:

p q p ↔ q

O operador ↔ é um operador binário.

Lógica Proposicional Ordem dos Operadores

É necessário ainda definir a ordem de aplicação, ou precedência dos operadores. A ordem de aplicação dos operadores é (da maior para a menor precedência):

Parênteses: “(” e “)”, são utilizados para determinar uma ordem específica de aplicação das operações em uma expressão (como em aritmética).

Lógica Proposicional Exercícios

Considere a seguinte proposição:

Considere as seguintes frases:

Uma condição suficiente para que João faça o biênio da Poli é que ele tenha passado no vestibular. Um código é legível e corresponde a um algoritmo somente se ele estiver bem estruturado e for finito.

Defina símbolos para proposições e traduza as frases para sentenças proposicionais.

Lógica Proposicional Equivalência

A equivalência, ≡ (ou também ⇔), entre duas proposições significa que elas possuem o mesmo valor verdade para cada possível combinação dos seus átomos constituintes. Exemplos:

Lógica Proposicional Equivalência

Contradição, ou fbf insatisfazível: quando uma proposição for sempre falsa, para todo possível valor verdade de seus átomos.

Tautologia, ou fbf válida: quando uma proposição for sempre verdadeira, para todo possível valor verdade de seus átomos.

Assim, p ≡ q sse p ↔ q for uma tautologia.

Lógica Proposicional Propriedade dos operadores

Propriedades da disjunção:

Idempotência a ∨ a ≡ a

Identidade a ∨ F ≡ a

Propriedades da conjunção:

Idempotência a ∧ a ≡ a

Identidade a ∧ V ≡ a

Lógica Proposicional Propriedade de operadores

Propriedades distributivas:

Propriedades de absorção:

Propriedade de negação:

Lógica Proposicional Propriedade de operadores

Propriedades de De Morgan:

Propriedade da implicação:

Lógica Proposicional Exercícios

Prove, usando tabela verdade, a equivalência de:

(3) Usando as propriedades dos operadores, prove a equivalência lógica para a ⊕ b:

Lógica Proposicional Resposta dos exercícios

Lógica Proposicional Resposta dos exercícios

Prove, usando tabela verdade, a equivalência de: (2) a → b ≡ ¬a ∨ b (IMPLICAÇÃO) Para isso, temos que mostrar que a → b ↔ ¬a ∨ b é uma tautologia:

Lógica Proposicional Resposta dos exercícios

P Referência Bibliográfica

Referência Bibliográfica da Aula:

Johnsonbaugh, Richard. Discrete mathematics. 6th. ed., Pearson Prentice Hall. Chapter 1: p.1 – 75.

Comentários