• Outro

O cálculo proposicional

Recursos básicos do PC

O ramo mais simples e básico da lógica é o cálculo proposicional, doravante denominado PC, assim chamado porque lida apenas com proposições completas não analisadas e certas combinações em que entram. Várias notações para PC são usadas na literatura. Naquele usado aqui, os símbolos empregados no PC primeiro incluir variáveis ​​(para as quais as letras p , o que , r ,… São usados, com ou sem subscritos numéricos); segundo, operadores (para os quais os símbolos ∼, ·, ∨, ⊃ e ≡ são empregados); e terceiro, colchetes ou parênteses. As regras para a construção de fórmulas são discutidas abaixo ( Veja abaixo Regras de formação para PC ), mas as interpretações pretendidas desses símbolos - ou seja, os significados a serem dados a eles - são indicadas aqui imediatamente: as variáveis ​​devem ser vistas como representando proposições não especificadas ou como marcando os lugares em fórmulas em que sentenças, e apenas sentenças, pode ser inserido. (Isso às vezes é expresso dizendo que as variáveis ​​variam em relação às proposições ou que elas tomam as proposições como seus valores.) Portanto, elas são freqüentemente chamadas de variáveis ​​proposicionais. Supõe-se que toda proposição é verdadeira ou falsa e que nenhuma proposição é verdadeira e falsa. Verdade e falsidade são considerados os valores de verdade das proposições. A função de um operador é formar uma nova proposição a partir de uma ou mais proposições, chamadas de argumentos do operador. Os operadores ∼, ·, ∨, ⊃ e ≡ correspondem respectivamente às expressões em inglês não, e, ou, se ..., então (ou implica), e é equivalente a, quando estas são usadas nos seguintes sentidos:

1. Dada uma proposição p , então ∼ p (não p ) deve ser considerado falso quando p é verdadeiro e verdadeiro quando p é falso; ∼ (quando assim interpretado) é conhecido como o sinal de negação, e ∼ p como a negação de p .
2. Dadas quaisquer duas proposições p e o que , então p · o que ( p e o que ) deve ser considerado verdadeiro quando p e o que são verdadeiras e falsas em todos os outros casos (ou seja, quando p é verdade e o que falso, quando p é falso e o que verdade, e quando p e o que são ambos falsos); p · o que é dito ser a conjunção de p e o que ; · É conhecido como o sinal de conjunção e seus argumentos ( p , o que ) como orações.
3. Dadas quaisquer duas proposições p e o que , então p ∨ o que ( p ou o que ) deve ser considerado falso quando p e o que são falsas e verdadeiras em todos os outros casos; portanto, representa a afirmação de que pelo menos um dos p e o que é verdade. P ∨ o que é conhecido como a disjunção de p e o que ; ∨ é o sinal de disjunção, e seus argumentos ( p , o que ) são conhecidos como disjuntos.
4. Dadas quaisquer duas proposições p e o que , então p ⊃ o que (E se p [então] o que ou p [materialmente] implica o que ) deve ser considerado falso quando p é verdade e o que é falso e verdadeiro em todos os outros casos; portanto, tem o mesmo significado que não p ou o que ou como não ambos p e não- o que . O símbolo ⊃ é conhecido como o (material) implicação sinal, o primeiro argumento como antecedente e o segundo como consequente; o que ⊃ p é conhecido como o inverso de p ⊃ o que .
5. Finalmente, p ≡ o que ( p é [materialmente] equivalente a o que ou p se e apenas se o que ) deve ser considerado verdadeiro quando p e o que têm o mesmo valor de verdade (ou seja, quando ambos são verdadeiros ou quando ambos são falsos) e falso quando têm valores de verdade diferentes; os argumentos de ≡ (o sinal de equivalência [material]) são chamados de equivalentes.

Os colchetes são usados ​​para indicar agrupamento; eles tornam possível distinguir, por exemplo, entre p · ( o que ∨ r ) (Ambas p e também- o que -ou- r ) e ( p · o que ) ∨ r (ambos- p -e- o que ou r ) Regras precisas para agrupamento são fornecidas abaixo.

Todos os operadores de PC tomam proposições como seus argumentos, e o resultado de aplicá-las também é, em cada caso, uma proposição. Por essa razão, às vezes são chamados de operadores formadores de proposições em proposições ou, mais resumidamente, conectivos proposicionais. Um operador que, como ∼, requer apenas um único argumento é conhecido como operador monádico; operadores que, como todos os outros listados, requerem dois argumentos são conhecidos como diádicos.

