Noções de lógica matemática - UFV 131/2019-I/slides/logica Matematic… · "Matemática é a arte de dar o mesmo nome para coisas diferentes "(Henri Poincar

Noções de lógica matemática

MAT 131-2018 II

Pouya Mehdipour

11 de abril de 2019

Pouya Mehdipour 11 de abril de 2019 1 / 60

Referências

• ALENCAR FILHO, E. Iniciação à Lógica Matemática , Nobel,2006.

• ROSEN, K. H, Matematica discreta e sua aplicações, sexta edição,AMGH Editora, Ltd, 2010

• ALENCAR FILHO, E. Teoria Elementar dos Conjuntos, Nobel,1974.

• DOMINGUES, H.H. & IEZZI, G. Álgebra Moderna. 4a Edição.Atual Editora, 2003.

• SÉRATES, J. , Raciocínio Lógico, vol 1, Olímpica Ltda, Brasília,1997.


https://vagnerfk.files.wordpress.com/2015/08/matemc3a1tica-discreta-e-suas-aplicac3a7c3b5es-kenneth-h-rosen-6c2aa-ed-pt.pdf

Lógica Proposicional/ Historicamente

ARISTOTLE: 384-322 B.C.

G.BOOLE:1815-64

J. W. TUKEY:1915-2000

R. SMULLYAN:

1919-2017

A. DE MORGAN:

1806–1871A. ADA: 1815-1852


Lógica Proposicional/ Historicamente

H. M. SHEFFER:

1883–1964

CH.S.PEIRCE:

1839–1914CH.L. DODGSON:

1832–1898

G. H.HARDY: 1877–1947

S. RAMANUJAN: 1887–1920


Lógica Proposicional

Definição:A proposição é uma sentença declarativa (isto é, uma sentença quedeclara um fato) que é ou verdadeira ou falsa, mas não ambas.

Valor lógica de uma proposição é verdadeira (V) ou falsa(F).Exemplo: Considerem as seguintes proposições:

p= o céu é azul.

q= a terra é o sol.

Então V(p)=V, leia o valor lógico de p é verdadeiro e V(q)=F, leia ovalor lógico de q é falso.


Lógica Proposicional

Exercício: Decida se as seguintes frases são declarativas ou não:• (a) Qual é o seu nome?• (b) Feche a porta!• (c) A grama é verde.• (d) Grama é vermelha.• (e) Um excelente livro.• (f) Eu sou honesto.• (g) Você não deve trapacear.


Princípios da Lógica

** 3 Leis de Pensamento **

• Princípio de Identidade:Uma coisa é sempre igual a ela mesmo: uma proposição verdadeiraé verdadeira e uma proposição falsa é falsa.

Se Algo é @, é @.• Princípio da Não-Contradição:Um enonciado não pode ser ao mesmo tempo verdadeiro e falso.Exemplo: p= a terra é sol. Então V (p) = F , logo V (p) 6= V .

• Princípio do Terceiro Excluído:Uma proposição ou será verdadeira, ou será falsa. Não há umaterceira opção. Exemplo: p= a terra é redonda. Se o valor lógicode p não for falso, então V (p) = V.


Operadores Lógicos

** Conectivos **Tendo várias proposições(simples), usando os seguinte conectivospodemos obter proposições compostas.• ¬ ou ∼ (negação);• ∧ (conectivo “e”);• ∨ (conectivo “ou”);• Y (conectivo “ou”);• → (conectivo “implica”);• ↔ (conectivo “se, e somente se”).

O valor lógico das proposições compostas pode ser visto atravez deTabelas- Verdades.Obs 1: valores lógicos com respeito a uma proposição simples:V ou F.Então a composição de n proposições lógicas tem 2n linhas natab-verdade.


Operadores Lógicos/Exemplos

¬ ou ∼ (negação):

Exemplo: p= a terra é sol.¬p = a terra não é sol.Exemplo: p= hoje é sábado.¬p = hoje não é sábado.

Tabela- Verdade

∧ (conectivo “e” conjunção):Exemplo: p= a terra éredonda, q= o céu é azul.p ∧ q = a terra é redonda e océu é azul.Exemplo: p= o sapo é verde,q= 2 é número ímpar. p ∧ q =o sapo é verde e 2 é numeroimpar.

Tabela- Verdade


Operadores lógicos/Exemplos

∨ (conectivo “ou” disjunção):Exemplo: p= a terra é sol, q=o céu é azul. p ∨ q = a terra ésol ou o céu é azul.Exemplo: p= hoje é sábado,q= todo número natural é umnúmero inteiro. p ∨ q = hoje ésábado ou todo númeronatural é um número inteiro.

Tabela- Verdade

Exercício: Com um exemplo mostre a tabela verdade do conectivo“ou”.


Algebra Booleana/Portas Lógicas Basicas


Algebra Booleana/Portas Lógicas

Exercício: Encontre os Símbolos de XNOR e XOR e construa suatabela-verdade binária.Exercício: Construam a tabela-verdade de XNOR e XOR.



∨ (conectivo “implica” condicional):Exemplo: p= Brasília é acapital do Brasil, q= 2+3=5.A p→ q = Se Brasília é acapital do Brasil, então2 + 3 = 5.Exemplo: p= O pólitico A foieleito na eleição, q= oimposto vai diminuir.p→ q = Se o pólitico A, foieleito na eleição então, oimposto vai diminuir.

Tabela- Verdade



↔ (conectivo “se, e somente se” bicondicional):

Exemplo: p=(2+3=1), q= osol é verde. A p↔ q = o2 + 3 = 1 se, e somente se osol é verde.Exemplo: p= você viajou poravião, q= você comprou umapassagem. p↔ q = vocêviajou de avião se, esomente se você comprouuma passagem.

Tabela- Verdade

Obs 2: o p↔ q é exatamente o mesmo que (p→ q) ∧ (q → p).(Exercício)


Propriedades de Operadores Lógicos

Podemos construir proposições compostas usando operadores lógicos.Porém,• Parênteses são usados para especificar a ordem em que osoperadores são aplicados;

• A negação é aplicada antes de qualquer outro operador: ∼ p ∧ qsignifica ∼ p e q e não significa ∼ de p ∧ q;

• A conjunção tem pioridade sobre a disjunção: p ∧ q ∨ s significa(p ∧ q) ∨ s em vez de p ∧ (q ∨ s);

• Condicional e bicondicional tem pioridade menor que a conjunçãoe a disjunção: p ∨ q → s significa (p ∨ q)→ s;

• A Condicional tem prioridade maior do que A Bicondicional.


Exercícios

Exercício 1: SejamP= Hoje choveu,(V)Q= Nancy foi a Praia,(V)R= José foi à academia(V).Enconterem o valor lógico relacionado aos seguintes:1)P∧ ∼ Q,2)∼ P ∨Q,3)∼ P → Q,4)∼ P → (∼ Q∧ ∼ R),5)Quantas linhas tem a tabela-verdade para (Q∧ ∼ R)→ P?Exercício 2: Dadas as proposições compostas:1)3 + 6 = 9↔ 52 = 205,2)20 = 1→ π é um número racional.3)(√3 < −1 ∧ π2 < 0)→

