Exercício Resolvido

Agora que já formalizamos as condições lógicas do problema dos astronautas, já podemos usar a tabela-verdade para ajudar a resolvê-lo. Só que temos um problema. Você lembra como se constrói a tabela-verdade? Uma coluna para cada proposição atômica e uma linha para cada combinação de valores dessas proposições, o que significa $2^n$ linhas, onde $n$ é o número de proposições. Aqui temos 8 proposições atômicas e, consequentemente, precisaríamos de $2^8$ = 256 linhas! Fazer esse trabalho manualmente é MUITO tedioso... Para resolver esse problema, nós usamos um software para preparação de planilhas. Esse tipo de software ajuda a trabalhar com tabelas em geral, pois já tem as linhas e colunas arrumadinhas para uso. Além disso, podemos usar recursos de copiar e colar para padrões que se repetem e controlar que linhas e colunas aparecem em cada instante, o que garante mais facilidade para visualizar a informação que nos interessa naquele momento. Nós mostraremos aqui partes da tabela e o seu raciocínio.

Primeiramente, vamos identificar as colunas necessárias. Temos as 8 proposições atômicas e as fórmulas correspondentes às restrições do problema (restrições (2), (3) e (4)). Para já simplificar nosso trabalho e diminuir o número de linhas, vamos apenas criar linhas que satisfazem à primeira condição, ou seja, com exatamente 2 físicos e 2 matemáticos. Por essa razão, não precisaremos da formalização dessa condição.

Quantos serão então os grupos possíveis, de acordo com a primeira condição? Comecemos pelos físicos: F, G, H e I. Os grupos que contêm exatamente dois desses físicos são 6:

F e G, F e H, F e I, G e H, G e I, H e I

O mesmo pode ser feito com os matemáticos, formando-se também 6 grupos:

R e S, R e T, R e U, S e T, S e U, T e U

Para montarmos um grupo completo, precisamos juntar um grupo de dois físicos com um grupo de dois matemáticos. Isso significa que podemos montar ao todo 36 = 6 x 6 grupos, o que corresponde a juntar cada um dos grupos de físicos com cada um dos grupos de matemáticos. A tabela preenchida com essas linhas fica então com 36 linhas, onde cada linha corresponde a um grupo possível, de acordo com a restrição (1). Ficaremos então com a tabela a seguir, na qual, ao invés de usarmos V e F para verdadeiro e falso, usamos 1 para representar verdadeiro e 0 para representar falso. Essa notação é muito utilizada na computação, então vamos utilizá-la também.

Completando agora a tabela com os valores das outras restrições, ficamos com a seguinte tabela, que explicaremos a seguir:

Note que quando encontramos uma falsidade (valor 0) como resultado de alguma restrição, não precisamos verificar o restante das restrições, pois precisamos que todas sejam verdadeiras. Então... como interpretamos essa tabela? Considere por exemplo a coluna correspondente à restrição (2) (coluna I). As linhas em que o seu valor é falso (F) correspondem a grupos que não satisfazem a restrição. Se estivermos trabalhando no software para planilhas, já podemos esconder essas linhas (linhas cor goiaba). O mesmo pode ser feito em relação às restrições (3) (linhas amarelas) e (4) (linhas azuis).

Finalmente, ficamos com apenas 13 situações possíveis, que mostramos na tabela a seguir:

Agora, podemos olhar para as questões.

Questão 1. Se R está no grupo, qual dos seguintes candidatos não pode estar?

1. H
2. I
3. S
4. T
5. U

Que linhas correspondem a grupos dos quais R faz parte? É só olhar se há alguma coluna que tem o valor falso em todas essas linhas. Sim, a coluna que diz que I faz parte do grupo. Então, se R está no grupo, I não está.