Lógica proposicional
A lógica matemática é fundamental para a computação e informática, ao aprofundar nessa área da Matemática encontramos a lógica clássica ou lógica de 1º ordem que é composta por:
-
Lógica proposicional (ou cálculo proposicional): é formada por proposições e conectivos lógicos
-
Cálculo de predicados: é composto por quantificadores existenciais (
) e universais ( )
A lógica clássica é especialmente útil para descrever propriedades de objetos discretos (número, conjuntos)
Objeto discreto significa que é formada por elementos distintos desconexos entre si.
Definição
A definição formal de proposição é a seguinte:
“Uma proposição é uma asserção à qual se pode atribuir um valor de juízo.”
Em outras palavras, a proposição é uma afirmação que, no caso de computação, tem como resposta verdadeiro ou falso. Esse tipo de lógica são denominadas de lógicas booleanas, pois possuem valores de juízo booleano.
A tabela abaixo mostra exemplos de proposições e não proposições:
| Proposição | Contra-Exemplo |
|---|---|
| Brasil é um país | Vá tomar banho. |
| Buenos Aires é a capital do Brasil | Que horas são ? |
| 3 + 4 > 5 | Parabéns! |
| 7 - 1 = 5 | Você estudou quantas horas hoje ? |
Como tudo na matemática se resume a letras e símbolos, a seguir as representações simbólicas de alguns conceitos abordado acima:
-
= proposição -
valor de juízo (valor-verdade) da proposição
Alguns exemplos:
Outro conceitos da lógica proposicional é conetivos lógicos que são responsável por ligar proposições menores, denominadas preposições atômicas ou átomos, e então formar uma proposição maior e mais complexa.
Os conectivos lógicos fundamentais da lógica proposicional são:
-
negação
-
conjunção (e)
-
disjunção (ou)
-
condição (se … então)
-
bicondição (se e somente se)
A seguir exemplos da junção de proposições atômicas usando conectivos lógicos:
-
Windows não é um software livre.
-
Windows é um sistema operacional e Pascal é uma linguagem de programação.
-
Vou comprar um PC ou vou comprar um MAC.
-
Se os alunos estudarem então todos passarão em Matemática Discreta.
-
Um número é par se e somente se ele for divisível por 2.
Além da semânticas (significado) desses conectivos, é importante sabermos a sua sintaxe (representação simbólica) e a representação na tabela-verdade dos possíveis valores que podem assumir:
OBS: o símbolo
denota a semântica de um preposição
-
Negação (não)
Sintaxe:
Semântica:
Tabela-Verdade:
V F F V -
Conjunção (e)
Sintaxe:
Semântica:
Tabela-Verdade:
V V V V F F F V F F F F -
Disjunção (ou)
Sintaxe:
Semântica:
Tabela-Verdade:
V V V V F V F V V F F F -
Condição (Se … então)
Sintaxe:
Semântica:
Tabela-Verdade:
V V V V F F F V V F F V -
Bicondição (Se somente se)
Sintaxe:
Semântica:
Tabela-Verdade:
V V V V F F F V F F F V
Equivalência
-
Conectivo
é equivalente a ? q V V V F V V V F F F F V F V V V V V F F V F V V A última coluna da tabela deu tudo verdadeiro, logo
é equivalente a -
Conectivo
é equivalente a ? V V V V V V V V F F F V F V F V F V F F V F F V V V V V A última coluna da tabela deu tudo verdadeiro, logo
é equivalente a
Fórmulas
A definição de fórmula na literatura é a seguinte:
Uma fórmula (sintaticamente válida) é definida recursivamente por:
Toda proposição atômica
é uma fórmula. se
e são fórmulas, então também são fórmulas:
A união de proposições atômicos por meio de conectivos lógicos formal sentenças lógicas que são estrutura denotadas de fórmulas lógicas (ou simplesmente de fórmula).
A seguir alguns exemplos de fórmulas:
Após definir o que são fórmulas, é importante salientar que agora devemos respeitar alguns conceitos algébricos, como a ordem de precedência entre os conectivos:
-
Conectivos entre parênteses (mais interno
mais externo) -
Negação (
) -
Conjunção (
) e disjunção ( ) -
Condição (
) -
Bicondição (
)
A ordem de precedência é importante para evitarmos redundâncias e facilitar a legibilidade das sentenças lógicas
A seguir alguns exemplos simplificando a utilização de parênteses desnecessários:
Lembrando que utilizamos a notação matemática, pois a definição de conectivos foi para proposições e não para fórmulas.
A fórmula em si não têm nenhuma valor de juízo, ela o adquire a partir do momento em que atribuímos o valor de juízo para as proposições atômicas que a compõem.
Dessa forma para calcularmos os valores de juízos possível para uma fórmula, vamos utilizar as tabelas-verdades. Vale ressaltar que o número de linhas na tabela é proporcional ao número de proposições atômicas e que segue a seguinte fórmula:
Sendo
A demonstração dessa fórmula é bem simples, pois para cada proposição pode ser atribuído V ou F, ou seja, existem 2 valores possível, com isso podemos escrevê-la em notação matemática da seguinte forma:
Cada atribuição de um valor de juízo (V ou F) para as proposições atômicas em uma linha da tabela-verdade é chamada de valoração (daqui vem a representação simbólica
Vamos calcular os valores de juízo possíveis para a fórmula
| p | q |
|---|---|
| V | V |
| V | F |
| F | V |
| F | F |
| p | q | |
|---|---|---|
| V | V | F |
| V | F | V |
| F | V | F |
| F | F | V |
| p | q | ||
|---|---|---|---|
| V | V | F | V |
| V | F | V | V |
| F | V | F | F |
| F | F | V | V |
Lembrando que
é uma fórmula e os valores dessa coluna definem os valores de juízo dela.
Podemos classificar uma fórmula com base nos valores de juízo de uma fórmula:
-
Podemos dizer que uma fórmula é uma tautologia quando todas as valorações possíveis para cada proposição atômica der verdade, ou seja, quando toda a coluna da fórmula tiver o valor V;
-
Podemos dizer que uma fórmula é uma contradição quando todas as valorações possíveis para cada proposição atômica der falso, ou seja, quando toda a coluna da fórmula tiver o valor F.
Veja o exemplo abaixo:
| p | q | ||
|---|---|---|---|
| V | F | V | F |
| F | V | V | F |
A fórmula
Relação de equivalência
Considerando que
Exercícios
Exercício 1
Construa a tabela-verdade para a seguinte fórmula e verifique se ela é uma tautologia:
| p | q | r | ||||||
|---|---|---|---|---|---|---|---|---|
| V | V | V | V | V | V | V | V | V |
| V | V | F | V | V | V | F | V | V |
| V | F | V | V | V | F | V | V | V |
| V | F | F | F | F | F | F | F | F |
| F | V | V | V | F | F | F | F | F |
| F | V | F | V | F | F | F | F | F |
| F | F | V | V | F | F | F | F | F |
| F | F | F | F | F | F | F | F | F |
A fórmula acima pode ser uma tautologia, pois todos os valores de juízo satisfazem o operador lógico
Exercícios extra-classe
Exercício 1
Exercício 2
-
p q V V F V F V F V V F F V F F V F F V V F -
p q V V F V F V F V V F F V F V F F F V F V -