√2 > 1.

Qual tem valor lógico verdadeiro?


Tabela verdade para três proposições(P,Q,R)

Sejam P,Q,R três proposições simples.

Tabela-Verdade:


Exercícios

Exercício 3: Sejam P, Q, R três proposições simples.Enconterem a tabela-verdade relacionada aos seguintes:1)∼ P ∧Q,2)∼ R ∨Q,3)∼ R↔∼ Q ∧ P,4)P → (∼ Q∧ ∼ R),Exercício 4: Encontrem a tabela-binária relacionada aos seguintes:1)porta básica A.B.C = A ∧B ∧ C2)porta básica D ⊕ E = D Y E3)porta básica (A ∧B ∧ C) ∨ (A YB)4)esboça simbolicamente a porta básica 3.Exercício 5: Sejam p, q duas sequências binárias, tais quep = 11010110 e q = 10011011. Encontre as sequências binárias tipo”ou” e tipo ”e”. Exercícios Extras: 28, 29, 30, 37, 38 do LivroROSEN, K. H.


Equivalências Proposicionais

"Matemática é a arte de dar o mesmonome para coisas diferentes "

(Henri Poincaré)

Tautologia, Contradição e Contingência:Uma proposição composta que é sempre verdadeira, é chamada detautologia. Uma proposição composta que é sempre falsa é chamadade contradição. Uma proposição composta que não é tautologia nemcontradição é chamada de contingência.



Implicação Lógica:

o conectivo "Implica"ou → semuda por relação ⇒ chamado"Implicação Lógica"quandop→ q for uma tautologia.

Tabela- Verdade

Equivalência Lógica:o conectivo "Se, e somentese"ou ↔ se muda por relação⇔ chamado "EquivalênciaLógica"quando p↔ q for umatautologia.

Tabela- Verdade

Obs 3: Lembrando Obs 2, p⇔ q é exatamente (p⇒ q) ∧ (q ⇒ p). Onde(p⇒ q) significa que p→ q é uma Tautologia.



Implicação Lógica:Exemplo: Seguintes proposições compostas são implicação lógica?1- p⇒ p (reflexiva)2- (p→ q) ∧ (q → r)⇒ (p→ r) (transitiva)3- p ∧ ¬p⇒ q4- (p↔ q ∧ p)⇒ q.

Equivalência Lógica:Exemplo: Seguintes proposições compostas são equivalência lógica.1- p→ q ⇔ ¬p ∨ q2- ¬(p ∨ q)⇔ ¬p ∧ ¬q3- (p↔ q)⇔ (¬p ∧ ¬q) ∨ (p ∧ q.)4- p ∨ (q ∧ r)⇔ (p ∨ q) ∧ (p ∨ r).

Obs 4: p ∧ V = p, p ∧ F = F e p ∨ V = V, p ∨ F = p.


Álgebra das Proposições

Equivalências Importantes: (V= tautologia, F=Contradição)


Método Dedutivo*

Usando tabela verdade:Exercício 6: Mostrem que (p→ q) ∧ ¬q → ¬p são implicação lógica.Exercício 7: Mostrem que p↔ ¬q e p→ q não são implicação lógica.Exercício 8*: Mostrem que ¬(p→ q) e p ∧ ¬q são logicamenteequivalente.Exercício 9: Mostrem que ¬(p↔ q) e p↔ ¬q são logicamenteequivalente.Exercício 10*: Mostrem que (p ∧ q)→ (p ∨ q) é uma tautologia. Oque significa isso?Exercício 11: Mostrem que (p↔ ¬q) ∧ (p ∧ q) é uma contradição.Exercício 12: Mostrem que p↔ (p ∧ q) é uma contingência.

Resp 8* (por método dedutivo): Pelo forma normal (FN), (p→ q)⇔ (¬p ∨ q)