Todos os operadores de PC também têm a seguinte característica importante: dados os valores de verdade dos argumentos, o valor de verdade da proposição formada por eles e o operador é determinado em todos os casos. Um operador que tem essa característica é conhecido como operador funcional de verdade, e uma proposição formada por tal operador é chamada de função de verdade do (s) argumento (s) do operador. A funcionalidade de verdade dos operadores de PC é claramente trazida ao resumir o relato acima deles em tabela 1. Nele, verdadeiro é abreviado por 1 e falso por 0, e à esquerda da linha vertical são tabuladas todas as combinações possíveis de valores verdade dos argumentos dos operadores. As colunas de 1s e 0s nas várias funções de verdade indicam seus valores de verdade para cada um dos casos; essas colunas são conhecidas como tabelas verdade dos operadores relevantes. Deve-se notar que qualquer coluna de quatro 1s ou 0s ou ambos especificará um operador funcional de verdade diádico. Porque existem precisamente 2⁴(ou seja, 16) maneiras de formar uma sequência de quatro símbolos, cada um dos quais deve ser 1 ou 0 (1111, 1110, 1101, ..., 0000), existem 16 desses operadores ao todo; os quatro listados aqui são apenas os quatro mais úteis em geral.

Regras de formação para PC

Em qualquer sistema lógico, é necessário especificar quais sequências de símbolos contam como fórmulas aceitáveis ​​- ou, como são geralmente chamadas, fórmulas bem formadas (wffs). As regras que especificam isso são chamadas de regras de formação. De um ponto de vista intuitivo, é desejável que as wffs do PC sejam apenas aquelas sequências de símbolos do PC que, em termos da interpretação dada acima, façam sentido e sejam inequívocas; e isso pode ser garantido estipulando que as wffs do PC devem ser todas aquelas expressões construídas de acordo com as seguintes regras de formação de PC, e apenas estas:

• FR1.A variável isolada é um wff.
• FR2.Se α é um wff, isα também o é.
• FR3. Se α e β são wffs, (α · β), (α β), (α ∨ β), (α ⊃ β), e (α ≡ β) são wffs.

Nessas regras, α e β são variáveis ​​que representam fórmulas arbitrárias de PC. Eles não são símbolos do PC, mas são usados ​​na discussão do PC. Essas variáveis ​​são conhecidas como variáveis ​​metalógicas. Deve-se notar que as regras, embora concebidas para garantir um sentido inequívoco para as wffs do PC sob a interpretação pretendida, são elas mesmas declaradas sem qualquer referência à interpretação e de tal forma que haja um procedimento eficaz para determinar, novamente sem qualquer referência à interpretação, seja qualquer sequência arbitrária de símbolos uma wff ou não. (Um procedimento eficaz é aquele que é de natureza mecânica e sempre pode ser confiável para dar um resultado definido em um número finito de etapas. A noção de eficácia desempenha um papel importante na lógica formal.)

Exemplos de wffs são: p ; ∼ o que ; ∼ ( p · o que ), Ou seja, não ambos p e o que ; e [∼ p ∨ ( o que ≡ p )] - ou seja, não p se não o que é equivalente a p .

Para maior facilidade na escrita ou leitura de fórmulas, as regras de formação são freqüentemente relaxadas. Os seguintes relaxamentos são comuns: (1) Os colchetes envolvendo uma fórmula completa podem ser omitidos. (2) O estilo tipográfico dos colchetes pode variar dentro de uma fórmula para tornar o emparelhamento dos colchetes mais evidente à vista. (3) Conjunções e disjunções podem ter mais de dois argumentos - por exemplo, p · ( o que ⊃ r ) · ∼ r pode ser escrito em vez de [ p · ( o que ⊃ r )] · ∼ r . (A conjunção p · o que · r é então interpretado como significando que p , o que , e r são todos verdadeiros, p ∨ o que ∨ r para significar que pelo menos um de p , o que , e r é verdade e assim por diante.)

Validade no PC

Dada a interpretação padrão, um wff de PC torna-se uma sentença, verdadeira ou falsa, quando todas as suas variáveis ​​são substituídas por sentenças reais. Tal wff é, portanto, uma forma de proposição no sentido explicado acima e, portanto, é válida se e somente se todas as suas instâncias expressam proposições verdadeiras. Uma wff em que todas as ocorrências são falsas é considerada insatisfatória, e uma com algumas ocorrências verdadeiras e outras falsas é considerada contingente.

Um problema importante para qualquer sistema lógico é o problema de decisão para a classe de wffs válidos desse sistema (às vezes simplesmente chamado de problema de decisão para o sistema). Este é o problema de encontrar um procedimento eficaz, no sentido explicado na seção anterior, para testar a validade de qualquer wff do sistema. Esse procedimento é denominado procedimento de decisão. Para alguns sistemas, um procedimento de decisão pode ser encontrado; o problema de decisão para um sistema desse tipo é então considerado solucionável e o sistema é considerado decidível. Para outros sistemas, pode-se provar que nenhum procedimento de decisão é possível; o problema de decisão para tal sistema é então considerado insolúvel e o sistema é considerado indecidível.

