unidade 1 logica 2022_1

Prévia do material em texto

Unidade 1 – Noções de Lógica
Definição. Uma proposição é uma sentença declarativa à qual se pode atribuir o valor verdade
verdadeiro ou falso.
Exemplos. 1) São proposições as seguintes sentenças:
Buenos Aires é a capital do Brasil (proposição falsa)
2 + 3 = 5 (proposição verdadeira)
4válidas:
1. Idempotência: p ∨ p⇐⇒ p e p ∧ p⇐⇒ p
2. Comutatividade: p ∨ q ⇐⇒ q ∨ p e p ∧ q ⇐⇒ q ∧ p
3. Associatividade: p ∨ (q ∨ r)⇐⇒ (p ∨ q) ∨ r e p ∧ (q ∧ r)⇐⇒ (p ∧ q) ∧ r
4. Distributividade: p ∨ (q ∧ r)⇐⇒ (p ∨ q) ∧ (p ∨ r) e p ∧ (q ∨ r)⇐⇒ (p ∧ q) ∨ (p ∧ r)
5. Identidades: p ∨ V ⇐⇒ V e p ∧ F ⇐⇒ F
p ∧ V ⇐⇒ p e p ∨ F ⇐⇒ p
6. Complementares: p ∨ ¬p⇐⇒ V e p ∧ ¬p⇐⇒ F
7. Dupla negação : ¬(¬p)⇐⇒ p
8. Absorção: p ∧ (p ∨ q)⇐⇒ p e p ∨ (p ∧ q)⇐⇒ p
9. Leis de De Morgan: ¬(p ∨ q)⇐⇒ ¬p ∧ ¬q
¬(p ∧ q)⇐⇒ ¬p ∨ ¬q
Todas essas propriedades podem ser provadas usando tabelas-verdade. Exemplificamos com
Leis de De Morgan: ¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q
¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q
Para provar a primeira dessas leis, constrúımos uma tabela verdade.
5
luisa
Linha
p q p ∨ q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q ¬(p ∨ q)↔ ¬p ∧ ¬q
V V V F F F F V
V F V F F V F V
F V V F V F F V
F F F V V V V V
Como a quarta e a sétima colunas são iguais, conclúımos que ¬(p∨ q) ⇐⇒ ¬p∧¬q. Note que
a equivalência também pode ser verificada na última coluna da tabela, já que o bicondicional
entre as duas proposições é uma tautologia.
A demonstração da outra lei de De Morgan pode ser feita da mesma maneira e fica como
exerćıcio.
Observe que:
1. a propriedade associativa, (p∨q)∨r ⇐⇒ p∨(q∨r) e (p∧q)∧r ⇐⇒ p∧(q∧r) dos conetivos
conjunção e disjunção também é válida para as operações de adição e multiplicação em
R : (x+ y)+ z = x+(y+ z) e (x · y) · z = x · (y · z). Essas operações em R são operações
binárias, dado um par de números reais (x, y) ∈ R2, a ele está associado um número real
chamado de soma de x e y e denotado por x+y. Em prinćıpio, x+y+z não teria sentido,
pois (x, y, z) não é um par. Para dar um sentido, teŕıamos que introduzir parênteses. Só
que isso pode ser feito de duas maneiras, (x + y) + z e x + (y + z). Pela propriedade
associativa, as duas maneiras de associar dão na mesma, seja qual for a maneira que
associarmos os números, o resultado é o mesmo. Logo podemos escrever x + y + z sem
que dáı resulte uma ambiguidade. A mesma observação se aplica às operações ∨ e ∧ entre
proposições.
2. a propriedade distributiva: (p∨q)∧r ⇐⇒ (p∧r)∨(q∧r) e (p∧q)∨r ⇐⇒ (p∨r)∧(q∨r)
também é semelhante a propriedade distributiva (da multiplicação perante a adição)
(x + y) · z = (x · z) + (y · z) para números reais. Note que em R não vale a outra
distributividade (adição perante multiplicação), (x · y) + z ̸= (x+ z) · (y + z).
Conforme o que foi explicado acima, a associatividade permite falar em p1 ∨ p2 ∨ . . .∨ pn e em
p1 ∧ p2 ∧ . . . ∧ pn.
As Leis de De Morgan se estendem para
¬(p1 ∨ p2 ∨ . . . ∨ pn) ⇐⇒ ¬p1 ∧ ¬p2 ∧ · · · ∧ ¬pn
e
¬(p1 ∧ p2 ∧ . . . ∧ pn) ⇐⇒ ¬p1 ∨ ¬p2 ∨ · · · ∨ ¬pn
Exemplo. Mostrar que ¬(p ∨ (¬p ∧ q)) ⇐⇒ ¬p ∧ ¬q.
Podemos mostrar isso de duas maneiras, contruindo uma tabela verdade ou usando as
propriedades. Vamos provar da segunda maneira, deixando a tabela verdade a cargo do leitor.
¬(p ∨ (¬p ∧ q))
(9)⇐⇒ ¬p ∧ ¬(¬p ∧ q)
(9)⇐⇒ ¬p ∧ (¬¬p ∨ ¬q) (7)⇐⇒ ¬p ∧ (p ∨ ¬q)
6
(4)⇐⇒ (¬p ∧ p) ∨ (¬p ∧ ¬q) (6)⇐⇒ F ∨ (¬p ∧ ¬q) (5)⇐⇒ ¬p ∧ ¬q.
onde F é um proposição composta que é sempre falsa (contradição).
Observação. Assim como existem dois śımbolos ↔ e ⇐⇒ com significados diferentes,
acontece o mesmo com → e =⇒. Assim, dadas duas proposições p e q, temos que p → q é
uma nova proposição. Já p =⇒ q é uma relação entre as duas proposições, significa que p→ q
é uma tautologia.
Exerćıcio resolvido. Mostre que (p ∧ q)→ (p ∨ q) é uma tautologia.
Solução: Podemos resolver de duas maneiras:
1) Construindo uma tabela verdade. Deixamos isso a cargo do leitor.
2) Usando várias das propriedades recém enunciadas e a propriedade (*) (r → s)⇐⇒ (s∨¬r)
já demonstrada.
Substituindo r por (p ∧ q) e s por (p ∨ q) em (*) obtemos,
(p ∧ q)→ (p ∨ q) ⇐⇒ (p ∨ q) ∨ ¬(p ∧ q)
seguimos usando a Lei de De Morgan (9) e obtemos,
(p ∨ q) ∨ ¬(p ∧ q)⇐⇒ (p ∨ q) ∨ (¬p ∨ ¬q)
e utilizando a comutatividade (2) e associatividade (3) repetidamente chegamos a
(p ∨ q) ∨ (¬p ∨ ¬q)⇐⇒ (p ∨ ¬p) ∨ (q ∨ ¬q).
Agora basta utilizar (6), complementar para obter,
(p ∨ ¬p) ∨ (q ∨ ¬q)⇐⇒ V ∨ V
Finalmente, utilizando a idempotência (1) obtemos V ∨ V ⇐⇒ V ,
Portanto (p ∧ q) → (p ∨ q) é sempre verdadeira, ou seja, é uma tautologia. Logo, pela
observação acima temos uma implicação entre (p ∧ q) e (p ∨ q), e podemos escrever
(p ∧ q) =⇒ (p ∨ q).
Podemos abreviar a escrita dessa demonstração para:
(p ∧ q)→ (p ∨ q)
(∗)⇐⇒ (p ∨ q) ∨ ¬(p ∧ q)
(9)⇐⇒ (p ∨ q) ∨ (¬p ∨ ¬q)
(2)e(3)⇐⇒ (p ∨ ¬p) ∨ (q ∨ ¬q) (6)⇐⇒ V ∨ V (1)⇐⇒ V
Mais exemplos equivalências:
(p→ q) ∧ (p→ r) ⇐⇒ p→ (q ∧ r)
(p→ q) ∨ (p→ r) ⇐⇒ p→ (q ∨ r)
7
luisa
Linha
Predicados e quantificadores
Definição. Um predicado é uma afirmação contendo variáveis.
Exemplos. 1) x > 1 2) x+ y = z.
Quando se especifica um valor para a(s) variável(eis) a afirmação se torna uma proposição e
tem um valor lógico.
Exemplo. 1. Seja P (x) a afirmação
P (x) : x > 2.
P (x) é um predicado. P (3) é uma proposição verdadeira. P (0) é uma proposição falsa.
2. Seja Q(x, y, z) : x+ y = z.
Q(x, y, z) é um predicado. Q(2, 3, 5) é uma proposição verdadeira. Q(1, 1, 3) é falsa.
Quantificador universal
Dado um predicado P (x), formamos (∀x)
(
P (x)
)
, que se lê
“Para todo x (no conjunto universo de discurso U) P (x)”.
Às vezes, para enfatizar o universo de discurso U, escreve-se (∀x ∈ U)
(
P (x)
)
.
Exemplo. 1) (∀x ∈ R)(x2 ≥ 0) é uma proposição verdadeira.
2) (∀x ∈ R)(x2 > 0) é falsa. Um contraexemplo para ela é x = 0. Isso porque 02 > 0 é falsa.
Um contraexemplo é um exemplo que mostra que uma dada proposição envolvendo o quan-
tificador universal é falsa.
São sinônimos as expressões “para qualquer x”, “para todo x”, “para cada x” e “qualquer
que seja x”.
Quantificador existencial
Dado um conjunto universo U e um predicado P (x), a proposição (∃x)(P (x)) lê-se “Existe x
tal que P (x)”.
Exemplo. A proposição (∃x ∈ R)(x2 = x) é verdadeira pois, 02 = 0 e 12 = 1.
Quantificador de unicidade
(∃!x)(P (x)) lê-se “Existe um único x tal que P (x).”
Em alguns textos, é usada a notação ∃1x em vez de ∃!x.
Exemplo. (∃!x ∈ N)(x2 = 4) é verdadeira. Seria falsa se o universo de discurso fosse Z.
Note que se a proposição (∃!x ∈ U)(P (x)) for verdadeira, então (∃x ∈ U)(P (x)) também é.
8
Negação de proposições e envolvendo quantificadores
Observe os seguintes exemplos:
1) Considere a proposição p : “Todo aluno de Matemática Discreta está matriculado em
Cálculo”. Se quisermos mostrar que p é falsa, isto é, que ¬p é verdadeira, precisaremos dar um
exemplo de um aluno de Matemática Discreta que não esteja matriculado em Cálculo, ou seja,
precisamos mostrar que existe um aluno de Matemática Discreta que não está matriculado em
Cálculo.
Conclusão: A negação de uma proposição do tipo (∀x)(P (x)) é (∃x)(¬P (x)).
2) Considere agora a proposição q : “Existe uma raiz real positiva para a equação x3+2x−1 =
0”.
Num primeiro momento diŕıamos que a negação de q seria “Não existe uma raiz positiva para
a equação x3 + 2x− 1 = 0”. Pensando melhor, podeŕıamos dizer ¬q é “Qualquer raiz real da
equação x3 + 2x− 1 = 0 é menor ou igual a 0”.
Conclusão: A negação de uma proposição do tipo (∃x)(P (x)) é (∀x)(¬P (x)).
Quantificadores encadeados
Exemplos: Tomando como universo de discurso para as variáveis o conjunto U = R dos
números reais, consideremos as proposições:
1. (∀x)(∃y)(x+ y = 0) é uma proposição verdadeira.
Por exemplo, para x = 3, existe y = −3. Para x = 0, existe y = 0. Para um x genérico,
existe y = −x.
2. (∀x)(∃y)(xy = 1) é falsa.
Para x = 0, não existe y tal que xy = 0 · y = 1, pois (∀y)(0 · y = 0).
Portanto é verdadeira a negação de nossa proposição. Essa negação é (∃x)(∀y)(xy ̸= 1).
Conclusão: Confirmando o que vimos acima, a negação de (∀x)(∃y)(P (x, y)) é
(∃x)(∀y)(¬P (x, y)).
3. (∃x)(∀y)(x+ y = y) é uma proposição verdadeira.Para provar que é verdadeira uma proposição que começa com existe x, precisamos dar
um exemplo de um x. Seja x = 0. Então, para qualquer y ∈ R, temos x+ y = 0+ y = y.
4. (∃x)(∀y)(x+ y = 0) é falsa.
Para mostrar que a proposição é falsa, precisamos justificar que não existe x, isto é, que
para todo x existe y tal que x+ y ̸= 0. Mas isso é fácil. Qualquer que seja x ∈ R, existe
y, por exemplo y = 1− x tal que x+ y = x+ 1− x = 1 ̸= 0.
Conclusão: Confirmando o que vimos anteriormente, a negação de (∃x)(∀y)(P (x, y)) é
(∀x)(∃y)(¬P (x, y)).
5. (∀x)(∀y)
[
(x > 0) ∧ (y > 0)→ (xy > 0)
]
é verdadeira.
Provamos que essa proposição é verdadeira da seguinte maneira. Sejam x e y dois ele-
mentos de R. Vamos verificar que para esses x e y vale a implicação
9
(x > 0) ∧ (y > 0)→ (xy > 0).
Se o lado esquerdo (x > 0)∧ (y > 0) for falso, a implicação já é verdadeira. Suponhamos
então que (x > 0) ∧ (y > 0) seja verdadeira. Mas x e y sendo positivos, segue que
seu produto xy é positivo. Esse argumento mostra que, qualquer que fosse a maneira de
escolher os elementos x e y dois elementos em R, a implicação (x > 0)∧(y > 0)→ (xy > 0)
seria verdadeira.
Ordem dos quantificadores. Às vezes a ordem dos quantificadores é fundamental para o
significado. Por exemplo,
(∀x ∈ Z)(∃y ∈ Z)(x+ y = 0)
é uma proposição verdadeira. Por exemplo, para x = 1, existe y = −1 tal que x+ y = 0. Para
x = 0, também existe y = 0 tal que x+ y = 0. Nossa proposição afirma que para cada x existe
um y. Para um outro x′ também existe o seu y′, que pode ser diferente do y anterior.
Trocando a ordem dos quantificadores, a proposição
(∃y ∈ Z)(∀x ∈ Z)(x+ y = 0)
é falsa. De fato, ela está afirmando que existe UM elemento y, tal que qualquer que seja x
tem-se x + y = 0. Note que com esta ordem dos quantificadores a proposição está afirmando
que o y é sempre o mesmo, inclusive quando o x mudar. No caso anterior, mudando o x, o y
também pode mudar.
(∃x)(∀y)(P (x, y) ) =⇒ (∀y)(∃x)(P (x, y) )
⇍
Em outras situações a ordem dos quantificadores não importa.
(∃x ∈ Z)(∃y ∈ Z)(xy = 1) e (∃y ∈ Z)(∃x ∈ Z)(xy = 1) são equivalentes. Ambas afirmam
que existe um par de valores inteiros cujo produto é igual a 1. A afirmação é verdadeira, por
exemplo x = y = 1, ou ainda x = y = −1.
Exemplo. Vejamos um exemplo de utilização de quantificadores encadeados.
A operação de + no conjunto R dos números reais tem as seguintes propriedades:
1. Associativa: (∀x ∈ R)(∀y ∈ R)(∀z ∈ R)
(
(x+ y) + z = x+ (y + z)
)
.
2. Elemento neutro: (∃x ∈ R)(∀y ∈ R)( x+ y = y + x = y ).
De fato, existe x = 0 com essa propriedade. 0 é chamado de elemento neutro da adição,
pois 0 somado a qualquer número real não altera esse número.
3. Oposto: (∀x ∈ R)(∃y ∈ R)( x+ y = y + x = 0 ).
De fato, cada x ∈ R tem o seu oposto, o número que somado a x dá o neutro.
4. Comutativa: (∀x ∈ R)(∀y ∈ R)( x+ y = y + x ).
Exerćıcios resolvidos
1. Verifique se é verdadeira ou falsa e negue a proposição (∀x ∈ R)(x2 > 0).
10
Solução: A proposição é falsa, pois sua negação
(∃x ∈ R)(x2 ≤ 0)
é verdadeira. Esta negação começa com (∃x), para mostrar que é verdadeira precisamos
dar um exemplo de x. Mas x = 0 satisfaz x2 = 02 = 0 ≤ 0.
2. Reescreva a afirmação ¬(∀x)(∃y)(x2 + y