Matemática Discreta - Lógica Proposicional
As regras da lógica matemática especificam métodos de raciocínio de afirmações matemáticas. O filósofo grego Aristóteles foi o pioneiro do raciocínio lógico. O raciocínio lógico fornece a base teórica para muitas áreas da matemática e, consequentemente, da ciência da computação. Tem muitas aplicações práticas em ciência da computação como design de máquinas de computação, inteligência artificial, definição de estruturas de dados para linguagens de programação, etc.
Propositional Logicpreocupa-se com declarações às quais os valores de verdade, “verdadeiro” e “falso”, podem ser atribuídos. O objetivo é analisar essas afirmações individualmente ou de forma composta.
Lógica Preposicional - Definição
Uma proposição é uma coleção de declarações declarativas que têm um valor de verdade "verdadeiro" ou um valor de verdade "falso". Uma proposição consiste em variáveis proposicionais e conectivos. Denotamos as variáveis proposicionais por letras maiúsculas (A, B, etc). Os conectivos conectam as variáveis proposicionais.
Alguns exemplos de proposições são fornecidos abaixo -
- "Homem é Mortal", retorna o valor de verdade “VERDADEIRO”
- "12 + 9 = 3 - 2", retorna o valor verdadeiro “FALSO”
O seguinte não é uma proposição -
"A é menor que 2". É porque, a menos que forneçamos um valor específico de A, não podemos dizer se a afirmação é verdadeira ou falsa.
Conectivos
Na lógica proposicional geralmente usamos cinco conectivos que são -
OU ($ \ lor $)
AND ($ \ land $)
Negação / NÃO ($ \ lnot $)
Implicação / se-então ($ \ rightarrow $)
Se e somente se ($ \ Leftrightarrow $).
OR ($\lor$) - A operação OR de duas proposições A e B (escritas como $ A \ lor B $) é verdadeira se pelo menos qualquer uma das variáveis proposicionais A ou B for verdadeira.
A tabela de verdade é a seguinte -
| UMA | B | A ∨ B |
|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro |
| Verdadeiro | Falso | Verdadeiro |
| Falso | Verdadeiro | Verdadeiro |
| Falso | Falso | Falso |
AND ($\land$) - A operação AND de duas proposições A e B (escritas como $ A \ land B $) é verdadeira se ambas as variáveis proposicionais A e B são verdadeiras.
A tabela de verdade é a seguinte -
| UMA | B | A ∧ B |
|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro |
| Verdadeiro | Falso | Falso |
| Falso | Verdadeiro | Falso |
| Falso | Falso | Falso |
Negation ($\lnot$) - A negação de uma proposição A (escrita como $ \ lnot A $) é falsa quando A é verdadeira e é verdadeira quando A é falsa.
A tabela de verdade é a seguinte -
| UMA | ¬ A |
|---|---|
| Verdadeiro | Falso |
| Falso | Verdadeiro |
Implication / if-then ($\rightarrow$)- Uma implicação $ A \ rightarrow B $ é a proposição “se A, então B”. É falso se A for verdadeiro e B for falso. Os demais casos são verdadeiros.
A tabela de verdade é a seguinte -
| UMA | B | A → B |
|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro |
| Verdadeiro | Falso | Falso |
| Falso | Verdadeiro | Verdadeiro |
| Falso | Falso | Verdadeiro |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ é um conectivo lógico bi-condicional que é verdadeiro quando peq são iguais, ou seja, ambos são falsos ou ambos são verdadeiros.
A tabela de verdade é a seguinte -
| UMA | B | A ⇔ B |
|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro |
| Verdadeiro | Falso | Falso |
| Falso | Verdadeiro | Falso |
| Falso | Falso | Verdadeiro |
Tautologias
Uma tautologia é uma fórmula que é sempre verdadeira para todos os valores de suas variáveis proposicionais.
Example - Prove que $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ é uma tautologia
A tabela de verdade é a seguinte -
| UMA | B | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro | Verdadeiro | Verdadeiro |
| Verdadeiro | Falso | Falso | Falso | Verdadeiro |
| Falso | Verdadeiro | Verdadeiro | Falso | Verdadeiro |
| Falso | Falso | Verdadeiro | Falso | Verdadeiro |
Como podemos ver, cada valor de $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ é "Verdadeiro", é uma tautologia.
Contradições
Uma Contradição é uma fórmula que é sempre falsa para cada valor de suas variáveis proposicionais.
Example - Prove $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ é uma contradição
A tabela de verdade é a seguinte -
| UMA | B | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro | Falso | Falso | Falso | Falso |
| Verdadeiro | Falso | Verdadeiro | Falso | Verdadeiro | Falso | Falso |
| Falso | Verdadeiro | Verdadeiro | Verdadeiro | Falso | Falso | Falso |
| Falso | Falso | Falso | Verdadeiro | Verdadeiro | Verdadeiro | Falso |
Como podemos ver cada valor de $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ é “False”, é uma contradição.
Contingência
Uma contingência é uma fórmula que possui alguns valores verdadeiros e falsos para cada valor de suas variáveis proposicionais.
Example - Prove $ (A \ lor B) \ land (\ lnot A) $ a contingência
A tabela de verdade é a seguinte -
| UMA | B | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro | Falso | Falso |
| Verdadeiro | Falso | Verdadeiro | Falso | Falso |
| Falso | Verdadeiro | Verdadeiro | Verdadeiro | Verdadeiro |
| Falso | Falso | Falso | Verdadeiro | Falso |
Como podemos ver, cada valor de $ (A \ lor B) \ land (\ lnot A) $ tem tanto “Verdadeiro” quanto “Falso”, é uma contingência.
Equivalências proposicionais
Duas declarações X e Y são logicamente equivalentes se qualquer uma das seguintes condições for mantida -
As tabelas de verdade de cada afirmação têm os mesmos valores de verdade.
A declaração bi-condicional $ X \ Leftrightarrow Y $ é uma tautologia.
Example - Prove que $ \ lnot (A \ lor B) e \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ são equivalentes
Teste pelo 1º método (tabela de verdade de correspondência)
| UMA | B | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Verdadeiro | Verdadeiro | Verdadeiro | Falso | Falso | Falso | Falso |
| Verdadeiro | Falso | Verdadeiro | Falso | Falso | Verdadeiro | Falso |
| Falso | Verdadeiro | Verdadeiro | Falso | Verdadeiro | Falso | Falso |
| Falso | Falso | Falso | Verdadeiro | Verdadeiro | Verdadeiro | Verdadeiro |
Aqui, podemos ver que os valores verdadeiros de $ \ lnot (A \ lor B) e \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ são os mesmos, portanto, as declarações são equivalentes.
Teste pelo 2º método (Bi-condicionalidade)
| UMA | B | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Verdadeiro | Verdadeiro | Falso | Falso | Verdadeiro |
| Verdadeiro | Falso | Falso | Falso | Verdadeiro |
| Falso | Verdadeiro | Falso | Falso | Verdadeiro |
| Falso | Falso | Verdadeiro | Verdadeiro | Verdadeiro |
Como $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ é uma tautologia, as afirmações são equivalentes.
Inverso, Converse e Contra-positivo
Implicação / if-then $ (\ rightarrow) $ também é chamada de declaração condicional. Tem duas partes -
- Hipótese, p
- Conclusão, q
Conforme mencionado anteriormente, é denotado como $ p \ rightarrow q $.
Example of Conditional Statement- “Se você fizer sua lição de casa, você não será punido.” Aqui, "você faz sua lição de casa" é a hipótese, p, e "você não será punido" é a conclusão, q.
Inverse- O inverso da afirmação condicional é a negação da hipótese e da conclusão. Se a declaração for “Se p, então q”, o inverso será “Se não p, então não q”. Assim, o inverso de $ p \ rightarrow q $ é $ \ lnot p \ rightarrow \ lnot q $.
Example - O inverso de “Se você fizer sua lição de casa, não será punido” é “Se você não fizer sua lição de casa, você será punido”.
Converse- O inverso da declaração condicional é calculado trocando a hipótese e a conclusão. Se a declaração for “Se p, então q”, o inverso será “Se q, então p”. O inverso de $ p \ rightarrow q $ é $ q \ rightarrow p $.
Example - O inverso de "Se você fizer sua lição de casa, não será punido" é "Se você não for punido, você faz sua lição de casa".
Contra-positive- O contra-positivo da condicional é calculado trocando a hipótese e a conclusão da declaração inversa. Se a afirmação for “Se p, então q”, o contra-positivo será “Se não q, então não p”. O contra-positivo de $ p \ rightarrow q $ é $ \ lnot q \ rightarrow \ lnot p $.
Example - O Contra-positivo de "Se você fizer sua lição de casa, não será punido" é "Se você for punido, você não fez sua lição de casa".
Princípio da Dualidade
O princípio da dualidade afirma que, para qualquer afirmação verdadeira, a afirmação dual obtida trocando uniões em interseções (e vice-versa) e trocando conjunto universal por conjunto nulo (e vice-versa) também é verdadeira. Se dual de qualquer afirmação for a própria afirmação, é ditoself-dual declaração.
Example - O dual de $ (A \ cap B) \ xícara C $ é $ (A \ xícara B) \ cap C $
Formas normais
Podemos converter qualquer proposição em duas formas normais -
- Forma normal conjuntiva
- Forma normal disjuntiva
Forma normal conjuntiva
Um enunciado composto está na forma normal conjuntiva se for obtido operando AND entre variáveis (negação de variáveis incluídas) conectadas com ORs. Em termos de operações de conjunto, é um enunciado composto obtido por Intersecção entre variáveis ligadas aos Sindicatos.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ xícara Q) \ cap (Q \ xícara R) $
Forma normal disjuntiva
Uma declaração composta está na forma normal disjuntiva se for obtida operando OR entre variáveis (negação de variáveis incluídas) conectadas com ANDs. Em termos de operações de conjunto, é uma declaração composta obtida por Union entre variáveis conectadas com Intersecções.
Examples
$ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $
$ (P \ cap Q) \ xícara (Q \ cap R) $