A linguagem da Lógica Proposicional
Resumo
Esta nota revisa a linguagem da lógica proposicional como uma metalinguagem utilizada para obter expressões válidas da linguagem base formada por dois símbolos. São explicadas as regras de sintaxe, os conceitos de variáveis proposicionais e conectores, e também é introduzida a negação conjunta, o uso de parênteses e reordenamento para facilitar a leitura das expressões. Além disso, são mencionadas as vocalizações das expressões da lógica proposicional. Finalmente, sintetiza-se a linguagem da lógica proposicional como uma ferramenta fundamental na matemática e na lógica, e reflete-se sobre a possibilidade de encontrar uma “linguagem base da base” a partir da qual tudo o mais poderia ser reconstruído.
Objetivos de aprendizado:
Ao completar esta seção, espera-se que o estudante seja capaz de:
- Entender o conceito de metalinguagem e sua aplicação na lógica proposicional.
- Compreender as regras de sintaxe da linguagem da lógica proposicional.
- Conhecer o conceito de variável proposicional e seu uso na construção de expressões.
- Entender o uso do conector e da negação conjunta na linguagem da lógica proposicional.
- Aprender a usar parênteses e reordenamento para facilitar a leitura das expressões.
- Conhecer as vocalizações das expressões da lógica proposicional.
- Sintetizar a linguagem da lógica proposicional como uma ferramenta fundamental na matemática e na lógica.
- Refletir sobre a possibilidade de encontrar uma “linguagem base da base” a partir da qual tudo o mais poderia ser reconstruído.
- Aplicar os conceitos aprendidos na construção de expressões da lógica proposicional.
- Utilizar a linguagem da lógica proposicional para compreender e resolver problemas matemáticos e lógicos.
Índice
A LINGUAGEM DA LÓGICA PROPOSICIONAL: ALFABETOS E CADEIAS DE SÍMBOLOS
COMECEMOS COM UM ÚNICO SÍMBOLO
VAMOS ADICIONAR UM SEGUNDO SÍMBOLO
A LINGUAGEM DA LÓGICA PROPOSICIONAL: SINTAXE
EXEMPLOS DE REVISÃO DE SINTAXE
CONVENÇÕES DE NOTAÇÃO
METAVARIÁVEIS E O CONECTOR \downarrow
EXEMPLOS DO USO DA NEGAÇÃO CONJUNTA
REORDENAMENTO E PARÊNTESES
CONECTORES DERIVADOS
VOCALIZAÇÃO DAS EXPRESSÕES DA LÓGICA PROPOSICIONAL
SÍNTESE E REFLEXÕES SOBRE A LINGUAGEM DA LÓGICA PROPOSICIONAL
A MATRIX POR TRÁS DA MATRIX POR TRÁS DA COMPREENSÃO DE TODAS AS COISAS
A linguagem da Lógica Proposicional: Alfabetos e cadeias de símbolos
Comecemos com um único símbolo
Para construir a Linguagem da Lógica Proposicional, vamos iniciar nosso estudo a partir do alfabeto mais simples: aquele que possui um único símbolo. Não importa a forma que ele tenha, mas o fato de que ele é único. Se escrevermos usando tal alfabeto, a única coisa que distingue uma cadeia de símbolos de outra é o número de vezes que tal símbolo é repetido. Portanto, se temos a capacidade de escrever cadeias de símbolos de até comprimento N, só poderemos escrever N cadeias diferentes. Como você pode ver, este alfabeto é bastante limitado e não há muito mais o que se possa dizer sobre ele.
Vamos adicionar um segundo símbolo
Se adicionarmos um segundo símbolo ao nosso alfabeto, a escrita se torna mais rica do que no alfabeto anterior. Agora podemos apreciar a forma como os símbolos são ordenados, por exemplo, se 0 e 1 são nossos símbolos, podemos distinguir entre 01 e 10. Ambas as cadeias envolvem os mesmos símbolos, mas em ordem diferente. Se a cadeia mais longa que podemos escrever tem comprimento N =1,2,3,\cdots, então podemos escrever 2^1=2 cadeias de comprimento 1, 2^2=4 cadeias de comprimento 2, 2^3=8 cadeias de comprimento 3, e assim por diante 2^N cadeias distintas de comprimento N.
Exercício: Escreva em uma folha todas as cadeias distintas que é possível escrever com entre 1 e N símbolos. Quantas cadeias são escritas no total?
Solução: Se S_N é a soma de todas as cadeias, de comprimento 1, 2, 3, e assim por diante até chegar a N, então já vimos que:
\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N
Multiplicando por 2 a expressão anterior temos:
\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}
E portanto:
\displaystyle S_N=2 S_N - S_N = 2^N-1
Consequentemente, o número total de cadeias escritas na folha será 2^N-1.
A linguagem da Lógica Proposicional: Sintaxe
Vimos que, com dois símbolos, podemos distinguir uma cadeia de outra por seu comprimento e pela ordem em que estão dispostos. Isso é importante porque nos permite definir uma sintaxe para o alfabeto que construímos. Uma sintaxe é um conjunto de regras que separam as cadeias de símbolos em duas categorias: Expressões e Não-Expressões. Se \mathcal{L}_2 é o conjunto de todas as cadeias que podem ser construídas com os símbolos 0 e 1, então a sintaxe de \mathcal{L}_2 é um subconjunto \mathcal{SL}_2\subset\mathcal{L}_2.
Podemos definir o conjunto \mathcal{SL}_2 com as seguintes regras recursivas:
- 00, 11 \in \mathcal{SL}_2
- Se \alpha, \beta \in \mathcal{SL}_2, então 01\alpha\beta \in \mathcal{SL}_2
Com essas duas regras podemos construir expressões da linguagem e verificar se uma cadeia dada é uma expressão da linguagem. Uma linguagem é um alfabeto com uma sintaxe associada. A linguagem que foi apresentada aqui será chamada de “Língua Base de dois Símbolos”, ou \mathcal{B}_2.
Exemplos de revisão de sintaxe
Para tornar essas ideias mais fáceis de entender, vamos revisar os seguintes exemplos:
Exemplo: Dado que 0000 e 1111 estão contidos em \mathcal{SL}_2, temos que 0100 00 01 0011 01 110000 e 0111111111 estão em \mathcal{SL}_2; portanto, são expressões de \mathcal{B}_2. Isso é demonstrado aplicando as regras que acabamos de introduzir.
Fim do exemplo \blacksquare
Exercício: No exemplo anterior, vimos como construir expressões a partir de outras duas expressões elementares. Isso não é uma tarefa complicada; no entanto, no processo inverso, que consiste em demonstrar se uma determinada expressão é ou não uma expressão válida, podemos nos deparar com algo um pouco mais desafiador.
Determine, usando as regras de sintaxe, se as seguintes cadeias são ou não expressões de \mathcal{B}_2:
{}012100
101100
{}0100010000
0101000011
{}01010000010000
01010010000100101000011
Solução:
Antes de ver a solução, recomendo que você tente primeiro por conta própria e depois compare os resultados. Se já fez isso, então vá em frente 👍
012100.
Como podemos ver, esta inclui o símbolo 2, que não está contido em \mathcal{L}_2; essa cadeia não pode estar contida em \mathcal{SL}_2 e, portanto, não é uma expressão de \mathcal{B}_2.
101100.
Aqui podemos ver que esta cadeia começa com 10. Das regras de sintaxe, podemos inferir que todas as cadeias de comprimento superior a 2 começam, necessariamente, com 01, portanto, não pode ser uma expressão de \mathcal{B}_2.
0100010000
Esta cadeia começa com 01, passando no primeiro teste. A partir daqui, para que seja uma expressão de \mathcal{L}_2, é necessário que a parte marcada em azul possa ser decomposta de maneira única em duas expressões.
0100010000
Se, mesmo cumprindo as leis de sintaxe, a decomposição não for única, então a sintaxe definida é ambígua e, portanto, deve ser corrigida.
Analisando a parte azul, temos as seguintes possíveis separações:
00010000 00010000 00010000 00010000 00010000 00010000 00010000 Nesta parte, devemos notar que, se a parte dourada não é 0000 ou 1111, então a parte azul correspondente deve começar com 01 para que a cadeia completa seja uma expressão; então, é possível fazer as seguintes exclusões:
0{}0010000❌ 00010000✅ 000{}10000❌ 00010000❌ 00010000❌ 00010000❌ 00010000❌ É por isso que a única separação que sobrevive a esta análise é 00010000, onde a parte dourada é uma expressão e a azul se separa de maneira única e consistente com a sintaxe. Finalmente, a cadeia 0100010000 admite uma decomposição única e consistente com a sintaxe, que é 0100010000, e portanto é uma expressão da linguagem \mathcal{B}_2
0101000011
Para esta cadeia, podemos fazer a seguinte separação, que marco com cores:
010100001111
Pelas regras de sintaxe, para que uma cadeia de comprimento superior a 2 seja uma expressão, é necessário que comece com 01, e depois disso devem seguir duas expressões, que marquei em azul e dourado. É fácil ver que essa separação é única, pois, se a área azul ou dourada mudarem de comprimento, qualquer mudança que seja, ambas as partes deixarão de ser uma expressão ao mesmo tempo.
01010000010000
Revisando da direita para a esquerda, podemos encontrar a seguinte separação:
\underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{expressão}}\underbrace{01\overbrace{00}\overbrace{00}}_{{expressão}}}_{{expressão}}
01010010000100101000011
Um olho aguçado notará que esta cadeia tem comprimento 23 e que é impossível construir uma cadeia de comprimento ímpar através das leis de sintaxe de \mathcal{L}_2, que constrói expressões justapondo cadeias de comprimento par. Todas as cadeias de \mathcal{SL}_2 têm comprimento par, portanto, 01010010000100101000011 não é uma expressão de \mathcal{B}_2.
Fim do exercício \blacksquare
Convenções de Notação
Trabalhar com zeros e uns pode ser confuso para nossa percepção e pode nos levar a cometer erros. Para tornar o processo mais amigável à maneira como os humanos interpretam as coisas, podemos usar convenções de notação e alguns metasímbolos.
metavariáveis e o conector \downarrow
Um metasímbolo é um símbolo usado para representar cadeias de símbolos de uma linguagem alvo. Por exemplo, quando a sintaxe \mathcal{SL}_2 de \mathcal{L}_2 foi definida, os símbolos \alpha e \beta foram usados para representar expressões de \mathcal{B}_2. Esses símbolos são chamados de metavariáveis de \mathcal{B}_2: metasímbolos que, quando todos substituídos por expressões da linguagem, geram através da sintaxe outra expressão da linguagem, como estabelecido pela segunda regra sobre os elementos de \mathcal{SL}_2:
Se \alpha,\beta \in \mathcal{SL}_2, então 01\alpha\beta \in\mathcal{SL}_2
Por esta razão, diz-se que essas metavariáveis são metaexpressões de \mathcal{B}_2.
Para facilitar nossa escrita daqui em diante, vamos usar o metasímbolo \downarrow para representar a cadeia 01. Este metasímbolo é o que chamamos de conector e é conhecido como Negação Conjunta por razões semânticas.
Com isso, podemos expressar a sintaxe \mathcal{SL}_2 de maneira metalinguística através das seguintes regras recursivas:
Todas as metavariáveis de \mathcal{B}_2 são metaexpressões \mathcal{B}_2
Se \alpha e \beta são metavariáveis de \mathcal{B}_2, então \downarrow\alpha\beta é uma metaexpressão \mathcal{B}_2
Com essas regras, podemos escrever metaexpressões que, quando todas as suas metavariáveis são substituídas por expressões e conectores em sua forma representada por zeros e uns, obtemos uma expressão de \mathcal{B}_2. Cada metaexpressão desse tipo faz referência a uma família infinita de expressões de \mathcal{B}_2: o conjunto de todas as expressões de \mathcal{B}_2 que podem ser representadas por essa estrutura. Isso é exatamente o que significa ter uma linguagem formal.
Exemplos do uso da negação conjunta
Exemplo: A partir da metaexpressão \downarrow\alpha\downarrow\beta\gamma, podem ser obtidas, através de substituições, as seguintes expressões:
Substituindo \alpha := 00, \beta := 011100 e \gamma := 010011
Chegamos à expressão:
010001011100010011
Se substituirmos \alpha := 011100, \beta := 0111011100 e \gamma := 0111010011
É gerado:
010111000101110111000111010011
A metaexpressão \downarrow\alpha\downarrow\beta\gamma não é apenas mais fácil de assimilar do que qualquer outra expressão que satisfaça sua forma, mas também representa todas as expressões que podem ser obtidas a partir dela, substituindo suas metavariáveis por expressões.
Fim do exemplo \blacksquare
Quando uma metavariável é substituída, ela é substituída em todos os lugares onde aparece
Exemplo: Consideremos a metaexpressão \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma
- Se substituirmos \alpha:=11, obtemos:
\downarrow\downarrow 11\beta\downarrow 11\gamma
- Se agora fizermos \beta:=011100, o resultado será:
\downarrow\downarrow 11011100\downarrow 11\gamma
- E se agora fizermos a substituição \gamma:=011111, ficaremos com:
\downarrow\downarrow 11011100\downarrow 11011111
- Finalmente, mudando \downarrow:=01, concluiremos com esta expressão:
0101110111000111011111
Fim do exemplo \blacksquare
Reordenamento e parênteses
Verificar que esta é uma metaexpressão não é especialmente difícil, mas requer uma atenção constante ao número de metasímbolos e ao alcance do conector \downarrow. Essa dificuldade aumenta rapidamente com o aumento do comprimento da metaexpressão. Por isso, é válida a pergunta se existe alguma forma de representar essas coisas de uma maneira mais fácil de verificar, e a resposta é sim; de fato, podemos utilizar parênteses e reordenamentos adequados para a metaexpressão que se adaptam melhor à nossa forma natural de agrupar as coisas. Para ilustrar esse ponto, vamos revisar a seguinte metaexpressão:
\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha
Acontece que, embora não seja particularmente difícil confirmar que isso é uma metaexpressão, não é algo que possamos fazer sem ter que contar símbolos e correr o risco de perder a conta no processo, e o risco cresce rapidamente à medida que o comprimento da metaexpressão aumenta. Existe alguma forma de representar o mesmo de uma maneira mais fácil de ler? A verdade é que tal método existe e é configurado de acordo com nossa forma natural de agrupar as coisas. Para isso, são introduzidos os parênteses e o reordenamento através da seguinte convenção de notação:
\downarrow\alpha\beta:=(\alpha\downarrow\beta)
Exemplo: Consideremos a metaexpressão \downarrow\alpha\downarrow\downarrow\beta\gamma\delta. Se aplicarmos a introdução de parênteses e o reordenamento, ela se transformará da seguinte maneira:
| \downarrow\alpha\downarrow\downarrow\beta\gamma\delta | := | \downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta |
| \downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta | := | \downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta) |
| \downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta) | := | (\alpha \downarrow((\beta\downarrow \gamma)\downarrow\delta)) ✅ |
Esta última metaexpressão é muito mais fácil de ler e revisar do que a original, porque cada bloco de parênteses é uma metaexpressão composta de elementos fáceis de distinguir: uma negação conjunta no centro e uma metaexpressão de cada lado.
Fim do exemplo \blacksquare
Conectores Derivados
Tanto na lógica quanto no restante da matemática, existem certas combinações de conectores que são frequentemente utilizadas. Por isso, para tornar a escrita ainda mais confortável (para os humanos), são introduzidos os conectores derivados através das seguintes convenções de notação:
| Negação: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Disjunção Inclusiva: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Conjunção: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implicação: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Dupla Implicação: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Disjunção Exclusiva: | (\alpha \veebar \beta) | := | \neg(\alpha\leftrightarrow \beta) |
Este metalinguagem que construímos sobre a língua base de dois símbolos é o que se conhece como Linguagem de Ordem Zero da Lógica Proposicional. Através dessa linguagem, todas as expressões da lógica proposicional são representadas de maneira precisa e livre de ambiguidades.
Vocalização das expressões da lógica proposicional
Embora não seja necessário para fazer lógica, é importante lembrar que nossa comunicação não se baseia apenas em símbolos escritos, mas também temos a tendência natural de vocalizar as coisas em nossa linguagem natural. Por isso, para as expressões da linguagem da lógica proposicional, existem vocalizações que evocam ideias semelhantes às que tratam seus homólogos na lógica proposicional. Essas vocalizações são as seguintes:
| (\alpha \downarrow \beta) | Nem \alpha nem \beta |
| \neg \alpha | Negação de \alpha |
| (\alpha \vee \beta) | \alpha ou \beta |
| (\alpha \wedge \beta) | \alpha e \beta |
| (\alpha \rightarrow \beta) | \alpha implica \beta |
| (\alpha \leftrightarrow \beta) | \alpha se e somente se \beta |
| (\alpha \veebar \beta) | ou \alpha, ou \beta, mas não ambos |
Síntese e reflexões sobre a linguagem da lógica proposicional
Com esta última parte, conclui-se a construção da linguagem da lógica proposicional, que podemos sintetizar como um metalinguagem que permite obter expressões válidas na língua base de dois símbolos. A linguagem da lógica proposicional é uma linguagem formal, pois define a estrutura (ou forma) das expressões na língua base, e cada uma de suas expressões determina a forma de uma família infinita de expressões na língua base. Como mencionamos anteriormente, a sintaxe de uma linguagem formal é extremamente rígida, mas em troca é precisa e exata: não tem ambiguidade.
A Matrix por trás da Matrix por trás da compreensão de todas as coisas
Uma última coisa. A lógica proposicional e a matemática se baseiam fortemente na lógica proposicional, que, por sua vez, é construída a partir de uma língua base formada por zeros e uns. Isso significa que, através disso, chegamos à “Matrix” por trás da lógica e da matemática? É possível. Mas também é possível considerar uma língua base para a língua base, a partir da qual seria possível reconstruir todo o resto; no entanto, para encontrar tal língua, precisaríamos encontrar noções ainda mais fundamentais do que os conceitos de ordem e quantidade (os que foram usados para estabelecer a primeira língua base). Encontrar uma língua base da base implica refletir sobre os aspectos mais fundamentais do que significa “entender as coisas”. Se você se aprofundar mais, se conseguir chegar ao fundo, poderíamos dizer que você conseguiu ver “a Matrix por trás da Matrix por trás da compreensão de todas as coisas”, e é possível que esse processo de fundamentação possa continuar indefinidamente, proporcionando uma nova camada de profundidade de conhecimento em cada passo fundamental.