LÓGICA PROPOSICIONAL: UMA INTRODUÇÃO

LÓGICA PROPOSICIONAL  

UMA INTRODUÇÃO METATEÓRICA

VINICIUS DIAS DE SOUZA

Lógica proposicional , também conhecida como lógica sentencial e lógica de declaração, é o ramo da lógica que estuda maneiras de unir e / ou modificar proposições, frases ou frases inteiras para formar proposições, frases ou frases mais complicadas, bem como as relações e propriedades lógicas derivadas desses métodos de combinação ou alteração de declarações . Na lógica proposicional, as afirmações mais simples são consideradas como unidades indivisíveis e, portanto, a lógica proposicional não estuda as propriedades e relações lógicas que dependem de partes de declarações que não são declarações próprias, como o sujeito e o predicado de uma declaração . O ramo mais proposto da lógica proposicional é a lógica proposicional verdadeira-funcional funcional, que estuda operadores lógicos e conectivos que são usados ​​para produzir enunciados complexos cujo valor de verdade depende inteiramente dos valores de verdade das declarações mais simples, fazendo com que cada afirmação seja verdadeira ou falsa e não ambas. No entanto, existem outras formas de lógica proposicional em que outros valores de verdade são considerados, ou em que há consideração de conectivos que são usados ​​para produzir declarações cujos valores de verdade dependem não apenas dos valores de verdade das peças, mas adicionais coisas como sua necessidade, possibilidade ou relação entre eles.

1. Introdução

Uma declaração pode ser definida como uma frase declarativa, ou parte de uma frase, que é capaz de ter um valor de verdade, como ser verdadeiro ou falso. Então, por exemplo, as seguintes são declarações:

• George W. Bush é o 43º presidente dos Estados Unidos.
• Paris é a capital da França.
• Todo mundo nascido na segunda-feira tem cabelo roxo.

Às vezes, uma declaração pode conter uma ou mais outras declarações como partes. Considere, por exemplo, a seguinte declaração:

• Ou Ganymede é uma lua de Júpiter ou Ganimedes é uma lua de Saturno.

Enquanto a frase composta acima é em si uma afirmação, porque é verdade, as duas partes, "Ganimedes é uma lua de Júpiter" e "Ganímedes é uma lua de Saturno", são afirmações, porque a primeira é verdadeira e a segunda é falso.

O termo proposição às vezes é usado de forma sinônima com declaração . No entanto, às vezes é usado para nomear algo abstrato que duas declarações diferentes com o mesmo significado são ambas ditas a "expressar". Neste uso, a frase inglesa, "Está chovendo", e a frase francesa "Il pleut", seria considerada como expressando a mesma proposição; Da mesma forma, as duas frases em inglês, "Callisto orbita Júpiter" e "Júpiter é orbitada por Callisto" também seriam consideradas para expressar a mesma proposição. No entanto, a natureza ou existência de proposições como significados abstratos ainda é uma questão de controvérsia filosófica e, para os propósitos deste artigo, as frases "declaração" e "proposição" são usadas indistintamente.

A lógica proposicional , também conhecida como lógica sentencial , é aquele ramo da lógica que estuda maneiras de combinar ou alterar afirmações ou proposições para formar declarações ou proposições mais complicadas. Juntar duas proposições mais simples com a palavra "e" é uma maneira comum de combinar declarações. Quando duas instruções são juntas com "e", a declaração complexa formada por eles é verdadeira se e somente se ambas as declarações de componente forem verdadeiras. Por causa disto, um argumento da seguinte forma é logicamente válido:

Paris é a capital da França e Paris tem uma população de mais de dois milhões. 
Portanto, Paris tem uma população de mais de dois milhões.

A lógica proposicional envolve, em grande parte, o estudo de conectivos lógicos, como as palavras "e" e "ou", e as regras que determinam os valores de verdade das proposições que são usadas para se juntar, bem como o que essas regras significam para a validade dos argumentos e tal as relações lógicas entre as declarações são consistentes ou inconsistentes entre si, bem como as propriedades lógicas das proposições, tais como ser verdadeiramente tautologicamente, sendo contingente e sendo autocontraditório. (Estas noções são definidas abaixo .)

A lógica proposicional também estuda maneira de modificar declarações, como a adição da palavra "não" que é usada para alterar uma afirmação afirmativa em uma declaração negativa. Aqui, o princípio lógico fundamental envolvido é que, se uma afirmação positiva afirmativa for verdadeira, a negação dessa afirmação é falsa e, se uma afirmação afirmativa dada for falsa, a negação dessa afirmação é verdadeira.

O que é distintivo sobre a lógica proposicional em oposição a outros ramos de lógica (geralmente mais complicados) é que a lógica proposicional não lida com relacionamentos e propriedades lógicas que envolvem as partes de uma declaração menor do que as declarações simples que compõem. Portanto, a lógica proposicional não estuda as características lógicas das proposições abaixo em virtude das quais constituem um argumento válido:

1. George W. Bush é um presidente dos Estados Unidos.
2. George W. Bush é filho de um presidente dos Estados Unidos.
3. Portanto, há alguém que é um presidente dos Estados Unidos e um filho de um presidente dos Estados Unidos.

O reconhecimento de que o argumento acima é válido exige que se reconheça que o sujeito na primeira premissa é o mesmo que o sujeito na segunda premissa. No entanto, na lógica proposicional, as declarações simples são consideradas como partes indivisíveis, e essas relações e propriedades lógicas que envolvem partes de declarações como seus assuntos e predicados não são levadas em consideração.

A lógica proposicional pode ser pensada principalmente no estudo de operadores lógicos. Um operador lógico é qualquer palavra ou frase usada para modificar uma instrução para fazer uma declaração diferente ou juntar várias instruções juntas para formar uma declaração mais complicada. Em inglês, palavras como "e", "ou", "não", "se ... então ...", "porque" e "necessariamente", são todos operadores.

Um operador lógico é dito ser funcional da verdade se os valores de verdade (a verdade ou a falsidade, etc.) das declarações que é usado para construir sempre dependem inteiramente da verdade ou da falsidade das declarações a partir das quais são construídas. As palavras inglesas "e", "ou" e "não" são (pelo menos sem dúvida) verdade-funcionais, porque uma declaração composta unida com a palavra "e" é verdadeira se ambas as declarações assim juntas forem verdadeiras e falsas se um ou ambos são falsos, uma declaração composta unida com a palavra "ou" é verdadeira se pelo menos uma das declarações juntas for verdadeira e falso se ambas as instruções juntas forem falsas e a negação de uma declaração for verdadeira se e somente se a declaração negada for falsa.

Alguns operadores lógicos não são verdadeiramente funcionais. Um exemplo de um operador em inglês que não é verdade-funcional é a palavra "necessariamente". Se uma declaração formada usando este operador é verdadeira ou falsa não depende inteiramente da verdade ou da falsidade da declaração a que o operador é aplicado. Por exemplo, as duas afirmações a seguir são verdadeiras:

• 2 + 2 = 4.
• Alguém está lendo um artigo em uma enciclopédia de filosofia.

No entanto, considere agora as declarações correspondentes modificadas com o operador "necessariamente":

• Necessariamente, 2 + 2 = 4.
• Necessariamente, alguém está lendo um artigo em uma enciclopédia de filosofia.

Aqui, o primeiro exemplo é verdadeiro, mas o segundo exemplo é falso. Portanto, a verdade ou a falsidade de uma declaração que usa o operador "necessariamente" não depende inteiramente da verdade ou da falsidade da declaração modificada.

A lógica proposicional verdade-funcional é aquele ramo da lógica proposicional que se limita ao estudo de operadores verdade-funcionais. A lógica proposicional verdade-funcional clássica (ou "bivalente") é aquele ramo da lógica proposicional verdade-funcional que supõe que existem apenas dois valores de verdade possíveis, uma afirmação (seja simples ou complexa) pode ter: (1) verdade e (2) falsidade, e que cada afirmação é verdadeira ou falsa, mas não ambas.

