Equivalencias- Matemática Discreta
18 pág.

Equivalencias- Matemática Discreta


DisciplinaMatemática Discreta4.476 materiais83.224 seguidores
Pré-visualização4 páginas
Novo Mo´dulo de MD 2016 Unidade 1
Matema´tica Discreta
To´picos da Linguagem e da Lo´gica Matema´ticas
Texto da Semana 3, Parte 2
Equivale\u2c6ncia
Suma´rio
1 Introduc¸a\u2dco 13
2 Equivale\u2c6ncia de enunciados 14
3 Interpretac¸o\u2dces para dois enunciados e Me´todo das Tabelas para
Equivale\u2c6ncia 15
3.1 Observac¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Negac¸a\u2dco de enunciados 22
4.1 Observac¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1 Introduc¸a\u2dco
Neste texto, iniciamos as aplicac¸o\u2dces de simbolizac¸o\u2dces e tabelas na resoluc¸a\u2dco de
problemas lo´gicos que esta\u2dco associados diretamente com a pra´tica matema´tica. Va-
mos estudar a equivale\u2c6ncia lo´gica de enunciados e a reescrita da negac¸a\u2dco de enunci-
ados por meio de equivale\u2c6ncias.
Na pra´tica, dependendo de como entendemos o significado de um enunciado, ele
pode ser simbolizado de mais de uma maneira.
Por exemplo, o enunciado
na\u2dco e´ o caso que 2 na\u2dco e´ par (1)
pode ser reescrito como
na\u2dco (na\u2dco (2 e´ par))
Assim, de acordo com a legenda
p : 2 e´ par (2)
(1) pode ser simbolizado diretamente como
¬¬p
13
Novo Mo´dulo de MD 2016 Unidade 1
Mas, levando em conta que dizer que 2 na\u2dco e´ par e´ o mesmo que dizer que 2 e´
\u131´mpar, e que dizer que 2 na\u2dco e´ \u131´mpar e´ o mesmo que dizer que 2 e´ par, podemos
considerar que o enunciado (1) quer dizer, simplesmente, que 2 e´ par.
Assim, uma outra simbolizac¸a\u2dco indireta para (1), de acordo com a legenda (2),
pode ser
p
Estritamente falando, negamos um enunciado \u3d5 escrevendo o ¬ na frente dele,
obtendo ¬\u3d5. Assim, para a Lo´gica \u2014 por definic¸a\u2dco \u2014, a negac¸a\u2dco de
¬ (2 e´ par)
e´
¬ [ ¬ (2 e´ par) ]
Mas, em Matema´tica, quando falamos em negar um enunciado, na\u2dco estamos fa-
lando em negar no sentido estrito. O que queremos, na verdade, e´ obter um enunci-
ado equivalente a` negac¸a\u2dco, que nos transmita a mesma informac¸a\u2dco de uma maneira
mais adequada do que a obtida simplesmente pela colocac¸a\u2dco de uma ocorre\u2c6ncia do
¬ na frente do enunciado negado.
Assim, em Matema´tica, ao inve´s de escrevermos
¬ [ ¬ (2 e´ par) ]
escrevemos, simplesmente,
2 e´ par
ja´ que, como veremos na Sec¸a\u2dco 2, estes enunciados sa\u2dco logicamente equivalentes.
Determinar quando dois enunciados sa\u2dco lo´gicamente equivalentes e reescrever a
negac¸a\u2dco de enunciados por meio de equivale\u2c6ncias sa\u2dco habilidades ba´sicas que todo
estudante de Matema´tica deve possuir. Por esta raza\u2dco, voce\u2c6 deve estudar os concei-
tos e resultados apresentados neste texto com a ma´xima atenc¸a\u2dco, ate´ absorver todos
estes conteu´dos.
Especificamente, neste texto, vamos abordar as noc¸e\u2dcs de: equivale\u2c6ncia lo´gica de
enunciados (Sec¸a\u2dco 2); interpretac¸a\u2dco de um enunciado (Sec¸a\u2dco 3); o Problema da
Equivale\u2c6ncia e sua resoluc¸a\u2dco pelo Me´todo das Tabelas para Equivale\u2c6ncia (Sec¸a\u2dco 3);
e, finalmente, a reescrita da negac¸a\u2dco de em enunciado por meio de equivale\u2c6ncias
(Sec¸a\u2dco 4).
Depois de estudarmos este texto, vamos ser capazes de: usar tabelas para decidir
quando dois enunciados (constru´\u131dos por aplicac¸o\u2dces dos conectivos) sa\u2dco equivalentes
ou na\u2dco (Exerc´\u131cios 1 e 2); aplicar equivale\u2c6ncias na reescrita da negac¸a\u2dco de um enun-
ciado (Sec¸a\u2dco 4); reescrever a negac¸a\u2dco de um enunciado constru´\u131do por aplicac¸o\u2dces
dos conectivos; (Exerc´\u131cio 3); mostrar que dois enunciados sa\u2dco equivalentes, exibindo
uma seque\u2c6ncia de enunciados equivalentes, que mostra como um enunciado pode ser
transformado no outro (Exerc´\u131cio 4).
14
Novo Mo´dulo de MD 2016 Unidade 1
2 Equivale\u2c6ncia de enunciados
Em Matema´tica, dois enunciados sa\u2dco logicamente equivalentes quando (1)
sa\u2dco ambos verdadeiros ou ambos falsos no contexto em que sa\u2dco proferidos e
(2) sa\u2dco ambos verdadeiros ou ambos falsos em qualquer outro contexto.
Surge, enta\u2dco, o Problema da Equivale\u2c6ncia Lo´gica de enunciados, isto e´, o pro-
blema de
dados dois enunciados, classifica´-los como logicamente equivalentes ou
na\u2dco.
O Problema da Equivale\u2c6ncia Lo´gica pode ser resolvido com o uso de tabelas
de avaliac¸a\u2dco, quando os enunciados envolvidos sa\u2dco constru´\u131dos por aplicac¸a\u2dco dos
conectivos lo´gicos.
Como sempre acontece em Lo´gica, o primeiro passo para a resoluc¸a\u2dco de qual-
quer problema e´ a simbolizac¸a\u2dco dos enunciados envolvidos. Assim, nas ex-
plicac¸o\u2dces que seguem assumimos que todos os enunciados em questa\u2dco esta\u2dco
devidamente simbolizados.
3 Interpretac¸o\u2dces para dois enunciados e Me´todo
das Tabelas para Equivale\u2c6ncia
Como os conectivos lo´gicos sa\u2dco por func¸a\u2dco de verdade, a u´nica informac¸a\u2dco rele-
vante para a comparac¸a\u2dco dos valores de dois enunciados sa\u2dco as atribuic¸o\u2dces de valores
aos seus enunciados componentes.
Interpretac¸o\u2dces para dois enunciados
Sejam \u3d5 e \u3c8 dois enunciados simbolizados, na\u2dco necessariamente distintos.
Uma interpretac¸a\u2dco para \u3d5 e \u3c8 e´ uma atribuic¸a\u2dco de valores, V ou F , para
todas as varia´veis que ocorrem em \u3d5 e \u3c8, de modo que a cada varia´vel seja
atribu´\u131do um u´nico valor.
15
Novo Mo´dulo de MD 2016 Unidade 1
Exemplo 1 (a) Os enunciados p e ¬¬p possuem duas interpretac¸o\u2dces:
p
V
F.
(b) Os enunciados ¬(p \u2227 q) e ¬p \u2228 ¬q possuem quatro interpretac¸o\u2dces:
p q
V V
V F
F V
F F.
(c) Os enunciados p\u2192 (q \u2192 r) e (p\u2192 q)\u2192 r possuem oito interpretac¸o\u2dces:
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F.
Sejam \u3d5 e \u3c8 enunciados simbolizados.
Dizemos que \u3d5 e \u3c8 sa\u2dco logicamente equivalentes se, para cada interpretac¸a\u2dco
para \u3d5 e \u3c8, os valores de \u3d5 e \u3c8 sa\u2dco iguais.
Me´todo das Tabelas para Equivale\u2c6ncia
Exemplo 2 (a) Para cada interpretac¸a\u2dco para a varia´vel p, os enunciados p e ¬¬p
assumem os mesmos valores, como vemos ao comparar a primeira e a terceira colunas
da tabela abaixo:
p ¬p ¬¬p
V F V
F V F
\u21d1 \u21d1
Assim, os enunciados p e ¬¬p sa\u2dco equivalentes.
Esta equivale\u2c6ncia garante que na\u2dco precisamos escrever duas aplicac¸o\u2dces sucessivas
do conectivo ¬.
16
Novo Mo´dulo de MD 2016 Unidade 1
(b) Para cada interpretac¸a\u2dco para as varia´veis p, q, os enunciados ¬(p\u2227 q) e ¬p \u2228 ¬q
assumem os mesmos valores, como vemos ao comparar a quarta e a se´tima colunas
da tabela abaixo:
p q p \u2227 q ¬(p \u2227 q) ¬p ¬q ¬p \u2228 ¬q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
\u21d1 \u21d1
Assim, os enunciados ¬(p \u2227 q) e ¬p \u2228 ¬q sa\u2dco equivalentes.
Esta equivale\u2c6ncia garante que a negac¸a\u2dco de uma conjunc¸a\u2dco pode ser reescrita
como uma disjunc¸a\u2dco de negac¸o\u2dces.
(c) Vamos agora verificar que os enunciados p \u2192 (q \u2192 r) e (p \u2192 q) \u2192 r na\u2dco sa\u2dco
equivalentes. Isto e´, que a maneira como agrupamos os enunciados componentes
em aplicac¸o\u2dces iteradas do conectivo \u2192 e´ relevante para a determinac¸a\u2dco do valor do
enunciado.
Para mostrar isto, devemos mostrar que
na\u2dco e´ o caso que para cada interpretac¸a\u2dco para p, q, r, os valores de
p\u2192 (q \u2192 r) e (p\u2192 q)\u2192 r sa\u2dco iguais.
Ou seja, devemos mostrar que
para ao menos uma interpretac¸a\u2dco para p, q, r, os valores de p\u2192 (q \u2192 r)
e (p\u2192 q)\u2192 r sa\u2dco diferentes.
De fato, comparando a quinta e a se´tima colunas da tabela:
p q r q \u2192 r p\u2192 (q \u2192 r) p\u2192 q (p\u2192 q)\u2192 r
V V V V V V V
V V F F F V F
V F V V V F V
V F F V V F V
F V V V V V V
F V F F V V F \u21d0
F F V V V V V
F F F V V V F
\u21d1 \u21d1
observamos que na sexta linha (descontando a linha de refere\u2c6ncia),
quando p e´ F , q e´ V e r e´ F , o enunciado p\u2192 (q \u2192 r) e´ V e o enunciado
(p\u2192 q)\u2192 r e´ F .
Como os valores de p\u2192 (q \u2192 r) e (p\u2192 q)\u2192 r sa\u2dco diferentes para pelo menos uma
interpretac¸a\u2dco, eles na\u2dco sa\u2dco equivalentes. \ufffd
17
Novo Mo´dulo de MD 2016 Unidade 1
O me´todo que usamos para resolver o problema da equivale\u2c6ncia de enunciados
simbolizados pode ser resumido em 5 passos: