Suponha que existam duas fórmulas, X e Y. Essas fórmulas serão conhecidas como equivalência se X ↔ Y for uma tautologia. Se duas fórmulas X ↔ Y são uma tautologia, então também podemos escrevê-la como X ⇔ Y, e podemos ler esta relação como X é equivalência a Y.
Nota: Existem alguns pontos que devemos ter em mente durante a equivalência linear da fórmula, que são descritos a seguir:
- ⇔ é usado para indicar apenas um símbolo, mas não é conectivo.
- O valor verdade de X e Y será sempre igual se X ↔ Y for uma tautologia.
- A relação de equivalência contém duas propriedades, ou seja, simétrica e transitiva.
Método 1: Método da tabela verdade:
Neste método, construiremos as tabelas verdade de qualquer fórmula de duas afirmações e depois verificaremos se essas afirmações são equivalentes.
Exemplo 1: Neste exemplo, temos que provar X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Solução: A tabela verdade de X ∨ Y ⇔ ¬(¬X ∧ ¬Y) é descrita a seguir:
| X | E | X ∨ Y | ¬X | ¬E | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | T | F | T | F | T | T |
| F | T | T | T | F | F | T | T |
| F | F | F | T | T | T | F | T |
Como podemos ver que X ∨ Y e ¬(¬X ∧ ¬Y) é uma tautologia. Portanto, X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Exemplo 2: Neste exemplo, temos que provar (X → Y) ⇔ (¬X ∨ Y).
Solução: A tabela verdade de (X → Y) ⇔ (¬X ∨ Y) é descrita a seguir:
| X | E | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Como podemos ver que X → Y e (¬X ∨ Y) são uma tautologia. Portanto (X → Y) ⇔ (¬X ∨ Y)
Fórmula de equivalência:
Existem várias leis que são usadas para provar a fórmula de equivalência, que é descrita a seguir:
Lei idempotente: Se houver uma fórmula de instrução, ela terá as seguintes propriedades:
X ∨ X ⇔ X X ∧ X ⇔ X
Direito associativo: Se houver três fórmulas de instrução, ela terá as seguintes propriedades:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Lei comutativa: Se houver duas fórmulas de instrução, ela terá as seguintes propriedades:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Lei distributiva: Se houver três fórmulas de instrução, ela terá as seguintes propriedades:
ddl versus dml
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Lei de identidade: Se houver uma fórmula de instrução, ela terá as seguintes propriedades:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Lei complementar: Se houver uma fórmula de instrução, ela terá as seguintes propriedades:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Lei de Absorção: Se houver duas fórmulas de instrução, ela terá as seguintes propriedades:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Da Lei de Morgan: Se houver duas fórmulas de instrução, ela terá as seguintes propriedades:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Método 2: Processo de Substituição
Neste método, assumiremos uma fórmula A: X → (Y → Z). A fórmula Y → Z pode ser conhecida como parte da fórmula. Se substituirmos esta parte da fórmula, ou seja, Y → Z, pela ajuda da fórmula de equivalência ¬Y ∨ Z em A, obteremos outra fórmula, ou seja, B : X → (¬Y ∨ Z). É um processo fácil verificar se as fórmulas A e B fornecidas são equivalentes entre si ou não. Com a ajuda do processo de substituição, podemos obter B de A.
Exemplo 1: Neste exemplo, temos que provar que {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Solução: Aqui, pegaremos a parte esquerda e tentaremos pegar a parte direita.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Agora usaremos a lei associativa assim:
⇔ (¬X ∨ ¬Y) ∨ Z
Agora usaremos a lei de De Morgan assim:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Daí provado
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Exemplo 2: Neste exemplo, temos que provar que {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Solução: Aqui, pegaremos a parte esquerda e tentaremos pegar a parte direita.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Daí provado
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Exemplo 3: Neste exemplo, temos que provar que X → (Y → X) ⇔ ¬X → (X → Y).
Solução: Aqui, pegaremos a parte esquerda e tentaremos pegar a parte direita.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Daí provado
X → (Y → X) ⇔ ¬X → (X → Y)
Exemplo 4: Neste exemplo, temos que provar que (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Solução: Aqui, pegaremos a parte esquerda e tentaremos pegar a parte direita.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Agora usaremos as leis Associativas e Distributivas assim:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Agora usaremos a lei de De Morgan assim:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Agora usaremos a lei distributiva assim:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Daí provado
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Exemplo 5: Neste exemplo, temos que mostrar que ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) é uma tautologia.
Solução: Aqui vamos pegar pequenas peças e resolvê-las.
Primeiro, usaremos a lei de De Morgan e obteremos o seguinte:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Portanto,
c++ converte int em string
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Também
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Por isso
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Por isso
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Portanto, podemos dizer que a fórmula dada é uma tautologia.
Exemplo 6: Neste exemplo, temos que mostrar que (X ∧ Y) → (X ∨ Y) é uma tautologia.
Solução: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Agora usaremos a lei de De Morgan assim:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Agora usaremos a lei associativa e a lei comutativa assim:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Agora usaremos a lei da negação assim:
⇔ (T ∨ T) ⇔ T
Portanto, podemos dizer que a fórmula dada é uma tautologia.
Exemplo 7: Neste exemplo, temos que escrever a negação de algumas afirmações, que são descritas a seguir:
- Casar concluirá seus estudos ou aceitará a carta de adesão da Empresa XYZ.
- Harry irá dar um passeio ou correr amanhã.
- Se eu tirar boas notas, meu primo ficará com ciúmes.
Solução: Primeiro, resolveremos a primeira afirmação assim:
1. Suponha X: Casar completará seus estudos.
Y: Aceite a carta de adesão da Empresa XYZ.
Podemos usar a seguinte forma simbólica para expressar esta afirmação:
X ∨ Y
A negação de X ∨ Y é descrita a seguir:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Em conclusão, a negação da afirmação dada será:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Suponha X: Harry vai dar um passeio
Y: Harry irá correr amanhã
Podemos usar a seguinte forma simbólica para expressar esta afirmação:
X ∨ Y
A negação de X ∨ Y é descrita a seguir:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Em conclusão, a negação da afirmação dada será:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Suponha X: Se eu tirar boas notas.
Y: Meu primo vai ficar com ciúmes.
Podemos usar a seguinte forma simbólica para expressar esta afirmação:
X → Y
A negação de X → Y é descrita a seguir:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Em conclusão, a negação da afirmação dada será:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Exemplo 8: Neste exemplo, temos que escrever a negação de algumas afirmações com a ajuda da lei de De Morgan. Essas declarações são descritas a seguir:
- Preciso de um conjunto de diamantes que vale um anel de ouro.
- Você consegue um bom emprego ou não consegue um bom parceiro.
- Dou muito trabalho e não aguento.
- Meu cachorro viaja ou faz bagunça na casa.
Solução: A negação de todas as afirmações com a ajuda da lei de De Morgan é descrita uma por uma assim:
- Não preciso de um conjunto de diamantes ou não valho um anel de ouro.
- Você não conseguirá um bom emprego e conseguirá um bom parceiro.
- Eu não dou muito trabalho ou posso lidar com isso.
- Meu cachorro não viaja e não faz bagunça na casa.
Exemplo 9: Neste exemplo, temos algumas afirmações e temos que escrever a negação dessas afirmações. As declarações são descritas a seguir:
- Se estiver chovendo, o plano de ir à praia é cancelado.
- Se eu estudar muito, terei boas notas no exame.
- Se eu for a uma festa tarde da noite, serei punido por meu pai.
- Se você não quiser falar comigo, terá que bloquear meu número.
Solução: A negação de todas as afirmações é descrita uma por uma assim:
- Se o plano de ir à praia for cancelado, então está chovendo.
- Se eu tirar boas notas no exame, estudo muito.
- Se eu for punido por meu pai, então irei a uma festa tarde da noite.
- Se você tiver que bloquear meu número, não vai querer falar comigo.
Exemplo 10: Neste exemplo, temos que verificar se (X → Y) → Z e X → (Y → Z) são logicamente equivalentes ou não. Temos de justificar a nossa resposta com a ajuda de tabelas verdade e com a ajuda de regras de lógica para simplificar ambas as expressões.
Solução: Primeiro, usaremos o método 1 para verificar se (X → Y) → Z e X → (Y → Z) são logicamente equivalentes, que é descrito a seguir:
programa c para matriz bidimensional
Método 1: Aqui, assumiremos o seguinte:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
E
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Método 2: Agora, usaremos o segundo método. Neste método, usaremos a tabela verdade.
| X | E | COM | X → Y | (X → Y) → Z | Y → Z | X → (Y → Z) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | F | F | T |
| F | F | T | T | T | T | T |
| F | F | F | T | F | T | T |
Nesta tabela verdade, podemos ver que as colunas de (X → Y) → Z e X → (Y → Z) não contêm valores idênticos.