entao ¬(p→ q) = ¬(¬p ∨ q) e pelo Lei de Demorgan, ¬(¬p ∨ q) = p ∧ ¬q.


Método Dedutivo*

Forma Normal de uma Proposição (FN):Diz-se que uma proposição esta na forma normal quando só contémconectivos ¬,∧,∨.

Obs 5: Toda proposição pode ser levada para FN equivalênte. Basta casoexistir, subistituir p→ q por ¬p ∨ q e substituir p↔ q por (¬p ∧ ¬q) ∨ (p ∧ q.)Isto é porque são equivalente lógica com suas formas normais:1-(p→ q)⇔ (¬p ∨ q)2-(p→ q)⇔ (¬p ∧ ¬q) ∨ (p ∧ q).

Usando o método dedutivo mostrem:Exercício 13: p ∧ q ⇒ p.Exercício 14: p⇒ p ∨ q.Exercício 15: p ∧ q ⇒ p ∨ q.Exercício 16: (p→ r) ∧ (q → r)⇔ (p ∨ q → r).Exercício 17: (p→ q) ∨ (p→ r)⇔ (p→ q ∨ r).


Método Dedutivo/Exercicios

Usando o método dedutivo mostrem:Exercício 18: p ∧ ¬p⇒ q;Exercício 19: p⇒ ¬p→ q;*Exercício 20: p ∨ (p ∧ q)⇔ p;Exercício 21: ¬p→ p⇔ p;Exercício 22: (p→ p ∧ q)⇔ p→ q;Exercício 23: (p→ q)→ q ⇔ (p ∨ q);Exercício 24: simplifiquem as seguintes proposições:• ¬(¬p→ ¬q);• ¬(p ∨ q) ∨ (¬p ∨ q);• (p→ q) ∧ (¬p→ q)

• p ∧ (p→ q) ∧ (p→ ¬q).

Resp *: p ∨ (p ∧ q)⇔ (p ∧ V ) ∨ (p ∧ q)⇔ p ∧ (V ∨ q)⇔ (p ∧ V )⇔ p.


Sentenças Abertas e Quantificadores

Sentenças Abertas (Predicados): Sentenças que envolvem varíaveis:

x > 5, x = y + 2, z = x+ y.

Sentença Aberta em A com uma variável:Seja A um conjunto qualquer. Chama-se uma sentença aberta(função proposicional), uma expressão P (x) tal que P (a) é falsa (F) ouverdadeira(V) para todo a ∈ A.Obs 6: O conjunto A chama-se Universo ou Domínio da variável x.Exemplo: Seja A = N e P (x) : x+ 2 ≥ 7.

Conjunto-Verdade de uma sentença aberta:Diz-se conjunto-verdade de sentença aberta P (x) em A, o conjuntode todos a ∈ A tal que P (a) é verdadeira.(VP = {x|x ∈ A e P (x) é V })Exemplo: No exemplo anterior o conjunto-verdade de p(x) denotadopor VP = {x|x ∈ Aex+ 2 ≥ 7} = {x ≥ 5}.



Condição Universal, Condição possível, Condição impossívelSe P (x) é uma sentença aberta em A, três casos podem acontecer:• P (x) é verdadeira para todo x ∈ A (condição Universal: VP = A);• P (x) é verdadeira para alguns x ∈ A (condição Possível: VP ⊂ A);• P (x) é verdadeira para nenhum x ∈ A (condição Impossível: VP = ∅.)

Exemplos:Seja A = N.• P (x) : x é maior que zero;• P (x) : x é divisor de 5;• P (x) : x é múltiplo de 20;• P (x) : x2 + 3x+ 2 = 0.



Produto CartesianoSejam A e B dois conjuntos quaisquer. O produto Cartesiano dessesconjuntos pela definição é o par ordenado:

A×B = {(a, b)|a ∈ A ∧ b ∈ B.}

Sentença Aberta em A×B com duas variáveis

É uma expressão P (x, y) tal que P (a, b) é falso (F) ou verdadeiro(V)para todo (a, b) ∈ A×B. Neste caso temos:• Conjunto-Universo ou Dominio: A×B;

• Conjunto-Verdade: VP = {(x, y)|x ∈ A ∧ y ∈ B ∧ P (x, y) é V.}Exemplo: A = {1, 2, 3}, B = {5, 6} e P (x, y) : y = 2x.

Obs 7: Na mesma forma pode-se definir sentenças abertas emA1 ×A2 · · ·An com n variáveis.


Exemplos:a) Seja Q(x, y) a proposição "x é a capital de y". Quais osvalores-lógicos das proposições a seguir?

• Q :(Belo Horizonte, Minas Gerais);

• Q :(Santos, São paulo);

• Q :(Natal, Spírito Santo);

b) Determinem o valor-lógico de x após a instrução se P (x) entãox := 1 é executado, onde P (x) é a declaração “x > 2,1)x = 0, 2)x = 4, 3) x = 2.

c) Encontrem o conjunto- verdade das seguintes sentenças abertas edigam quais sua condição em respeito ao conjunto Universo.1- A = {1, 2, 3}, B = {3, 4, 5} e P (x, y) : y = x+ 2;2- A×B = N× N e P (x, y) : 2x+ y = 10;3- A×B = Z× Z e P (x, y) : x2 + y2 = 1;4- A = {6, 2, 8}, B = {4, 6} e P (x, y) : m.d.c.(x, y) = 1;5- A1 ×A2 ×A3 = N× N× N e R(x, y, z) : x+ y = −z;



QuantificadoresSeja P1(x) : x > 0 e P2(x) : x é primo, sentenças abertas (predicados)no universo N. Então,• ∀ (universal:) Lê-se:"para todo,"ou "qualquer que seja".Exemplo:∀x|P1(x): para todo x, (ou qualque que seja o elementox) ele é maior que zero.

• ∃ (existencial:) Lê-se: "existe".Exemplo: ∃x, P2(x): existe um elemento x tal que é primo.

• ∃! Lê-se: "existe único".Exemplo: ∃!x|P2(x): existe único elemento x tal que é primo.

• @ Lê-se: "não existe".Exemplo: @x|P1(x): não existe elemento x tal que é maior quezero.(∀x,¬P (x))

Obs 8: Quantificadores ∀,∃ tem prioridade maior do que todos os conectivos.Pouya Mehdipour 11 de abril de 2019 30 / 60


Quantificadores/Exemplo

Seja A = {5, 7, 8, 9, 11, 13}, então usando quantificadores:

• ∀x ∈ A, x é natural;

• ∃x ∈ A, x é ímpar;

• ∃!x, x é par;

• @x|x é múltiplo de 15.

Considerações Importantes1- É comum em livros, sentenças com quantificador universal omitido:

"sendo x, y números reais, x+ y = y + x."2- Especialmente quando universo A = {a1, ..., an} for finito, temos

∀x ∈ A, P (x) ⇔ (P (a1) ∧ P (a2) ∧ ... ∧ P (an));3- Especialmente quando universo A = {a1, ..., an} for finito, temos

∃x ∈ A, P (x) ⇔ (P (a1) ∨ P (a2) ∨ ... ∨ P (an));4- Especialmente quando universo A = {a1, ..., an} for finito, temos

∃!x ∈ A, P (x) ⇔ (P (a1) Y P (a2) Y ... Y P (an));Pouya Mehdipour 11 de abril de 2019 31 / 60


ExercíciosExercício 25: Determinem o conjunto-verdade em Z , das seguintessentenças abertas:1)x2 − 6x+ 5 = 0. 2) |x− 3| = 5. 3) |3x− 9| = 1− x.Exercício 26: Determinem o conjunto verdade da sentença abertax+ 2y = 10 em N× N.Exercício 27: Sejam A = {2, 3, 4}. determinem o conjunto- verdade dasentença aberta "m.d.c. (x, y) = 1"em A×A.

Exercício 28: Sejam as sentenças abertas em A = {1, 2, 3, 4, 5, 6, 7, 9} emque P (x) : x2 ∈ A e Qx) : x é impar.

• a) o conjunto verdade de P (x) ∧Q(x);

• b) o conjunto verdade de P (x) ∨Q(x);

• c) o conjunto verdade de Q(x)→ P (x);

• d) o conjunto verdade de P (x)↔ Q(x).Pouya Mehdipour 11 de abril de 2019 32 / 60


ExercíciosExercício 29: determinem o valor lógico (V ou F) das seguintesproposições:• a) (∀x ∈ N)(x+ 5 > 7);• b) (∀x ∈ R)(x2 ≥ 0);• c) (∃x ∈ R)(3x+ 5 = −4);• d) (∃!x ∈ N)(x3 = x);

Exercício 30: No conjunto R, determinem o valor lógica (V ou F) decada uma das proposições:• a) (∀x)(x3 = x);• b) (∀x)(x2 + 3 ≥ 0);• c) (∃x)(|x| = x);• d) No R× R(∃!(x, y))(x2 + y2 = 1);


Negando expressões quantificadas:

• (¬∀x, P (x)) ≡ (∃x,¬P (x));• (¬∃x,Q(x)) ≡ (∀x,¬Q(x));

Exemplo: Seja p(x) : x é pólitico honesto,∃x, P (x) : existe político que é honesto; Negação: ∀x,¬P (x)∀x, P (x) : qualquer pólitico é honesto, Negação: ∃x,¬P (x).



Quais as negações das seguintes proposições:• (∀x)(x2 ≥ x);• (∃x)(x3 + 2 = 5).

Exercício 31: Mostrem que ¬∀x(P (x)→ Q(x)) e ∃x(P (x) ∧ ¬Q(x))são logicamente equivalentes.

Traduzir do Portugês para Lógica MatemáticaExercício 32: traduza as seguintes frases em português para alinguagem matemática:• a) Há estudante na sala que sabe falar francês;• b) Há uma pessoa em sala que não sabe nadar ou xadrez;• c) Todos as pessoas gostam de comida tailandesa e não gostam decomida árabe;

• d) Alguém da sala visitou o México e ninguem visitou o Canada;• e) Todas as árvores ou tem flor ou tem fruta.



Observações Importantes• a)@x(P (x)) ≡ ∀x(¬P (x)) e¬@x(P (x)) ≡ ¬(∀x(¬P (x))) ≡ ∃x(P (x)).

• b) ∃!x(P (x)) ≡ ∃x(P (x) ∧ ∀y(P (y)→ (x = y))) ≡∃x(P (x) ∧ ∀y(¬P (y) ∨ (x = y))) ≡ ∃x(P (x) ∧ ∀y(¬[P (y) ∧ (x 6=y))) ≡ ∃x(P (x) ∧ @y(P (y) ∧ x 6= y)).

• c) ¬∃!x(P (x)) ≡ ¬(∃x(P (x) ∧ @y(P (y) ∧ x 6= y))) ≡∀x(¬P (x) ∨ ∃y(P (y) ∧ x 6= y)))

