Upload
dalila-carreiro-teixeira
View
215
Download
1
Embed Size (px)
Citation preview
Tema 1 – Lógica e Teoria dos Conjuntos
1. Proposições e valores lógicos
. Um termo ou designação é uma expressão que nomeia ou designa um ente.
. Uma proposição é toda a expressão p susceptível de ser verdadeira ou falsa.
. O universo dos valores lógicos é {V, F} correspondente a verdade ou falsidade.
. Duas proposições p e q dizem-se equivalentes quando e apenas quando p e q têm o mesmo valor lógico e escreve-se: p qUma proposição não pode ser simultaneamente verdadeira e falsa,
Princípio da não contradiçãoUma proposição é verdadeira ou a sua negação é verdadeira,
Princípio do terceiro excluído
Consideremos, por exemplo, a proposição:A Maria vai à praia se e só se acordar cedo. Esta proposição é a composta das proposições:
A Maria vai à praia. A Maria acorda cedo.
A equivalência p q entre duas proposições p e q é uma nova proposição que é verdadeira apenas no caso de p e q terem ambas o mesmo valor lógico.
EquivalênciaTabela de verdade
Negação
Consideremos, por exemplo, a proposição:
A Maria gosta de bolos. e a proposição:A Maria não gosta de bolos.
A segunda proposição nega o que afirma a primeira.
Tabela de verdade
A negação de uma proposição é uma outra proposição que é verdadeira se a primeira proposição for falsa e é falsa se a primeira for verdadeira.
A conjunção p Ʌ q de duas proposições p e q é uma proposição que é verdadeira se, e só se, p e q forem ambas verdadeiras.
Tabela de verdadeConsideremos, por exemplo, a proposição:A Maria gosta de bolos e o Manuel gosta de sandes.que resulta da ligação das proposições:
A Maria gosta de bolos. O Manuel gosta de
sandes.pela palavra e.
Conjunção
Consideremos, por exemplo, a proposição:A Maria gosta de bolos ou a Maria gosta de sandes.que resulta da ligação das proposições:
A Maria gosta de bolos. A Maria gosta de sandes.
pela palavra ou.A disjunção p V q de duas proposições p e q é uma proposição que é falsa se, e só se, p e q forem ambas falsas.
DisjunçãoTabela de verdade
Consideremos, por exemplo, a proposição:Se a Maria acordar cedo, então vai à praia. Esta proposição é a composta das proposições:
A Maria acorda cedo. A Maria vai à praia.
A implicação p q entre duas proposições p e q é uma nova proposição que é falsa se, e só se, o antecedente p é verdadeiro e o consequente q é falso.
Tabela de verdade
Implicação
2. Operações lógicas sobre proposições (Quadro Resumo)
. Uma tautologia é uma proposição que é verdadeira, independentemente dos valores lógicos das proposições elementares que a constituem.
. Uma contradição é uma proposição que é falsa, independentemente dos valores lógicos das proposições elementares que a constituem.
Tabelas de verdade
Como construir tabelas de verdade?As tabelas deverão ter tantas linhas quantas as necessárias para contemplar todas as possibilidades de sequência de valores lógicos para as proposições operandas ( portanto 2n linhas, sendo n o número de proposições operandas).
Para demonstrar propriedades das operações com proposições , podem usar-se diferentes técnicas tais como: tabelas de verdade, argumentos que envolvam apenas as definições das operações, ou ainda, recorrendo a propriedades já verificadas.
Exemplo ( Número de proposições operandas: 2 → 22 linhas)
Nas duas primeiras colunas, colocamos as combinações possíveis para os valores lógicos das proposições operandas p e q .Para preencher a coluna relativa a cada operação, utilizamos o conhecimento da tabela de verdade dessa operação e os valores lógicos de p e q constantes em cada linha.Neste exemplo, a identidade dos valores lógicos apresentados nas 3ª e 4ª colunas demonstra que a disjunção é comutativa.
Exemplo ( Número de proposições operandas : 3 → 23 linhas)
A identidade dos valores lógicos apresentados nas 6ª e 7ª colunas demonstra a equivalência:
Propriedades da conjunção e disjunção:
Dadas as proposições p, q e r:
. propriedade comutativa:
. propriedade associativa :
. propriedade distributiva da conjunção em relação à disjunção:
. propriedade distributiva da disjunção em relação à conjunção:
. elemento neutro da conjunção:
. elemento neutro da disjunção:
. elemento absorvente da conjunção:
. elemento absorvente da disjunção:
. idempotência da conjunção:
. idempotência da disjunção:
. Primeiras Leis de De Morgan:
Propriedades da implicação.
Dadas as proposições p, q e r:
. Relação da implicação com a disjunção:
. Negação da implicação:
. Princípio da dupla implicação:
. Implicação contrarrecíproca (Lei da conversão):
. Implicação é transitiva:
Observação:
Em qualquer sequência de operações lógicas, a menos que se utilizem parênteses, devem respeitar-se as seguintes prioridades: primeiro negação, seguindo-se as conjunções e as disjunções pela ordem que aparecem e, por fim, implicações e equivalências pela ordem que aparecem.
Nota:
Dada a implicação , diz-se que:
. é a implicação recíproca
. é a implicação contrária
. é a implicação contrarrecíproca
3. Condições e conjuntos
. Uma expressão designatória é uma expressão p(x) envolvendo uma variável x tal que, substituindo x por um objeto a, se obtém uma designação p(a).
. Uma expressão proposicional ou condição é uma expressão p(x) envolvendo uma variável x, tal que, substituindo x por um objeto a, se obtém uma proposição p(a).
. Domínio é o conjunto de valores que uma variável de uma expressão designatória ou de uma condição toma.
. Quantificador universal: (lê-se “para todo/todos”)
A proposição é verdadeira quando e apenas quando se obtém uma proposição verdadeira para todos os valores de x.
. Quantificador existencial: (lê-se “existe pelo menos um”)
Dada uma condição p(x), a proposição é verdadeira quando e apenas quando se obtém uma proposição verdadeira para pelo menos um valor de x.
Classificação de condições
A condição p(x) é universal se e só se a proposição é verdadeira.
A condição p(x) é possível se e só se é verdadeira.
Se uma condição não é possível, então diz-se impossível.
Propriedades
Sejam c(x) uma condição qualquer, u(x) uma condição universal e i(x) uma condição impossível:
Segundas Leis de De Morgan
Para uma condição c(x):
Classificação de condições num conjunto U
. Dada uma condição p(x) e um conjunto U, . Se a proposição for verdadeira, p(x) designa-se por condição universal em U.
. Dada uma condição p(x) e um conjunto U, Se a proposição for verdadeira, p(x) designa-se por condição possível em U e, caso contrário, por condição impossível em U.
Negação de uma condição
A negação de uma condição universal é uma condição impossível.
A negação de uma condição impossível é uma condição universal.
Dada uma condição p(x) e um conjunto U:
Negação de uma implicação:
Dadas as condições p(x) e q(x): Conceito de condição suficiente e condição necessária
Estar a chover Haver nuvens(condição suficiente) (condição necessária)
Conjuntos e condições
. Igualdade de conjuntos: Dados dois conjuntos A e B diz-se A = B se e somente se ∀𝑥 ,𝑥 ∈𝐴 ⟺𝑥 ∈𝐵.
. Dada uma condição p(x) e um conjunto U, ሼ𝑥∈𝑈∶ 𝑝(𝑥)ሽ⟺ሼ𝑥:𝑥∈𝑈∧𝑝(𝑥)ሽ designa-se por conjunto-solução de p(x) em U.
. Reunião (ou união) de conjuntos: Dados os conjuntos A e B, o conjunto-reunião (ou união) de A e B representa-se por 𝐴∪𝐵= ሼ𝑥∶ 𝑥 ∈𝐴 ∨𝑥 ∈𝐵ሽ. . Interseção de conjuntos: Dados os conjuntos A e B, o conjunto-interseção de A e B representa-se por 𝐴∩𝐵= ሼ𝑥∶ 𝑥 ∈𝐴 ∧𝑥 ∈𝐵ሽ.
Condição a(x) b(x) a(x) ∨ b(x) a(x) ∧ b(x) Conjunto-solução A B A ∪ B A ∩ B
. Inclusão de conjuntos: Dados os conjuntos A e B, diz-se que A está contido em B quando ∀ 𝑥 ∈𝐴 ⇒𝑥 ∈𝐵 e representa-se por 𝐴⊂ 𝐵. Neste caso, A é um subconjunto de B ou uma parte de B.
. Diferença entre conjuntos: Dados os conjuntos A e B designa-se por diferença entre A e B o conjunto ሼ𝑥∶ 𝑥 ∈𝐴 ∧𝑥 ∉𝐵ሽ e representa-se por A\B.
Se B ⊂ 𝐴, então A\B = 𝐵ത onde 𝐵ത se designa por complementar de B em A
Condição a(x) b(x) ∼a(x) a(x) ∧∼ b(x) Conjunto-solução A B 𝐴ҧ A ∩ 𝐵ത =A\B
Princípio da dupla inclusão: Dados os conjuntos A e B, diz-se que A = B se e somente se 𝐴⊂ 𝐵 e 𝐵⊂ 𝐴.
Condição a(x) b(x) a(x) ⇒ b(x) b(x) ⇒ a(x) a(x) ⟺ b(x)
Conjunto-solução A B
A ⊂ B
B ⊂ A
A = B
Demonstração de equivalências por dupla inclusão Dadas as condições p(x) e q(x), ∀ 𝑥,𝑝ሺ𝑥ሻ⇔ 𝑞ሺ𝑥ሻ é 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎 ∀𝑥,(𝑝ሺ𝑥ሻ⇒𝑞ሺ𝑥ሻ ∧𝑞ሺ𝑥ሻ⟹𝑝ሺ𝑥ሻ)
Exemplo:
Queremos mostrar que: ∀ 𝑥 ∈𝐼𝑅, 𝑥2 > 4 ⟺𝑥> 2 ∨𝑥< −2, que é equivalente mostrar que (𝑥2 > 4 ⟹𝑥> 2 ∨𝑥< −2) e (𝑥> 2 ∨𝑥< −2 ⟹𝑥2 > 4)
1.ª parte:
𝑥2 − 4 > 0 ⟹ሺ𝑥− 2ሻሺ𝑥+ 2ሻ> 0 ⟹ሺ 𝑥− 2 > 0 ∧𝑥+ 2 > 0ሻ∨(𝑥− 2 < 0 ∧𝑥+ 2 < 0) ⟹ ሺ 𝑥> 2 ∧𝑥> −2 ሻ∨ሺ𝑥< 2 ∧𝑥< −2ሻ⟹𝑥> 2 ∨𝑥< −2
2.ª parte:
𝑥> 2 ∨𝑥< −2 ⟹ȁ.𝑥ȁ.> 2 ⟹𝑥2 > 4
Da dupla implicação resulta a equivalência.
Negação de uma implicação universal Dadas as condições p(x) e q(x) a negação da proposição ∀ 𝑥 , 𝑝ሺ𝑥ሻ ⇒𝑞(𝑥) é equivalente à proposição ∃ 𝑥∶ 𝑝ሺ𝑥ሻ∧ ∼ 𝑞(𝑥), isto é, a proposição ∀ 𝑥 , 𝑝ሺ𝑥ሻ ⇒𝑞(𝑥) é falsa se, e somente se, existir a tal que p(a) é verdadeira e q(a) é falsa.
Exemplo:
A proposição “Qualquer número primo é impar” é falsa pois a sua negação é equivalente “Existe um número primo que não é ímpar”, que é verdadeira.
De facto, existe um número que é primo e não é ímpar, o número 2.
Demonstração por contrarrecíproco Dadas as condições p(x) e q(x), a proposição ∀ 𝑥 , 𝑝ሺ𝑥ሻ ⇒𝑞(𝑥) é equivalente a ∀ 𝑥 , ∼ 𝑞ሺ𝑥ሻ ⇒∼ 𝑝(𝑥).
Exemplo:
Queremos mostrar que a proposição ∀ 𝑥 ∈𝐼𝑅,𝑥2 < 1 ⟹𝑥< 1
Vamos utilizar o contrarrecíproco, isto é, ∀ 𝑥 ∈𝐼𝑅, ~ሺ𝑥< 1ሻ⟹~(𝑥2 < 1) Ou seja, ∀ 𝑥 ∈𝐼𝑅, 𝑥≥ 1 ⟹𝑥2 ≥ 1
Seja 𝑥≥ 1, Se 𝑥= 1 então 𝑥2 = 1
Se 𝑥> 1 então 𝑥2 > 1, pois x > 1 e x > 0 ⟹ 𝑥× 𝑥> 1 × 𝑥, ou seja, 𝑥2 > 𝑥
Como x > 1, por transitividade, vem 𝑥2 > 1