Todos os termos que a calculadora, os guias e os exercícios usam, definidos num só lugar.
Procure um termo, veja a sua notação e abra o exemplo na calculadora para o ver a funcionar. Os termos definidos aqui são destacados na primeira vez que aparecem num guia.
Os 62 termos
O estudo de que conclusões decorrem realmente de que pressupostos.
A lógica estuda a forma do raciocínio, não o seu conteúdo. A lógica formal substitui frases por símbolos, de modo que saber se uma conclusão decorre se decide apenas pela forma do argumento e se verifica mecanicamente.
Um enunciado que é verdadeiro ou falso, mas não ambos.
Uma proposição é um enunciado declarativo com exatamente um valor de verdade. «Está a chover» é uma proposição; uma pergunta ou uma ordem não é, porque nelas não há nada que seja verdadeiro ou falso.
Um dos dois valores que uma proposição pode tomar: verdadeiro ou falso.
A lógica clássica atribui a cada proposição exatamente um de dois valores de verdade, escritos ⊤ e ⊥ (ou 1 e 0). Cada linha de uma tabela de verdade é uma atribuição de valores às variáveis e o resultado que a fórmula aí toma.
Uma proposição que não contém nenhum conectivo.
Uma proposição atómica não se decompõe em proposições menores: não tem negação, conjunção nem qualquer outro conectivo. Tudo o resto é composto, construído a partir de átomos, e o seu valor de verdade depende do deles.
Uma letra como p ou A que representa uma proposição qualquer.
Uma variável proposicional é um marcador para qualquer proposição. A calculadora aceita letras isoladas como variáveis e dá a cada uma uma coluna da tabela de verdade, com uma linha para cada combinação possível de valores.
Na calculadorap → qUma cadeia de símbolos que a gramática da linguagem realmente permite.
Uma fórmula bem formada constrói-se pelas regras: uma variável é uma, e também o é qualquer fórmula obtida de outras menores por um conectivo. «p ∧ ∨ q» não é, e por isso a calculadora assinala um erro em vez de adivinhar.
Uma atribuição de valores de verdade a todas as variáveis de uma fórmula.
Uma interpretação diz quanto vale cada variável e fixa assim o valor da fórmula inteira. Uma fórmula com n variáveis tem 2ⁿ interpretações, que são exatamente as linhas da sua tabela de verdade.
Um conjunto de premissas apresentadas em apoio de uma conclusão.
Um argumento afirma que a sua conclusão decorre das premissas. Escreva-o na calculadora com um traço de asserção — premissas antes, conclusão depois — e cada linha será verificada à procura de um caso em que as premissas valem e a conclusão falha.
Na calculadorap → q, p ⊨ qUm enunciado que um argumento supõe para chegar à conclusão.
As premissas são o ponto de partida de um argumento. A validade pergunta apenas se a conclusão vale onde todas as premissas valem; se estas são de facto verdadeiras é outra questão, a que a solidez acrescenta.
Na calculadorap → q, p ⊨ qO enunciado que um argumento procura estabelecer.
A conclusão é aquilo que as premissas apoiam. Na calculadora é a expressão a seguir ao traço de asserção, e um argumento é válido quando nenhuma interpretação torna as premissas verdadeiras e a conclusão falsa.
Na calculadorap → q, p ⊨ qUm símbolo que constrói uma proposição composta a partir de outras.
Um conectivo como ¬, ∧, ∨, → ou ↔ combina proposições numa maior cujo valor de verdade depende apenas dos delas. É essa dependência que uma tabela de verdade regista, uma linha por combinação de entradas.
Inverte um valor de verdade: ¬p é verdadeira exatamente quando p é falsa.
A negação é o único conectivo unário da lógica proposicional. Escrita ¬p, ~p ou !p, transforma o verdadeiro em falso e o falso em verdadeiro, pelo que negar duas vezes devolve a proposição original.
Na calculadora¬pVerdadeira só quando ambas as partes são verdadeiras: p ∧ q.
Uma conjunção afirma as duas partes. É verdadeira em exatamente uma linha da sua tabela de verdade — aquela em que ambas as partes são verdadeiras — o que a torna o mais estrito dos conectivos binários.
Na calculadorap ∧ qVerdadeira quando pelo menos uma parte é verdadeira: p ∨ q.
Em lógica a disjunção é inclusiva: p ∨ q é verdadeira quando p é verdadeira, quando q é verdadeira e quando ambas o são. A leitura exclusiva de «ou», verdadeira só se as partes diferirem, é um conectivo distinto.
Na calculadorap ∨ qVerdadeira quando exatamente uma das duas proposições é verdadeira.
A disjunção exclusiva, escrita ⊕ ou XOR, vale quando as suas partes diferem e falha quando coincidem. É a negação do bicondicional e pode escrever-se como (p ∨ q) ∧ ¬(p ∧ q).
Na calculadora(p ∨ q) ∧ ¬(p ∧ q)p → q, falso apenas quando p é verdadeira e q é falsa.
O condicional material não diz mais do que «não acontece: antecedente verdadeiro e consequente falso», pelo que vale automaticamente sempre que o antecedente falha. Por isso p → q equivale a ¬p ∨ q.
Na calculadorap → qp ↔ q, verdadeiro quando as duas partes têm o mesmo valor de verdade.
O bicondicional afirma cada lado sob a condição do outro: é verdadeiro quando ambas as partes são verdadeiras e quando ambas são falsas. Um bicondicional que é uma tautologia exprime exatamente uma equivalência lógica.
Na calculadorap ↔ qA parte «se» de um condicional: o p em p → q.
O antecedente é a condição de que um condicional depende. Quando é falso, o condicional inteiro é verdadeiro seja qual for o consequente, e daí vêm quase todas as surpresas da tabela de →.
Na calculadorap → qA parte «então» de um condicional: o q em p → q.
O consequente é o que um condicional afirma que se segue se o seu antecedente valer. Um consequente verdadeiro torna o condicional verdadeiro, mas não torna o antecedente verdadeiro: inferi-lo é uma falácia formal.
Na calculadorap → qO condicional com as duas partes trocadas: q → p.
A recíproca de p → q é q → p, e as duas não são equivalentes: a calculadora encontra uma linha em que uma vale e a outra falha. Tratá-las como intercambiáveis é afirmar o consequente.
Na calculadoraq → p¬q → ¬p, que tem sempre o mesmo valor de verdade que p → q.
A contrarrecíproca nega as duas partes de um condicional e troca-as. Ao contrário da recíproca, é genuinamente equivalente ao original, e é isso que torna legítima a demonstração por contraposição em matemática.
Na calculadora(p → q) ≡ (¬q → ¬p)A negação de uma conjunção: verdadeira exceto se ambas as entradas o forem.
NAND, escrito ↑, é ¬(p ∧ q). É funcionalmente completo: qualquer outro conectivo pode ser construído apenas com NAND, o que faz dele uma peça central do projeto de circuitos digitais.
Na calculadora¬(p ∧ q)A negação de uma disjunção: verdadeira só se ambas as entradas forem falsas.
NOR, escrito ↓, é ¬(p ∨ q). Como o NAND, é funcionalmente completo por si só, pelo que um circuito pode ser construído inteiramente com portas NOR e mais nada.
Na calculadora¬(p ∨ q)Que conectivo se aplica primeiro quando faltam parênteses.
A negação liga mais forte, depois a conjunção, a disjunção, o condicional e por fim o bicondicional. Assim ¬p ∧ q ∨ r lê-se ((¬p) ∧ q) ∨ r; os parênteses alteram essa ordem sempre que a leitura pretendida é outra.
Na calculadora¬p ∧ q ∨ rUma linha por atribuição de valores, com o valor da fórmula em cada uma.
Uma tabela de verdade lista todas as 2ⁿ interpretações das n variáveis de uma fórmula e calcula o seu valor em cada uma. Sendo exaustiva, resolve toda a questão semântica da lógica proposicional: equivalência, validade, satisfazibilidade e as restantes.
Na calculadorap → qUma fórmula verdadeira sob qualquer interpretação.
Uma tautologia é verdadeira em todas as linhas da sua tabela de verdade, pelo que nada diz sobre o mundo: p ∨ ¬p é verdadeira valha o que valer p. Duas fórmulas são equivalentes exatamente quando o bicondicional entre elas é uma tautologia.
Na calculadorap ∨ ¬pUma fórmula falsa sob qualquer interpretação.
Uma contradição como p ∧ ¬p é falsa em todas as linhas da sua tabela de verdade. Derivar uma a partir de um conjunto de suposições mostra que estas não podem valer todas, o que é o motor da demonstração por absurdo.
Na calculadorap ∧ ¬pUma fórmula verdadeira sob algumas interpretações e falsa sob outras.
Uma fórmula contingente não é tautologia nem contradição: a sua tabela de verdade tem pelo menos uma linha verdadeira e uma falsa. Quase todas as fórmulas que alguém escreve são contingentes, e é isso que as torna informativas.
Na calculadorap ∧ qSe alguma interpretação torna a fórmula verdadeira.
Uma fórmula é satisfazível quando pelo menos uma linha da sua tabela de verdade é verdadeira, e essa linha é um modelo dela. Decidir a satisfazibilidade é o problema central dos solucionadores SAT e, através deles, de grande parte do raciocínio automático.
Na calculadorap ∧ (p → q)Duas fórmulas com tabelas de verdade idênticas.
Fórmulas equivalentes concordam sob qualquer interpretação, pelo que qualquer uma pode substituir a outra sem mudar o que é dito. Escreva um sinal de igual entre duas expressões e a calculadora comparará as suas colunas linha a linha.
Na calculadora(p → q) ≡ (¬p ∨ q)A conclusão vale em toda a interpretação em que valem as premissas.
Escrita Γ ⊨ φ, a consequência lógica é o que um argumento válido reivindica. Verifica-se procurando um contraexemplo: uma interpretação que torne todas as premissas verdadeiras e a conclusão falsa. Se não houver nenhum, a consequência vale.
Na calculadorap → q, p ⊨ qNenhuma interpretação torna as premissas verdadeiras e a conclusão falsa.
A validade é uma propriedade da forma do argumento, não dos factos: um argumento válido pode ter premissas falsas e conclusão falsa. O que não pode ter são premissas verdadeiras a par de uma conclusão falsa.
Na calculadorap → q, p ⊨ qUm argumento válido cujas premissas são também verdadeiras.
A solidez acrescenta uma afirmação factual a uma formal: o argumento é válido e as suas premissas valem. A lógica sozinha resolve a primeira metade; a segunda pertence àquilo de que o argumento trata.
Uma interpretação que torna as premissas verdadeiras e a conclusão falsa.
Um contramodelo prova que um argumento é inválido — basta uma linha. A calculadora mostra a que encontra, o que transforma «isto não decorre» numa atribuição concreta que se pode verificar à mão.
Na calculadorap → q ⊨ q → pAlguma interpretação torna verdadeiros todos os enunciados do conjunto ao mesmo tempo.
Um conjunto de premissas é consistente quando todas podem valer juntas. Premissas inconsistentes implicam absolutamente tudo, pelo que um argumento construído sobre elas é tecnicamente válido e não vale nada.
Na calculadorap → q, ¬q ⊨ ¬pUma variável ou a sua negação, como p ou ¬p.
Os literais são os átomos das formas normais: uma cláusula é uma disjunção de literais e um mintermo uma conjunção deles. Um literal é positivo quando a variável aparece sozinha e negativo quando está negada.
Na calculadora¬pUma disjunção de literais, como p ∨ ¬q ∨ r.
Uma cláusula é um dos grupos entre parênteses de que é feita uma forma normal conjuntiva. Como uma conjunção só é verdadeira se todas as partes o forem, uma fórmula em FNC vale exatamente quando valem todas as suas cláusulas.
Na calculadorap ∨ ¬q ∨ rUm OU de Es: uma disjunção de conjunções de literais.
Toda a fórmula tem uma forma normal disjuntiva, e ela lê-se diretamente na tabela de verdade: uma conjunção por cada linha verdadeira, ligadas por ∨. A calculadora dá ainda uma FND minimizada, que diz o mesmo com menos literais.
Na calculadora(p ∧ q) ∨ (¬p ∧ r)Um E de OUs: uma conjunção de cláusulas.
A forma normal conjuntiva lê-se nas linhas falsas da tabela de verdade, uma cláusula por linha. É o formato de entrada que os solucionadores SAT esperam, o que faz da conversão para FNC um passo de rotina do raciocínio automático.
Na calculadora(p ∨ q) ∧ (¬p ∨ r)Uma conjunção que designa exatamente uma linha da tabela de verdade.
Um mintermo menciona cada variável uma vez, negada ou não, de modo que apenas uma interpretação o satisfaz. Reunir os mintermos das linhas verdadeiras e ligá-los com ∨ dá a forma normal disjuntiva da fórmula.
Na calculadorap ∧ ¬q ∧ rUma disjunção que exclui exatamente uma linha da tabela de verdade.
Um maxtermo menciona cada variável uma vez e é falso numa única interpretação. Tomar o maxtermo de cada linha falsa e ligá-los com ∧ dá a forma normal conjuntiva da fórmula.
Na calculadorap ∨ ¬q ∨ rA negação troca ∧ por ∨ e ∨ por ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
As leis de De Morgan empurram uma negação para dentro de uma conjunção ou de uma disjunção, trocando o conectivo pelo caminho. É assim que uma fórmula é levada até uma forma normal e assim que se simplificam negações no código e nos circuitos.
Na calculadora¬(p ∧ q) ≡ ¬p ∨ ¬qNegar duas vezes devolve o original: ¬¬p ≡ p.
A dupla negação vale na lógica clássica nos dois sentidos, pelo que ¬¬p e p podem sempre trocar-se. A lógica intuicionista guarda apenas o sentido de p para ¬¬p, e é aí que os dois sistemas se separam.
Na calculadora¬¬p ≡ pA álgebra de dois valores, com ∧, ∨ e ¬ como operações.
A álgebra de Boole é lógica proposicional escrita como aritmética sobre 0 e 1, com leis — comutatividade, distributividade, absorção, De Morgan — que permitem reescrever e simplificar expressões. É a matemática em que se projetam os circuitos digitais.
Na calculadora(p ∧ q) ∨ (p ∧ ¬q) ≡ pUma grelha da tabela de verdade que torna visíveis as simplificações.
Um mapa de Karnaugh dispõe as linhas de forma que as células vizinhas difiram numa variável, e as bordas ligam-se. Também se escreve mapa K, K-map ou kmap. Grupos retangulares de 1 adjacentes de tamanho 1, 2, 4 ou 8 leem-se então como termos de uma expressão mínima.
Na calculadora(p ∧ q) ∨ (p ∧ ¬r)Um grupo no mapa que já não pode ser aumentado.
Um implicante é uma conjunção de literais que força a fórmula a ser verdadeira; é primo quando retirar-lhe qualquer literal deixaria de o fazer. Num mapa de Karnaugh os implicantes primos são os retângulos maximais de 1.
O único implicante primo que cobre um determinado 1.
Quando um 1 do mapa pertence a um só grupo maximal, esse grupo tem de aparecer em qualquer cobertura mínima, pelo que é tomado primeiro. O que sobra é a parte da cobertura que realmente é preciso procurar.
Um elemento de circuito que calcula um conectivo sobre as suas entradas.
As portas AND, OR, NOT, NAND, NOR e XOR são a contrapartida física dos conectivos. Uma fórmula e um circuito são o mesmo objeto desenhado duas vezes, e por isso a calculadora pode mostrar uma expressão como diagrama de portas.
Na calculadora(p ∧ q) ∨ ¬rUm passo autorizado de fórmulas já obtidas para uma nova.
Uma regra de inferência é um padrão como o modus ponens, aplicável sempre que existam fórmulas com a forma certa. Os sistemas de demonstração constroem-se com um punhado delas, escolhidas para que só se derivem conclusões que decorrem.
De p → q e p infere-se q.
O modus ponens é a regra básica do condicional: dado um condicional e o seu antecedente, segue-se o consequente. A sua validade vê-se na tabela de verdade: a única linha com ambas as premissas verdadeiras tem também a conclusão verdadeira.
Na calculadorap → q, p ⊨ qDe p → q e ¬q infere-se ¬p.
O modus tollens percorre um condicional ao contrário: se o consequente falha, o antecedente não pode ter valido. É a contrarrecíproca em ação e a forma de todo o argumento que refuta uma hipótese pondo à prova as suas previsões.
Na calculadorap → q, ¬q ⊨ ¬pDe p → q e q → r infere-se p → r.
O silogismo hipotético encadeia condicionais, o que torna possíveis as derivações longas: cada elo leva o argumento um passo mais longe sem que nenhuma premissa seja afirmada.
Na calculadorap → q, q → r ⊨ p → rDe p ∨ q e ¬p infere-se q.
O silogismo disjuntivo elimina a opção excluída: se vale uma de duas alternativas e a primeira não, a segunda tem de valer. É a regra por trás do raciocínio por eliminação.
Na calculadorap ∨ q, ¬p ⊨ qProvar uma conclusão aplicando regras de inferência passo a passo.
A dedução natural obtém uma conclusão a partir de premissas com regras de introdução e eliminação para cada conectivo, permitindo suposições temporárias que depois se descarregam. Prova o que uma tabela de verdade verifica, mas sem percorrer todas as linhas.
Supor o contrário, derivar uma contradição, concluir o original.
Para provar φ supõe-se ¬φ e deriva-se algo da forma ψ ∧ ¬ψ. Como nenhuma interpretação torna verdadeira uma contradição, a suposição não pode valer e φ segue-se. É assim que costumam ir as provas de irracionalidade e de infinitude.
Na calculadorap ∧ ¬pO passo inválido de p → q e q para p.
Um consequente verdadeiro não estabelece o antecedente: outra coisa pode tê-lo produzido. A calculadora mostra o contramodelo — p falsa, q verdadeira — que é a linha que separa isto do modus ponens.
Na calculadorap → q, q ⊨ pO passo inválido de p → q e ¬p para ¬q.
Um condicional nada diz sobre o que acontece quando o seu antecedente falha, pelo que excluir o antecedente deixa o consequente em aberto. O contramodelo é a linha em que p é falsa e q verdadeira.
Na calculadorap → q, ¬p ⊨ ¬qLógica que olha para dentro das proposições, para objetos e propriedades.
A lógica de predicados acrescenta predicados, termos e quantificadores, de modo que «todo o primo maior do que dois é ímpar» passa a ser uma fórmula e não uma única letra. É estritamente mais expressiva do que a proposicional, e nenhuma tabela de verdade a pode decidir.
Um símbolo que diz de quantos objetos um predicado vale.
Os dois quantificadores clássicos são ∀ (todos) e ∃ (pelo menos um), e cada um é a negação do outro com o corpo negado. A variável que um quantificador liga é o que distingue a lógica de predicados da proposicional.
∀x φ: φ vale de todos os objetos do domínio.
Uma afirmação universal é refutada por um único contraexemplo e vale vaziamente sobre um domínio vazio. ∀x φ equivale a ¬∃x ¬φ, que é a contrapartida das leis de De Morgan para quantificadores.
∃x φ: φ vale de pelo menos um objeto do domínio.
Uma afirmação existencial estabelece-se exibindo uma testemunha. ∃x φ equivale a ¬∀x ¬φ, pelo que cada quantificador pode ser definido a partir do outro e da negação.
Lógica alargada com «necessariamente» (□) e «possivelmente» (◇).
A lógica modal avalia fórmulas em mundos possíveis em vez de numa só interpretação: □φ vale quando φ vale em todos os mundos acessíveis, ◇φ quando vale nalgum. Variar o que significa «acessível» dá os diferentes sistemas modais.
