Matemática Discreta - Aula 03

[!info] Disclaimer Eu não pude participar da aula presencialmente e pode ser que o conteúdo ministrado em aula esteja diferente (com mais ou menos conteúdo) do que as minhas anotações, tendo em vista que estas estão somente de acordo com os materiais disponibilizados

Lógica Clássica

A lógica Clássica trabalha com sentenças ou conclusões que possuem uma forma de classificação bem específica, dentro de um sistema dicotômico.

Muitas demonstrações em matemática e em algoritmos utilizam de expressões lógicas como: $$ SE \ \ x \ \ ENTÃO \ \ y \ \ \text{“ou”} \ \ SE \ \ x_1 \ \ E \ \ x_2\ \ ENTÃO \ \ y_1 \ \ OU \ \ y_2 $$ Portanto, é necessário conhecer os casos nos quais essas expressões têm valor FALSO ou VERDADEIRO.

[!faq] Dicotômico Podem somente ter uma de duas possibilidades → Verdadeiro e Falso.

Princípios da Lógica que regem o raciocínio

Princípio de terceiro excluído

Toda Sentença é verdadeira ou falsa, não existindo contradição. Isto é, não há uma terceira possibilidade.

Princípio da não contradição

Nenhuma sentença é verdadeira e falsa simultaneamente, não existindo outra condição.

A Lógica Proposicional

