Tema 1 – Lógica e Teoria dos Conjuntos Uma proposição não pode ser simultaneamente verdadeira...

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