A lógica proposicional clássica verdade-funcional é, de longe, o ramo proposital mais amplamente estudado, e por esse motivo, a maior parte do restante deste artigo se concentra exclusivamente nesta área da lógica. Além da lógica proposicional clássica verdade-funcional, existem outros ramos da lógica proposicional que estudam operadores lógicos, como "necessariamente", que não são verdade-funcionais. Há também lógicas proposicionais "não clássicas" em que tais possibilidades como (i) uma proposição tem um valor de verdade diferente de verdade ou falsidade, (ii) uma proposição que tem um valor de verdade indeterminado ou que não possui um valor de verdade completamente, e às vezes até (iii) uma proposta que é verdadeira e falsa, são consideradas.Seção VIII abaixo.)

2. História

O estudo sério da lógica como uma disciplina independente começou com o trabalho de Aristóteles(384-322 aC). Geralmente, no entanto, os escritos sofisticados de Aristóteles em lógica tratavam da lógica de categorias e quantificadores como "todos" e "alguns", que não são tratados na lógica proposicional. No entanto, em seus escritos metafísicos, Aristóteles adotou dois princípios de grande importância na lógica proposicional, que passou a ser chamada de Lei do Médio Excluído e da Lei da Contradição. Interpretado na lógica proposicional, o primeiro é o princípio de que cada afirmação é verdadeira ou falsa, a segunda é o princípio de que nenhuma afirmação é verdadeira e falsa. Essas são, claro, as pedras angulares da lógica proposicional clássica. Há alguma evidência de que Aristóteles , ou pelo menos seu sucessor no Liceu , Teófrasto (d. 287 aC), reconheceram a necessidade de desenvolver uma doutrina de proposições "complexas" ou "hipotéticas", ou seja, envolvendo conjunções ( declarações unidas por "e"), disjunções (declarações unidas por "ou") e condicionais (declarações unidas por "se ... então ..."), mas suas investigações sobre esse ramo da lógica parecem ter sido muito menores.

Tentativas mais sérias para estudar tais operações como "e", "ou" e "se ... então ..." foram conduzidas pelos filósofos estóicos no final do século III aC. Como a maioria de suas obras originais - se de fato, muitos escritos foram produzidos - estão perdidos, não podemos fazer muitas afirmações definitivas sobre exatamente quem primeiro fez investigações sobre as áreas da lógica proposicional, mas sabemos dos escritos de Sextus Empiricus que Diodoro Cronus e seu aluno Philo haviam se envolvido em um longo debate sobre se a verdade de uma declaração condicional depende inteiramente de que não é o caso de que seu antecedente (if-clause) é verdadeiro enquanto a consequente (então-cláusula) é falsa, ou se requer algum tipo de ligação mais forte entre o antecedente e conseqüente - um debate que continua a ter relevância para a discussão moderna dos condicionais. O filósofo estóico Chrysippus(aproximadamente 280-205 aC) talvez tenha feito o máximo em avançar a lógica proposicional estóica, marcando várias maneiras diferentes de formar premissas complexas para argumentos e, para cada uma, listando esquemas de inferência válidos. Chrysippus sugeriu que os seguintes esquemas de inferência devem ser considerados os mais básicos:

1. Se o primeiro, depois o segundo; mas o primeiro; portanto, o segundo.
2. Se o primeiro, depois o segundo; mas não o segundo; portanto, não o primeiro.
3. Não tanto o primeiro como o segundo; mas o primeiro; portanto, não o segundo.
4. Ou o primeiro ou o segundo [e não ambos]; mas o primeiro; portanto, não o segundo.
5. Ou o primeiro ou o segundo; mas não o segundo; portanto, o primeiro.

As regras de inferência, como as acima, correspondem muito de perto aos princípios básicos em um sistema contemporâneo de dedução natural para a lógica proposicional. Por exemplo, as duas primeiras regras correspondem às regras de modus ponens e modus tollens , respectivamente. Esses esquemas de inferência básica foram expandidos por esquemas de inferência menos básicos pelo próprio Chrysippus e outros estóicos, e são preservados no trabalho de Diógenes Laertius, Sextus Empiricus e mais tarde, no trabalho de Cícero.

Os avanços no trabalho dos estóicos foram realizados em pequenos passos nos séculos que se seguiram. Este trabalho foi feito, por exemplo, pelo lógico do século II Galen (cerca de 129-210 EC), o filósofo do século VI Boeio (aproximadamente 480-525 EC) e mais tarde por pensadores medievais como Peter Abelard (1079-1142) e William de Ockham (1288-1347) e outros. Grande parte de seu trabalho envolveu produzir melhores formalizações dos princípios de Aristóteles ou Chrysippus, introduzindo terminologia melhorada e promovendo a discussão das relações entre operadores. Abelard, por exemplo, parece ter sido o primeiro a diferenciar-se claramente da disjunção inclusiva (discutido abaixo), e sugerir que a disjunção inclusiva é a noção mais importante para o desenvolvimento de uma lógica relativamente simples de disjunções.

O próximo grande passo em frente no desenvolvimento da lógica proposicional veio muito mais tarde com o advento da lógica simbólica no trabalho de lógicos como Augustus DeMorgan (1806-1871) e, especialmente, George Boole (1815-1864), no meio do meio- século 19. Boole estava principalmente interessado em desenvolver uma "álgebra" de estilo matemático para substituir a lógica silogística aristotélica, principalmente empregando o numeral "1" para a classe universal, o numeral "0" para a classe vazia, a notação de multiplicação "xy" para a classe vazia interseção das classes x e y, a notação de adição "x + y" para a união das classes x e y, etc., para que as afirmações da lógica silogística possam ser tratadas de forma quase matemática como equações; por exemplo, "No x is y" pode ser escrito como "xy = 0". Contudo, Boole percebeu que, se uma equação, como "x = 1", é lida como "x é verdadeiro" e "x = 0" é lido como "x é falso", as regras dadas para sua lógica de classes podem ser transformadas em lógica para proposições, com "x + y = 1" reinterpretado dizendo que x ou y são verdadeiros, e "xy = 1" reinterpretado no sentido de que x e y são ambos verdadeiros. O trabalho de Boole provocou um rápido interesse pela lógica entre os matemáticos e, mais tarde, as "álgebras booleanas" foram usadas para formar a base das lógicas proposicionais verdade-funcionais utilizadas no design e programação de computadores.

No final do século 19, Gottlob Frege (1848-1925) apresentou a lógica como um ramo da investigação sistemática mais fundamental que a matemática ou a álgebra e apresentou o primeiro cálculo axiomático moderno da lógica em sua obra Begriffsschrift em 1879 . Embora abrande mais do que a lógica proposicional, a partir da axiomatização de Frege é possível destilar a primeira axiomatização completa da lógica proposicional clássica verdade-funcional. Frege também foi o primeiro a argumentar sistematicamente que todos os conectivos verdade-funcionais poderiam ser definidos em termos de negação e material condicional.

No início do século 20, Bertrand Russell deu uma axiomatização completa e diferente da lógica proposicional, considerada por si própria, em seu artigo de 1906 "The Theory of Implication", e mais tarde, junto com Whitehead, produziu outra axiomatização usando disjunção e negação como primitivas no trabalho de 1910 Principia Mathematica . A prova da possibilidade de definir todos os operadores funcionais da verdade em virtude de um único operador binário foi publicada pela primeira vez pelo lógico americano HM Sheffer em 1913, embora CS Peirce (1839-1914) pareça ter descoberto décadas anteriores. Em 1917, o lógico francês Jean Nicod descobriu que era possível uma axiomatização para a lógica proposicional usando o golpe de Sheffer envolvendo apenas um único esquema de axioma e uma única regra de inferência.

Embora a noção de uma "tabela de verdade" utilizada frequentemente na discussão de conectivos verdade-funcionais, discutidos abaixo, parece ter sido pelo menos implícita no trabalho de Peirce, WS Jevons (1835-1882), Lewis Carroll (1832-1898) ), John Venn (1834-1923) e Allan Marquand (1853-1924), e as tabelas de verdade aparecem explicitamente em escritos de Eugen Müller em 1909, seu uso ganhou popularidade rápida no início da década de 1920, talvez devido à influência combinada do trabalho de Emil Post, cujo 1921 faz uso liberal deles, e Tractatus Logos-Philosophicus 1921 de Ludwig Wittgenstein , em que as tabelas da verdade e a funcionalidade da verdade são proeminentes.

A investigação sistemática sobre sistemas axiomáticos para lógica proposicional e metáfora relacionada foi realizada nos anos 1920, 1930 e 1940 por pensadores como David Hilbert, Paul Bernays, Alfred Tarski, Jan Łukasiewicz, Kurt Gödel, Igreja Alonzo e outros. É durante este período que a maioria dos importantes resultados metatheoréticos, como os discutidos na Seção VII, foram descobertos.

Os sistemas completos de dedução natural para a lógica proposicional da verdade clássica da verdade foram desenvolvidos e popularizados no trabalho de Gerhard Gentzen em meados da década de 1930, e posteriormente introduzidos em livros didáticos influentes como o de FB Fitch (1952) e Irving Copi (1953).

As lógicas proposicionais modais são a forma mais amplamente estudada de lógica proposicional não-verdade-funcional. Enquanto o interesse pela lógica modal remonta a Aristóteles, segundo os padrões contemporâneos, o primeiro inquérito sistemático sobre esta lógica proposicional modal pode ser encontrado no trabalho de CI Lewis em 1912 e 1913. Entre outras formas bem conhecidas de proposicional não-verdade-funcional lógica, a lógica deontica começou com o trabalho de Ernst Mally em 1926, e a lógica epistêmica foi primeiramente tratada sistematicamente por Jaakko Hintikka no início dos anos 1960. O estudo moderno da lógica proposicional de três valores começou no trabalho de Jan Łukasiewicz em 1917, e outras formas de lógica proposicional não clássica logo seguiram o exemplo. A lógica proposicional de relevância é relativamente mais recente; que data de meados da década de 1970 no trabalho de AR Anderson e ND Belnap. Lógica paraconsistente,

3. A Linguagem da Lógica Proposicional

As regras e princípios básicos da lógica proposicional clássica verdade-funcional são, entre os lógicos contemporâneos, quase inteiramente acordados e capazes de serem declarados de forma definitiva. Isso é mais facilmente feito se utilizarmos uma linguagem lógica simplificada que trate apenas de declarações simples consideradas como unidades indivisíveis, bem como enunciados complexos unidos por meio de conectivos funcionais de verdade. Consideramos primeiro uma linguagem chamada PL para "Lógica Proposicional". Mais tarde, consideraremos duas linguagens ainda mais simples, PL 'e PL' '.

 Regras de sintaxe e formação de PL

Em qualquer linguagem comum, uma afirmação nunca consistiria em uma única palavra, mas sempre, pelo menos, consistiria em um substantivo ou pronome junto com um verbo. No entanto, uma vez que a lógica proposicional não considera partes menores de declarações e trata declarações simples como partes indivisíveis, a linguagem PL usa letras maiúsculas 'A', 'B', 'C', etc., em lugar de instruções completas. Os sinais lógicos '&', ' v ', '→', '↔' e '¬' são usados ​​no lugar dos operadores verdade-funcionais "e", "ou", "se ... então .. "," se e somente se ", e" não ", respectivamente. Então, considere novamente o seguinte exemplo de argumento, mencionado na Seção I .

Paris é a capital da França e Paris tem uma população de mais de dois milhões. 
Portanto, Paris tem uma população de mais de dois milhões.

Se usarmos a letra "C" como nossa tradução da declaração "Paris é o capitão da França" em PL, e a letra "P" como a nossa tradução da declaração "Paris tem uma população de mais de dois milhões" e usa uma linha horizontal para separar a (s) premissa (s) de um argumento da conclusão, o argumento acima pode ser simbolizado no idioma PL da seguinte maneira:

C & P
P

Além das letras de instruções como 'C' e 'P' e as operadoras, os únicos outros sinais que às vezes aparecem no idioma PL são parênteses que são usados ​​na formação de declarações ainda mais complexas. Considere a frase composta inglesa: "Paris é a cidade mais importante da França se e somente se Paris é a capital da França e Paris tem uma população de mais de dois milhões". Se usarmos a letra "I" na linguagem PL para significar que Paris é a cidade mais importante da França, esta frase seria traduzida para PL da seguinte forma:

I ↔ (C & P)

Os parênteses são usados ​​para agrupar as declarações 'C' e 'P' e diferenciar a declaração acima da que seria escrita da seguinte maneira:

(I ↔ C) & P

Esta última afirmação afirma que Paris é a cidade mais importante da França se e somente se for a capital da França, e (separada disso), Paris tem uma população de mais de dois milhões. A diferença entre os dois é sutil, mas importante logicamente.

É importante descrever a sintaxe e a composição das instruções no idioma PL de forma precisa e dar algumas definições que serão usadas mais tarde. Antes de fazer isso, vale a pena fazer uma distinção entre o idioma em que estaremos discutindo PL, a saber, Inglês, do próprio PL. Sempre que um idioma é usado para discutir outro, o idioma em que a discussão ocorre é chamado de metalinguagem , e o idioma em discussão é chamado de linguagem de objeto. Nesse contexto, o idioma do objeto é o idioma PL, e a metalinguagem é o inglês, ou para ser mais preciso, o inglês complementado com certos dispositivos especiais que são usados ​​para falar sobre linguagem PL. É possível em inglês falar sobre palavras e frases em outras línguas, e quando fazemos, colocamos as palavras ou frases que queremos falar entre aspas. Portanto, usando o inglês comum, posso dizer que "parler" é um verbo francês, e "I & C" é uma declaração da PL. A seguinte expressão faz parte do PL, e não o inglês:

(I ↔ C) & P

No entanto, a seguinte expressão é uma parte do inglês; Em particular, é o nome em inglês de uma sentença PL:

"(I ↔ C) & P"

Este ponto pode parecer bastante trivial, mas é fácil confundir se alguém não for cuidadoso.

Em nossa metalinguagem, também devemos usar certas variáveis ​​que são usadas para representar expressões arbitrárias construídas a partir dos símbolos básicos de PL. No que se segue, as letras gregas 'α', 'β', e assim por diante, são usadas para qualquer expressão de linguagem de objeto (PL) de uma determinada forma designada. Por exemplo, mais tarde, devemos dizer isso, se α for uma declaração de PL, então, então, é ¬α . Observe que 'α' em si não é um símbolo que aparece em PL; é um símbolo usado em inglês para falar sobre símbolos de PL. Também faremos uso dos chamados "Quine corners", escritos ' ' e ' ', que são um dispositivo metalinguístico especial usado para falar sobre expressões de linguagem de objeto construídas de uma certa maneira. Suponha que α seja a afirmação "(I ↔ C)" e β é a declaração "β é a declaração complexa "(I ↔ C) v (P & C)".

Passemos agora a dar certas definições usadas na metalinguagem quando falamos do idioma PL.

Definição : uma letra de declaração de PL é definida como qualquer letra maiúscula escrita com ou sem um subíndice numérico.

Nota: De acordo com esta definição, 'A', 'B', 'B 2 ', 'C 3 ' e 'P 14 ' são exemplos de letras de indicação. Os subíndices numéricos são usados ​​apenas no caso de precisarmos lidar com mais de 26 declarações simples: nesse caso, podemos usar 'P 1 ' para significar algo diferente de 'P 2 ', e assim por diante.

Definição : Um conectivo ou operador de PL é qualquer um dos sinais '¬', '&', ' v ', '→' e '↔'.

Definição : Uma fórmula bem formada (doravante abreviada como wff ) de PL é definida recursivamente da seguinte maneira:

1. Qualquer carta de declaração é uma fórmula bem formada.
2. Se α é uma fórmula bem formada, então então é ¬α .
3. Se α e β são fórmulas bem formadas, então também é (α & β) .
4. Se α e β são fórmulas bem formadas, então é (α v β) .
5. Se α e β são fórmulas bem formadas, então assim é (α → β) .
6. Se α e β são fórmulas bem formadas, então assim é (α ↔ β) .
7. Nada que não possa ser construído por passos sucessivos de (1) - (6) é uma fórmula bem formada.

Nota: De acordo com a parte (1) desta definição, as letras da declaração 'C', 'P' e 'M' são wffs. Porque 'C' e 'P' são wffs, por parte (3), "(C & P)" é um wff. Porque é um wff, e 'M' também é um wff, por parte (6), "(M ↔ (C & P))" é um wff. É convencional considerar os parênteses mais externos em um wff como opcional, de modo que "M ↔ (C & P)" seja tratado como uma forma abreviada de "(M ↔ (C & P))". No entanto, sempre que um wff mais curto é usado na construção de um wff mais complicado, os parênteses no wff mais curto são necessários.