• d)¬∃x(P (x)) ≡ ∀x(¬P (x)) ≡ @x(P (x)).

• e) Para negar expressões que contenham → ou ↔, primeiro escrevaem sua forma normal e então faça a negação.Pouya Mehdipour 11 de abril de 2019 36 / 60

Quantificadores Agrupados

Dois quantificadores são agrupados quando um esta no escopo do outro.Assuma que estamos no universo de numeros reais:

• ∀x∃y(x+ y = 0);

• ∀x∀y(x+ y = y + x);Exercicios do Livro: 21,22,23 seção 1.4

A Ordem dos quantificadores


Quantificadores Agrupados

Exemplo: Seja P (x, y, z) : x+ y = z em que as variáveis x, y, z pertencem aouniverso R. Então, podemos ver que seguintes sentenças tem valor lógicodiferentes.

• ∀x∀y∃z(x+ y = z);

• ∃z∀x∀y(x+ y = z);

Exemplo: Seja P (m,n) : n2 < m onde as variaveis m,n pertencem ao universoZ. Então, podemos ver que as seguintes sentenças tem valor lógica diferentes.

• ∀m∃n(n2 < m);

• ∃m∀n(n2 < m);

• ∀m∀n(n2 < m);

• ∃m∃n(n2 < m);

Exercicios do Livro: 28,30,31,32 seção 1.4Pouya Mehdipour 11 de abril de 2019 38 / 60

Traduzindo Portugês/ Linguagem Lógica Matemática:

Exercício 33: Traduza as seguintes frases em português para a linguagemmatemática:

• a) Existe uma mulher que tenha pegado uma voo em todas as companhiasaéreas do mundo;

• b) Não existe uma mulher que tenha pegado uma voo em todas as companhiasaéreas do mundo;

• c) Todas pessoas tem exatamente um melhor amigo;

• d) Todo número real, exceto zero, tem um inverso multiplicativo;

Exercício 34: Traduza as seguintes frases em matemática para linguagemportuguês:

• a) ∀x(C(x) ∨ ∃y(C(y) ∧ F (x, y))),onde C(x) é “x tem um computador”, F (x, y) é “x e y são amigos” e o domíniopara x e y é composto por todos os alunos da UFV;

• b) ∃x∀y∀z((F (x, y) ∧ F (x, z) ∧ (y 6= z))→ ¬F (y, z)),onde F (a, b) significa que a e b são amigos e o domínio para x, y e z consisteem todos os alunos da sala.

Exercicios do Livro: 1 a 10 seção 1.4Pouya Mehdipour 11 de abril de 2019 39 / 60

Regras de Inferência

Argumentos Validos em Lógica proposicionalExemplo: Se você tem uma senha atualizada, então você pode entrar na rede."você tem uma senha atualizada."Então:"Você pode enterar na rede."

• Definição: Um argumento na lógica proposicional é uma sequência deproposições. Todos menos a proposição final no argumento são chamadosde premissas e a proposição final é chamada de conclusão. Oargumento é válido se a verdade de todas as suas premissas implica que aconclusão é verdadeira.

• Definição: Uma forma de argumento na lógica proposicional é umaseqüência de proposições compostas envolvendo variáveis proposicionais.Uma forma de argumento é válida independentemente de qual sãosubstituídas pelas variáveis proposicionais em suas premissas, aconclusão é verdadeira se as premissas são todas verdadeiras.

OBs: A chave para mostrar que um argumento na lógica proposicional éválido é mostrar que sua forma de argumento é válida.


Regras de Inferência e Prova Lógica

Regra de Premissas:Você pode escreveruma premissa emqualquer etapa deuma prova lógica.



Exemplo: Está esfriando agora, portanto está esfriando agora ou chovendo.Exemplo: Está esfriando e chovendo agora, portanto está esfriando agora.Exemplo: Se chover hoje, então não teremos churrasco hoje. Se não fizermosum churrasco hoje, então teremos um churrasco amanhã. Portanto, se choverhoje, então teremos um churrasco amanhã.

Usando regras de inferência para construir argumentosExemplo: “Se você me enviar uma mensagem de e-mail, eu terminarei deescrever o programa ”,“ Se você não enviar uma mensagem de e-mail, eu voudormir cedo ”e“ Se eu for dormir cedo, então vou acordar sentindo-merevigorado ”levar à conclusão“ Se eu não terminar de escrever o programa, vouacordar sentindo-me revigorado ”.Exemplo: O Jasmim está esquiando ou não está nevando ”e“ está nevando ouBart está jogando hockey ”implica que“ Jasmine está esquiando ou Bart estájogando hockey ”.

Exercícios do Livro: 1 a 8 seção 1.5Pouya Mehdipour 11 de abril de 2019 42 / 60


Falácias

As falácias se assemelham a regras de inferência mas se baseiam em contingências enão em tautologias.Exemplo: ((p→ q) ∧ q)→ p não é uma tautologia. Se você fizer todos os problemasdeste livro, aprenderá matemática discreta. Você aprendeu matemática discreta.Portanto, você fez todos os problemas neste livro.Exemplo: ((p→ q) ∧ ¬p)→ ¬q não é uma tautologia. É correto supor que você nãoaprende matemática discreta se você não fez todos os problemas no livro, assumindoque se você fizer cada problema deste livro, você aprenderá matemática discreta?

Exercício 35: Determinem se os seguintes argumentos são válidos ou falácia.Justifiquem.

• se n é um número real tal que n > 1, então n2 > 1. Suponha que n2 > 1. Entãon > 1.