O PC é um sistema decidível. Na verdade, vários procedimentos de decisão para isso são conhecidos. Destes, o mais simples e mais importante teoricamente (embora nem sempre o mais fácil de aplicar na prática) é o método das tabelas de verdade, que agora será explicado brevemente. Uma vez que todos os operadores em uma wff de PC são funcionais de verdade, para descobrir o valor de verdade de qualquer instância de tal wff, é desnecessário considerar nada além dos valores de verdade das sentenças que substituem as variáveis. Em outras palavras, a atribuição de um valor verdade para cada uma das variáveis ​​em uma wff determina exclusivamente um valor verdade para toda a wff. Uma vez que existem apenas dois valores de verdade e cada wff contém apenas um número finito de variáveis, há apenas um número finito de atribuições de valores de verdade às variáveis ​​a serem consideradas (se houver n variáveis ​​distintas no wff, existem 2 ⁿ tais atribuições); estes podem ser facilmente tabulados de forma sistemática. Para cada uma dessas atribuições, as tabelas de verdade dos operadores permitem calcular o valor de verdade resultante de toda a wff; o wff é válido se e somente se esse valor de verdade for verdade em cada caso. Como um exemplo, [( p ⊃ o que ) r ] ⊃ [(∼ r ∨ p ) ⊃ o que ] pode ser testado para validade. Essa fórmula afirma que, se uma proposição implica uma segunda, e uma certa terceira proposição é verdadeira, então se a terceira proposição é falsa ou a primeira é verdadeira, a segunda é verdadeira.

O cálculo é mostrado em mesa 2. Como antes, 1 representa a verdade e 0 a falsidade. Uma vez que o wff contém três variáveis, existem 2³(ou seja, 8) atribuições diferentes às variáveis ​​a serem consideradas, que, portanto, geram as oito linhas da tabela. Essas atribuições são tabuladas à esquerda da linha vertical. Os números entre parênteses no pé indicam a ordem em que as etapas (de 1 a 6) devem ser realizadas para determinar os valores verdade (1 ou 0) a serem inseridos na tabela. Assim, a coluna 1, caindo sob o símbolo ⊃, estabelece os valores de p ⊃ o que para cada tarefa, obtida nas colunas sob p e o que pela tabela de verdade para ⊃; coluna 2, para ( p ⊃ o que ) r , é então obtido empregando os valores da coluna 1 juntamente com os da coluna sob r pelo uso da tabela verdade para ·; … Até que finalmente a coluna 6, que fornece os valores para toda a wff, é obtida das colunas 2 e 5. Essa coluna é chamada de tabela verdade de toda a wff. Visto que consiste inteiramente em 1s, mostra que wff é verdadeiro para todas as atribuições dadas às variáveis ​​e, portanto, é válido. Uma wff para a qual a tabela verdade consiste inteiramente de 0s nunca é satisfeita, e uma wff para a qual a tabela verdade contém pelo menos um 1 e pelo menos um 0 é contingente. Resulta das regras de formação e do fato de que uma tabela verdade inicial foi especificada para cada operador que uma tabela verdade pode ser construída para qualquer wff de PC.

Entre as wffs válidas mais importantes do PC estão as de Tabela 3, todos os quais podem ser comprovados como válidos por uma aplicação mecânica do método da tabela de verdade. Eles também podem ser vistos como expressando princípios gerais intuitivamente sólidos sobre proposições. Por exemplo, porque não (... ou ...) pode ser reformulado como nem ... nem ..., a primeira lei De Morgan pode ser lida como ambos p e o que se e somente se nenhum não- p nem não- o que ; assim, expressa o princípio de que duas proposições são conjuntamente verdadeiras se e somente se nenhuma delas for falsa. Sempre que, como é o caso na maioria dos exemplos dados, um wff da forma α ≡ β é válido, os wffs correspondentes α ⊃ β e β ⊃ α também são válidos. Por exemplo, porque ( p · o que ) ≡ ∼ (∼ p ∨ ∼ o que ) é válido, então são ( p · o que ) ⊃ ∼ (∼ p ∨ ∼ o que ) e ∼ (∼ p ∨ ∼ o que ) ⊃ ( p · o que )

Além disso, embora p ⊃ o que não significa isso o que pode ser deduzido de p , no entanto, sempre que uma wff da forma α ⊃ β é válida, a forma de inferência α, portanto β, é igualmente válida. Esse fato é facilmente percebido pelo fato de que α ⊃ β significa o mesmo que não ambos: α e não-β; pois, como foi observado acima, sempre que a última for uma forma de proposição válida, α, portanto β é uma forma válida inferência Formato.

Seja α qualquer wff. Se qualquer variável nele é agora uniformemente substituída por algum wff, o wff resultante é chamado de instância de substituição de α. Desse modo [ p ⊃ ( o que ∨ ∼ r )] ≡ [∼ ( o que ∨ ∼ r ) ⊃ ∼ p ] é uma instância de substituição de ( p ⊃ o que ) ≡ (∼ o que ⊃ ∼ p ), obtido dele substituindo o que uniformemente por ( o que ∨ ∼ r ) É um princípio importante que, sempre que uma wff é válida, o mesmo ocorre com cada substituição-instância dela (a regra da substituição [uniforme]).

Outro princípio importante é a regra de substituição de equivalentes. Duas wffs, α e β, são consideradas equivalentes quando α ≡ β é válido. (As wffs α e β são equivalentes se e somente se tiverem tabelas de verdade idênticas.) A regra afirma que, se qualquer parte de uma wff for substituída por um equivalente dessa parte, a wff resultante e o original também são equivalentes. Essas substituições não precisam ser uniformes. A aplicação desta regra é considerada uma transformação de equivalência.

Compartilhar: