956 views

Let $\varphi$ be a propositional formula on a set of variables  $A$ and  $\psi$ be a propositional  formula on a set of  variables $B$ , such that $\varphi \Rightarrow \psi$ . A $\textit{Craig interpolant}$ of $\varphi$ and $\psi$ is a propositional formula $\mu$ on variables $A \cap B$ such that $\varphi$ $\Rightarrow$ $\mu$ and $\mu$ $\Rightarrow$ $\psi$. Given propositional formula $\varphi = q \vee (r \wedge s)$ on the set of variables $A = \{q,r,s\}$ and propositional formula $\psi = \neg q \rightarrow (s \vee t)$ on the set of variables $B =\{q,s,t\}$, which of the following is a Craig interpolant for $\varphi$ and $\psi$ ?

1. $q$
2. $\varphi$ itself
3. $q \vee s$
4. $q \vee r$
5. $\neg q \wedge s$

### 1 comment

C?

Set of variables for $A$={$q,r,s$}
Set of variables for $B$={$q,s,t$}
$\therefore$Variables in $A \cap B$ ={$q,s$}
$φ =q \vee (r \wedge s)$
$Ψ= \neg q (s \vee t)$
$Ψ=\neg \neg q \vee (s \vee t)$

$Ψ=q \vee s \vee t$

According to problem we have two conditions:

1. $φ \implies μ$

So, when $φ$ is true $μ$ must be true.
Therefore, $μ=q \vee s$ (Since $r$ is not in the domain of $μ$)

ii. $μ \implies Ψ$

Taking $μ$ as $q \vee s$ also satisfy the above constraint as

$q \vee s \implies q \vee s \vee t$

### 1 comment

Intermediate step : φ = q ∨ (r ∧ s) = (q ∨ r) ∧ (q ∨ s)

For φ to be true, both (q ∨ r) and (q ∨ s) have to be true and since domain of μ has only {q,s} and φ ⟹ μ , so μ = q ∨ s.

1
3,236 views