Slide 3 do Renato

Prévia do material em texto

Álgebra de Boole
Eric Araújo
7 de Abril de 2014
Conteúdo
Argumentos: Regras de Inferência
Validade de Argumento
Regras de Inferência
Validade Mediante Regras de Inferência
Validade Mediante Regras de Inferência e Equivalências
Quantificadores
Predicados e proposições quantificadas
Quantificador Universal
Quantificador Existencial
Quantificador de Existência e Unicidade
Matemática Discreta
Negação de Proposições com Quantificador
Verdade por “default” de proposições universais
Proposições com múltiplos quantificadores
Displaying Information
Table
Figure
Theorem
Citations
Eric Araújo | UFLA – Departamento de Ciência da Computação 3/72
Matemática Discreta
Argumentos: Regras de Inferência
Sejam P1, P2, . . . , Pn(n ≥ 1) e Q proposições quaisquer, simples ou compostas.
Definição: Chama-se argumento toda a afirmação de que uma dada sequência
finita P1, P2, . . . , Pn(n ≥ 1) de proposições tem como consequência, ou acarreta
uma proposição final Q.
As proposições P1, P2, . . . , Pn dizem-se as premissas do argumento, e a proposi-
ção final Q diz-se a conclusão do argumento.
Indicaremos um argumento da seguinte forma:
P1, P2, . . . , Pn ⇒ Q
Eric Araújo | UFLA – Departamento de Ciência da Computação 4/72
Matemática Discreta
Validade de Argumento
Definição: Um argumento P1, P2, . . . , Pn ⇒ Q diz-se VÁLIDO se e somente se
a conclusão Q é verdadeira todas as vezes que as premissas P1, P2, . . . , Pn são
verdadeiras.
Um argumento não-válido é dito sofisma.
Eric Araújo | UFLA – Departamento de Ciência da Computação 5/72
Matemática Discreta
Critério de Validade de Argumento
Teorema (Validade de Argumento)
Um argumento P1, P2, . . . , Pn ⇒ Q é válido se e somente se a
condicional:
(P1 ∧ P2 ∧ . . . ∧ Pn)→ Q
é tautológica.
Eric Araújo | UFLA – Departamento de Ciência da Computação 6/72
Matemática Discreta
Regras de Inferência
Os argumentos básicos mostrados anteriormente são usados para
fazer inferências, ou seja, executar os passos de uma dedução ou
demonstração. Daí serem chamadas de regras de inferência. Existem
várias formas de notar uma regra de inferência.
(1) Regra da Adição (AD)
(i) p
p ∨ q (ii)
p
q ∨ p
(2) Regra de Simplificação
(SIMP)
(i) p ∧ q
p
(ii) p ∧ q
q
Eric Araújo | UFLA – Departamento de Ciência da Computação 7/72
Matemática Discreta
(3) Regra da Conjunção (CONJ)
(i)
p
q
p ∧ q
(ii)
p
q
q ∧ p
(4) Regra da Absorção (ABS)
p→ q
p→ (p ∧ q)
Eric Araújo | UFLA – Departamento de Ciência da Computação 8/72
Matemática Discreta
(5) Regra Modus Ponens (MP)
p→ q
p
q
(6) Regra Modus Tollens (MT)
p→ q
¬q
¬p
Eric Araújo | UFLA – Departamento de Ciência da Computação 9/72
Matemática Discreta
(7) Regra do Silogismo Disjuntivo
(SD)
(i)
p ∨ q
¬p
q
(ii)
p ∨ q
¬q
p
(8) Regra do Silogismo
Hipotético (SH)
p→ q
q → r
p→ r
Eric Araújo | UFLA – Departamento de Ciência da Computação 10/72
Matemática Discreta
(9) Regra do Dilema Construtivo
(DC)
p→ q
r → s
p ∨ r
q ∨ s
(10) Regra do Dilema Destrutivo
(DD)
p→ q
r → s
¬q ∨ ¬s
¬p ∨ ¬r
Com o auxílio dessas 10 inferências, é possível mostrar a validade de
um grande número de argumentos complexos.
Eric Araújo | UFLA – Departamento de Ciência da Computação 11/72
Matemática Discreta
Uso de Regras de Inferência para Demonstrar Argumentos 1
Regra da Adição Dada uma pro-
posição p, dela pode-se deduzir a
sua disjunção com qualquer outra
proposição, isto é, deduzir p ∨ q
ou p ∨ r ou s ∨ p, etc.
Exemplos
(a)
(1) p
(2) p ∨ ¬q AD(1)
(b)
(1) p ∨ q
(2) (r ∧ s) ∨ (p ∨ q) AD(1)
Eric Araújo | UFLA – Departamento de Ciência da Computação 12/72
Matemática Discreta
Uso de Regras de Inferência para Demonstrar Argumentos 2
Regra da Simplificação Da conjun-
ção p ∧ q de duas proposições se
pode deduzir cada uma das pro-
posições, p ou q.
Exemplos
(a)
(1) (p ∨ q) ∧ r
(2) p ∨ q SIMP (1)
(b)
(1) p ∧ ¬q
(2) ¬q SIMP(1)
Eric Araújo | UFLA – Departamento de Ciência da Computação 13/72
Matemática Discreta
Uso de Regras de Inferência para Demonstrar Argumentos 3
Regra da Conjunção Permite deduzir de duas proposições dadas p e
q (premissas) a sua conjunção p ∧ q ou q ∧ p (conclusão).
Exemplos
(a)
(1) p ∨ q
(2) ¬r
(3) (p ∨ q) ∧ ¬r CONJ (1) e (2)
Eric Araújo | UFLA – Departamento de Ciência da Computação 14/72
Matemática Discreta
(b)
(1) p ∨ q
(2) q ∨ r
(3) (p ∨ q) ∧ (q ∨ r) CONJ (1) e (2)
Eric Araújo | UFLA – Departamento de Ciência da Computação 15/72
Matemática Discreta
Uso de Regras de Inferência para Demonstrar Argumentos –
Mais exemplos
As demais regras podem ser vistas no capítulo 9 do livro de Iniciação
à Lógica Matemática
Eric Araújo | UFLA – Departamento de Ciência da Computação 16/72
Matemática Discreta
Validade Mediante Regras de Inferência
Este método é também conhecido como Método Dedutivo. Veremos
alguns exemplos de uso das regras de inferência para verificar a
validade de alguns argumentos.
Eric Araújo | UFLA – Departamento de Ciência da Computação 17/72
Matemática Discreta
Exemplo 1 Verificar se é válido o argumento:
p→ q, p ∧ r ⇒ q
(1) p→ q P
(2) p ∧ r P
(3) p SIMP (2)
(4) q MP (1) e (3)
Eric Araújo | UFLA – Departamento de Ciência da Computação 18/72
Matemática Discreta
Exemplo 2 Verificar se é válido o argumento:
p ∧ q, p ∨ r → s⇒ p ∧ s
(1) p ∧ q P
(2) p ∨ r → s P
(3) p SIMP (1)
(4) p ∨ r AD (3)
(5) s MP (2) e (4)
(6) p ∧ s CONJ (3) e (5)
Eric Araújo | UFLA – Departamento de Ciência da Computação 19/72
Matemática Discreta
Exemplo 3 Verificar se é válido o argumento:
p→ (q → r), p→ q, p⇒ r
(1) p→ (q → r) P
(2) p→ q P
(3) p P
(4) q → r MP (1) e (3)
(5) q MP (2) e (3)
(6) r MP (4) e (5)
Eric Araújo | UFLA – Departamento de Ciência da Computação 20/72
Matemática Discreta
Exemplo 4 Verificar se é válido o argumento:
p→ q, p ∧ q → r, ¬(p ∧ r)⇒ ¬p
(1) p→ q P
(2) p ∧ q → r P
(3) ¬(p ∧ r) P
(4) p→ p ∧ q ABS (1)
(5) p→ r SH (2) e (4)
(6) p→ p ∧ r ABS (5)
(7) ¬p MT (3) e (6)
Eric Araújo | UFLA – Departamento de Ciência da Computação 21/72
Matemática Discreta
Exemplo 5 Verificar se é válido o argumento:
p→ q, q → r, s→ t, p ∨ s⇒ r ∨ t
Faça.
Eric Araújo | UFLA – Departamento de Ciência da Computação 22/72
Matemática Discreta
Exemplo 5 Verificar se é válido o argumento:
p→ q, q → r, s→ t, p ∨ s⇒ r ∨ t
(1) p→ q P
(2) q → r P
(3) s→ t P
(4) p ∨ s P
(5) p→ r SH (1) e (2)
(6) r ∨ t DC (3), (4) e (5)
Eric Araújo | UFLA – Departamento de Ciência da Computação 23/72
Matemática Discreta
Outros Exemplos
No capítulo 10 do livro de Iniciação à Lógica
Eric Araújo | UFLA – Departamento de Ciência da Computação 24/72
Matemática Discreta
Validade Mediante Regras de Inferência e
Equivalências
Podemos utilizar as regras de Equivalência para demons-
trar, verificar ou testar a validade de argumentos mais
complexos.
Eric Araújo | UFLA – Departamento de Ciência da Computação 25/72
Matemática Discreta
Exemplo 1 Verificar se é válido o argumento:
p→ ¬q, q ⇒ ¬p
(1) p→ ¬q P
(2) q P
(3) ¬¬q → ¬p CP (1)
(4) q → ¬p DN (3)
(5) ¬p MP (2) e (4)
Eric Araújo | UFLA – Departamento de Ciência da Computação 26/72
Matemática Discreta
Exemplo 2 Verificar se é válido o argumento:
p→ q, r → ¬q ⇒ p→ ¬r
(1) p→ q P
(2) r → ¬q P
(3) ¬¬q → ¬r CP (2)
(4) q → ¬r DN (3)
(5) p→ ¬r SH (1) e (4)
Eric Araújo | UFLA – Departamento de Ciência da Computação 27/72
Matemática Discreta
Exemplo 3 Verificar se é válido o argumento:
p ∨ (q ∧ r), p ∨ q → s⇒ p ∨ s
(1) p ∨ (q ∧ r) P
(2) p ∨ q → s P
(3) (p ∨ q) ∧ (p ∨ r) DIST (1)
(4) p ∨ q SIMP (3)
(5) s MP (2) e (4)
(6) p ∨ s AD (5)
Eric Araújo| UFLA – Departamento de Ciência da Computação 28/72
Matemática Discreta
Exemplo 4 Verificar se é válido o argumento:
p ∨ q → r ∧ s, ¬s⇒ ¬q
Faça.
Eric Araújo | UFLA – Departamento de Ciência da Computação 29/72
Matemática Discreta
Exemplo 4 Verificar se é válido o argumento:
p ∨ q → r ∧ s, ¬s⇒ ¬q
(1) p ∨ q → r ∧ s P
(2) ¬s P
(3) ¬r ∨ ¬s AD (2)
(4) ¬(r ∧ s) DM (3)
(5) ¬(p ∨ q) MT (1) e (4)
(6) ¬p ∧ ¬q DM (5)
(7) ¬q SIMP (6)
Eric Araújo | UFLA – Departamento de Ciência da Computação 30/72
Matemática Discreta
Outros Exemplos
No capítulo 11 do livro de Iniciação à Lógica
Eric Araújo | UFLA – Departamento de Ciência da Computação 31/72
Matemática Discreta
Quantificadores
Já estudamos os conectivos ∨, ∧, ¬, →, ↔.
Apesar da grande quantidade de situações que podemos
representar com estes operadores, temos algumas onde
não é possível.
Todos os seres humanos são mortais
Sócrates é um ser humano
∴ Sócrates é mortal
Eric Araújo | UFLA – Departamento de Ciência da Computação 32/72
Matemática Discreta
Todos os seres humanos são mortais
Sócrates é um ser humano
∴ Sócrates é mortal
Argumento intuitivamente correto. Porém,
• Validade não pode ser obtida com os métodos já vistos.
• Validade é determinada separando as proposições em partes.
• Vocábulos que denotam quantidades (TODOS e ALGUNS) têm
função especial na análise.
Eric Araújo | UFLA – Departamento de Ciência da Computação 33/72
Matemática Discreta
Predicados e proposições quantificadas
Cálculo de predicados: área que trata da análise simbólica de predicados
e proposições quantificadas.
Cálculo de proposições ou cálculo proposicional: área que trata da
análise de proposições compostas.
Eric Araújo | UFLA – Departamento de Ciência da Computação 34/72
Matemática Discreta
Definição: Se P (x) é um predicado e x tem domínio D, o conjunto
verdade de P (x) é o conjunto de todos elementos de D que fazem P (x)
verdadeiro quando substituído por x.
O conjunto verdade de P (x) é denotado por
{x ∈ D|P (x)}
Eric Araújo | UFLA – Departamento de Ciência da Computação 35/72
Matemática Discreta
Exemplo 1
P (x): “x é um fator de 8” e o domínio de x é o conjunto de todos os
inteiros positivos.
O conjunto verdade de P (x) é {1, 2, 4, 8}.
Eric Araújo | UFLA – Departamento de Ciência da Computação 36/72
Matemática Discreta
Notação: Sejam P (x) e Q(x) predicados e suponha que o domínio comum
de x é D.
A notação P (x)⇒ Q(x) significa que cada elemento no conjunto verdade
de P (x) está no conjunto verdade de Q(x).
A notação P (x)⇔ Q(x) significa que P (x) e Q(x) têm conjuntos verdade
idênticos.
Eric Araújo | UFLA – Departamento de Ciência da Computação 37/72
Matemática Discreta
Exemplo 2
P (x): x é um fator de 8;
Q(x): x é um fator de 4;
R(x): x < 5 e x = 3, e
o domínio de x é Z+ (inteiros positivos).
Que relações podem ser expressas entre os três predicados?
O conjunto verdade de P (x) é {1, 2, 4, 8};
O conjunto verdade de Q(x) é {1, 2, 4};
O conjunto verdade de R(x) é {1, 2, 4};
∴ Q(x)⇒ P (x);
∴ R(x)⇒ P (x);
∴ Q(x)⇔ R(x);
Eric Araújo | UFLA – Departamento de Ciência da Computação 38/72
Matemática Discreta
Quantificador Universal
Seja p(x) uma sentença aberta em um conjunto não vazio A (A 6= φ) e
seja Vp o seu conjunto verdade:
Vp = {x|x ∈ A ∧ p(x)}
Quando Vp = A, isto é, todos os elementos de A satisfazem a sentença
aberta p(x), dizemos que “para todo elemento x de A, p(x) é verdadeira
(V)”.
∀x ∈ A, p(x)
Eric Araújo | UFLA – Departamento de Ciência da Computação 39/72
Matemática Discreta
∀: denota “para todos” e é chamado de quantificador universal.
Exemplo 3
∀ seres humanos x, x é mortal.
∀x ∈ S, x é mortal
onde S é o conjunto de todos seres humanos.
Eric Araújo | UFLA – Departamento de Ciência da Computação 40/72
Matemática Discreta
Definição: Seja Q(x) um predicado eD o domínio de x. Uma proposição
universal é uma proposição da forma “∀x ∈ D,Q(x).”
• A proposição universal é verdadeira sse Q(x) é verdadeiro para todo
x em D.
• A proposição universal é falsa sse Q(x) é falso para pelo menos um
x em D.
O valor de x para o qual Q(x) é falso é chamado de contra-exemplo
para a proposição universal.
Eric Araújo | UFLA – Departamento de Ciência da Computação 41/72
Matemática Discreta
Exemplo 4
A proposição
∀n ∈ N, n+ 5 > 3
é verdadeira, pois o conjunto verdade da sentença aberta p(n) : n+5 > 3
é:
Vp = {n|n ∈ N ∧ n+ 5 > 3} = {1, 2, 3, . . .} = N
Eric Araújo | UFLA – Departamento de Ciência da Computação 42/72
Matemática Discreta
Exemplo 5
A proposição
∀n ∈ N, n+ 3 > 7
é falsa, pois o conjunto verdade da sentença aberta p(n) : n+ 3 > 7 é:
Vp = {n|n ∈ N ∧ n+ 3 > 7} = {5, 6, 7, . . .} 6= N
Eric Araújo | UFLA – Departamento de Ciência da Computação 43/72
Matemática Discreta
Outros exemplos
Defina o valor das proposições abaixo:
∀x ∈ R, x2 ≥ 0
∀x ∈ R, 3x− 5 = 0
Eric Araújo | UFLA – Departamento de Ciência da Computação 44/72
Matemática Discreta
Outros exemplos
Defina o valor das proposições abaixo:
∀x ∈ R, x2 ≥ 0 Verdadeira
∀x ∈ R, 3x− 5 = 0 Falsa
Eric Araújo | UFLA – Departamento de Ciência da Computação 45/72
Matemática Discreta
Quantificador Existencial
Seja P (x) uma sentença aberta em um conjunto não vazio A (A 6= φ) e
seja Vp o seu conjunto verdade:
Vp = {x | x ∈ A ∧ p(x)}
Quando Vp não é vazio (Vp 6= φ), então, um elemento, pelo menos, do
conjunto A satisfaz a sentença aberta p(x), e podemos afirmar que “existe
pelo menos um x ∈ A tal que p(x) é verdadeira (V)”
∃x ∈ A, p(x)
Eric Araújo | UFLA – Departamento de Ciência da Computação 46/72
Matemática Discreta
∃: denota “existe” e é chamado de quantificador existencial.
Exemplo 6
∃ uma pessoa s | s é um estudante de Matemática Discreta.
∃s ∈ S | s é um estudante de Matemática Discreta.
onde S é o conjunto de todas as pessoas.
Eric Araújo | UFLA – Departamento de Ciência da Computação 47/72
Matemática Discreta
Definição: Seja Q(x) um predicado eD o domínio de x. Uma proposição
existencial é uma proposição da forma “∃x ∈ D | Q(x)”.
• A proposição existencial é verdadeira sse Q(x) é verdadeiro para
pelo menos um x em D.
• A proposição existencial é falsa sse Q(x) é falso para todo x em D.
Eric Araújo | UFLA – Departamento de Ciência da Computação 48/72
Matemática Discreta
Exemplo 7
Verifique se a proposição existencial é verdadeira ou falsa:
∃m ∈ Z | m2 = m.
12 = 1.
∴ m2 = m para pelo menos um inteiro m
Logo, a proposição ∃m ∈ Z | m2 = m é verdadeira.
Eric Araújo | UFLA – Departamento de Ciência da Computação 49/72
Matemática Discreta
Exemplo 8
Verifique se a proposição existencial é verdadeira ou falsa:
Seja E = {5, 6, 7, 8, 9, 10} e a proposição
∃m ∈ E | m2 = m.
52 = 25 6= 5 62 = 36 6= 6 72 = 49 6= 7
82 = 64 6= 8 92 = 81 6= 9 102 = 100 6= 10
∴ a proposição ∃m ∈ E | m2 = m é falsa.
Eric Araújo | UFLA – Departamento de Ciência da Computação 50/72
Matemática Discreta
Quantificador de Existência e Unicidade
Consideremos em R a sentença aberta “x2 = 16”. Por termos
42 = 16 (−4)2 = 16 e 4 6= −4
podemos concluir que
∃x, y ∈ R, x2 = 16 ∧ y2 = 16 ∧ x 6= y
Eric Araújo | UFLA – Departamento de Ciência da Computação 51/72
Matemática Discreta
Já para a sentença aberta “x3 = 27” em R teremos as duas proposições:
(1) ∃x ∈ R, x3 = 27
(2) x3 = 27 ∧ y3 = 27⇒ x = y
A proposição (1) diz que existe pelo menos um x ∈ R tal que x3 = 27 (x = 3):
é uma afirmação de existência.
A proposição (2) diz que não pode existir mais de um x ∈ R tal que x3 = 27:
é uma afirmação de unicidade.
A conjunção das duas proposições diz que existe um x ∈ R e um só tal que
x3 = 27.
Eric Araújo | UFLA – Departamento de Ciênciada Computação 52/72
Matemática Discreta
Para indicar o fato da conjunção, escreve-se:
∃! x ∈ R, x3 = 27
onde o símbolo ∃! é chamado de quantificador existencial de unicidade
e se lê existe um e um só.
Outros Exemplos
∃! x ∈ N, n2 − 9 = 0
∃! x ∈ Z, −1 < x < 1
∃! x ∈ R, |x| = 0
Eric Araújo | UFLA – Departamento de Ciência da Computação 53/72
Matemática Discreta
Negação de Proposições com Quantificador
Um quantificador universal ou existencial pode ser precedido do símbolo
de negação (¬). Alguns exemplos:
(i) ∀x, x fala francês (ii) ¬∀x, x fala francês
(iii) ∃x, x foi à Lua (iv) ¬∃x, x foi à Lua
1. Toda pessoa fala francês
2. Nem toda pessoa fala francês
3. Alguém foi à Lua
4. Ninguém foi à Lua
Eric Araújo | UFLA – Departamento de Ciência da Computação 54/72
Matemática Discreta
A equivalência a seguir é válida:
¬∀x, x fala francês ⇔ ∃x, ¬x fala francês
Assim, a negação da proposição ∀x ∈ A, p(x) é equivalente a afirmação
de que para ao menos um x ∈ A, p(x) é falsa, ou ¬p(x) é verdadeira.
¬[∀x ∈ A, p(x)]⇔ ∃x ∈ A, ¬p(x)
Eric Araújo | UFLA – Departamento de Ciência da Computação 55/72
Matemática Discreta
Outra equivalência válida:
¬∃x, x foi à Lua ⇔ ∀x, ¬x foi à Lua
A negação da proposição ∃x ∈ A, p(x) é equivalente à afirmação de que,
para todo x ∈ A, p(x) é falsa ou ¬p(x) é verdadeira.
¬[∃x ∈ A, p(x)]⇔ ∀x ∈ A, ¬p(x)
Eric Araújo | UFLA – Departamento de Ciência da Computação 56/72
Matemática Discreta
Estas duas equivalências são conhecidas como segundas regras de negação
de DE MORGAN.
Em resumo: A negação transforma o quantificador universal em quantifi-
cador existencial (seguido de negação) e vice-versa.
Eric Araújo | UFLA – Departamento de Ciência da Computação 57/72
Matemática Discreta
Exemplo 9
A negação da proposição: “Todo o aluno da turma A é bem comportado” é a
proposição “Existe pelo menos um aluno da turma A que não é bem comportado”.
Exemplo 10
A negação da proposição: “Existe pelo menos um aluno da turma A que está
doente” é a proposição “Qualquer que seja o aluno da turma A, ele não está
doente” ou “Nenhum aluno da turma A está doente”.
Exemplo 11
A negação da proposição: “Existe um planeta que é a habitável” é a proposição
“Todos os planetas não são habitáveis”, ou “Nenhum planeta é habitável”.
Eric Araújo | UFLA – Departamento de Ciência da Computação 58/72
Matemática Discreta
Exemplo 12
¬(∃x ∈ R)(x2 < 0)⇔ (∀x ∈ R)(x2 ≥ 0)
Exemplo 13
¬(∀x ∈ R)(sen x = 0)⇔ (∃x ∈ R)(sen x 6= 0)
Eric Araújo | UFLA – Departamento de Ciência da Computação 59/72
Matemática Discreta
Verdade por “default” de proposições universais
Uma proposição na forma
∀x ∈ D, se P (x) então Q(x)
é chamada de verdade por “default” sse P (x) é falso para cada x em D.
Eric Araújo | UFLA – Departamento de Ciência da Computação 60/72
Matemática Discreta
Exemplo 13
Sejam cinco bolas azuis, cinco brancas e um prato.
Cenário 1: três bolas azuis e uma branca são colocadas no prato.
• P: Todas as bolas no prato são azuis.
• → P é falso, já que é possível identificar uma bola branca no prato.
Cenário 2: o prato está vazio.
• P: Todas as bolas no prato são azuis.
• → P é verdadeiro ou falso?
Eric Araújo | UFLA – Departamento de Ciência da Computação 61/72
Matemática Discreta
Exemplo 13 (cont.) A proposição é falsa sse sua negação for verdadeira.
A negação é:
¬P : Existe pelo menos uma bola no prato que não é azul.
¬P só é verdadeiro se houver (existir) no prato uma bola que não seja azul.
Como não existe, a negação é falsa e, assim, a proposição é verdadeira
por “default”.
Eric Araújo | UFLA – Departamento de Ciência da Computação 62/72
Matemática Discreta
Proposições com múltiplos quantificadores
Reescreva as sentenças abaixo formalmente usando quantificadores e variáveis:
(a) Todo mundo ama alguém.
∀ pessoas x,∃ uma pessoa y tal que x ama y.
(b) Alguém ama todo mundo.
∃ uma pessoa x tal que ∀ pessoas y, x ama y.
As sentenças (a) e (b) são equivalentes logicamente?
(a) ≡? (b)
Não. Em geral, ao se trocar a ordem dos quantificadores na sentença o sentido muda.
Eric Araújo | UFLA – Departamento de Ciência da Computação 63/72
Matemática Discreta
Negação de proposições quantificadas multiplamente
Qual é a negação da seguinte afirmação:
P : ∀ pessoas x, ∃ uma pessoa y tal que x ama y.
O que significa a sentença ser falsa?
A propriedade não ser válida para todas as pessoas.
¬P : ∃ uma pessoa x tal que ¬(∃ uma pessoa y tal que x ama y) ≡
∃ uma pessoa x tal que ∀ pessoas y, x não ama y
Eric Araújo | UFLA – Departamento de Ciência da Computação 64/72
Matemática Discreta
Negação de proposições quantificadas multiplamente
Regra geral:
P : ∀x, ∃y tal que C(x, y).
¬P : ∃x tal que ∀y, ¬C(x, y).
Exemplo 14
P : ∀ inteiros n, ∃ um inteiro k tal que n = 2k.
¬P : ∃ um inteiro n tal que ∀ inteiro k, n 6= 2k.
Eric Araújo | UFLA – Departamento de Ciência da Computação 65/72
Matemática Discreta
Negação de proposições quantificadas multiplamente
Regra geral:
P : ∃ x tal que ∀y, C(x, y).
¬P : ∀x, ∃y tal que ¬C(x, y).
Exemplo 15
P : ∃ uma pessoa x tal que ∀ pessoas y, x ama y.
¬P : ∀ pessoas x ∃ uma pessoa y tal que x não ama y.
Eric Araújo | UFLA – Departamento de Ciência da Computação 66/72
Matemática Discreta
\mybox{0.8\textwidth}{
\begin{theorem}[Murphy (1949)]
Anything that can go wrong, will go wrong.
\end{theorem}
}
Eric Araújo | UFLA – Departamento de Ciência da Computação 67/72
Matemática Discreta
Displaying Information
Eric Araújo | UFLA – Departamento de Ciência da Computação 68/72
Matemática Discreta
Table
Treatments Response 1 Response 2
Treatment 1 0.0003262 0.562
Treatment 2 0.0015681 0.910
Treatment 3 0.0009271 0.296
Tabela 1: Table caption
Eric Araújo | UFLA – Departamento de Ciência da Computação 69/72
Matemática Discreta
Figure
Eric Araújo | UFLA – Departamento de Ciência da Computação 70/72
Matemática Discreta
Theorem
The most common definition of Murphy’s Law is as follows.
Teorema (Murphy (1949))
Anything that can go wrong, will go wrong.
Demonstração. A special case of this theorem is proven in the textbook.
Remark
This is a remark.
Algorithm
This is an algorithm.
Eric Araújo | UFLA – Departamento de Ciência da Computação 71/72
Matemática Discreta
Citations
An example of the \cite command to cite within the presentation:
This statement requires citation [?].
Eric Araújo | UFLA – Departamento de Ciência da Computação 72/72
Questions?