edited by
1,264 views
6 votes
6 votes

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$
edited by

2 Answers

8 votes
8 votes

Answer is 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$
 

edited by
Answer:

Related questions

4 votes
4 votes
2 answers
1
Arjun asked Dec 18, 2018
4,148 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above
11 votes
11 votes
5 answers
2
Arjun asked Dec 18, 2018
4,427 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$8$$16$$32$$64$None of the above
5 votes
5 votes
1 answer
3
10 votes
10 votes
2 answers
4