A noção de uma fórmula bem formada deve ser entendida como correspondente à noção de uma declaração gramatical gramaticalmente correta ou devidamente construída. Esta definição nos diz, por exemplo, que "¬ (Q v ¬R)" é gramatical para PL porque é uma fórmula bem formada, enquanto a seqüência de símbolos, ") ¬Q¬ v (↔P &", enquanto consista inteiramente de símbolos usados ​​em PL, não é gramatical porque não está bem formado.

b. Funções de Verdade e Tabelas de Verdade

Até agora, descrevemos, de fato, a gramática da linguagem PL. Ao configurar um idioma completamente, no entanto, é necessário não só estabelecer regras de gramática, mas também descrever os significados dos símbolos usados ​​no idioma. Nós já sugerimos que as letras maiúsculas são usadas como instruções simples completas. Uma vez que a lógica proposicional verdade-funcional não analisa as partes de afirmações simples e considera apenas as formas de combiná-las para formar afirmações mais complicadas que tornem a verdade ou a falsidade total dependente da verdade ou da falsidade das partes, de fato , não importa o significado que atribuimos às letras de indicação individuais como 'P', 'Q' e 'R', etc., desde que cada uma seja tomada como verdadeira ou falsa (e não ambas).

No entanto, é preciso dizer mais sobre o significado ou semântica, dos operadores lógicos '&', ' v ', '→', '↔' e '¬'. Como mencionado acima, estes são usados ​​no lugar das palavras em inglês, 'e', ​​'ou', 'se ... então ...', 'se e somente se', e 'não', respectivamente. No entanto, a correspondência é realmente apenas áspera, porque as operadoras de PL são consideradas inteiramente verdadeiras, enquanto as suas homólogas inglesas nem sempre são usadas verdadeiramente. Considere, por exemplo, as seguintes afirmações:

1. Se Bob Dole é presidente dos Estados Unidos em 2004, o presidente dos Estados Unidos em 2004 é membro do partido republicano.
2. Se Al Gore é presidente dos Estados Unidos em 2004, o presidente dos Estados Unidos em 2004 é membro do partido republicano.

Para aqueles que estão familiarizados com a política americana, é tentador considerar a frase inglesa (1) como verdadeira, mas considerar (2) como falso, uma vez que Dole é republicano, mas Gore não é. Mas observe que, em ambos os casos, a afirmação simples na parte "if" da declaração "if ... then ..." é falsa e a declaração simples na parte "então" da declaração é verdadeira. Isso mostra que o operador inglês "se ... então ..." não é totalmente funcional da verdade. No entanto, todos os operadores da linguagem PL são inteiramente verdadeiros, de modo que o sinal '→', embora parecido de muitas maneiras com o inglês "se ... então ..." não é de todos os modos o mesmo. Mais informações sobre este operador estão abaixo .

Uma vez que nosso estudo se limita às formas pelas quais os valores de verdade de enunciados complexos dependem dos valores de verdade das partes, para cada operador, o único aspecto de seu significado relevante neste contexto é a função verdadeira associada. A função de verdade para um operador pode ser representada como uma tabela, cada uma das quais expressa uma possível combinação de valores de verdade para as instruções mais simples às quais o operador se aplica, juntamente com o valor de verdade resultante para a instrução complexa formada usando o operador.

Os sinais '&', ' v ', '→', '↔', e '¬', correspondem, respectivamente, para as funções de verdade de conjugação , disjunção , implicação material , equivalência de material , e negação . Devemos considerá-los individualmente.

Conjunção: a conjunção de duas afirmações α e β, escrita em PL como(α & β), é verdadeira se ambos α e β são verdadeiros e é falso se α é falso ou β é falso ou ambos são falsos. Com efeito, osignificado do operador '&' pode ser exibido de acordo com o quadro a seguir, que mostra o valor da verdade da conjunção, dependendo das quatro possibilidades dos valores de verdade das partes:

α	β	(α & β)
T  T  F  F	T  F  T  F	T  F  F  F

Conjunção usando o operador '&' é o equivalente bruto do PL do idioma para juntar declarações junto com 'e' em inglês. Em uma declaração da forma (α & β) , as duas instruções juntas, α e β, são chamadas conjuntas , e a declaração completa é chamada de conjunção .

Em vez do sinal '&', alguns outros trabalhos lógicos usam os sinais '∧' ou '•' para a conjunção.

Disjunção: a disjunção de duas instruções α e β, escrita em PL como(α v β), é verdadeira se qualquer α é verdadeiro ou β é verdadeiro, ou ambos α e β são verdadeiros e é falso somente seambos α e β são falsas. Um gráfico semelhante ao dado acima para a conjunção, modificado para mostrar o significado do sinal de disjunção ' v ', seria desenhado da seguinte maneira:

α	β	(α v β)
T  T  F  F	T  F  T  F	T  T  T  F

Este é o equivalente em bruto do PL do idioma de juntar declarações junto com a palavra 'ou' em inglês. No entanto, deve notar-se que o sinal ' v ' é usado para disjunção no sentido inclusivo . Às vezes, quando a palavra 'ou' é usada para unir duas declarações em inglês, consideramos o todo como verdadeiro se um lado ou outro é verdadeiro, mas não ambos, como quando a afirmação " Oupodemos comprar o robô de brinquedo, ou podemos comprar o caminhão de brinquedo, você deve escolher! " é falado por um pai para uma criança que quer ambos os brinquedos. Isso é chamado de sentido exclusivo de 'ou'. No entanto, em PL, o sinal ' v'é usado inclusivamente, e é mais análogo à palavra inglesa' ou 'como aparece em uma declaração como (por exemplo, disse sobre alguém que acabou de receber uma pontuação perfeita no SAT), ou ela estudou muito, ou ela é extremamente brilhante ", o que não significa para excluir a possibilidade de que ela estudou tanto e brilhante. Em uma declaração da forma (α v β) , as duas instruções juntas, α e β, são chamadas de disjunções , e a declaração completa é chamada de disjunção .

Implicação de Material: Esta função de verdade é representada no idioma PL com o sinal '→'. Uma declaração da forma (α → β) é falsa se α é verdadeiro e β é falso e é verdadeiro se α é falso ou β é verdadeiro (ou ambos). Essa função de verdade gera o seguinte gráfico:

α	β	(α → β)
T  T  F  F	T  F  T  F	T  F  T  T

Como a verdade de uma declaração da forma (α → β) exclui a possibilidade de α ser verdadeira e β ser falso, há alguma semelhança entre o operador '→' e a frase em inglês, "se ... então .. . ", que também é usado para excluir a possibilidade de uma afirmação ser verdadeira e outra falsa; no entanto, '→' é usado inteiramente de verdade, funcionalmente e, por razões discutidas anteriormente, não é inteiramente análogo com "se ... então ..." em inglês. Se α for falso, então (α → β) é considerado verdadeiro, seja ou não uma conexão entre a falsidade de α e o valor de verdade de β. Em uma declaração da forma, (α → β) , chamamos α do antecedente , e chamamos de β o conseqüente ,(α → β) às vezes também é chamado de (material) condicional .

O sinal '⊃' às vezes é usado em vez de '→' para implicação material.

Equivalência de material: esta função de verdade é representada no idioma PL com o sinal '↔'. Uma afirmação da forma(α ↔ β)é considerada verdadeira se α e β são ambos verdadeiros ou ambos falsos e são considerados falsos se tiverem diferentes valores de verdade. Por isso, temos o seguinte quadro:

α	β	(α ↔ β)
T  T  F  F	T  F  T  F	T  F  F  T

Uma vez que a verdade de uma declaração da forma (α ↔ β) requer que α e β tenham o mesmo valor de verdade, esse operador é frequentemente comparado com a frase em inglês "... if and only if ...". Novamente, no entanto, eles não são de todos os modos, porque '↔' é usado inteiramente de verdade - funcionalmente. Independentemente do que são α e β, e que relação (se houver) eles têm um ao outro, se ambos são falsos, (α ↔ β) é considerado verdadeiro. No entanto, nós normalmente não consideramos a declaração "Al Gore é o presidente dos Estados Unidos em 2004 se e somente se Bob Dole é o presidente dos Estados Unidos em 2004" como verdade simplesmente porque ambas as declarações mais simples são falsas..

O sinal '≡' às vezes é usado em vez de '↔' para equivalência de material.

