LPLbook_-_Captulo_04_-_A_Lgica_dos_Conectivos_Booleanos (1)

Prévia do material em texto

Caṕıtulo 4
A Lógica dos Conectivos
Booleanos
Os conectivos ∧, ∨ e ¬ são conectivos verofuncionais. Lembre-se o que isso sig-
nifica: o valor verdade de uma sentença complexa constrúıda por meio de um
destes śımbolos pode ser determinado simplesmente olhando para os valores
verdade dos constituintes imediatos da sentença. Assim, para saber se P ∨ Q
é verdadeira, só precisamos saber os valores verdade de P e Q. Este compor-
tamento particularmente simples é o que nos permite capturar os significados
de conectivos verofuncionais usando tabelas verdade.
Outros conectivos que podeŕıamos estudar não são tão simples. Considere
a sentença é necessariamente o caso que S. Uma vez que algumas proposições operadores
verofuncionais vs.
operadores não
verofuncionais
verdadeiras são necessariamente verdadeiras, ou seja, não poderiam ter sido
falsas (por exemplo, a = a), enquanto outras proposições não são necessari-
amente verdadeiras (por exemplo, Cube(a)), não podemos descobrir o valor
verdade da sentença original, se nos for dito apenas o valor verdade de uma
sentença constituinte S. É necessariamente o caso, ao contrário de não é o
caso, não é verofuncional.
O fato de que os conectivos booleanos são verofuncionais torna muito fácil
explicar seus significados. Ele também nos fornece uma técnica simples, mas
poderosa, para estudar a sua lógica. A técnica é uma extensão das tabelas
verdade usadas para apresentar os significados dos conectivos. Acontece que
muitas vezes podemos calcular as propriedades lógicas de sentenças complexas
através da construção de tabelas verdade que exibem todas as atribuições
posśıveis de valores verdade para os componentes atômicos a partir dos quais
as sentenças são constrúıdas. A técnica pode, por exemplo, dizer-nos que uma
sentença em particular S é uma consequência lógica de algumas premissas
P1, . . . ,Pn. E, visto que consequência lógica é uma das nossas principais pre-
ocupações, a técnica é um passo importante a ser aprendido.
Neste caṕıtulo, vamos discutir o que tabelas verdade podem nos dizer sobre
três noções lógicas relacionadas: as noções de consequência lógica, equivalência
lógica e verdade lógica. Apesar de já termos discutido algo sobre consequência
lógica, vamos resolver isso em ordem inversa, uma vez que as técnicas de
tabelas verdade relacionadas são mais fáceis de compreender nesta ordem.
101
102 / A Lógica dos Conectivos Booleanos
Seção 4.1
Tautologias e verdade lógica
Dissemos que uma sentença S é uma consequência lógica de um conjunto de
premissas P1, . . . ,Pn se é imposśıvel que todas as premissas sejam verdadeiras
e a conclusão S seja falsa. Ou seja, a conclusão deve ser verdadeira se as
premissas são verdadeiras.
Observe que, de acordo com esta definição, existem algumas sentenças
que são consequências lógicas de qualquer conjunto de premissas, mesmo o
conjunto vazio. Isto será verdade para qualquer sentença cuja verdade é em si
uma necessidade lógica. Por exemplo, dadas as nossas suposições sobre fol,
a sentença a = a é necessariamente verdadeira. Então, é claro, não importa
o que suas premissas iniciais possam ser, será imposśıvel que essas premissas
sejam verdadeiras e que a = a seja falsa— simplesmente porque é imposśıvel
que a = a seja falsa! Chamaremos tais sentenças logicamente necessárias de
verdades lógicas.verdade lógica
As noções intuitivas de possibilidade lógica e necessidade lógica já apare-
ceram várias vezes neste livro na caracterização de argumentos válidos e
na relação de consequência . Mas esta é a primeira vez que as aplicamos
a sentenças individuais. Intuitivamente, uma sentença é logicamente posśıvelpossibilidade lógica e
necessidade lógica se pudesse ser (ou poderia ter sido) verdadeira, pelo menos por razões lógicas.
Pode haver algumas outras razões, digamos f́ısicas, porque a declaração não
poderia ser verdadeira, mas não existem razões lógicas impedindo isto. Por
exemplo, não é fisicamente posśıvel ir mais rápido do que a velocidade da luz,
embora seja logicamente posśıvel: eles fazem isso em Star Trek o tempo todo.
Por outro lado, não é nem mesmo posśıvel logicamente um objeto não ser
idêntico a si mesmo. Isso seria simplesmente violar o sentido da identidade. A
forma como geralmente se coloca é que a afirmação é logicamente posśıvel se
existe alguma circunstância logicamente posśıvel (ou situação ou mundo), em
que a afirmação é verdadeira. Da mesma forma, uma sentença é logicamente
necessária, se é verdade em qualquer circunstância logicamente posśıvel.
Essas noções são muito importantes, mas elas também são irritantemente
vagas. A medida que avançamos neste livro, vamos introduzir alguns con-
ceitos precisos que nos ajudarão a esclarecer essas noções. O primeiro destestautologia
conceitos precisos, o qual nós apresentamos nesta seção, é a noção de um
tautologia.
Como pode um conceito preciso ajudar a esclarecer uma noção imprecisa
e intuitiva? Vamos pensar por um momento sobre a linguagem de blocos e
a noção intuitiva de possibilidade lógica. Presumivelmente, uma sentença da
Caṕıtulo 4
Tautologias e verdade lógica / 103
linguagem de blocos é logicamente posśıvel se existisse um mundo de blocos
em que fosse verdadeira. Claramente, se podemos construir um mundo em que
Tarski’s World a torna verdadeira, então isto demonstra que a sentença é de
fato logicamente posśıvel. Por outro lado, há sentenças logicamente posśıveis
que não podem ser feitas verdadeiras nos mundos que você pode construir
com Tarski’s World . Por exemplo, a sentença
¬(Tet(b) ∨ Cube(b) ∨ Dodec(b))
é, sem dúvida logicamente posśıvel, digamos se b fosse uma esfera ou um
icosaedro. Você não pode construir um mundo com Tarski’s World , mas isso
não é culpa da lógica, assim como não é culpa da lógica que você não possa
viajar mais rápido do que a velocidade da luz. Tarski’s World tem suas leis
não lógicas e restrições assim como o mundo f́ısico.
O programa Tarski’s World dá origem a uma noção precisa da possibili-
dade de sentenças na linguagem de blocos. Podeŕıamos dizer que uma sentença
é tw-posśıvel, se ela é verdade em algum mundo que pode ser constrúıdo u- tw-posśıvel
sando o programa. Nossas observações no parágrafo anterior poderiam, então,
ser reformuladas, dizendo que todos as sentenças tw-posśıveis são logicamente
posśıveis, mas que o inverso, em geral, não é verdadeiro. Algumas sentenças
logicamente posśıveis não são tw-posśıveis.
Pode parecer surpreendente que podemos fazer tais proposições definitivas
envolvendo uma noção vaga como possibilidade lógica. Mas, realmente, não é
mais surpreendente do que o fato de que podemos dizer com certeza que uma
determinada maçã é vermelha, embora as fronteiras da cor vermelha sejam
vagas. Pode haver casos em que seja dif́ıcil decidir se algo é vermelho, mas
isto não significa que não há muitos casos perfeitamente claros.
Tarski’s World nos dá um método preciso para demonstrar que uma sen-
tença da linguagem de blocos é logicamente posśıvel, uma vez que tudo o
que é posśıvel em Tarski’s World é logicamente posśıvel. Nesta seção, apre-
sentaremos um outro método preciso, que pode ser usado para demonstrar
que uma sentença constrúıda usando conectivos verofuncionais é logicamente método da tabela
verdadenecessária. O método utiliza tabelas verdade para demonstrar que certas sen-
tenças não podem ser falsas, simplesmente devido aos significados dos conec-
tivos verofuncionais que elas contêm. Como o método que nos foi dado por
Tarski’s World , o método da tabela verdade só funciona em uma direção:
quando se diz que uma sentença é logicamente necessária, ela definitivamente
é. Por outro lado, algumas sentenças sãologicamente necessárias por razões
que o método da tabela verdade não pode detectar.
Suponha que tenhamos uma sentença complexa S com n sentenças atômi-
cas, A1, . . . ,An. Para construir uma tabela verdade para S, se escreve as sen-
Seção 4.1
104 / A Lógica dos Conectivos Booleanos
tenças atômicas A1,. . . , An na parte superior da página, com a sentença S
à sua direita. É costume desenhar uma linha dupla que separa as sentenças
atômicas de S. Sua tabela verdade terá uma linha para cada forma posśıvel de
atribuir true e false para as sentenças atômicas. Uma vez que existem duas
atribuições posśıveis para cada sentença atômica, existirão 2n linhas. Assim, se
n = 1 haverá duas linhas , se n = 2 haverá quatro linhas, se n = 3 haverá oitonúmero de linhas em
uma tabela verdade linhas, se n = 4 haverá dezesseis linhas, e assim por diante. Costuma-se fazer
a coluna mais à esquerda ter a metade superior das linhas marcadas true,
a segunda metade false. A coluna seguinte divide cada uma delas, sendo os
primeiro e terceiro quartos das linhas com true, os segundo e quarto quartos
com false, e assim por diante. Isto irá resultar na última coluna tendo true
e false alternados à medida que descemos a coluna.
Vamos começar olhando para um exemplo muito simples de uma tabela
verdade para a sentença Cube(a) ∨ ¬Cube(a). Uma vez que esta sentença é
constrúıda a partir de uma sentença atômica, a nossa tabela verdade conterá
duas linhas, uma para o caso onde Cube(a) é verdadeira e uma para quando
ela é falsa.
Cube(a) Cube(a) ∨ ¬Cube(a)
T
F
Em uma tabela verdade, a coluna ou as colunas abaixo das sentenças
atômicas são chamadas colunas de referência. Uma vez que as colunas decolunas de referência
referência foram preenchidas, estamos prontos para preencher o restante da
tabela. Para fazer isso, vamos construir colunas de T’s e F’s abaixo de cada
conectivo da senteça alvo S. Estas colunas são preenchidas, uma por uma,
usando as tabelas verdade para os vários conectivos. Começamos trabalhando
em conectivos que se aplicam só a sentenças atômicas. Uma vez feito isso,
nós trabalhamos com conectivos que se aplicam a sentenças cujo principal
conectivo já tenha sua coluna preenchida. Continuamos este processo até que
o conectivo principal de S teve sua coluna preenchida. Esta é a coluna que
mostra como a verdade de S depende da verdade de suas peças atômicas.
Nosso primeiro passo no preenchimento dessa tabela verdade, então, é cal-
cular os valores verdade que devem ir na coluna sob o conectivo mais interno,
que neste caso é o ¬. Fazemos isso, referindo-se aos valores verdade na coluna
de referência em Cube(a), trocando valores de acordo com o significado de ¬.
Cube(a) Cube(a) ∨ ¬Cube(a)
t F
f T
Caṕıtulo 4
Tautologias e verdade lógica / 105
Uma vez que esta coluna for preenchida, podemos determinar os valores
verdade que devem ir sob o ∨, olhando para os valores em Cube(a) e aqueles
sob o śımbolo de negação, uma vez que estes correspondam aos valores das
duas sentenças às quais o ∨ é aplicado. (Você entende isso?) Visto que existe
pelo menos um T em cada linha, a última coluna da tabela verdade se parece
com isso.
Cube(a) Cube(a) ∨ ¬Cube(a)
t T f
f T t
Não surpreendentemente, a nossa tabela nos diz que Cube(a) ∨ ¬Cube(a)
não pode ser falsa. É o que chamamos de uma tautologia, um tipo de verdade
lógica especialmente simples. Vamos dar uma definição precisa de tautologias
posteriormente. Nossa sentença é na verdade uma instância de um prinćıpio,
P ∨ ¬P, que é conhecido como a lei do meio exclúıdo (ou lei do terceiro ex- lei do meio exclúıdo
clúıdo). Cada exemplo deste prinćıpio é uma tautologia.
Vamos agora olhar uma tabela verdade mais complexa, para uma sentença
constrúıda a partir de três sentenças atômicas.
(Cube(a) ∧ Cube(b)) ∨ ¬Cube(c)
A fim de tornar nossa tabela mais fácil de ler, vamos abreviar as sentenças
atômicas para A, B e C. Visto que há três sentenças atômicas, a nossa tabela
terá oito (23) linhas. Olhe atentamente para como distribúımos T’s e F’s e se
convença que cada atribuição posśıvel é representada por uma das linhas.
A B C (A ∧ B) ∨ ¬C
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Uma vez que dois dos conectivos na sentença alvo se aplicam a sentenças
atômicas cujos valores estão especificados na coluna de referência, podemos
preencher essas colunas usando as tabelas verdade para ∧ e ¬ dadas anterior-
mente.
Seção 4.1
106 / A Lógica dos Conectivos Booleanos
A B C (A ∧ B) ∨ ¬C
t t t T F
t t f T T
t f t F F
t f f F T
f t t F F
f t f F T
f f t F F
f f f F T
Isso deixa apenas um conectivo, o conectivo principal da sentença. Nós preen-
chemos a coluna sob ele, referindo-se às duas colunas que acabamos de con-
cluir, usando a tabela verdade para ∨.
A B C (A ∧ B) ∨ ¬C
t t t t T f
t t f t T t
t f t f F f
t f f f T t
f t t f F f
f t f f T t
f f t f F f
f f f f T t
Quando inspecionarmos a última coluna preenchida desta tabela, a col-
una abaixo do conectivo ∨, vemos que a sentença será falsa em qualquer
circunstância em que Cube(c) for verdadeira e uma de Cube(a) ou Cube(b) é
falsa. Esta tabela mostra que a nossa sentença não é uma tautologia. Além
disso, uma vez que claramente existem mundos de blocos em que c é um cubo e
ou a ou b não é, a alegação feita por nossa sentença original não é logicamente
necessária.
Vejamos mais um exemplo, desta vez para uma sentença da forma
¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
Esta sentença, embora tenha o mesmo número de componentes atômicos, é
consideravelmente mais complexa do que o nosso exemplo anterior. Começamos
a tabela verdade, preenchendo as colunas sob os dois conectivos que se aplicam
diretamente às sentenças atômicas.
Caṕıtulo 4
Tautologias e verdade lógica / 107
A B C ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
t t t F T
t t f F F
t f t F F
t f f F F
f t t T T
f t f T F
f f t T F
f f f T F
Podemos agora preencher a coluna sob o ∨ que liga ¬A e B ∧ C, referindo-
se apenas às colunas recém-preenchidas. Esta coluna terá um F pequeno nela
se, e somente se, ambos as sentenças constituintes são falsas.
A B C ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
t t t f T t
t t f f F f
t f t f F f
t f f f F f
f t t t T t
f t f t T f
f f t t T f
f f f t T f
Vamos agora preencher a coluna sob o ∧ restante. Para fazer isso, nós
precisamos nos referir à coluna de referência em A, e à coluna que acabamos
de preencher. A melhor maneira de fazer isso é passar dois dedos pelas colunas
relevantes e inserir um T apenas nas linhas em que ambos os seus dedos
estejam apontando para T’s.
A B C ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
t t t T f t t
t t f F f f f
t f t F f f f
t f f F f f f
f t t F t t t
f t f F t t f
f f t F t t f
f f f F t t f
Podemos agora preencher a coluna para o ¬ restante referindo-se à coluna
previamente conclúıda. O ¬ simplesmente inverte T’s e F’s.
Seção 4.1
108 / A Lógica dos Conectivos Booleanos
A B C ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
t t t F t f t t
t t f T f f f f
t f t T f f f f
t f f T f f f f
f t t T f t t t
f t f T f t t f
f f t T f t t f
f f f T f t t f
Enfim, podemos preencher a coluna sob o principal conectivo da nossa
sentença. Fazemos isso com o método dos dois dedos: passando os dedos para
baixo na coluna de referência para B e na coluna que acabamos de concluir,
inserindo T sempre que pelo menos um dedo apontar para um T.
A B C ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
t t t f t f t t T
t t f t f f f f T
t f t t f f f f T
t f f t f f f f T
f t t t f t t t T
f t f t f t t f T
f f t t f t t f T
f f f t f t t f T
Digamos que uma tautologia seja qualquer sentença cuja tabela verdade
tem apenas T ’s na coluna sob o seu principal conectivo Assim, vemos natautologia
última coluna da tabela acima que qualquer sentença da forma
¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B
é uma tautologia.
Tente você mesmo. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
� 1. Abra o programa Boole do software que acompanha o livro. Nós usaremos
Boole para reconstruir a tabela verdade que acabamos de discutir. A
primeira coisa a fazer é inserir a sentença ¬(A ∧ (¬A ∨ (B ∧ C))) ∨ B no
topo direito da tabela. Para fazer isso, use a barra de ferramentas para
inserir os śımbolos lógicos e o teclado para digitar as letras A, B e C. (Você
também pode inserir os śımbolos lógicos a partir do teclado, digitando &,
Caṕıtulo 4
Tautologias e verdade lógica / 109
| e ∼ para ∧,∨, e ¬, respectivamente. Se você digitar os śımbolos lógicos
a partir do teclado, certifique-se de adicionar espaços antes e depois dos
conectivos binários para que as colunas sob eles estejam razoavelmente
espaçadas.) Se a sua sentença está bem formada, o “(1)” pequeno acima
da sentença ficará verde.
�2. Para construir as colunas de referência, clique na parte superior esquerda
da tabela para mover o seu ponto de inserção para o topo da primeira
coluna de referência. Digite C nesta coluna. Em seguida, escolha Add
Column Before (Adicionar Coluna Antes) no menu Table (Tabela)
e insira B. Repita este procedimento e adicione uma coluna encabeçada
pelo A. Para preencher as colunas de referência, clique em cada uma delas
por vez, e digite o padrão desejado de T’s e F’s.
�3. Clique sob os vários conectivos na sentença alvo, e observe que quadrados
verdes aparecem nas colunas de cujos valores o conectivo depende. Sele-
cione uma coluna para a qual as colunas destacadas já estejam preenchi-
dos, e preencha essa coluna com os valores verdade apropriados. Continue
esse processo até a sua tabela estar completa. Quando você terminar, use
o item Verify (Verifique) do menu Table para ver se todos os valores
estão corretos e sua tabela está completa. Você também pode verificar a
sua tabela usando o botão colorido na barra de ferramentas (à esquerda
do botão de impressão). Se você tiver preenchido a tabela corretamente,
marcas de confirmação verdes devem aparecer à esquerda de cada linha, e
ao lado da sentença alvo. Cruzes vermelhas indicam que você cometeu um
erro, e você deve corrigi-los agora.
�4. Uma vez que você tenha uma tabela verdade correta e completa, clique
no botão Assessment (Avaliação) na área rosa sob a barra de ferra-
mentas. Isso permitirá a você dizer se você acha que a sentença é uma
tautologia. Diga que é (visto que é), e verifique a sua avaliação selecio-
nando novamente Verify no menu Table (ou usando o botão da barra de
ferramentas). Agora você deve ver uma marca verde ao lado da palavra
“Tautology” (“Tautologia”) no painel de avaliação. Salve sua tabela como
Table Tautology 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parabéns
Há um pequeno problema com a nossa definição de uma tautologia, visto
que ela supõe que cada sentença tem um conectivo principal. Isto é quase
sempre o caso, mas não em sentenças como: conectivos principais
P ∧ Q ∧ R
Seção 4.1
110 / A Lógica dos Conectivos Booleanos
Para fins de construção de tabelas verdade, vamos supor que o conectivo prin-
cipal em conjunção com mais de duas sentenças é sempre o ∧ mais à direita.
Ou seja, vamos construir uma tabela verdade para P ∧ Q ∧ R da mesma forma
que iŕıamos construir uma tabela verdade para:
(P ∧ Q) ∧ R
De modo mais geral, constrúımos a tabela verdade para:
P1 ∧ P2 ∧ P3 ∧ . . . ∧ Pn
como se fosse “acentuado” da seguinte forma:
(((P1 ∧ P2) ∧ P3) ∧ . . .) ∧ Pn
Tratamos disjunções longas da mesma forma.
Qualquer tautologia é logicamente necessária. Afinal de contas, a sua ver-
dade é garantida simplesmente pela sua estrutura e pelos significados dostautologias e
necessidade lógica conectivos verofuncionais. Tautologias são necessidades lógicas num sentido
muito forte. Sua verdade é independente tanto da maneira que o mundo é
bem como dos significados das sentenças atômicas que as compõem.
Deve ficar claro, no entanto, que nem todas as proposições logicamente
necessárias são tautologias. O exemplo mais simples de uma proposição logi-
camente necessária que não é uma tautologia é a sentença fol a = a. Como
esta é uma sentença atômica, sua tabela verdade iria conter um T e um F.
O método da tabela verdade é muito grosseiro para reconhecer que a linha
contendo o F não representa uma possibilidade real.
Você deveria ser capaz de pensar em qualquer número de sentenças que
não são tautológicas, mas que no entanto parecem logicamente necessárias.
Por exemplo, a sentença
¬(Larger(a, b) ∧ Larger(b, a))
não pode ser falsa, mas uma tabela verdade para a sentença não demonstrará
isso. A sentença será falsa na linha da tabela verdade que atribui T tanto a
Larger(a, b) como a Larger(b, a).
Agora temos dois métodos para explorar as noções de possibilidade lógica
e necessidade lógica, pelo menos para a linguagem de blocos. Em primeiro
lugar, há os mundos de blocos que podem ser constrúıdos usando Tarski’s
World . Se a sentença é verdadeira em algum desses mundo, nós o chamamos
de tw-posśıvel. Da mesma forma, se uma sentença é verdadeira em todos os
mundos em que ela tem um valor verdade (isto é, em que todos os seus nomes
têm referências), podemos chamá-lo de tw-necessária. O segundo método é
o da tabela verdade. Se uma sentença é verdadeira em cada uma das linhas
Caṕıtulo 4
Tautologias e verdade lógica / 111
Figura 4.1: A relação entre tautologias, verdades lógicas, e necessidade tw.
de sua tabela verdade, podeŕıamos chamá-la de tt-necessária ou, mais tradi-
cionalmente, tautológica. Se a sentença é verdadeira em pelo menos uma linha
de sua tabela verdade, vamos chamá-la de tt-posśıvel. tt-posśıvel
Nenhum desses conceitos corresponde exatamente às vagas noções de pos-
sibilidade lógica e necessidade lógica. Mas existem relações claras e impor-
tantes entre as noções. Do lado da necessidade, sabemos que todas as tau-
tologias são logicamente necessárias, e que todas as necessidades lógicas são
tw-necessárias. Estas relações são representadas no “diagrama de Euler” na
Figura 4.1, onde representamos o conjunto de necessidades lógicas como o
interior de um ćırculo com uma fronteira difusa. O conjunto de tautologias é
representado por um ćırculo preciso contido dentro do ćırculo difuso, e o con-
junto de necessidades Tarski’s World é representado por um ćırculo preciso
que contém ambos estes ćırculos.
Há, de fato, um outro método para demonstrar que uma sentença é um
verdade lógica, o qual utiliza a técnica de provas. Se você pode provar uma sen- prova e verdade lógica
tença usando nenhuma premissa, então, a sentença é logicamente necessária.
Nos caṕıtulos seguintes, vamos dar-lhe alguns métodos a mais de dar provas.
Usando estes métodos, você vai ser capaz de provar que sentenças são logica-
Seção 4.1
112 / A Lógica dos Conectivos Booleanos
mente necessárias sem construir suas tabelas verdade. Quando acrescentarmos
quantificadores à nossa linguagem, a diferença entre tautologias e verdades
lógicas irá se tornar muito evidente, tornando o método da tabela verdade
menos útil. Por outro lado, os métodos de prova sobre os quais nós discutire-
mos mais tarde naturalmente se estenderão para sentenças contendo quantifi-
cadores.
Lembre-se
Seja S uma sentença de fol constrúıda a partir de sentenças atômicas
por meio apenas de conectivos verofuncionais. A tabela verdade para S
mostra como a verdade de S depende da verdade de suas partes atômicas.
1. S é uma tautologia se, e somente se, todas as linhas da tabela verdade
atribuem true para S.
2. Se S é uma tautologia, então S é uma verdade lógica (isto é, é logica-
mente necessária).
3. Algumasverdades lógicas não são tautologias.
4. S é tt-posśıvel se, e somente se, pelo menos uma linha da tabela
verdade atribuir true para S.
Exerćıcios
Neste caṕıtulo, você estará frequentemente usando Boole para construir tabelas verdade. Embora Boole
tenha a capacidade de construção e preenchimento de colunas de referência para você, não use este
recurso. Para entender tabelas verdade, você precisa ser capaz de fazer isso sozinho. Em caṕıtulos pos-
teriores, vamos deixá-lo usar o recurso, uma vez que você aprendeu como fazê-lo sozinho. O Grade
Grinder vai, aliás, ser capaz de dizer se Boole construiu as colunas de referência.
4.1
�
Se você pulou a seção Tente você mesmo, volte e faça-a agora. Submeta o arquivo Table
Tautology 1.
4.2
�
Assuma que A, B e C são sentenças atômicas. Use Boole para construir tabelas verdade para
cada uma das seguintes sentenças e, com base nas suas tabelas verdade, diga quais são tau-
tologias. Nomeie suas tabelas Table 4.2.x, onde x é o número da sentença.
1. (A ∧ B) ∨ (¬A ∨ ¬B)
2. (A ∧ B) ∨ (A ∧ ¬B)
3. ¬(A ∧ B) ∨ C
4. (A ∨ B) ∨ ¬(A ∨ (B ∧ C))
Caṕıtulo 4
Tautologias e verdade lógica / 113
4.3
��
No Exerćıcio 4.2 você deve ter descoberto que duas das quatro sentenças são tautologias e,
portanto, verdades lógicas.
1. Suponha que você foi informado que a sentença atômica A é de fato uma verdade lógica
(por exemplo, a = a). Você pode determinar se quaisquer sentenças adicionais na lista
(1) - (4) são logicamente necessária com base nessas informações?
2. Suponha que você foi informado que A é de fato logicamente uma sentença falsa (por
exemplo, a �= a). Você pode determinar se quaisquer sentenças adicionais na lista (1) -
(4) são verdades lógicas baseadas nesta informação?
Nos quatro exerćıcios seguintes, use Boole para construir tabelas verdade e indicar se a sentença é tt-
posśıvel e se é uma tautologia. Lembre-se de como você deve tratar as conjunções e disjunções longas.
4.4
�
¬(B ∧ ¬C ∧ ¬B) 4.5
�
A ∨ ¬(B ∨ ¬(C ∧ A))
4.6
�
¬[¬A ∨ ¬(B ∧ C) ∨ (A ∧ B)] 4.7
�
¬[(¬A ∨ B) ∧ ¬(C ∧ D)]
4.8
�
Faça uma cópia do diagrama de Euler na página 111 e coloque os números das seguintes
sentenças na região apropriada.
1. a = b
2. a = b ∨ b = b
3. a = b ∧ b = b
4. ¬(Large(a) ∧ Large(b) ∧ Adjoins(a, b))
5. Larger(a, b) ∨ ¬Larger(a, b)
6. Larger(a, b) ∨ Smaller(a, b)
7. ¬Tet(a) ∨ ¬Cube(b) ∨ a �= b
8. ¬(Small(a) ∧ Small(b)) ∨ Small(a)
9. SameSize(a, b) ∨ ¬(Small(a) ∧ Small(b))
10. ¬(SameCol(a, b) ∧ SameRow(a, b))
4.9
�|�
(Dependências lógicas) Use Tarski’s World para abrir Weiner’s Sentences.
1. Para cada uma das dez sentenças neste arquivo, construa uma tabela verdade Boole e
avalie se a sentença é tt-posśıvel. Nomeie suas tabelas Table 4.9.x, onde x é o número
da sentença. Use os resultados para preencher a primeira coluna da tabela a seguir:
Sentença tt-posśıvel tw-posśıvel
1
2
...
10
Seção 4.1
114 / A Lógica dos Conectivos Booleanos
2. Na segunda coluna da tabela, coloque sim se você acha que a sentença é tw-posśıvel,
isto é, se é posśıvel tornar a sentença verdadeira através da construção de um mundo em
Tarski’s World , e não caso contrário. Para cada sentença que você marcar como tw-
posśıvel, construa um mundo em que é ela é realmente verdade e nomeie-o World 4.9.x,
onde x é o número da sentença em questão. As tabelas verdade que você construiu
antes pode ajudar a construir estes mundos.
3. Algumas das sentenças são tt-posśıveis, mas não tw-posśıveis? Explique por que
isso pode acontecer. Alguma das sentenças são tw-posśıveis, mas não tt-posśıveis?
Explique por que não. Submeta os arquivos que você criou e entregue a tabela e
explicações para seu instrutor.
4.10
��
Desenhe um diagrama de Euler semelhante ao diagrama na página 111, mas desta vez
mostrando a relação entre as noções de possibilidade lógica, tw-possibilidade, e tt-
possibilidade. Para cada região no diagrama, indique uma sentença exemplo que ficaria naquela
região. Não se esqueça da região que está fora de todos os ćırculos.
Todas as verdades necessárias são, obviamente, posśıveis: uma vez que elas são verdadeiras
em todas as circunstâncias posśıveis, elas são certamente verdadeiras em algumas circunstâncias
posśıveis. Diante dessa reflexão, onde se encaixariam as sentenças de nosso diagrama anterior
da página 111 no novo diagrama?
4.11
���
Suponha que S é uma tautologia, com sentenças atômicas A, B e C. Suponha que nós subs-
titúımos todas as ocorrências de A por outra sentença P, possivelmente complexa. Explique por
que o resultando sentença ainda é uma tautologia. Isto é expresso dizendo que a substituição
preserva tautologicalidade. Explique por que a substituição de sentenças atômicas nem sempre
preservam verdade lógica, mesmo que preserve tautologias. Dê um exemplo.
Seção 4.2
Equivalência lógica e tautológica
No último caṕıtulo, nós introduzimos a noção de sentenças logicamente equiva-
lente, sentenças que têm os mesmos valores verdade em todas as circunstâncias
posśıveis. Quando duas sentenças são logicamente equivalentes, dizemos também
que têm as mesmas condições verdade, já que as condições em que elas são
verdadeiras ou falsas são idênticas.
A noção de equivalência lógica, bem como de necessidade lógica, é um
pouco vaga, mas não de uma forma que nos impeça de estudá-la com pre-equivalência lógica
cisão. Pois aqui também podemos introduzir conceitos precisos que carregam
consigo uma relação clara com a noção intuitiva que pretendemos entender
melhor. O conceito chave que vamos introduzir nesta seção é o de equivalência
Caṕıtulo 4
Equivalência lógica e tautológica / 115
tautológica. Duas sentenças são tautologicamente equivalentes se elas podem equivalência tautológica
ser vistas como equivalentes simplesmente em virtude dos significados dos
conectivos verofuncionais. Como se poderia esperar, pode-se verificar se há
equivalência tautológica usando tabelas verdade.
Suponha que temos duas sentenças, S e S′, entre as quais queremos verificar
se há equivalência tautológica. O que fazemos é construir uma tabela verdade
com uma coluna de referência para cada uma das sentenças atômicas que
aparecem em qualquer uma das duas sentenças. À direita, escrevemos tanto
S quanto S′, com uma linha vertical que as separa, e preenchemos os valores
verdade sob os conectivos, como de costume. Nós chamamos isso de tabela
verdade conjunta para as sentenças S e S′. Quando a tabela verdade conjunta tabelas verdade
conjuntasestiver conclúıda, vamos comparar a coluna sob o principal conectivo de S com
a coluna sob o principal conectivo de S′. Se estas colunas são idênticas, então
nós sabemos que as condições verdade das duas sentenças são as mesmas.
Vejamos um exemplo. Usando A e B para representar sentenças atômicas
arbitrárias, vamos testar a primeira lei de DeMorgan para equivalência tau-
tológica. Gostaŕıamos de fazer isso usando a seguinte tabela verdade conjunta.
A B ¬(A ∧ B) ¬A ∨ ¬B
t t F t f F f
t f T f f T t
f t T f t T f
f f T f t T t
Nesta tabela, as colunas em negrito correspondem aos principais conectivos
das duas sentenças. Visto que estas colunas são idênticas, sabemos que as
sentenças devem ter os mesmos valores verdade, não importa o que os valores
verdade de seus constituintes atômicos possam ser. Isto é simplesmente devido
à estrutura das duas sentenças e aos significados dos conectivos booleanos.
Assim, as duas sentenças são de fato tautologicamente equivalentes.
Vejamos um segundo exemplo, desta vez para ver se ¬((A ∨ B) ∧ ¬C) é
tautologicamente equivalente a (¬A ∧ ¬B) ∨ C. Para construir uma tabela ver-
dade para este par de sentenças, precisaremos de oito linhas, uma vez que
existem três sentenças atômicas. A tabela completa se parececom isto.
Seção 4.2
116 / A Lógica dos Conectivos Booleanos
A B C ¬((A ∨ B) ∧ ¬C) (¬A ∧ ¬B) ∨ C
t t t T t f f f f f T
t t f F t t t f f f F
t f t T t f f f f t T
t f f F t t t f f t F
f t t T t f f t f f T
f t f F t t t t f f F
f f t T f f f t t t T
f f f T f f t t t t T
Mais uma vez, examinando as colunas finais sob os dois principais conectivos
revela-se que as sentenças são tautologicamente equivalentes e, portanto, logi-
camente equivalentes.
Todas as sentenças tautologicamente equivalentes são logicamente equiva-
lentes, mas o oposto não é geralmente verdade. De fato, a relação entre estasequivalência tautológica
vs. equivalência lógica noções é a mesma que entre tautologias e verdades lógicas. Equivalência tau-
tológica é uma forma estrita de equivalência lógica, que não se aplica a alguns
pares de sentenças logicamente equivalentes. Considere o par de sentenças:
a = b ∧ Cube(a)
a = b ∧ Cube(b)
Essas sentenças são logicamente equivalentes, como é demonstrado na seguinte
prova informal.
Prova: Suponha que a sentença a = b ∧ Cube(a) é verdadeira. Então
a = b e Cube(a) são ambas verdadeiras. Usando a indiscernibilidade
dos idênticos (Eliminação de Identidade), sabemos que Cube(b) é
verdadeira, e, portanto, que a = b ∧ Cube(b) é verdadeira. Assim,
a verdade de a = b ∧ Cube(a) implica logicamente na verdade de
a = b ∧ Cube(b).
O inverso se aplica também. Suponha que a = b ∧ Cube(b) é ver-
dadeira. Então, por simetria de identidade, também sabemos que
b = a. A partir disso e Cube(b) podemos concluir Cube(a), e, por-
tanto, que a = b ∧ Cube(a) é verdadeira. Assim, a verdade de a = b ∧
Cube(a) implica na verdade de a = b ∧ Cube(a).
Portanto, a = b ∧ Cube(a) é verdadeira se, e somente se, a = b ∧ Cube(b)
é verdadeira.
Esta prova mostra que essas duas sentenças têm os mesmos valores verdade
em qualquer circunstância posśıvel. Porque, se uma delas fosse verdadeira e
a outra fosse falsa, isto estaria em contradição com a conclusão de uma das
Caṕıtulo 4
Equivalência lógica e tautológica / 117
duas partes da prova. Mas considere o que acontece quando nós constrúımos
uma tabela verdade conjunta para estas sentenças. Três sentenças atômicas número de linhas em
tabela conjuntaaparecem no par de sentenças, de modo que a tabela conjunta será parecida
com esta. (Observe que a tabela verdade comum para uma das sentenças por
si só, tem apenas quatro linhas, mas que a tabela conjunta deve ter oito. Você
entende por quê?)
a = b Cube(a) Cube(b) a = b ∧ Cube(a) a = b ∧ Cube(b)
t t t T T
t t f T F
t f t F T
t f f F F
f t t F F
f t f F F
f f t F F
f f f F F
Esta tabela mostra que as duas sentenças não são tautologicamente equiva-
lentes, uma vez que atribui às sentenças valores diferentes na segunda linha e
na terceira linha. Olhe atentamente para essas duas linhas para ver o que está
acontecendo. Note-se que nessas duas linhas é atribuido T a a = b enquanto
são atribúıdos diferentes valores verdade a Cube(a) e Cube(b). Claro, nós sabe-
mos que nenhuma destas linhas corresponde a uma circunstância logicamente
posśıvel, pois se a e b são idênticos, os valores verdade de Cube(a) e Cube(b)
devem ser os mesmos. Mas o método da tabela verdade não detecta isto, uma
vez que é senśıvel apenas aos significados dos conectivos verofucionais.
À medida que expandirmos a nossa linguagem para incluir quantificadores,
vamos encontrar muitas equivalências lógicas que não são equivalências tau-
tológicas. Mas isto não quer dizer que não haja um monte de equivalências
tautológicas importantes e interessantes. Nós já destacamos três no último
caṕıtulo: dupla negação e as duas equivalências de DeMorgan. Deixamos para
você verificar se esses prinćıpios são, de fato, equivalências tautológicas. Na
próxima seção, vamos introduzir outros prinćıpios e ver como eles podem ser
usados para simplificar sentenças de fol.
Seção 4.2
118 / A Lógica dos Conectivos Booleanos
Lembre-se
Sejam S e S′ sentenças de fol constrúıdas a partir de sentenças atômicas
por meio apenas de conectivos verofuncionais. Para testar equivalência
tautológica, constrúımos uma tabela verdade conjunta para as duas sen-
tenças.
1. S e S′ são tautologicamente equivalentes se, e somente se, cada linha
da tabela verdade conjunta atribuir os mesmos valores para S e S′.
2. Se S e S′ são tautologicamente equivalentes, então, elas são logicamente
equivalentes.
3. Algumas sentenças logicamente equivalentes não são tautologicamente
equivalentes.
Exerćıcios
Nos exerćıcios 4.12-4.18, use Boole para construir tabelas verdade conjuntas que mostram que os pares
de sentenças são logicamente (na verdade, tautologicamente) equivalentes. Para adicionar uma segunda
sentença à sua tabela verdade conjunta, escolha Add Column After (Adicionar Coluna Após) no
menu Table (Tabela). Não se esqueça de especificar suas avaliações, e lembre-se, você deve construir
e preencher suas próprias colunas referência.
4.12
�
(DeMorgan)
¬(A ∨ B) and ¬A ∧ ¬B
4.13
�
(Associatividade)
(A ∧ B) ∧ C and A ∧ (B ∧ C)
4.14
�
(Associatividade)
(A ∨ B) ∨ C and A ∨ (B ∨ C)
4.15
�
(Idempotência)
A ∧ B ∧ A and A ∧ B
4.16
�
(Idempotência)
A ∨ B ∨ A and A ∨ B
4.17
�
(Distribuição)
A ∧ (B ∨ C) and (A ∧ B) ∨ (A ∧ C)
4.18
�
(Distribuição)
A ∨ (B ∧ C) and (A ∨ B) ∧ (A ∨ C)
Caṕıtulo 4
Consequência lógica e tautológica / 119
4.19
�
(tw-equivalência) Suponha que introduzimos a noção de tw-equivalência, dizendo que duas
sentenças da linguagem de blocos são tw-equivalentes se, e somente se, elas têm o mesmo valor
verdade em todos os mundos que podem ser constrúıdos em Tarski’s World .
1. Qual é a relação entre tw-equivalência, equivalência tautológica e equivalência lógica?
2. Dê um exemplo de um par de sentenças que são tw-equivalentes, mas não são logica-
mente equivalentes.
Seção 4.3
Consequência lógica e tautológica
A nossa principal preocupação neste livro é com a relação de consequência
lógica, da qual verdade lógica e equivalência lógica podem ser pensadas como
casos muito especiais: a verdade lógica é uma sentença que é uma consequência
lógica de qualquer conjunto de premissas, e sentenças logicamente equivalentes
são sentenças que são consequências lógicas uma da outra.
Como você provavelmente já adivinhou, tabelas verdade nos permitem
definir uma noção precisa da consequência tautológica, uma forma ŕıgida de
consequência lógica, da mesma forma que nos permitiu definir tautologias
e equivalências tautológicas, formas ŕıgidas de verdade lógica e equivalência
lógica.
Vejamos o caso simples de duas sentenças, P e Q, ambas constrúıdas a
partir de sentenças atômicas por meio de conectivos verofuncionais. Suponha
que você quer saber se Q é uma consequência de P. Crie uma tabela verdade
conjunta para P e Q, assim como você faria se estivesse testando equivalência
tautológica. Depois de preencher as colunas para P e Q, verifique as colunas
sob os principais conectivos dessas sentenças. Em particular, olhe para cada
linha da tabela na qual P é verdadeira. Se cada uma dessas linhas é também
uma em que Q é verdadeira, então Q é dita ser uma consequência tautológica de consequência
tautológicaP. A tabela verdade mostra que se P é verdadeira, então Q deve ser verdadeira
também, e que isto é devido simplesmente aos significados dos conectivos
verofuncionais.
Assim como tautologias são logicamente necessárias, qualquer consequência
tautológica Q de uma sentença P também deve ser uma consequência lógica de
P. Podemos ver isso, provando que se Q não é uma consequência lógica de P,
então ela não pode passar no nosso teste da tabela verdade para consequência
tautológica.
Prova: Suponha que Q não é uma consequência lógica de P. Então,
pela nossa definiçãode consequência lógica, tem de haver uma cir-
Seção 4.3
120 / A Lógica dos Conectivos Booleanos
cunstância posśıvel em que P é verdadeira mas Q é falsa. Esta cir-
cunstância irá determinar valores verdade para as sentenças atômicas
em P e Q, e esses valores correspondem a uma linha na tabela ver-
dade conjunta para P e Q, uma vez que todas as atribuições posśıveis
de valores verdade para as sentenças atômicas são representadas na
tabela verdade. Além disso, visto que P e Q são constrúıdas a par-
tir das sentenças atômicas e conectivos verofuncionais, e uma vez
que a primeira é verdadeira na circunstância original e a última é
falsa, P receberá T nesta linha e Q receberá F. Assim, Q não é uma
consequência tautológica de P.
Vejamos um exemplo muito simples. Suponha que queremos verificar se
A ∨ B é uma consequência de A ∧ B. A tabela verdade conjunta para estas
sentenças se parece com isto.
A B A ∧ B A ∨ B
t t T T
t f F T
f t F T
f f F F
Quando você compara as colunas nestas duas sentenças, você vê que as sen-
tenças definitivamente não são tautologicamente equivalentes. Não é surpresa.
Mas estamos interessados em saber se A ∧ B implica logicamente A ∨ B, e as-
sim as únicas linhas com as quais nos preocupamos são aquelas em que a
primeira sentença é verdadeira. A ∧ B só é verdadeira na primeira linha, e
A ∨ B também é verdade nessa linha. Portanto, esta tabela mostra que A ∨ B
é uma consequência tautológica (e, portanto, uma consequência lógica) de
A ∧ B.
Observe que nossa tabela também demonstra que A ∧ B não é uma con-
sequência tautológica de A ∨ B, uma vez que existem linhas nas quais a última
sentença é verdade e a primeira falsa. Será que isso demonstra que A ∧ B não
é uma consequência lógica de A ∨ B? Bem, nós temos que ter cuidado. A ∧ B
não é, em geral, uma consequência lógica de A ∨ B, mas pode ser, em certos
casos, dependendo das sentenças A e B. Vamos pedir a você para pensar em
um exemplo nos exerćıcios.
Nem toda consequência lógica de uma sentença é uma consequência tau-
tológica dessa sentença. Por exemplo, a sentença a = c é uma consequênciaconsequência lógica vs.
consequência
tautológica
lógica da sentença (a = b ∧ b = c), mas não é uma consequência tautológica
dela. Pense sobre a linha que atribui T para as sentenças atômicas a = b e
b = c, mas F à sentença a = c. É evidente que esta linha, a qual impede a = c
de ser uma consequência tautológica de (a = b ∧ b = c), não respeita os signifi-
Caṕıtulo 4
Consequência lógica e tautológica / 121
cados das sentenças atômicas a partir das quais as sentenças são constrúıdas.
Ela não corresponde a uma circunstância verdadeira posśıvel, mas o método
da tabela verdade não detecta isso.
O método da tabela verdade de verificar consequência tautológica não
se restringe a apenas uma premissa. Você pode aplicá-lo a argumentos com
qualquer número de premissas P1, . . . ,Pn e conclusão Q. Para isso, você tem
que construir uma tabela verdade conjunta para todas as sentenças P1, . . . ,Pn
e Q. Uma vez feito isso, você precisa verificar cada linha em que todas as
premissas são verdadeiras para ver se a conclusão também é verdadeira. Se
assim for, a conclusão é uma consequência tautológica das premissas.
Vamos tentar fazer isso em alguns exemplos simples. Primeiro, suponha
que queremos verificar se B é uma consequência das duas premissas A ∨ B e
¬A. A tabela verdade conjunta para estas três sentenças fica assim. (Note-se
que como uma das nossas sentenças-alvo, a conclusão B, é atômica, simples-
mente repetimos a coluna de referência quando esta sentença aparece nova-
mente à direita.)
A B A ∨ B ¬A B
t t T F T
t f T F F
f t T T T
f f F T F
Examinando as colunas sob nossas duas premissas, A ∨ B e ¬A, vemos que
há apenas uma linha em que ambas as premissas são verdadeiras, ou seja, a
terceira. E na terceira linha, a conclusão B também fica verdadeira. Então B
é de fato uma consequência tautológica (e, portanto, lógica) destas premissas.
Em ambos os exemplos que examinamos até agora, houve apenas uma
linha em que as todas as premissas são verdadeiras. Isso faz com que seja fácil
verificar a validade dos argumentos, mas não é de maneira alguma algo com o
qual você pode contar. Por exemplo, suponha que o método da tabela verdade
foi utilizado para verificar se A ∨ C é uma consequência de A ∨ ¬B e B ∨ C. A
tabela verdade conjunta para estas três sentenças se parece com isto.
Seção 4.3
122 / A Lógica dos Conectivos Booleanos
A B C A ∨ ¬B B ∨ C A ∨ C
t t t T f T T
t t f T f T T
t f t T t T T
t f f T t F T
f t t F f T T
f t f F f T F
f f t T t T T
f f f T t F F
Aqui, há quatro linhas em que as premissas, A ∨ ¬B e B ∨ C, são ver-
dadeiras: a primeira, a segunda, a terceira e a sétima. Mas em cada uma
destas linhas a conclusão, A ∨ C, também é verdadeira. A conclusão é ver-
dadeira em outras linhas também, mas nós não nos importamos com isso.
Essa inferência, de A ∨ ¬B e B ∨ C para A ∨ C, é logicamente válida, e é uma
instância de um padrão importante conhecido na ciência da computação como
resolução.
Devemos olhar para um exemplo onde o método de tabela verdade revela
que a conclusão não é consequência tautológica das premissas. Na verdade, a
última tabela verdade vai servir a esse propósito. Esta tabela também mostra
que a sentença A ∨ ¬B não é uma consequência tautológica das duas premissas
B ∨ C e A ∨ C. Você pode encontrar a linha que mostra isto? (Dica: Tem que
ser a primeira, a segunda, a terceira, a quinta, ou a sétima, já que estas são
as linhas em que B ∨ C e A ∨ C são verdadeiras.)
Lembre-se
Sejam P1, . . . ,Pn e Q sentenças de fol constrúıdas a partir de sentenças
atômicas usando conectivos verofuncionais. Construa uma tabela verdade
conjunta para todas essas sentenças.
1. Q é uma consequência tautológica de P1, . . . ,Pn se, e somente se, toda
linha que atribui T para cada uma de P1, . . . ,Pn também atribui T a
Q.
2. Se Q é uma consequência tautológica de P1, . . . ,Pn, então Q é também
uma consequência lógica de P1, . . . ,Pn.
3. Algumas consequências lógicas não são consequências tautológicas.
Caṕıtulo 4
Consequência tautológica em Fitch / 123
Exerćıcios
Para cada um dos argumentos abaixo, use o método da tabela verdade para determinar se a conclusão
é uma consequência tautológica das premissas. Sua tabela verdade para o Exerćıcio 4.24 será bastante
grande. É bom para a alma construir uma tabela verdade grande de vez em quando. Seja grato por ter
Boole para ajudá-lo. (Mas certifique-se de construir suas próprias colunas de referência!)
4.20
�
(Tet(a) ∧ Small(a)) ∨ Small(b)
Small(a) ∨ Small(b)
4.21
�
Taller(claire,max) ∨ Taller(max, claire)
Taller(claire,max)
¬Taller(max, claire)
4.22
�
Large(a)
Cube(a) ∨ Dodec(a)
(Cube(a) ∧ Large(a)) ∨ (Dodec(a) ∧ Large(a))
4.23
��
A ∨ ¬B
B ∨ C
C ∨ D
A ∨ ¬D
4.24
��
¬A ∨ B ∨ C
¬C ∨ D
¬(B ∧ ¬E)
D ∨ ¬A ∨ E
4.25
��
Dê um exemplo de duas sentenças diferentes A e B na linguagem dos blocos tais que A ∧ B é
uma consequência lógica de A ∨ B. [Dica: Note que A ∧ A é uma consequência lógica de A ∨ A,
mas aqui insistimos que A e B sejam sentenças distintas.]
Seção 4.4
Consequência tautológica em Fitch
Nós esperamos que você tenha resolvido o Exerćıcio 4.24, porque a solução
dá a você um sentido tanto do poder como das desvantagens do método da
tabela verdade. Nós fomos tentados a pedir-lhe para construir uma tabela que
exigisse 64 linhas, mas pensamos melhor. Construir tabelas verdade grandes
podem construir caráter, mas como a maioria das coisas que formam o caráter,
é uma chatice.
Verificar para ver se Q é uma consequência tautológica de P1, . . . ,Pn é um
procedimento mecânico. Se as sentenças são longas pode exigir muitotrabalho
Seção 4.4
124 / A Lógica dos Conectivos Booleanos
tedioso, mas não é preciso qualquer originalidade. Isto é exatamente o tipo
de coisa no qual os computadores são bons. Devido a isso, nós constrúımos
um mecanismo para Fitch, chamado Taut Con, que é semelhante ao AnaMecanismo Taut Con
Con, mas verifica se a sentença é uma consequência tautológica das sentenças
citadas em apoio. Como Ana Con, Taut Con não é realmente uma regra de
inferência (vamos introduzir regras de inferência para os conectivos booleanos
no Caṕıtulo 6), mas é útil para testar rapidamente se uma sentença é tauto-
logicamente resultado das outras.
Tente você mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
� 1. Inicie Fitch e abra o arquivo Taut Con 1. Neste arquivo você vai encontrar
um argumento que tem a mesma forma que o argumento no Exerćıcio 4.23.
(Ignore as duas sentenças objetivo. Nós vamos chegar a elas mais tarde.)
Mova o cursor de foco para o último passo da prova. A partir do menu
Rule?, vá até o submenu Con e escolha Taut Con.
� 2. Agora cite as três premissas como suporte para esta sentença e confira
o passo. O passo não irá conferir uma vez que esta sentença não é uma
consequência tautológica das premissas, como você descobriu se você fez
Exerćıcio 4.23, que tem a mesma forma desta inferência.
� 3. Edite o passo que não conferiu para ler:
Home(max) ∨ Home(carl)
Esta sentença é uma consequência tautológica de duas premissas. Descubra
quais as duas e cite apenas elas. Se você citou as duas certas, o passo deve
conferir. Experimente.
� 4. Adicione mais um passo à prova e insira a sentença:
Home(carl) ∨ (Home(max) ∧ Home(pris))
Use Taut Con para ver se esta sentença é tautologicamente resultado das
três premissas. SelecioneVerify Proof do menu Proof. Você vai descobrir
que, embora o passo confira, o objetivo não confere. Isto é porque nós
colocamos uma restrição especial sobre o uso de Taut Con neste exerćıcio.
� 5. Selecione View Goal Constraints (Ver Restrições do Objetivo) do
menu Goal (Objetivo). Você vai descobrir que nesta prova, você está
autorizado a usar Taut Con, mas só pode citar duas sentenças ou menos
quando você usá-lo. Feche a janela do objetivo para voltar para a prova.
Caṕıtulo 4
Consequência tautológica em Fitch / 125
� 6. A sentença que você inseriu é resultado da sentença imediatamente acima
dela e de apenas uma das três premissas. Remova a citação às três pre-
missas e veja se você pode conferir o passo citando apenas duas sentenças
de apoio. Quando você tiver êxito, verifique a prova e salve-a como Proof
Taut Con 1. Não feche a prova, uma vez que ela será necessária na próxima
seção “Tente você mesmo.”
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parabéns
Você provavelmente está curioso sobre a relação entre Taut Con e Ana
Con—e por falar nisso, o que o outro item misterioso no menu de Con, FO
Con, pode fazer. Estes são, de fato três métodos cada vez mais fortes que Fitch Taut Con, FO Con, e
Ana Conusa para testar a consequência lógica. Taut Con é o mais fraco. Ele verifica se
o passo atual é resultado das sentenças citadas em virtude dos significados dos
conectivos verofuncionais. Ele ignora o significado de quaisquer predicados que
aparecem na sentença e, quando introduzirmos quantificadores à linguagem,
ele irá ignorá-los também.
Para ajudá-lo a manter o controle das informações que Taut Con con-
sidera ao verificar um passo, Fitch tem “óculos de proteção” que obscure-
cem a informação que não serão consideradas quando verificando o passo.
Como dissemos acima, as únicas coisas que importam quando verificamos um
passo justificado por um passo Taut Con são os conectivos proposicionais
nas fórmulas, e o padrão de ocorrência das fórmulas atômicas.
O que isto significa é que os significados dos śımbolos e nomes de predicados
nas fórmulas não importam, e os óculos de proteção de Fitch obscurecem essas
informações. Quando você coloca os óculos, cada fórmula atômica envolvida
no passo aparece como um bloco de cor, escondendo a fórmula atômica em
particular que está presente. Cada ocorrência da mesma fórmula atômica será
representada pela mesma cor, e diferentes fórmulas terão cores diferentes.
Tente você mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
�1. Volte novamente para o arquivo Taut Con 1 que você fez na seção “Tente
você mesmo” anterior, e foque no último passo da prova, que contém uma
aplicação da regra Taut Con.
�2. Clique sobre a imagem de um par de óculos que aparece à direita do nome
da regra, e observe como a conclusão e as sentenças citadas transformam-se
em blocos de cor.
�
Seção 4.4
126 / A Lógica dos Conectivos Booleanos
3. Você deverá ver uma versão mais colorida disto
Hungry(carl) ∨ Hungry(pris)
Home(max) ∨ Hungry(carl)
Hungry(carl ∨ ( Home(max) ∧ Hungry(pris) ) Taut Con
Certifique-se de entender como as fórmulas atômicas se relacionam com
suas cores correspondentes.
� 4. Não há nada para salvar.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parabéns
FO Con, que significa “consequência de primeira ordem” (First Order
Consequence em Inglês), presta atenção aos conectivos verofuncionais, aos
quantificadores e ao predicado de identidade quando verifica consequência.
FO Con, por exemplo, identificaria a = c como consequência de a = b ∧ b = c.
Ela é mais forte do que Taut Con no sentido de que qualquer consequência
que Taut Con reconhecida como válida também será reconhecida por FO
Con. Mas pode levar mais tempo, uma vez que tem que aplicar um proce-
dimento mais complexo, graças à identidade e aos quantificadores. Depois de
chegarmos aos quantificadores, vamos falar mais sobre o procedimento que ela
está aplicando.
A regra mais forte das três é Ana Con, a qual tenta reconhecer as con-
sequências devido aos conectivos verofuncionais, quantificadores, identidade,
e a maior parte dos predicados da linguagem de blocos. (Ana Con ignora
Between e Adjoins, simplesmente por razões práticas.) Qualquer inferência
que confere usando ou Taut Con ou FO Con deve, em prinćıpio, conferir
com Ana Con também. Na prática, porém, o procedimento que Ana Con
usa pode “atolar” ou ficar sem memória em casos onde os dois primeiros não
têm problemas.
Como dissemos antes, você só deve usar um procedimento a partir do
menu Con quando o exerćıcio deixa claro que o procedimento é permitido
na solução. Além disso, se um exerćıcio pede para você usar Taut Con, não
use FO Con ou Ana Con, mesmo que essas regras mais poderosas pareçam
funcionar tão bem quanto a primeira. Se você estiver em dúvida sobre quais
regras você tem permissão de usar, escolhaView Goal Constraints no menu
Goal.
Caṕıtulo 4
Consequência tautológica em Fitch / 127
Tente você mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
� 1. Abra o arquivo Taut Con 2. Você vai encontrar uma prova contendo dez
passos cujas regras não foram especificadas.
�2. Foque em cada um destes passos. Você vai descobrir que as premissas de
apoio já foram citados. Convença-se que o passo é um resultado das sen-
tenças citadas. Ela é uma consequência tautológica das sentenças citadas?
Se for, altere a regra para Taut Con e veja se você estava certo. Se não,
mude para Ana Con e veja se ele confere. (Se Taut Con funcionar,
certifique-se de usá-la em vez da mais forte Ana Con.)
�3. Quando todos os seus passos conferirem usando Taut Con ou Ana Con,volte e encontre o passo cuja regra pode ser alterada de Ana Con para a
mais fraca FO Con.
�4. Quando cada passo verificar usando a regra Con mais fraca posśıvel, salve
a sua prova Proof Taut Con 2.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parabéns
Exerćıcios
4.26
�
Se você pulou as seções Tente você mesmo, volte e faça-as agora. Submeta os arquivos Proof
Taut Con 1 e Proof Taut Con 2.
Para cada um dos seguintes argumentos, decida se a conclusão é uma consequência tautológica das
premissas. Se for, submeta uma prova que estabelece a conclusão utilizando uma ou mais aplicações de
Taut Con. Não cite mais de duas sentenças de cada vez para qualquer uma das suas aplicações de
Taut Con. Se a conclusão não é uma consequência das premissas, submeta um mundo contraexemplo
mostrando que o argumento não é válido.
4.27
�
Cube(a) ∨ Cube(b)
Dodec(c) ∨ Dodec(d)
¬Cube(a) ∨ ¬Dodec(c)
Cube(b) ∨ Dodec(d)
4.28
�
Large(a) ∨ Large(b)
Large(a) ∨ Large(c)
Large(a) ∧ (Large(b) ∨ Large(c))
Seção 4.4
128 / A Lógica dos Conectivos Booleanos
4.29
�
Small(a) ∨ Small(b)
Small(b) ∨ Small(c)
Small(c) ∨ Small(d)
Small(d) ∨ Small(e)
¬Small(c)
Small(a) ∨ Small(e)
4.30
�
Tet(a) ∨ ¬(Tet(b) ∧ Tet(c))
¬(¬Tet(b) ∨ ¬Tet(d))
(Tet(e) ∧ Tet(c)) ∨ (Tet(c) ∧ Tet(d))
Tet(a)
Seção 4.5
Trabalhando com a negação
Quando duas sentenças são logicamente equivalentes, cada uma é uma con-
sequência lógica da outra. Como resultado, ao dar uma prova informal, você
sempre pode ir de uma sentença estabelecida para aquela que é logicamente
equivalente a ela. Este fato faz observações como as leis de DeMorgan e dupla
negação bastante útil ao darmos provas informais.
O que faz essas equivalências ainda mais úteis é o fato de que, sentenças
logicamente equivalentes podem ser substitúıdas uma pela outra, no contextosubstituição de
equivalentes lógicos de uma sentença maior e as sentenças resultantes também serão logicamente
equivalentes. Um exemplo ajudará a ilustrar o que queremos dizer. Suponha
que começamos com a sentença:
¬(Cube(a) ∧ ¬¬Small(a))
Pelo prinćıpio da dupla negação, sabemos que Small(a) é logicamente equiva-
lente a ¬¬Small(a). Uma vez que estas têm exatamente as mesmas condições
verdade, podemos substituir ¬¬Small(a) por Small(a), no contexto da sentença
acima, e o resultado,
¬(Cube(a) ∧ Small(a))
será logicamente equivalente à sentença original, um fato que você pode con-
ferir através da construção de uma tabela verdade conjunta para as duas
sentenças.
Podemos afirmar este fato importante da seguinte maneira. Vamos escrever
S(P) para uma sentença fol que contém a sentença (possivelmente complexa)
P como uma parte componente, e S(Q) para o resultado de substituir P por
Q em S(P). Então, se P e Q são logicamente equivalentes:
P ⇔ Q
Caṕıtulo 4
Trabalhando com a negação / 129
temos que S(P) e S(Q) também são logicamente equivalentes:
S(P) ⇔ S(Q)
Isto é conhecido como o prinćıpio da substituição de equivalentes lógicos.
Não vamos provar este prinćıpio no momento, porque exige uma prova por
indução, um estilo de prova ao qual chegaremos em um caṕıtulo posterior.
Mas a observação nos permite usar algumas equivalências simples para fazer
algumas coisas bem surpreendentes. Por exemplo, usando apenas as duas leis
de DeMorgan e dupla negação, podemos tomar qualquer sentença constrúıda
com ∧, ∨, e ¬, e transformá-la em uma onde ¬ aplica-se apenas às sentenças
atômicas. Outra forma de expressar isso é que qualquer sentença constrúıda
a partir de sentenças atômicas utilizando os três conectivos ∧, ∨, e ¬ é logi-
camente equivalente a uma constrúıda a partir de literais usando apenas ∧ e
∨.
Para obter tal sentença, basta mover o ¬ para dentro, trocando ∧ por ∨,
∨ por ∧, e cancelar qualquer par de ¬’s que estão ao lado uns dos outros, e forma normal da
negação(FNN)não separados por quaisquer parênteses. Tal sentença é dita estar em forma
normal da negação ou FNN. Aqui está um exemplo de uma derivação da
forma normal da negação de uma sentença. Usamos A, B, e C para representar
qualquer sentença atômica da linguagem.
¬((A ∨ B) ∧ ¬C) ⇔ ¬(A ∨ B) ∨ ¬¬C
⇔ ¬(A ∨ B) ∨ C
⇔ (¬A ∧ ¬B) ∨ C
Em leituras e derivações desse tipo, lembre-se que o śımbolo ⇔ não é em
si um śımbolo da linguagem de primeira ordem, mas uma forma abreviada
de dizer que duas sentenças são logicamente equivalentes. Neste derivação,
o primeiro passo é uma aplicação da primeira lei de DeMorgan à sentença
inteira. O segundo passo aplica dupla negação ao componente ¬¬C. O passo
final é uma aplicação da segunda lei de DeMorgan ao componente de ¬(A ∨ B).
A sentença com a qual terminamos está na forma normal da negação, uma
vez que os śımbolos de negação aplicam-se apenas às sentenças atômicas.
Terminamos esta seção com uma lista de algumas equivalências lógicas
adicionais que nos permitem simplificar sentenças de maneiras úteis. Você já
construiu tabelas verdade para a maioria dessas equivalências nos Exerćıcios
4.13-4.16 no final da Seção 4.2.
1. (Associatividade do ∧) Uma sentença fol P ∧ (Q ∧ R) é logicamente associatividade
equivalente a (P ∧ Q) ∧ R, a qual é por sua vez equivalente a P ∧ Q ∧ R.
Isto é,
P ∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R ⇔ P ∧ Q ∧ R
Seção 4.5
130 / A Lógica dos Conectivos Booleanos
2. (Associatividade do ∨) Uma sentença fol P ∨ (Q ∨ R) é logicamente
equivalente a (P ∨ Q) ∨ R, a qual é por sua vez equivalente a P ∨ Q ∨ R.
Isto é,
P ∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R ⇔ P ∨ Q ∨ R
3. (Comutatividade do ∧) Uma conjunção P ∧ Q é logicamente equivalentecomutatividade
a Q ∧ P. Isto é,
P ∧ Q ⇔ Q ∧ P
Como resultado, qualquer rearranjo dos componentes de uma conjunção
de uma sentença fol é logicamente equivalente à sentença original. Por
exemplo, P ∧ Q ∧ R é equivalente a R ∧ Q ∧ P.
4. (Comutatividade do ∨) Uma disjunção P ∨ Q é logicamente equivalente
a Q ∨ P. Isto é,
P ∨ Q ⇔ Q ∨ P
Como resultado, qualquer rearranjo dos componentes de uma disjunção
de uma sentença fol é logicamente equivalente à sentença original. Por
exemplo, P ∨ Q ∨ R é equivalente a R ∨ Q ∨ P.
5. (Idempotência do ∧)) Uma conjunção P ∧ P é equivalente a P. Isto é,idempotência
P ∧ P ⇔ P
De modo mais geral (dada a comutatividade), qualquer conjunção com
um componente repetido é equivalente ao resultado da remoção de to-
dos, menos uma ocorrência desse componente. Por exemplo, P ∧ Q ∧ P
é equivalente a P ∧ Q.
6. (Idempotência do ∨) Uma disjunção P ∨ P é equivalente a P. Isto é,
P ∨ P ⇔ P
De modo mais geral (dada a comutatividade), qualquer disjunção com
um componente repetido é equivalente ao resultado da remoção de to-
dos, menos uma ocorrência desse componente. Por exemplo, P ∨ Q ∨ P
é equivalente a P ∨ Q.
Aqui está um exemplo onde usamos algumas dessas leis para demonstrar
que a primeira sentença na lista a seguir é logicamente equivalente à última.
Mais uma vez (como no que se segue), usamos A, B, e C para representar sen-
tenças atômicas arbitrárias de fol. Assim, o resultado está na forma normal
da negação.
Caṕıtulo 4
Trabalhando com a negação / 131
(A ∨ B) ∧ C ∧ (¬(¬B ∧ ¬A) ∨ B) ⇔ (A ∨ B) ∧ C ∧ ((¬¬B ∨ ¬¬A) ∨ B)
⇔ (A ∨ B) ∧ C ∧ ((B ∨ A) ∨ B)
⇔ (A ∨ B) ∧ C ∧ (B ∨ A ∨ B)
⇔ (A ∨ B) ∧ C ∧ (B ∨ A)
⇔ (A ∨ B) ∧ C ∧ (A ∨ B)
⇔ (A ∨ B) ∧ C
Chamamos uma demonstração deste tipo de cadeia de equivalências. O cadeia de equivalências
primeiro passo nessa cadeia é justificada por uma das leis de DeMorgan. O
segundo passo envolve duas aplicações de dupla negação. No próximo passo,
usamos associatividade para remover os parênteses desnecessários. No quarto
passo, nós usamos idempotência do ∨. O penúltimo passo usa comutatividade
do ∨, enquanto o passo final usa idempotência do ∧.
Lembre-se
1. Substituição de equivalentes:Se P e Q são logicamente equivalentes:
P ⇔ Q
então os resultados da substituição de uma pela outra no contexto de
uma sentença maior também são logicamente equivalentes:
S(P) ⇔ S(Q)
2. A sentença está na formal normal da negação (FNN) se todas as
ocorrências de ¬ aplicam-se diretamente a sentenças atômicas.
3. Qualquer sentença constrúıda a partir de sentenças atômicas usando
apenas ∧, ∨ e ¬ pode ser colocada na forma normal da negação através
de aplicações repetidas das leis de DeMorgan e dupla negação.
4. Sentenças muitas vezes podem ser simplificadas ainda mais utilizando
os prinćıpios da associatividade, comutatividade e idempotência.
Seção 4.5
132 / A Lógica dos Conectivos Booleanos
Exerćıcios
4.31
�
(Forma normal da negação) Use Tarski’s World para abrir Turing’s Sentences. Você encontrará
as seguintes cinco sentenças, cada uma seguida por uma posição de sentença vazia.
1. ¬(Cube(a) ∧ Larger(a, b))
3. ¬(Cube(a) ∨ ¬Larger(b, a))
5. ¬(¬Cube(a) ∨ ¬Larger(a, b) ∨ a �= b)
7. ¬(Tet(b) ∨ (Large(c) ∧ ¬Smaller(d, e)))
9. Dodec(f) ∨ ¬(Tet(b) ∨ ¬Tet(f) ∨ ¬Dodec(f))
Nas posições vazias, escreva a forma normal da negação da sentença acima dela. Em seguida,
construa qualquer mundo onde todos os nomes estejam em uso. Se você chegar às formas
normais da negação corretas, cada sentença numerada par terá o mesmo valor verdade em seu
mundo que a sentença numerada ı́mpar acima dela. Verifique que isto acontece em seu mundo.
Submeta o arquivo de sentenças modificado como Sentences 4.31.
4.32
�
(Forma normal da negação) Use Tarski’s World para abrir o arquivo Sextus’ Sentences. Nos
espaços numerados ı́mpares, você encontrará as seguintes sentenças.
1. ¬(Home(carl) ∧ ¬Home(claire))
3. ¬[Happy(max) ∧ (¬Likes(carl, claire) ∨ ¬Likes(claire, carl))]
5. ¬¬¬[(Home(max) ∨ Home(carl)) ∧ (Happy(max) ∨ Happy(carl))]
Use as leis de Dupla Negação e de DeMorgan para colocar cada sentença na forma normal da
negação no espaço abaixo. Submeta o arquivo modificado como Sentences 4.32.
Em cada um dos seguintes exerćıcios, use associatividade, comutatividade e idempotência para simplificar
a sentença, o tanto quanto você pode, usando apenas estas regras. Sua resposta deve consistir de uma
cadeia de equivalências lógicas, como a cadeia dada na página 131. Em cada passo da cadeia, indique
qual prinćıpio você está usando.
4.33
�
(A ∧ B) ∧ A 4.34
�
(B ∧ (A ∧ B ∧ C))
4.35
�
(A ∨ B) ∨ (C ∧ D) ∨ A 4.36
�
(¬A ∨ B) ∨ (B ∨ C)
4.37
�
(A ∧ B) ∨ C ∨ (B ∧ A) ∨ A
Caṕıtulo 4
Formas normais conjuntiva e disjuntiva / 133
Seção 4.6
Formas normais conjuntiva e disjuntiva
Vimos que com alguns prinćıpios simples da lógica booleana, podemos começar
com uma sentença e transformá-la em uma sentença logicamente equiva-
lente na forma normal da negação, aquela em que todas as negações ocor-
rem na frente de sentenças atômicas. Podemos melhorar isso, introduzindo
as chamadas leis distributivas. Estas equivalências adicionais nos permitirão
transformar sentenças para o que se conhece como forma normal conjuntiva
(FNC) e forma normal disjuntiva (FND). Estas formas normais são muito im-
portantes em certas aplicações da lógica em ciência da computação, como dis-
cutiremos no Caṕıtulo 17. Também usaremos a forma normal disjuntiva para
demonstrar um fato importante sobre os conectivos booleanos no Caṕıtulo 7.
Lembre-se que em álgebra você aprendeu que multiplicação distribui so-
bre adição: a × (b + c) = (a × b) + (a × c). As leis distributivas da lógica distribuição
formalmente parecem a mesma coisa. Uma versão nos diz que P ∧ (Q ∨ R) é
logicamente equivalente a (P ∧ Q) ∨ (P ∧ R). Isto é, ∧ distribui sobre ∨. Para
ver que isto é assim, perceba que a primeira sentença é verdadeira se, e so-
mente se, P mais pelo menos uma de Q ou R é verdadeira. Mas um momento
de reflexão mostra que a segunda sentença é verdadeira exatamente nas mes-
mas circunstâncias. Isto também pode ser confirmado através da construção
de uma tabela verdade conjunta para as duas sentenças, o que você já fez se
fez o Exerćıcio 4.17.
Na aritmética, + não distribui sobre ×. No entanto, ∨ distribui sobre ∧.
Ou seja, P ∨ (Q ∧ R) é logicamente equivalente a (P ∨ Q) ∧ (P ∨ R), como você
também descobriu no Exerćıcio 4.18.
Lembre-se
(As leis distributivas) Para quaisquer sentenças P, Q, e R:
1. Distribuição de ∧ sobre ∨: P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
2. Distribution de ∨ sobre ∧: P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
Como você pode recordar da álgebra, a lei distributiva para × sobre + é
incrivelmente útil. Ela nos permite transformar qualquer expressão algébrica
envolvendo + e ×, não importa quão complexa, em uma que é apenas uma
soma de produtos. Por exemplo, a seguinte transformação usa distribuição
Seção 4.6
134 / A Lógica dos Conectivos Booleanos
três vezes.
(a+ b)(c+ d) = (a+ b)c+ (a+ b)d
= ac+ bc+ (a+ b)d
= ac+ bc+ ad+ bd
Exatamente da mesma maneira, a distribuição de ∧ sobre ∨ permite-nos
transformar qualquer sentença constrúıda a partir de literais usando ∧ e ∨
em uma sentença logicamente equivalente, que é uma disjunção de (uma ou
mais) conjunções de (um ou mais) literais. Isto é, utilizando esta primeira
lei distributiva, podemos transformar qualquer sentença na forma normal da
negação em uma sentença que é uma disjunção de conjunções de literais. Uma
sentença dessa forma é dita estar na forma formal disjuntiva.forma normal
disjuntiva (FND) Aqui está um exemplo que se assemelha ao nosso exemplo algébrico. Ob-
serve que, como no exemplo algébrico, estamos distribuindo tanto da direita
quanto da esquerda, apesar de nossa apresentação da regra só ilustrar dis-
tribuição da esquerda.
(A ∨ B) ∧ (C ∨ D) ⇔ [(A ∨ B) ∧ C] ∨ [(A ∨ B) ∧ D]
⇔ (A ∧ C) ∨ (B ∧ C) ∨ [(A ∨ B) ∧ D]
⇔ (A ∧ C) ∨ (B ∧ C) ∨ (A ∧ D) ∨ (B ∧ D)
Como você pode ver, a distribuição de ∧ sobre ∨ permite-nos levar śımbolos
de conjunção cada vez mais para dentro, assim como as leis de DeMorgan nos
permitem mover negações mais para dentro. Assim, se tomarmos qualquer
sentença e usarmos primeiro DeMorgan (e dupla negação) para obtermos uma
sentença na forma normal da negação, podemos então usar esta primeira lei
de distribuição para obter uma sentença na forma normal disjuntiva, na qual
todos os śımbolos de conjunção aplicam-se a literais.
Da mesma forma, usando a distribuição do ∨ sobre ∧, podemos trans-
formar qualquer sentença na forma normal da negação em uma que é uma
conjunção de uma ou mais sentenças, cada um das quais é uma disjunção de
um ou mais literais. A sentença nesta forma é dita estar na forma normal
conjuntiva (FNC). Aqui está um exemplo, paralelo ao dado acima, mas comforma normal
conjuntiva (FNC) ∧ e ∨ trocados:
(A ∧ B) ∨ (C ∧ D) ⇔ [(A ∧ B) ∨ C] ∧ [(A ∧ B) ∨ D]
⇔ (A ∨ C) ∧ (B ∨ C) ∧ [(A ∧ B) ∨ D]
⇔ (A ∨ C) ∧ (B ∨ C) ∧ (A ∨ D) ∧ (B ∨ D)
Na página 129, mostramos como transformar a sentença ¬((A ∨ B) ∧ ¬C)
em uma na forma normal da negação. O resultado foi (¬A ∧ ¬B) ∨ C. Esta sen-
tença está na forma normal disjuntiva. Vamos repetir a nossa transformação,
mas continuar até chegarmos a uma sentença na forma normal conjuntiva.
Caṕıtulo 4
Formas normais conjuntiva e disjuntiva / 135
¬((A ∨ B) ∧ ¬C) ⇔ ¬(A ∨ B) ∨ ¬¬C
⇔ ¬(A ∨ B) ∨ C
⇔ (¬A ∧ ¬B) ∨ C
⇔ (¬A ∨ C) ∧ (¬B ∨ C)
É importante lembrar que uma sentença pode se contar como estando
tanto na forma normal conjuntiva como na forma normal disjuntiva, ao mesmo
tempo. Por exemplo, a sentença
Home(claire) ∧ ¬Home(max)
está em ambas FND and FNC. Por um lado, ela está na forma normal dis-
juntiva uma vez que é uma disjunção de uma sentença (única) que é uma
conjunção de dois literais. Por outro lado, está na forma normal conjuntiva,
uma vez que é uma conjunção de duas sentenças, cada uma das quais é uma
disjunção de um literal.No caso de você encontrar esta última observação confusa, aqui estão testes
simples para verificar se sentenças estão na forma normal disjuntiva e forma
normal conjuntiva. Os testes assumem que a sentença não tem parênteses
desnecessários e contém somente os conectivos ∧, ∨ e ¬.
Para verificar se uma sentença está na FND, se pergunte se todos os teste para FND
śımbolos de negação se aplicam diretamente a sentenças atômicas e
se todos os śımbolos de conjunção se aplicam diretamente a literais.
Se ambas as respostas são sim, então a sentença está na forma normal
disjuntiva.
Para verificar se uma sentença está na FNC, se pergunte se todos os teste para FNC
śımbolos de negação se aplicam diretamente a sentenças atômicas e
se todos os śımbolos de disjunção se aplicam diretamente a literais.
Se ambas as respostas são sim, então a sentença está na forma normal
conjuntiva.
Agora olhe para a sentença acima e observe que ela passa em ambos os
testes (no caso FNC porque não tem śımbolos de disjunção).
Seção 4.6
136 / A Lógica dos Conectivos Booleanos
Lembre-se
1. Uma sentença está na forma normal disjuntiva (FND), se for uma
disjunção de uma ou mais conjunções de um ou mais literais.
2. Uma sentença está na forma normal conjuntiva (FNC), se for uma
conjunção de uma ou mais disjunções de um ou mais literais.
3. Distribuição do ∧ sobre ∨ permite que você transforme qualquer sen-
tença na forma normal da negação para a forma normal disjuntiva.
4. Distribuição do ∨ sobre ∧ permite que você transforme qualquer sen-
tença na forma normal da negação para a forma normal conjuntiva.
5. Algumas sentenças estão em ambas FNC and FND.
Tente você mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
� 1. Use Tarski’s World para abrir o arquivo DNF Example. Você vai encontrar
duas sentenças neste arquivo. A segunda sentença é o resultado de colo-
car a primeira na forma normal disjuntiva, então as duas sentenças são
logicamente equivalentes.
� 2. Construa um mundo em que as sentenças são verdadeiras. Uma vez que
são equivalentes, você poderia tentar fazer com que qualquer uma das duas
seja verdadeira, mas você vai achar a segunda mais fácil de trabalhar.
� 3. Jogue o jogo para cada sentença, comprometido corretamente com a ver-
dade da sentença. Você deve ser capaz de vencer duas vezes. Conte o
número de passos que você leva para ganhar.
� 4. Em geral, é mais fácil avaliar o valor verdade de uma sentença na forma
normal disjuntiva. Isto surge no jogo, o qual leva, no máximo, três passos
para uma sentença na FND, um para cada ∨, ∧, e ¬, nessa ordem. Não há
limite para o número de passos que uma sentença em outras formas pode
levar.
� 5. Salve o mundo que você criou como World DNF 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Parabéns
Caṕıtulo 4
Formas normais conjuntiva e disjuntiva / 137
Exerćıcios
4.38
�
Se você pulou a seção Tente você mesmo, volte e faça-a agora. Submeta o arquivo World
DNF 1.
4.39
�
Abra CNF Sentences. Neste arquivo, você encontrará as seguintes sentenças na forma normal
conjuntiva nas posições numeradas ı́mpares, mas você vai ver que as posições numeradas pares
estão em branco.
1. (LeftOf(a, b) ∨ BackOf(a, b)) ∧ Cube(a)
3. Larger(a, b) ∧ (Cube(a) ∨ Tet(a) ∨ a = b)
5. (Between(a, b, c) ∨ Tet(a) ∨ ¬Tet(b)) ∧ Dodec(c)
7. Cube(a) ∧ Cube(b) ∧ (¬Small(a) ∨ ¬Small(b))
9. (Small(a) ∨Medium(a)) ∧ (Cube(a) ∨ ¬Dodec(a))
Nas posições numeradas pares você deve preencher com uma sentença na FND logicamente
equivalente à sentença acima dela. Confira o seu trabalho, abrindo vários mundos e verificando
que cada uma de suas sentenças tem o mesmo valor verdade da que está acima dela. Envie o
arquivo modificado como Sentences 4.39.
4.40
�
Abra More CNF Sentences. Neste arquivo você vai encontrar as seguintes sentenças a cada três
posições.
1. ¬[(Cube(a) ∧ ¬Small(a)) ∨ (¬Cube(a) ∧ Small(a))]
4. ¬[(Cube(a) ∨ ¬Small(a)) ∧ (¬Cube(a) ∨ Small(a))]
7. ¬(Cube(a) ∧ Larger(a, b)) ∧ Dodec(b)
10. ¬(¬Cube(a) ∧ Tet(b))
13. ¬¬Cube(a) ∨ Tet(b)
Os dois espaços em branco que seguem cada sentença é para você transformar a primeira
sentença em forma normal da negação, e, em seguida, colocar essa sentença na FNC. Mais uma
vez, confira o seu trabalho, abrindo vários mundos para ver que cada uma de suas sentenças
tem o mesmo valor verdade que a original. Quando terminar, submeta o arquivo modificado
como Sentences 4.40.
Nos Exerćıcios 4.41-4.43, use uma cadeia de equivalências para converter cada sentença em uma sen-
tença equivalente na forma normal disjuntiva. Simplifique a sua resposta o tanto quanto posśıvel usando
as leis da associatividade, comutatividade e idempotência. A cada passo na sua cadeia, indique qual o
prinćıpio que você está aplicando. Suponha que A,B,C, e D sejam literais.
4.41
�
C ∧ (A ∨ (B ∧ C)) 4.42
�
B ∧ (A ∧ B ∧ (A ∨ B ∨ (B ∧ C)))
4.43
�
A ∧ (A ∧ (B ∨ (A ∧ C)))
Seção 4.6