PL - Aula 1

🌫 18 Setembro 2023 - #MFES

Ficha 1

Note

As resoluções dos exercícios aqui contidos podem conter erros. Se detetares um problema (e se o souberes resolver) por favor contacta-nos.

Ex 1 (Configuração de produtos)

Certos produtos, como é o caso dos automóveis, são altamente personalizáveis, mas podem haver dependências entre as configurações. Os clientes podem não estar cientes de todas essas dependências, e poderão escolher opções de configuração inconsistentes.
Como são muitas configurações e muitas dependências, podemos usar um SAT solver para verificar se o cliente escolhe opções de configuração consistentes. Para isso, podemos seguir os seguintes passos:

Codificar as dependências entre configurações como uma formula proposicional $ψ$
Codificar as opções selecionadas pelo cliente como uma fórmula proposicional $ϕ$ .
Usar o SAT solver para verificar se $ψ \land ϕ$ não é contraditório.

Considere agora a seguinte dependência entre as configurações disponíveis para a personalização de um automóvel:

"O ar condicionado Thermotronic comfort requer uma bateria de alta capacidade, exceto quando combinado com motores a gasolina de 3,2 litros."

Será que um cliente pode escolher o ar condicionado Thermotronic comfort, uma bateria de pequena capacidade e não escolher o motor de 3,2 litros? Como poderia responder a esta pergunta com a ajuda de um SAT solver?

Resolução

Legenda de variáveis utilizadas:
A - ar condicionado
B - bateria alta capacidade
C - motor 3,2 L

$A \land \neg B ⟹ G \equiv \neg (A \land \neg B) \lor G \equiv \neg A \lor B \lor G$

$(\neg A \lor B \lor G) \land A \land \neg B \land \neg G$ ----- SAT?

Ex 3 (Configuração de computadores)

Uma loja de eletrónica permite aos seus clientes personalizar o seu computador, escolhendo entre dois modelos de motherboards e dois modelos de monitor. Cada computador tem que ter obrigatoriamente uma única motherboard, um único CPU, uma única placa gráfica e uma única memória RAM. O computador poderá ou não ter um monitor. A personalização do computador deverá obedecer às regras:

A motherboard MB1 quando combinada com a placa gráfica PG1, obriga à utilização da RAM1;
A placa gráfica PG1 precisa do CPU1, exceto quando combinada com a memória RAM2;
O CPU2 só pode estar instalado na motherboard MB2;
O monitor MON1 para poder funcionar precisa da placa gráfca PG1 e da memória RAM2.

Codifique este problema em lógica proposicional. Assinale claramente o que denota cada variável proposicional que introduzir e escreva um conjunto de fórmulas proposicionais adequado à sua modelação.

Resolução

Legenda de variáveis utilizadas:
$C P U_{1}; C P U_{2}; R A M_{1}; R A M_{2}; M B_{1}; M B_{2}; P G_{1}; P G_{2}; M O N_{1}; M O N_{2}$

Problema modelado:

$C P U_{1} \lor C P U_{2}$
$C P U_{1} ⟹ \neg C P U_{2}$
$R A M_{1} \lor R A M_{2}$
$R A M_{1} ⟹ \neg R A M_{2}$
$M B_{1} \lor M B_{2}$
$M B_{1} ⟹ \neg M B_{2}$
$P G_{1} \lor P G_{2}$
$P G_{1} ⟹ \neg P G_{2}$
$M B_{1} \land P G_{1} ⟹ R A M_{1}$
$P G_{1} ⟹ C P U_{1} \lor R A M_{2} \equiv P G_{1} \land \neg R A M_{2} ⟹ C P U_{1}$
$C P U_{2} ⟹ M B_{2}$
$M O N_{1} ⟹ P G_{1} \land R A M_{2}$

Indique, apenas por palavras, como poderia usar um SAT solver para testar as consistências deste conjunto de regras.

Indique, apenas por palavras, como usaria um SAT solver para se pronuncias quanto à velocidade das seguintes afirmações:
(a) O monitor MON1 só poderá ser usado com uma motherboard MB1.

Resolução

??? $T ⊨ M O N_{1} ⟹ M B_{1}$
$T, \neg (M O N_{1} ⟹ M B_{1}) U N S A T$

T ⊨ F

sse

T, \neg F U N S A T

(b) Um cliente pode personalizar o seu computador da seguinte forma: uma motherboard MB2, o CPU1, a placa gráfica PG2 e a memória RAM1.

Resolução

$T, M B_{2} \land C P U_{1} \land P G_{2} \land R A M_{1}$ ---- SAT?

Ex 2 (Distribuição de Gabinetes)

Considere que temos 3 gabinetes e queremos distribuir 4 pessoas (Ana=1, Nuno=2, Pedro=3 e Maria=4) por esses gabinetes. Para codificar este problema em lógica proposicional, , vamos ter um conjunto de variáveis proposicionais $x_{p, g}$ com a seguinte semântica:
$x_{p, g}$ é verdade sse a pessoa $p$ ocupa o gabinete $g$ , com $p = 1. .4$ e $g = 1. .3$

Considere que forem estipuladas as seguintes regras de ocupação de gabinetes:

Cada pessoa ocupa um único gabinete.
O Nuno e o Pedro não podem partilhar gabinete.
Se a Ana ficar sozinha num gabinete, então o Pedro também terá que ficar sozinho num gabinete.
Cada gabinete só pode acomodar, no máximo, 2 pessoas.

Escreve um conjunto de fórumlas proposicionais adequado à modelação destas regras.

Resolução (por passos)

Cada pessoa ocupa só um único gabinete.

para cada pessoa p = 1..4
pelo menos um gabinete: $x_{p 1} \lor x_{p 2} \lor x_{p 3}$
no máximo 1 gabinete: $x_{p 1} ⟹ \neg x_{p 2} \land x_{p 3} \equiv x_{p 1} ⟹ \neg (x_{p 2} \lor x_{p 3}) \equiv x_{p 2} ⟹ \neg x_{p 3}$