Negação: a negação da afirmação α, simplesmente escrita¬na linguagem PL, é considerada verdadeira se α é falso e falso se α é verdadeiro. Ao contrário dos outros operadores que consideramos, a negação é aplicada a uma única declaração. O gráfico correspondente pode, portanto, ser desenhado de forma mais simples da seguinte forma:

α	¬α
T  F	F  T

O sinal de negação '¬' tem semelhanças óbvias com a palavra 'não' usada em inglês, bem como frases similares usadas para mudar uma afirmação de afirmativa para negativa ou vice-versa. Em linguagens lógicas, os sinais '~' ou '-' são às vezes usados ​​no lugar de '¬'.

Os cinco gráficos juntos fornecem as regras necessárias para determinar o valor de verdade de um determinado wff no idioma PL quando dados os valores de verdade das letras de indicação independentes que o compõem. Estas regras são muito fáceis de aplicar no caso de um wff muito simples como "(P & Q)". Suponha que 'P' seja verdadeiro, e 'Q' seja falso; de acordo com a segunda linha do gráfico dado para o operador, '&', podemos ver que esta afirmação é falsa.

No entanto, os gráficos também fornecem as regras necessárias para determinar o valor de verdade de declarações mais complicadas. Acabamos de ver que "(P & Q)" é falso se 'P' for verdadeiro e 'Q' for falso. Considere uma declaração mais complicada que contenha esta declaração como parte, por exemplo, "((P & Q) → ¬R)", e suponha, uma vez mais, que 'P' é verdadeiro e 'Q' é falso e, além disso, suponha que 'R' também é falso. Para determinar o valor da verdade dessa declaração complicada, começamos por determinar o valor da verdade das partes internas. A declaração "(P & Q)", como vimos, é falsa. A outra subestação, "¬R", é verdade, porque 'R' é falso e '¬' inverte o valor de verdade daquele a que é aplicado. Agora, podemos determinar o valor da verdade de todo o wff, "((P & Q) → ¬R)", consultando o gráfico fornecido acima para '→'. Aqui, o wff "(P & Q)" é o nosso α, e "¬R" é o nosso β, e como seus valores de verdade são F e T, respectivamente, consultamos a terceira linha do gráfico, e vemos isso a declaração complexa "((P & Q) → ¬R)" é verdadeira.

Até agora, consideramos o caso em que 'P' é verdadeiro e 'Q' e 'R' são ambos falsos. Há, no entanto, uma série de outras possibilidades em relação aos possíveis valores de verdade das letras da declaração, 'P', 'Q' e 'R'. Existem oito possibilidades, como mostrado na seguinte lista:

P	Q	R
T  T  T  T  F  F  F  F	T  T  F  F  T  T  F  F	T  F  T  F  T  F  T  F

Em termos estritos, cada uma das oito possibilidades acima representa uma atribuição de valor de verdade diferente , que pode ser definida como uma possível atribuição de valores de verdade T ou F às diferentes letras de declaração que compõem um wff ou série de wffs. Se um wff tiver n letras de declaração distintas, o número de possíveis atribuições de valor de verdade é 2 n . Com o wff, "((P & Q) → ¬R)", existem três letras de indicação, 'P', 'Q' e 'R', e, portanto, há 8 atribuições de valor de verdade.

Em seguida, torna-se possível desenhar um gráfico que mostra como o valor de verdade de um wff dado seria resolvido para cada possível atribuição de valor de verdade. Começamos com um gráfico que mostra todas as possíveis atribuições de valor de verdade para o wff, como o indicado acima. Em seguida, escrevemos o próprio wff no canto superior direito do nosso gráfico, com espaços entre os sinais. Então, para cada atribuição do valor da verdade, repetimos o valor de verdade apropriado, 'T' ou 'F', abaixo das letras da declaração, conforme elas aparecem no wff. Então, como os valores de verdade daqueles wffs que são partes do wff completo são determinados, nós escrevemos seus valores de verdade abaixo do sinal lógico que é usado para formá-los. A coluna final preenchida mostra o valor de verdade de toda a declaração para cada atribuição do valor da verdade. Dada a importância desta coluna, destacamos de alguma forma. Aqui, destacamos em amarelo.

P	Q	R	|	((P	&	Q)	→	¬	R)
T  T  T  T  F  F  F  F	T  T  F  F  T  T  F  F	T  F  T  F  T  F  T  F		T  T  T  T  F  F  F  F	T  T  F  F  F  F  F  F	T  T  F  F  T  T  F  F	F  T  T  T  T  T  T  T	F  T  F  T  F  T  F  T	T  F  T  F  T  F  T  F

Gráficos como o indicado acima são chamados de tabelas de verdade . Na lógica clássica proposicional verdade-funcional, uma tabela de verdade construída para um dado efeito, revela tudo o que é lógico importante sobre esse wff. O gráfico acima nos diz que o wff "((P & Q) → ¬R)" só pode ser falso se 'P', 'Q' e 'R' forem verdadeiros, e é verdade, caso contrário.

c. Definição dos Operadores e dos Idiomas PL 'e PL' '

O idioma PL, como vimos, contém operadores que são grosso modo análogos aos operadores ingleses e "," ou "," se ... então ... "," se e somente se "e" não ". Cada um desses, como também vimos, pode ser pensado como representando uma certa função de verdade. Pode-se objetar, no entanto, que existem outros métodos de combinação de declarações em que o valor da verdade da afirmação depende inteiramente dos valores da verdade das partes, ou, em outras palavras, que existam funções de verdade além da conjunção ( inclusiva) disjunção, implicação material, equivalência de material e negação. Por exemplo, observamos anteriormente que o sinal ' v ' é usado de forma análoga a 'ou' no sentido inclusivo ,. Pode-se pensar, no entanto, que o langauge PL está incompleto sem a adição de um símbolo adicional, diga ' v ', de modo que (α v β) seja considerado verdadeiro se α for verdadeiro e β for falso ou α seja falso e β é verdadeiro, mas seria considerado falso se tanto α como β forem verdadeiros ou ambos, α e β sejam falsos.

No entanto, uma possível resposta a esta objeção seria notar que, embora o idioma PL não inclua um sinal simples para este exclusivo senso de disjunção, é possível, usando os símbolos incluídos na PL, construir uma declaração verdadeira exatamente nas mesmas circunstâncias. Considere, por exemplo, uma declaração da forma, ¬ (α ↔ β) . É facilmente mostrado, usando uma tabela de verdade, que qualquer wff dessa forma teria o mesmo valor de verdade que uma declaração de potencial usando o operador ' v '. Veja o quadro a seguir:

α	β	|	¬	(α	↔	β)
T  T  F  F	T  F  T  F		F  T  T  F	T  T  F  F	T  F  F  T	T  F  T  F

Aqui vemos que um wff da forma ¬ (α ↔ β) é verdadeiro se α ou β é verdadeiro, mas não ambos. Isso mostra que PL não está faltando de forma alguma ao não conter um sinal ' v '. Todo o trabalho que alguém gostaria de fazer com este sinal pode ser feito usando os sinais '↔' e '¬'. Na verdade, pode-se afirmar que o sinal ' v ' pode ser definido em termos dos sinais '↔' e '¬', e então use a forma (α v β) como abreviatura de um wff da forma ¬ (α ↔ β) , sem expandir o vocabulário primitivo do idioma PL.

Os sinais '&', ' v ', '→', '↔' e '¬', foram escolhidos como operadores para incluir em PL porque eles correspondem (grosso modo) ao tipo de operadores verdade-funcionais que são mais freqüentemente usados ​​em discurso e raciocínio ordinários. No entanto, dada a discussão anterior, é natural perguntar se alguns operadores dessa lista podem ou não ser definidos em termos de outros. Acontece que eles podem. De fato, se, por algum motivo, desejássemos que nosso linguagem lógica tenha um vocabulário mais limitado, é possível obter usando apenas os sinais '¬' e '→', e definir todas as outras possíveis funções de verdade em virtude delas. Considere, por exemplo, a seguinte tabela de verdade para declarações da forma ¬ (α → ¬β) :

α	β	|	¬	(α	→	¬	β)
T  T  F  F	T  F  T  F		T  F  F  F	T  T  F  F	F  T  T  T	F  T  F  T	T  F  T  F

Podemos ver do acima que um wff da forma ¬ (α → ¬β) sempre tem o mesmo valor de verdade que a declaração correspondente da forma (α & β) . Isso mostra que o sinal '&' pode, de fato, ser definido usando os sinais '¬' e '→'.

Em seguida, considere a tabela de verdade para declarações do formulário (¬α → β) :

α	β	|	(¬	α	→	β)
T  T  F  F	T  F  T  F		F  F  T  T	T  T  F  F	T  T  T  F	T  F  T  F

Aqui podemos ver que uma declaração da forma (¬α → β) sempre tem o mesmo valor de verdade que a declaração correspondente da forma (α v β) . Mais uma vez, isso mostra que o sinal ' v ' poderia, de fato, ser definido usando os sinais '→' e '¬'.

Por último, considere a tabela de verdade para uma declaração da forma ¬ ((α → β) → ¬ (β → α)) :

α	β	|	¬	((α	→	β)	→	¬	(p	→	α))
T  T  F  F	T  F  T  F		T  F  F  T	T  T  F  F	T  F  T  T	T  F  T  F	F  T  T  F	F  F  T  F	T  F  T  F	T  T  F  T	T  T  F  F

Do acima, vemos que uma declaração da forma ¬ ((α → β) → ¬ (β → α)) sempre tem o mesmo valor de verdade que a declaração correspondente da forma (α ↔ β) . Na verdade, portanto, mostramos que os demais operadores de PL podem ser definidos em virtude de '→' e '¬', e que, se desejássemos, pudéssemos acabar com os operadores, '&', ' v 'e' ↔ ', e simplesmente fazer com essas expressões equivalentes construídas inteiramente de' → 'e' ¬ '.

Vamos chamar o idioma resultante dessa PL de simplicidade. Embora a definição de uma letra de declaração permaneça igual para PL 'como para PL, a definição de uma fórmula bem formada (wff) para PL' pode ser bastante simplificada. Com efeito, pode-se afirmar o seguinte:

Definição : Uma fórmula bem formada (ou wff ) de PL 'é definida recursivamente da seguinte maneira:

1. Qualquer carta de declaração é uma fórmula bem formada.
2. Se α é uma fórmula bem formada, então então é ¬α .
3. Se α e β são fórmulas bem formadas, então assim é (α → β) .
4. Nada que não possa ser construído por passos sucessivos de (1) - (3) é uma fórmula bem formada.

Estritamente falando, então, o lang 'PL' não contém nenhuma declaração usando os operadores ' v', '&', ou '↔'. No entanto, pode-se utilizar convenções que, na linguagem PL ', uma expressão da forma (α & β) seja considerada uma mera abreviatura ou mão curta para a declaração correspondente da forma ¬ (α → ¬β) e, de forma semelhante, as expressões das formas (α v β) e (α ↔ β) devem ser consideradas abreviaturas das expressões das formas (¬α → β) ou ¬ ((α → β) → ¬ (β → α )), respectivamente. Com efeito, isso significa que é possível traduzir qualquer wff do idioma PL em um equivalente wff do idioma PL '.

Na Seção VII , está comprovado que não só os "¬ 'e' → 'dos ​​operadores são suficientes para definir cada operador funcional da verdade incluído na linguagem PL, mas também que são suficientes para definir qualquer operador imaginável verdade-funcional em proposicional clássico lógica.

No entanto, a escolha de '¬' e '→' para os sinais primitivos utilizados na linguagem PL 'é, até certo ponto, arbitrária. Também teria sido possível definir todos os outros operadores de PL (incluindo '→') usando os sinais '¬' e ' v '. Nesta abordagem, (α & β) seria definido como ¬ (¬α v ¬β) , (α → β) seria definido como (¬α v β) , e (α ↔ β) seria definido como ¬ ( ¬ (¬α v β) v ¬ (¬β v α)) . Da mesma forma, poderíamos ter começado com '¬' e 'e' como nossos operadores iniciais. Por esta forma de proceder,β) seria definido como ¬ (¬α & ßβ) , (α → β) seria definido como ¬ (α & ßβ) e (α ↔ β) seria definido como (¬ (α & ¬β) & ¬ (β & ¬α) .

Há, como vimos, múltiplas formas diferentes de reduzir todos os operadores funcionais da verdade até duas primitivas. Há também duas maneiras de reduzir todos os operadores funcionais da verdade para um único operador primitivo, mas eles precisam usar um operador que não esteja incluído no idioma PL como primitivo. Em uma abordagem, utilizamos um operador escrito '|', e explicamos a função de verdade correspondente a este sinal por meio do seguinte gráfico:

α	β	(α | β)
T  T  F  F	T  F  T  F	F  T  T  T

Aqui podemos ver que uma declaração da forma (α | β) é falsa se tanto α como β são verdadeiros e verdade de outra forma. Por esta razão, pode-se ler '|' parecido com a expressão inglesa, "Nem ambos ... e ...". Na verdade, é possível representar esta função de verdade na linguagem PL usando uma expressão da forma, ¬ (α & β) . No entanto, uma vez que é nossa intenção mostrar que todos os outros operadores verdade-funcionais, incluindo '¬' e '&', podem ser derivados de '|', é melhor não considerar os significados de '¬' e 'e' como desempenhando uma parte do significado de '|', e, em vez disso, tente (por mais contraditória que possa parecer) considerar '|' como conceitualmente antes de '¬' e '&'.

O sinal '|' é chamado de golpe de Sheffer , e tem o nome de HM Sheffer, que publicou pela primeira vez o resultado de que todos os conectivos verdade-funcionais poderiam ser definidos em virtude de um único operador em 1913.

Podemos então ver que o "e" conectivo pode ser definido em virtude de '|', porque uma expressão da forma ((α | β) | (α | β)) gera a seguinte tabela de verdade e, portanto, é equivalente a a expressão correspondente da forma (α & β) :

α	β	|	(( α	|	β)	|	( α	|	β))
T  T  F  F	T  F  T  F		T  T  F  F	F  T  T  T	T  F  T  F	T  F  F  F	T  T  F  F	F  T  T  T	T  F  T  F

Da mesma forma, podemos definir o operador ' v ' usando '|' ao notar que uma expressão da forma ((α | α) | (β | β)) sempre tem o mesmo valor de verdade que a declaração correspondente da forma (α v β) :

α	β	|	(( α	|	α)	|	( p	|	β))
T  T  F  F	T  F  T  F		T  T  F  F	F  F  T  T	T  T  F  F	T  T  T  F	T  F  T  F	F  T  F  T	T  F  T  F

A seguinte tabela de verdade mostra que uma declaração da forma (α | (β | β)) sempre tem a mesma tabela de verdade como uma declaração da forma (α → β) :

α	β	|	(α	|	( p	|	β))
T  T  F  F	T  F  T  F		T  T  F  F	T  F  T  T	T  F  T  F	F  T  F  T	T  F  T  F

Embora longe de ser intuitivamente óbvio, a tabela a seguir mostra que uma expressão da forma (((α | α) | (β | β)) | (α | β)) sempre tem o mesmo valor de verdade que o wff correspondente do forma (α ↔ β) :

α

β

|

(((α

|

α)

|

(p

|

β))

|

(α

|

β))

T T  F  F

T  F  T  F

T  T  F  F

F  F  T  T

T  T  F  F

T  T  T  F

T  F  T  F

F  T  F  T

T  F  T  F

T  F  F  T

T  T  F  F

F  T  T  T

T  F  T  F

Isso deixa apenas o sinal '¬', que é talvez o mais fácil de definir usando '|', como claramente (α | α) , ou, grosso modo, "não ambos α e α", tem o valor de verdade oposto de α em si :

α	|	(α	|	α)
T F		T  F	F  T	T  F

Se, portanto, desejamos uma linguagem para o uso no estudo da lógica proposicional que possua um vocabulário tão pequeno quanto possível, sugerimos usar uma linguagem que empregue o sinal '|' como seu único operador primitivo, e define todos os outros operadores verdade-funcionais em virtude dele. Deixe-nos chamar uma linguagem PL ''. PL '' difere PL e PL 'apenas porque a definição de uma fórmula bem formada pode ser simplificada ainda mais:

Definição : Uma fórmula bem formada (ou wff ) de PL '' é definida recursivamente da seguinte maneira:

1. Qualquer carta de declaração é uma fórmula bem formada.
2. Se α e β são fórmulas bem formadas, então assim é (α | β) .
3. Nada que não possa ser construído por passos sucessivos de (1) - (2) é uma fórmula bem formada.

Na linguagem PL '', estritamente falando, '|' é o único operador. No entanto, por razões que deveriam ser claras a partir do acima, qualquer expressão do idioma PL que envolve qualquer ¬ ',' e ',' v ',' → 'ou' ↔ ' dos operadores pode ser traduzida para o idioma PL' "sem a perda de nenhuma das suas importantes propriedades lógicas. Com efeito, as declarações que usam esses sinais podem ser consideradas abreviaturas ou expressões taquigráficas para wffs de PL '' que usam apenas o operador '|'.

Mesmo aqui, a escolha de '|' Como o único primitivo é, em certa medida, arbitrário. Também seria possível reduzir todos os operadores verdade-funcionais para um único primitivo, fazendo uso de um sinal '↓', tratando-o como equivalente ao equivalente em inglês, "nem ... nem ...", então o gráfico correspondente seria desenhado da seguinte forma:

α	β	(α ↓ β)
T  T  F  F	T  F  T  F	F  F  F  T

Se usássemos '↓' como nosso único operador, poderíamos novamente definir todos os outros. ¬α seria definido como (α ↓ α) ; (α v β) seria definido como ((α ↓ β) ↓ (α ↓ β)) ; (α & β) seria definido como ((α ↓ α) ↓ (β ↓ β)) ; e de forma semelhante para os outros operadores. O sinal '↓' às vezes também é referido como o golpe de Sheffer , e também é chamado de punhal Peirce / Sheffer.

Dependendo dos propósitos de alguém ao estudar lógica proposicional, às vezes faz sentido usar uma linguagem rica como PL com operadores mais primitivos e às vezes faz sentido usar uma linguagem relativamente esparsa, como PL 'ou PL' ', com menos operadores primitivos. A vantagem da abordagem anterior é que ela está em conformidade melhor com nossos hábitos comuns de pensamento e raciocínio; A vantagem deste último é que ele simplifica a linguagem lógica, o que torna mais fáceis de provar certos resultados interessantes quanto aos sistemas dedutivos que fazem uso do idioma.

Para o restante deste artigo, devemos principalmente estar preocupados com as propriedades lógicas das declarações formadas no PL mais rico. No entanto, devemos considerar um sistema que utilize o idioma PL 'com algum detalhe na Seção VI , e também deve fazer uma breve menção de um sistema que usa o idioma PL' '.

4. Tautologias, Equivalência Lógica e Validade

A lógica proposicional da verdade-funcional se preocupa apenas com as formas de combinar declarações para formar afirmações mais complicadas, nas quais os valores de verdade das enunciadas complicadas dependem inteiramente dos valores da verdade das partes. Devido a isso, todas essas características de uma afirmação complexa que são estudadas na lógica proposicional derivam da maneira como seus valores de verdade são derivados daqueles de suas partes. Essas características são, portanto, sempre representadas na tabela de verdade para uma determinada declaração.

Algumas declarações complexas têm a característica interessante de que elas seriam verdadeiras, independentemente dos valores de verdade das declarações simples que as preparem. Um exemplo simples seria o wff "P v ¬P"; ou seja, "P ou não P". É bastante fácil ver que essa afirmação é verdadeira independentemente de "P" ser verdadeira ou 'P' é falso. Isso também é mostrado pela sua tabela de verdade:

P	|	P	v	¬	P
T F		T  F	T  T	F  T	T  F

No entanto, existem declarações para as quais isso é verdade, mas não é tão óbvio. Considere o wff, "R → ((P → Q) v ¬ (R → Q))". Isso também é tão verdadeiro, independentemente dos valores de verdade de 'P', 'Q' e 'R'.

P

Q

R

|

R

→

((P

→

Q)

v

¬

(R

→

Q))

T  T  T  T  F  F  F  F

T  T  F  F  T  T  F  F

T  F  T  F  T  F  T  F

T  F  T  F  T  F  T  F

T  T  T  T  T  T  T  T

T  T  T  T  F  F  F  F

T  T  F  F  T  T  T  T

T  T  F  F  T  T  F  F

T  T  T  F  T  T  T  T

F  F  T  F  F  F  T  F

T  F  T  F  T  F  T  F

T  T  F  T  T  T  F  T

T  T  F  F  T  T  F  F

As declarações que possuem essa característica interessante são chamadas de tautologias . Vamos definir essa noção com precisão.

Definição: um wff é uma tautologia se e somente se for verdade para todas as atribuições possíveis de valor de verdade para as letras da instrução que compõem.

As tautologias também são às vezes chamadas de verdades lógicas ou verdades da lógica porque as tautologias podem ser reconhecidas como verdadeiras unicamente em virtude dos princípios da lógica proposicional e sem recorrer a qualquer informação adicional.

Do outro lado do espectro, as tautologias são declarações que são falsas, independentemente dos valores de verdade das declarações simples que as compõem. Um exemplo simples de tal afirmação seria o wff "P & ¬P"; claramente, tal afirmação não pode ser verdadeira, já que ela se contradiz. Isso é revelado pela sua tabela de verdade:

P	|	P	&	¬	P
T F		T  F	F  F	F  T	T  F

Para indicar isso precisamente:

Definição: um wff é uma auto-contradição se e somente se for falso para todas as possíveis atribuições de valores de verdade para as letras da instrução que o compõem.

Outro, mais interessante, o exemplo de uma auto-contradição é a afirmação "¬ (P → Q) & ¬ (Q → P)"; Isso não é tão obviamente contraditório. No entanto, podemos ver que é quando consideramos sua tabela de verdade:

P	Q	|	¬	(P	→	Q)	&	¬	(Q	→	P)
T T  F  F	T  F  T  F		F  T  F  F	T  T  F  F	T  F  T  T	T  F  T  F	F  F  F  F	F  F  T  F	T  F  T  F	T  T  F  T	T  T  F  F

Uma afirmação que não é autocontraditória nem tautológica é chamada de declaração contingente. Uma afirmação contingente é verdadeira para algumas atribuições de valores de verdade para suas cartas de declaração e falsas para outros. A tabela de verdade para uma declaração contingente revela quais atribuições de valor de verdade tornam-se verdadeiras e que tornam-se falsas. Considere a tabela de verdade para a afirmação "(P → Q) & (P → ¬Q)":

P	Q	|	(P	→	Q)	&	(P	→	¬	Q)
T T  F  F	T  F  T  F		T  T  F  F	T  F  T  T	T  F  T  F	F  F  T  T	T  T  F  F	F  T  T  T	F  T  F  T	T  F  T  F

Podemos ver isso das quatro possíveis atribuições de valores de verdade para esta afirmação, duas tornam-se verdadeiras e duas tornam-se falsas. Especificamente, a afirmação é verdadeira quando 'P' é falso e 'Q' é verdadeiro e quando 'P' é falso e 'Q' é falso, e a declaração é falsa quando 'P' é verdadeiro e 'Q' é verdadeiro e quando 'P' é verdadeiro e 'Q' é falso.

As tabelas de verdade também são úteis para estudar relacionamentos lógicos que possuem entre duas ou mais declarações. Por exemplo, duas declarações são ditas consistentes quando é possível que ambas sejam verdadeiras, e são consideradas inconsistentes quando não é possível que ambas sejam verdadeiras. Na lógica proposicional, podemos tornar isso mais preciso da seguinte forma.

Definição: dois wffs são consistentes se e somente se houver pelo menos uma possível atribuição de valor de verdade para as letras da instrução que os compõem, o que faz ambos os wffs serem verdadeiros.

Definição: dois wffs são inconsistentes se e somente se não houver nenhuma atribuição de valor de verdade para as letras da instrução que as compõem, o que as torna ambas verdadeiras.

Seja ou não duas declarações consistentes podem ser determinadas por meio de uma tabela de verdade combinada para as duas declarações. Por exemplo, as duas instruções, "P v Q" e "¬ (P ↔ ¬Q)" são consistentes:

P	Q	|	P	v	Q		¬	(P	↔	¬	Q)
T T  F  F	T  F  T  F		T  T  F  F	T  T  T  F	T  F  T  F		T  F  F  T	T  T  F  F	F  T  T  F	F  T  F  T	T  F  T  F