[!info] Proposição Uma proposição (ou declaração, ou sentença) é uma sentença declarativa que pode ser verdadeira ou falsa, mas não ambos (cf. [[#Princípio da não contradição]])

^0b35a1

As sentenças, em linguagem corrente são classificadas em declarativas(i), interrogativas (ii), imperativas (iii) e exclamativas (iv). A Lógica proposicional se encarregará das primeiras, assim declarando: a proposição é o significado de uma sentença declarativa.

Considere as seguintes proposições:

1. Paris fica na França
2. $1+1=2$
3. $2+2=3$
4. Londres fica na Dinamarca
5. $9<6$
6. $x=2$ é a solução de $x^2=4$
7. Aonde você está indo?
8. Faça seu dever de casa.

No conceito que vimos, apenas os itens 7 e 8 NÃO SÃO PROPOSIÇÕES, ao que os itens 1, 2 e 6 são VERDADEIROS e 3, 4 e 5 são FALSOS.

A Importância da Lógica Proposicional

As diretrizes curriculares do MEC para os cursos de computação e informática (Brasil, 2008) destacam que:

[!quote] Lógica Matemática é uma ferramenta fundamental na definição de conceitos computacionais

E, para algumas matérias, sobretudo de Inteligência Artificial, o texto enfatiza:

[!quote] Como base ao estudo da inteligência artificial são imprescindíveis conhecimentos de lógica matemática.

Assim, a lógica permite definir a noção de teorema. Tal termo pode ser visto, frequentemente na área da computação, como um problema a ser implementado, e sua correspondente demonstração pode ser vista como uma solução computacional → isto é, um algoritmo.

[!quote] PARNAS, David O maior avanço da engenharia de software nos últimos dez anos foram os provadores de teoremas.

Proposições Compostas

Muitas proposições são compostas de subproposições e vários conectivos. Ficou difícil? Vou tentar simplificar. Esse tipo de proposição, chamadas de proposições compostas, é quando contém mais de uma proposição juntas. Conforme os exemplos abaixo:

• Hoje a temperatura está alta e está ventando bastante.
• Rosas são vermelhas e violetas são azuis.
• José é astuto ou estuda todas as noites.
• Não vai chover hoje e vamos para a praia.

Perceba que, se dividirmos as frases em duas onde o conector fique de fora, teremos duas proposições primitivas - isto é, proposições que não podem ser subdivididas em proposições mais simples.

• “Hoje a temperatura está alta” / “está ventando bastante”
• “Rosas são vermelhas” / “violetas são azuis”
• “José é astuto” / “[ele] estuda todas as noites”
• “vai chover hoje” / “vamos para a praia”

Todos os conectores que ficaram de fora das proposições primitivas, são chamados de [[#Operadores Lógicos]]

Operadores Lógicos

Na lógica, um operador lógico (ou conectivo lógico) é um símbolo ou palavra (signo) usado para conectar duas ou mais sentenças de uma maneira gramaticalmente válida.

Negação de uma proposição

Dada qualquer proposição $p$, outra proposição, denominada negação de $p$ pode ser formada escrevendo “não ocorre que…” ou “é falso que…” antes de p, ou, se possível, inserindo um $p$ a palavra não.

Há vários símbolos distintos para representar a negação de uma proposição em lógica. Os mais famosos, no entanto, são o ~$P$, ¬$P$ e $P$´. Todo são equivalentes entre si.

O valor lógico de ~$P$ depende do valor lógico de $P$ como a seguir:

SE $P$ É VERDADE, ENTÃO ~$P$ É FALSO; SE $P$ É FALSO, ENTÃO ~$P$ É VERDADE.

Exemplos:

1. Paris fica na França
2. Não ocorre que Paris fique na França
3. Paris não fica na França
4. $2+2=5$
5. Não ocorre que $2+2=5$
6. $2+2 \neq 5$

[!important] Resposta 2. e 3. São negação de 1. 5. e 6. São negação de 4. Como 1. é VERDADE, 2. e 3. são FALSAS Como 4. é FALSO, 5. e 6. são VERDADES

Outro detalhe é que a negação da negação é uma afirmação → do mesmo modo que dois números negativos multiplicados, resultam em um número positivo, ou naquelas tabelas de Ensino Fundamental: “menos com menos dá mais”. Essa negação da negação, em símbolos ficaria: $($$J) = J$ Exemplo

1. Não ocorre que Paris não fique na França Assim quebramos a proposição da seguinte maneira:

E, OU e OU…OU… nas proposições

Conjunção (E)

Quaisquer duas proposições podem ser combinadas pela palavra “$E$” para formar uma proposição composta chamada de conjunção das proposições originais. Simbolicamente representado por $p \land q$ (lê-se “p e q”) que é uma proposição em si mesma, dependendo do valor lógico de ambas as proposições primitivas, como se segue:

se $p$ e $q$ são VERDADEIRAS, então $p\land q$ é VERDADEIRA; caso contrário $p\land q$ é FALSA.

O valor lógico de uma conjunção pode ser definido pela tabela abaixo. Vemos que, tratando-se de conjunção, a mesma só será verdadeira se ambas as proposições primitivas forem verdadeiras.

Exemplo conforme a tabela:

1. Paris fica na França e $2+2=4$
2. Paris fica na França e $2+2=5$
3. Paris fica na Inglaterra e $2+2=4$
4. Paris fica na Inglaterra e $2+2=5$

Disjunção (OU)

Quaisquer duas proposições podem ser combinadas com a palavra “$OU$” para formar uma proposição composta chamada de disjunção das proposições originais. Simbolicamente representado por $p\lor q$ (lê-se “p ou q”) que é uma proposição em si mesma, dependendo do valor lógico de ambas as proposições primitivas, como se segue:

se $p$ e $q$ são FALSAS, então $p\lor q$ é FALSO; caso contrário $p\lor q$ é VERDADEIRO.

O Valor lógico de uma disjunção pode ser definido pela tabela abaixo. Vemos que a disjunção recebe praticamente o valor contrário de uma conjunção.

Exemplo conforme a tabela:

1. Paris fica na França e $2+2=4$
2. Paris fica na França e $2+2=5$
3. Paris fica na Inglaterra e $2+2=4$
4. Paris fica na Inglaterra e $2+2=5$

Se até este ponto, ainda faltou algo para entender de uma vez por todas, com a tabela abaixo será como a cereja do bolo:

Ou seja, as proposições e os conjuntos se assemelham, não somente na simbologia (“virado pra cima”, “virado pra baixo”) mas também nas próprias associações entre uma preposição e outra ou um conjunto e outro.

Disjunção Exclusiva

No português claro, uma disjunção exclusiva é quando usamos a palavra “ou” duas vezes. “Ou isso, ou aquilo”. Nunca será isso e aquilo juntos, mas “ou um, ou outro”. Simbolicamente é representado por $A \underline\lor B$ (lê-se “OU A OU B”). Note que a diferença entre essa disjunção da primeira é um traço abaixo do símbolo.

1. OU Paris fica na França OU $2+2=4$
2. OU Paris fica na França OU $2+2=5$
3. OU Paris fica na Inglaterra OU $2+2=4$
4. OU Paris fica na Inglaterra OU $2+2=5$

Já que falamos sobre a [[#Relação dos Operadores Lógicos e as Aula 02 MMD001 Conteúdo da Aula - Teoria de Conjuntos Teorias dos Conjuntos|Relação da Lógica Proposicional com os Conjuntos]] podemos dizer que, na Disjunção Exclusiva é como se fizéssemos $A\Delta B=(A-B)\cup (B-A)$, isto é, uma [[Aula 02 MMD001#Diferenças Simétricas|Diferença Simétrica]].

Declarações Condicionais e Bicondicionais

Condicionais (Se… então)

Muitas declarações, sobretudo em matemática e na parte computacional, são da forma “SE $p$ então $q$”. Sentenças deste tipo são chamadas de Condicionais e denotadas por $p \to q$ (lê-se “$p$ implica $q$”, “$p$ apenas se $q$” ou “se $p$, então $q$”). Neste caso, para saber o valor lógico da condicional, confira a tabela abaixo:

Em outras palavras, a condicional $p \to q$ é falsa APENAS quando a primeira proposição primitiva ($p$) é verdadeira e a segunda ($q$) é falsa. Consequentemente, quando a primeira é falsa, a condicional será verdadeira, não importando o valor lógico de $q$.

Observe a tabela abaixo:

Observe as colunas das proposições/sentenças “$p$ implica $q$” e “não $p$ ou $q$”. Elas possuem o mesmo valor, isto é, são idênticas. Consequentemente temos:

$$ p \to q \equiv \text{ ¬ }p \lor q $$

Bicondicionais (Se, e somente se)

Outra declaração comum, em que dizemos (por exemplo) “$Céu \ Azul$ se, e somente se, $sem \ nuvens$”. Esse tipo de declaração é chamado de Bicondicionais e possui a seguinte denotação: $p \rlap{, \gets}\to q$ lendo conforme o exemplo acima. Os valores lógicos provenientes de tal sentença podem ser observados na seguinte tabela:

Assim, toda bicondicional só será verdadeira caso ambas as proposições primitivas ($p$ e $q$) tiverem os mesmos valores lógicos; em caso contrário, será falsa.

Observe a tabela abaixo:

Observe as colunas das proposições/sentenças “$p$ se e somente se $q$” e “não ou $p$ ou $q$”. Elas possuem o mesmo valor, isto é, são idênticas. Consequentemente temos:

$$ p \rlap{, \gets}\to q \equiv \text{ ¬ }(p \underline\lor q) $$

Resumo

[!note] Para gravar na memória Toda vez que utilizamos Conjunção, qualquer proposição primitiva que retorne falso, o resultado da Conjunção é FALSO;

Por sua vez, quando utilizamos a Disjunção, qualquer proposição primitiva que retorne verdadeiro, o resultado da Disjunção será VERDADEIRO;

Por fim, caso haja uma Negação de qualquer proposição, o resultado desta negação é o INVERSO da proposição primitiva;

Caso haja uma negação de negação, o resultado retorna a ser igual a proposição primitiva.

Em caso de Disjunção Exclusiva, qualquer proposição primitiva cujo valor difira do valor da outra proposição, o resultado desta disjunção exclusiva retornará VERDADEIRO; caso contrário, isto é, se os valores das proposições primitivas forem iguais, o resultado da disjunção exclusiva retornará FALSO.

No caso de condicionais, o resultado é FALSO quando a primeira proposição primitiva ($p$) é verdadeira e a segunda difere. Nos demais casos, sempre será VERDADEIRA.

Por fim em bicondicionais, o retorno só será VERDADEIRO caso ambas as proposições sejam iguais. Isto é, pode ser representado pelo inverso (NÃO) Disjunção Exclusiva.

Precedência

É comum que utilizemos parênteses e outros separadores para demarcar a ordem desejada para interpretarmos e realizarmos o “cálculo” lógico dos operadores. No entanto, não descarta-se a possibilidade de uma ordem de precedência dentre os operadores. Sendo uma hierarquia bem estabelecida, indo do topo até a base da seguinte estrutura:

Isto é, no caso da seguinte sentença:

$$ \text{¬ } P \lor Q \to A \underline\lor B \land X $$

1. Primeiro faremos a Negação de $P$;
2. em seguida a Conjunção de $B$ com $X$; (Chamaremos de $S$)
3. para depois fazer a Disjunção de “Não $P$” com $Q$; (Chamaremos de $Y$)
4. Então partir para a Disjunção Exclusiva de $A$ com o $S$. (Chamaremos de $K$)
5. para, por fim, na Condicional final temos $Y \to K$.

Fontes: LIPSCHUTZ, S., LIPSON, M. Matemática Discreta MENEZES, P.B., TOSCANI, L.V., LÓPEZ, J.G. Aprendendo matemática discreta com exercícios GERSNTING, J.L. Fundamentos Matemáticos para a Ciência da Computação Material Fornecido pelo professor via MS Teams.

Matemática Discreta - Aula 02 Matemática Discreta - Aula 04