• Se n é um número real tal que n > 3, então n2 > 9. Suponha que n2 ≤ 9.Então n ≤ 3.

• Se n é um número real tal que n > 2, então n2 > 4. Suponha que n ≤ 2. Entãon2 ≤ 4.

nevar ou Bart está jogando hockey ”implica que“ Jasmine está esquiando ou Bartestá jogando hockey ”.



Regras de Inferências para Sentenças Quantificadas

Exercícios do Livro: 15,16,17 seção 1.5Pouya Mehdipour 11 de abril de 2019 44 / 60


Exemplo: Mostre que as premissas “Todos nesta turma fizeram umcurso de ciência da computação ”e“ Marla é uma aluna desta turma”implicam a conclusão de que“ Marla fez um curso de ciência dacomputação. ”Exercício 36: Mostre que as premissas “Um aluno desta turma não leuo livro”, e “Todos nesta turma passaram no primeiro exame "implica aconclusão"Alguém que passou no primeiro exame não tem Leia o livro."Exemplo: Suponha que “Para todos os inteiros positivos n, se n formaior que 4, então n2 é menor que 2n” é verdadeiro. Use o modusponens universal para mostrar que 1002 < 2100.Exercício 37: Justifique a regra do modus universal, mostrando queas premissas ∀x(P (x)→ Q(x)) e ¬Q(a) para um elemento particular ano domínio, implica ¬P (a).Exercícios do Livro: 26,27 seção 1.5


Introdução a Demonstração

• Definição: é um enunciado que explica o significado de um termo.

• Axioma: é simplesmente uma premissa válida ou ponto de partida pararaciocinar.

• Teorema: uma declaração ou fato que é considerada importante e podeser mostrado para ser verdade.

• Prova: é um argumento válido que estabelece a verdade de um teorema.

• Proposição: são teoremas menos importantes.

• Lemma: um teorema menos importante que é útil na prova de outrosresultados.

• Corolário: é um teorema que pode ser estabelecido diretamente de umteorema que foi provado.

• Conjetura: é uma afirmação que está sendo proposta para ser umaafirmação verdadeira.



Axiomas de Euclides:

1) Dados dois pontos, há um segmento de reta que osune;

2) Um segmento de reta pode ser prolongadoindefinidamente para construir uma reta;

3) Dados um ponto qualquer e uma distânciaqualquer pode-se construir um círculo de centronaquele ponto e com raio igual à distância dada;

4) Todos os ângulos retos são iguais;

• Paralelismo de Euclides: "Há um ponto P e umareta não incidentes tais que no plano que definemnão há mais do que uma reta incidente com P eparalela a r."

Euclides(323–283 BC)


Axiomas para números ReaisOS AXIOMAS DO CORPOS:Nós denotamos a soma e produto de dois números reais x e y por x+ y e xy. Alémdisso, por convenção, realizamos multiplicações antes de adições, a menos queparênteses sejam usados.

• Leis de Fechamentos para Adição/ Multiplicação: Para todos os números reaisx e y, x+ y/ xy são números reais.

• Leis Associativas para Adição/Multiplicação : Para todos os números reais x,y,z: x+ (y + z) = (x+ y) + z/ (x(yz) = (xy)z.)

• Leis comutativas para Adição/Multiplicação: Para todos os números reais x ey, x+ y = y + x/ ( xy = yx.)

• Leis de elementos neutros de Adiçaõ/multiplicação: Para todo número real x,x+ 0 = 0 + x = x / (x1 = 1x = x.)

• Leis de elementos Inversos para Adição/Multiplicação: Para todo número realx, existe um número −x/ ( 1

xonde x é não-nulo) tal que

x+ (−x) = (−x) + x = 0 / (x 1x= 1

xx = 1.)

• Leis Distribuitivas: Para todos os números reais x,y,z, x(y + z) = xy + xz e(x+ y)z = xz + yz.


Axiomas para números ReaisOS AXIOMAS DE ORDEM:

Especificamos propriedades da relação “maior que/ menor que”, denotada por >/ <,no conjunto de números reais. Escrevemos x > y (e y < x) quando x é maior que y,e escrevemos x ≥ y (e y ≤ x) quando x > y ou x = y.

• Lei de tricotomia: Para todos os números reais x e y, exatamente um de x = y,x > y ou y > x é verdade.

• Lei de transitividade: Para todos os números reais x, y, z, se x > y e y > z,então x > z.

• Leis de compatibilidades para Adição/Multiplicação: Para todos os númerosreais x e y,z, se x > y, então x+ z > y + z/(se z > 0, então xz > yz.)Exercício: Mostrem que para todos os números reais x e y,z, se x > y e z < 0,então xz < yz.Definição: Dado A, um conjunto não vazio. o número real b é um limitesuperior de A se para todo número real a em A, b ≥ a. Um número real s é omenor limite superior (ou Supremo) de A se s é um limite superior de A esempre que é um limite superior ligado de A, então temos s ≤ t.

• Propriedade de Complitude: Todo conjunto não vazio de números reais queseja limitado superiormente, tem um menor limite superior.Pouya Mehdipour 11 de abril de 2019 49 / 60

Introdução a DemonstraçãoObs Importantes: Os Axiomas de Corpo e Ordem são váalidos para (Q,+, .) emlugar de números reais. No caso de (Z,+, .) são validos a menos da Lei do inversomultiplicativo.

Exemplos de Teoremas:• Teorema 1: se m e n são quadrados perfeitos, então mn também é um

quadrado perfeito.