Aqui, vemos que há uma atribuição de valor de verdade, na qual tanto P 'quanto' Q 'são verdadeiros, o que torna "P v Q" e "¬ (P ↔ ¬Q)" verdade. No entanto, as declarações "(P → Q) & P" e "¬ (Q v ¬P)" são inconsistentes, porque não existe uma atribuição de valor verdadeiro em que ambos saem como verdadeiros.

P

Q

|

(P

→

Q)

&

P

¬

(Q

v

¬

P))

T T  F  F

T  F  T  F

T  T  F  F

T  F  T  T

T  F  T  F

T  F  F  F

T  T  F  F

F  T  F  F

T  F  T  F

T  F  T  T

F  F  T  T

T  T  F  F

Outro relacionamento que pode manter entre duas declarações é o de ter o mesmo valor de verdade, independentemente dos valores de verdade das declarações simples que os compõem. Considere uma tabela de verdade combinada para os wffs "¬P → ¬Q" e "¬ (Q & ¬P)":

P

Q

|

¬

P

→

¬

Q

¬

(Q

&

¬

P))

T T  F  F

T  F  T  F

F  F  T  T

T  T  F  F

T  T  F  T

F  T  F  T

T  F  T  F

T  T  F  T

T  F  T  F

F  F  T  F

F  F  T  T

T  T  F  F

Aqui vemos que essas duas declarações têm necessariamente o mesmo valor de verdade.

Definição: duas declarações são ditas serem logicamente equivalentes se e somente se todas as possíveis atribuições de valores de verdade às letras de instruções que as compõem resultam nos mesmos valores de verdade resultantes para todas as declarações.

As declarações acima são logicamente equivalentes. No entanto, a tabela de verdade apresentada acima para as afirmações "P v Q" e "¬ (P ↔ ¬Q)" mostram que eles, por outro lado, não são logicamente equivalentes, porque diferem em valor de verdade para três dos quatro possíveis atribuições de valores de verdade.

Finalmente, e talvez o mais importante, tabelas de verdade podem ser utilizadas para determinar se um argumento é ou não logicamente válido. Em geral, um argumento é dito ser logicamente válido sempre que tiver uma forma que impossibilite a conclusão de ser falso se as premissas forem verdadeiras. (Veja a entrada de enciclopédia sobre " Validade e solidez ".) Na lógica proposicional clássica, podemos dar uma caracterização mais precisa.

Definição: um wff β é dito ser uma conseqüência lógica de um conjunto de wffs α 1 , α 2 , ..., α n , se e somente se não houver atribuição de valor de verdade para as letras de instrução que compõem estas wffs que faz tudo de α 1 , α 2 , ..., α n verdadeiro, mas não faz β true.

Um argumento é logicamente válido se e somente se sua conclusão for uma conseqüência lógica de suas premissas. Se um argumento cuja conclusão é β e cuja única premissa é α é logicamente válido, então, α é dito que implica logicamente β.

Por exemplo, considere o seguinte argumento:

P → Q 
¬Q → P
Q

Podemos testar a validade desse argumento construindo uma tabela de verdade combinada para as três declarações.

P

Q

|

P

→

Q

¬

Q

→

P

Q

T T  F  F

T  F  T  F

T  T  F  F

T  F  T  T

T  F  T  F

F  T  F  T

T  F  T  F

T  T  T  F

T  T  F  F

T  F  T  F

Aqui vemos que ambas as premissas são verdadeiras no caso em que tanto P 'quanto' Q 'são verdadeiros, e em que' P 'é falso, mas' Q 'é verdade. No entanto, nesses casos, a conclusão também é verdadeira. É possível que a conclusão seja falsa, mas somente se uma das premissas for falsa também. Assim, podemos ver que a inferência representada por este argumento é preservar a verdade. Contraste isso com o seguinte exemplo:

P → Q
¬Q v ¬P

Considere a atribuição do valor da verdade, tornando ambos 'P' e 'Q' verdadeiros. Se devêssemos preencher essa linha do valor de verdade para essas afirmações, veríamos que "P → Q" aparece como verdadeiro, mas "¬Q v ¬P" aparece como falso. Mesmo que 'P' e 'Q' não sejam realmente verdadeiros, é possível que ambos sejam verdadeiros, e essa forma de raciocínio não é verdadeira. Em outras palavras, o argumento não é logicamente válido, e sua premissa não implica logicamente sua conclusão.

Uma das características mais marcantes das tabelas de verdade é que eles fornecem um procedimento eficaz para determinar a verdade lógica, ou tautologia de qualquer wff e para determinar a validade lógica de qualquer argumento escrito no idioma PL. O procedimento para a construção de tais tabelas é puramente rote, e enquanto o tamanho das tabelas cresce exponencialmente com o número de letras de indicação envolvidas no wff (s) em consideração, o número de linhas é sempre finito e, portanto, é, em princípio, possível termine a mesa e determine uma resposta definitiva. Em suma, a lógica proposicional clássica é decidível .

5. Dedução: regras de inferência e substituição

uma. Dedução Natural

As tabelas de verdade, como vimos, podem teoricamente ser usadas para resolver qualquer questão na lógica clássica proposicional verdade-funcional. No entanto, esse método tem suas desvantagens. O tamanho das tabelas cresce exponencialmente com o número de letras de declaração distintas que compõem as declarações envolvidas. Além disso, as tabelas de verdade são estranhas aos nossos padrões de raciocínio normais. Existe outro método para estabelecer a validade de um argumento que não possui essas desvantagens: o método de dedução natural. Na dedução natural, é feita uma tentativa de reduzir o raciocínio por trás de um argumento válido para uma série de etapas, cada uma das quais é intuitivamente justificada pelas premissas do argumento ou etapas anteriores na série.

Considere o seguinte argumento indicado em linguagem natural:

Ou a pele de gato ou peles de cachorro foi encontrada na cena do crime. Se o pêlo de cachorro fosse encontrado na cena do crime, o oficial Thompson teve um ataque de alergia. Se a pele do gato foi encontrada na cena do crime, então Macavity é responsável pelo crime. Mas o oficial Thompson não teve um ataque de alergia, e, portanto, Macavity deve ser responsável pelo crime.

A validade deste argumento pode ser mais evidente ao representar a cadeia de raciocínio que leva das premissas à conclusão:

1. Ou a pele do gato foi encontrada na cena do crime, ou a pele do cachorro foi encontrada na cena do crime. (Premissa)
2. Se o pêlo de cachorro fosse encontrado na cena do crime, o oficial Thompson teve um ataque de alergia. (Premissa)
3. Se a pele do gato foi encontrada na cena do crime, então Macavity é responsável pelo crime. (Premissa)
4. O agente Thompson não teve um ataque de alergia. (Premissa)
5. O pêlo de cachorro não foi encontrado na cena do crime. (Siga de 2 e 4.)
6. Pele de gato foi encontrada no local do crime. (Siga de 1 e 5.)
7. Macavity é responsável pelo crime. (Conclusão. Seguem de 3 e 6.)

Acima, não saltamos diretamente das premissas para a conclusão, mas mostre como as inferências intermediárias são usadas para finalmente justificar a conclusão por uma cadeia passo a passo. Cada passo na cadeia representa uma forma de raciocínio simples e obviamente válida. Neste exemplo, a forma de raciocínio exemplificada na linha 5 é chamada de modus tollens , que envolve deduzir a negação do antecedente de um condicional do condicional e a negação de seu consequente. A forma de raciocínio exemplificada na etapa 5 é chamada de silogismo disjuntivo e envolve a dedução de um desajuste de uma disjunção com base na disjunção e na negação do outro disjuntivo. Por fim, a forma de raciocínio encontrada na linha 7 é chamada de modus ponens, o que implica deduzir a verdade do conseqüente de uma verdade condicional dada tanto do condicional quanto do antecedente. "Modus ponens" é latino para o modo de afirmação, e "modus tollens" é latino para o modo de negação .

Um sistema de dedução natural consiste na especificação de uma lista de regras de inferência intuitivamente válidas para a construção de derivações ou deduções passo a passo. Muitos sistemas equivalentes de dedução foram dados para a lógica proposicional clássica verdade-funcional. No que se segue, esboçamos um sistema, que é derivado do livro de texto popular de Irving Copi (1953). O sistema faz uso do idioma PL.

• 
  CLIQUE AQUI PARA ACESSAR A [ PARTE 2 ]