Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$

Question

What I would like to do is figure out how to get from $(x \Rightarrow y) $ to $ (y \vee z)$, that what I could AND or OR to $(x \Rightarrow y) $ so as to give $ (y \vee z)$.

Breaking this down I imagine that I take the expression $(x \Rightarrow y) \vee K = (y \vee z)$. I am trying to solve that - if it can be solved.

I however could possibly have that $(x \Rightarrow y) \wedge G = (y \vee z)$. I am not sure how to proceed from here.

If we looked at an example that "Works" by construction we can see that: $$(x \Rightarrow y) \wedge (y \vee z) = (\neg x \wedge z) \vee y$$ hence if we were trying to solve $(x \Rightarrow y) \wedge G = (\neg x \wedge z) \vee y$ we would find that $G = (y \vee z)$

Is there the general algorithm works for something like this?

Thanks,

Brian

Answer 1

First, note that - as was said in the comments - the problem is not always solvable:

• There is no $F$ such that $(x\vee y)\vee F=x$. (No matter what $F$ is, the assignment $y=True, x=False$ will always satisfy the left side and not the right.)

• There is no $G$ such that $x\wedge G=y$. ($x\wedge G$ always implies $x$, while $y$ doesn't.)

We can rephrase the problem as follows: given a pair of Boolean expressions $\varphi(x_1, . . . , x_n, F)$ and $\psi(x_1, . . . , x_n)$,

• (1) determine whether there is a Boolean expression $\chi(x_1, . . . , x_n)$ such that $\varphi(x_1, . . . , x_n, \chi(x_1, . . . , x_n))=\psi(x_1, . . . , x_n)$, and

• (2) find such a $\chi$, if it exists.

We can now ask about the complexity of (1), or (1) and (2) together. Here are a few observations:

• (1) is at least as hard as SAT: given a Boolean expression $\theta(x_1, . . . , x_n)$, consider the following instance of (1): is there an $F$ such that $\neg\theta \wedge F=\theta$? If $\theta$ is satisfiable, then clearly this equation has no solution (since a truth assignment making the right side true will always make the left side false); if $\theta$ is unsatisfiable, then this is solved by setting $F=(x\wedge \neg x)$.

• Meanwhile, since there are only finitely many Boolean formulas (up to logical equivalence) in a given number of variables, the problem is certainly computable, and in fact in EXP.

• However, it's not obvious to me that (1) is in NP, even though it seems plausible - the obvious kind of certificate for showing that a Boolean expression $F$ satisfies a given equation is a propositional proof.

Answer 2

I'm still not sure what you're asking for. Does this answer your question?

$ \begin{eqnarray*} y \vee z &\equiv& ((x \Rightarrow y) \wedge (\neg x \Rightarrow y)) \vee z \\ &\equiv& ((\neg x \vee y) \wedge ( x \vee y)) \vee z \end{eqnarray*}$