• Lema 2: Se n é um número inteiro ímpar, então n2 é ímpar.

• Proposição 3: Seja n inteiro. Se 3n+ 2 é ímpar, então 3n é ímpar.

• Teorema 4: Seja a, b ∈ Z+. Se n = ab, então a ≤√n ou b ≤

√n.

• Teorema 5:A soma de dois números racionais é sempre racional.

• Teorema 6: Pelo menos quatro dos 22 dias do mês, devem cair no mesmo diada semana.

• Teorema 7: O n é um inteiro ímpar se e somente se n2 for ímpar.

• Teorema 8: Estas declarações sobre o inteiro n são equivalentes:1) n é par;2) n− 1 é ímpar;3) n2 é par.Pouya Mehdipour 11 de abril de 2019 50 / 60

Introdução a DemonstraçãoTipos de Provas:1) Prova Direta: Uma prova direta mostra que uma declaração

condicional p→ q é verdadeira mostrando que se p é verdadeiro, então qtambém deve ser verdadeiro, então a combinação p verdadeiro e q falso,nunca ocorre.

• Prova Direta do Teorema 1:Definição: Um inteiro a é um quadrado perfeito se existir um inteiro btal que a = b2.Prova: Assumimos que a hipótese deste afirmação condicional éverdadeira, isto é, assumimos que m e n são ambos quadrados perfeitos.Pela definição de um quadrado perfeito, segue-se que existem inteiros s, ttais que m = s2 e n = t2. O objetivo é mostrar que o mn também deveser um quadrado perfeito quando m e n são. Podemos mostrar issosubstituindo s2 por m e t2 por n. Este nos diz que mn = s2t2. Logo,mn = s2t2 = (sst)t = t(sst) = (st)(st) = (st)2, usando os Leis decomutatividade e associatividade de multiplicação dos Axiomas deCorpo.

Exercícios 38,39,40: Demonstrem o Lema 2 e Proposição 3 e Teorema 5usando prova direta.Pouya Mehdipour 11 de abril de 2019 51 / 60


Tipos de Provas:

2) Provas Indiretas: Provas de teoremas do tipo ∀x(P (x)→ Q(x)) quenão são diretos, isto é, que não começam com as premissas e terminamcom a conclusão, são chamadas de provas indiretas.

• Prova por Contrapositividade: Uma prova por contrapositividade dep→ q, é tomar ¬q como uma premissa, e usando axiomas, definições eteoremas previamente comprovados, juntos com regras de inferência,mostramos que ¬p deve seguir.Definição: O inteiro n é par se existe um inteiro k tal que n = 2k, e n éímpar se existir um inteiro k tal que n = 2k + 1.Prova da Proposição 3 por Contrapositiva: Suponhamos que nseja par. Então, por definição, n = 2k para algum inteiro k. Substituindo2k por n, encontramos 3n+ 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). Isso nosdiz que 3n+ 2 é par. Esta é a negação da premissa do teorema.

Exercício 41: Demonstrem o teorema 4 usando prova por contrapositiva.



Tipos de Provas:

2) Provas Indiretas: Provas de teoremas do tipo ∀x(P (x)→ Q(x)) quenão são diretas, isto é, que não começam com as premissas e terminamcom a conclusão, são chamadas de provas indiretas.

• Provas Vácuas e Triviais: Nós podemos provar rapidamente que umadeclaração condicional p→ q é verdadeira quando sabemos que p é falso,porque p→ q deve ser verdadeiro quando p é falso. Isso tambémacontece quando na declaração condicional p→ q sabemos que aconclusão q é verdade.

Exercício 42,43: Escrevam o Lema 2 e a Proposição 3 no formato decorolários e demonstrem os corolários usando vacuidade.


Introdução a DemonstraçãoTipos de Provas:

2) Provas Indiretas: Uma prova por contradição não prova um resultadodiretamente. Então, é um tipo de prova indireta.

• Provas por Contradição: Como a declaração r ∧ ¬r é sempre umacontradição, podemos provar que uma proposição p é verdadeira sepudermos mostrar que ¬p→ (r ∧ ¬r) é verdadeiro para algumaproposição r.Prova do Teorema 6 por contradição:Supomos por contradição que não existam quatro dias nos 22 dias quecaiam no mesma dia da semana(¬q). Então deve existir no máximo trêsdias que caim no mesmo dia da semana. Como uma semana tem 7 dias e3× 7 = 21, isso significa que deve existir 21 dias, o que contraidiz o fatode termos 22 dias. Isso significa p ∧ ¬p, que sabemos que sempre é umacontradição. Portanto o teorema é válido e existe no mínimo 4 diasdentro de 22 dias que caiam no mesmoa dia da semana.

Exercício 44,45: Usando prova por contradição, demonstrem o Teorema 5 eProposição 3.



Axiomas para Conjunto de Inteiros Positivos

• Axiom 1: O número 1 é um inteiro positivo.

• Axiom 2: Se n é um inteiro positivo, então n + 1, o sucessor de n,também é um positivo inteiro.

• Axiom 3: Cada inteiro positivo diferente de 1 é o sucessor de um inteiropositivo.

• Propriedade da Boa Ordenação: Todos os subconjuntos não-vaziosdo conjunto de positivos inteiros, tem um elemento menor.

• Axioma de Indução Matemática: Se S é um subconjunto de inteirospositivos tais que 1 ∈ S e para todos os inteiros positivos n se n ∈ S,então n+ 1 ∈ S, então S é o conjunto de todos inteiros positivos.


Introdução a DemonstraçãoProva por Indução MatemáticaPara provar que P(n) é verdadeira para todos inteiros positivos n, onde P(n) é umafunção proposicional, completamos dois passos:PASSO BÁSICO: Verificamos que P(1) é verdadeiro.PASSO INDUTIVO: Mostramos que a declaração condicional P (k)→ P (k + 1) éverdadeira para todos os inteiros positivos k.

Exemplos:Teorema*: Se a e b são inteiros positivos com a ≥ b, então an ≥ bn, para n natural.Prova por Indução matemática: Seja P(n): an ≥ bn.PASSO BÁSICO: P(1): a1 ≥ b1 é valido pelo hipôtese do Teorema.PASSO INDUTIVO: Assumindo que P(k): ak ≥ bk, é verdadeira, mostramos queimplica P(k+1): ak+1 ≥ bk+1. Isso acontece pois: ak+1 = ak a ≥ bk a ≥ bk b = bk+1.Portanto por indução matemática, o Teorema é válido para todo n natural.Exercício 46: Mostre que 1 + 2 + · · ·+ n = n(n+1)

2.

Exercício 47: Mostre que 2n < n! pra n ∈ Z+, com n ≥ 4.Exercício 48: Prove a seguinte progressão geométrica, onde r 6= 0.

n∑j=0

a rj := a + ar + ar2 + ..+ arn =a rn+1 − a

r − 1.


Outros Métodos de Demonstração

Demostração por CasosDef:(Números prímos) São os números naturais que têm apenas dois divisoresdiferentes: o 1 e ele mesmo.TEOREMA FUNDAMENTAL DA ARITMÉTICA: Cada inteiro n > 1,pode ser escrito como primo ou o produto de dois ou mais primos.Prova por Indução: Seja P(n) a proposição de que n é primo ou pode ser escritocomo o produto de primos.PASSO BÁSICO: P(2) é verdade, porque 2 pela definição é primo.PASSO INDUTIVO: Assume que P(j) é verdadeiro para todos inteiros j com2 ≤ j ≤ k e deve ser mostrado que P(k + 1) é verdadeiro. Pode acontecer dois casos:

• k + 1 é primo: então trivialmente p(k+1) é verdadeira.

• k + 1 é composto: então existe no mínimo a,b naturais, 2 ≤ a ≤ b < k tal quek + 1 = a b. Usando hipótese de passo indutivo, então a e b são primos oupodem ser escritos como produto de primos. Isso comprova que k + 1 éproduto de números primos. Então por indução matemática o Teorema éválido para todo n natural.

Exercício 49: Demonstrem o Lema: Para x, y ∈ R, então |xy| = |x||y|.


Outros Métodos de DemonstraçãoTEOREMA DE EUCLIDEs:Há infinitos números primos.Prova por Contradição e por casos: Assumimos que não existem infinitosnúmeros primos, ou seja, existem finitos números primos p1 p2 · · · , pk. SejaQ = p1 p2 .. pk + 1 pelo Teorema fundamental da aritmética, então acontecedois casos:

• Q é primo: então existe mais do que k primos o que é uma contradição, ahipótese.

• Q é composto por números primos. Mas Q é diviśivel por nenhum pj(por causa de +1), então deve existir outro primo fora de n1, n2, · · · , nk.Isso é uma contradição de novo. Então por contradição o teorema évalido e existe infinitos números primos.

CONJECTURA DE GOLDBACH-1742- ?(Exercício 50!)Todo inteiro ímpar n, n> 5, é a soma de três primos. Euler mostrou que aconjectura equivale à que todo inteiro par n, n> 2, é a soma de dois primos.


Outros Métodos de Demonstração

Teoremas tipo EquivalenciaPara provar um teorema que é uma declaração bicondicional, isto é, umadeclaração da forma p↔ q, mostramos que p→ q e q → p são ambosverdadeiros.Prova de Teorema 7:Teorema 6 é valido se acontece que p→ q ∧ q → p onde p : inteiro n é ímpar eq : n2 é ímpar. Parte p→ q já foi provado como Lema 2. Parte q → p éverdadeiro por contradição.Corolário 2.1: se n2 é par então n é par.(prova: é contrapositivo do Lemma 2.)

Obs: Às vezes, um teorema afirma que várias proposições são equivalentes.Tal teorema afirma que proposições p1, p2, ..., pn são equivalentes. Isso podeser escrito como,p1 ↔ p2 ↔ · · · ↔ pn ≡ (p1 → p2) ∧ (p2 → p3) ∧ · · · ∧ (pn → p1.)Exemplo: Demonstramos o Teorema 8.Exercícios do Livro: seção 1.6: 1 à 11-17,18,20,21,23,24,26,27,28,33,41,42


Erros em DemonstraçõesExistem muitos erros comuns cometidos na construção de provas matemáticas.Entre os erros mais comuns estão os erros aritméticos e de álgebra básico. Mesmomatemáticos profissionais cometem esses erros. Sempre que você usar esses cálculos,você deve verificá-los com cuidado sempre que possível.Exemplo: O que esta errado com a famosa demonstração de "2=1"?Prova:

Exemplo: O que esta errado com a demonstração do Teorema: se n2 é positivo,então n é positivo.Prova: Suponha que n2 seja positivo. Porque a declaração condicional "Se n épositivo, então n2 é positivo ” é verdade, podemos concluir que n é positivo.


Documents

Noções de lógica matemática - UFV 131/2019-I/slides/logica Matematic… · "Matemática é a arte de dar o mesmo nome para coisas diferentes "(Henri Poincar