<p>A nice book on this topic: "Optimization Methods for Logical Inference", V. Chandru, John N. Hooker, Wiley, 1999</p>

CC BY-SA 3.0
2014-11-29T13:11:20.027Z
2014-11-29T13:11:20.027Z
jjg
<p>"Modelled" can be interpreted in different ways!</p>

<p>Well, at perhaps the most basic level, a CNF clause $(x_1 \lor x_2 \lor \neg x_3)$ can be expressed as the IP constraint</p>

<p>$x_1 + x_2 + (1 - x_3) \ge 1 ~~~ (A)$,</p>

<p>where each $x_i$ is an integer in $\{0, 1\}$.</p>

<p>FO is contained in $L$, LP is poly-time solvable and IP is $NP$-complete -- so there should be reductions from a given FO instance to both LP and IP. $~~$ A special case of SO, which is SO-Krom (every CNF clause has at most 2 literals) captures $NL$ -- so again, SO-Krom instances can be reduced to LP and IP.</p>

<p>When you write your formulation as in (A) above, if the coefficient matrix on the left side "behaves" well, your integer programming formulation could be solved in polynomial time (e.g. if the matrix is totally unimodular).</p>

<p>ESO (existential SO) $= NP$ by Fagin's theorem, so you should be able to reduce an ESO instance to IP.</p>

<p>Does this answer your question?</p>

CC BY-SA 3.0
2014-11-29T06:43:03.177Z
Thanks for the comment. I am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP? I will add an example to the question.
Daniel
CC BY-SA 3.0
2014-11-29T00:37:09.597Z
2014-11-29T06:28:55.213Z
2014-11-29T06:28:55.213Z
Sameer Gupta
<p>Can first-order logic be modeled/simulated as linear programming or integer programming? 
What about other forms of logic (say second order)?</p>

<p>Update:  am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP?  </p>

<p>In the following, I define a a set of implication rules. Then I define a problem for fixed variables, and I ask some question. I also give the desired answer to each question(based on logical implication). The question is, can we model this problem as an LP/ILP? </p>

<p>Here is an example. Suppose I define the following types: </p>

<ul>
<li>A = CHILD </li>
<li>B = PARENT </li>
<li>C = SIBLING </li>
</ul>

<p>And I define the implication rule: </p>

<ul>
<li>R1: For any $(x,y) \in A $ (meaning that $x$ is child of $y$) $\Rightarrow $ $(y, x) \in B$ (meaning that $y$ is parent of $x$). </li>
<li>R2: For any $(x,y) \in B $ (meaning that $x$ is parent of $y$) $\Rightarrow $ $(y, x) \in A$ (meaning that $y$ is child of $x$). </li>
<li>R3: For any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) $\Rightarrow $ $(y, x) \in C$ (meaning that $y$ is sibling of $x$).</li>
<li>R4: or any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) and $(y,z) \in A $ (meaning that $y$ is child of $z$) $\Rightarrow $ $(x, z) \in A$ (meaning that $x$ is child of $z$).</li>
</ul>

<p>Now suppose we fix the variables (i.e. a problem is given). </p>

<p><strong>Problem 1:</strong> 
We know three variables $x, y, z$. We know the following facts</p>

<ul>
<li>F1: $(x,y) \in A$ (i.e. $x$ is child of $y$). </li>
</ul>

<p>And we want to be able to infer the answer to the following question(s): </p>

<pre><code> - Does it imply $(y,x) \in B$? (Answer: yes) 
 - Does it imply $(y,z) \in C$? (Answer: unknown)
 - Does it imply $(z,y) \in C$? (Answer: unknown)
</code></pre>

<p><strong>Problem 2:</strong> 
We know three variables $x, y, z$. We know the following facts</p>

<ul>
<li>F1: $(x,y) \in A$ (i.e. $x$ is child of $y$). </li>
<li>F2: $(x,z) \in C$ (i.e. $x$ is sibling of $z$). </li>
</ul>

<p>And we want to be able to infer the answer to the following question(s): </p>

<pre><code> - Does it imply $(y,x) \in B$? (Answer: yes) 
 - Does it imply $(y,z) \in C$? (Answer: yes) 
 - Does it imply $(z,y) \in C$? (Answer: no)
</code></pre>

<ds.algorithms><lo.logic><linear-programming><automated-theorem-proving>
Logic with Linear Programming
Daniel
# Logic with Linear Programming

(Asked by: username_0 on 2014-11-28)

Can first-order logic be modeled/simulated as linear programming or integer programming? 
What about other forms of logic (say second order)?
Update:  am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP?  
In the following, I define a a set of implication rules. Then I define a problem for fixed variables, and I ask some question. I also give the desired answer to each question(based on logical implication). The question is, can we model this problem as an LP/ILP? 
Here is an example. Suppose I define the following types: 

A = CHILD 
B = PARENT 
C = SIBLING 

And I define the implication rule: 

R1: For any $(x,y) \in A $ (meaning that $x$ is child of $y$) $\Rightarrow $ $(y, x) \in B$ (meaning that $y$ is parent of $x$). 
R2: For any $(x,y) \in B $ (meaning that $x$ is parent of $y$) $\Rightarrow $ $(y, x) \in A$ (meaning that $y$ is child of $x$). 
R3: For any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) $\Rightarrow $ $(y, x) \in C$ (meaning that $y$ is sibling of $x$).
R4: or any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) and $(y,z) \in A $ (meaning that $y$ is child of $z$) $\Rightarrow $ $(x, z) \in A$ (meaning that $x$ is child of $z$).

Now suppose we fix the variables (i.e. a problem is given). 
Problem 1: 
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$). 

And we want to be able to infer the answer to the following question(s): 
 - Does it imply $(y,x) \in B$? (Answer: yes) 
 - Does it imply $(y,z) \in C$? (Answer: unknown)
 - Does it imply $(z,y) \in C$? (Answer: unknown)

Problem 2: 
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$). 
F2: $(x,z) \in C$ (i.e. $x$ is sibling of $z$). 

And we want to be able to infer the answer to the following question(s): 
 - Does it imply $(y,x) \in B$? (Answer: yes) 
 - Does it imply $(y,z) \in C$? (Answer: yes) 
 - Does it imply $(z,y) \in C$? (Answer: no)

**Tags:** ds.algorithms, lo.logic, linear-programming, automated-theorem-proving


---

## 2 answers

### Answer by username_1 on 2014-11-29. Score: 1

A nice book on this topic: "Optimization Methods for Logical Inference", V. Chandru, John N. Hooker, Wiley, 1999


---

### Answer by username_2 on 2014-11-29. Score: 0

"Modelled" can be interpreted in different ways!

Well, at perhaps the most basic level, a CNF clause $(x\_1 \lor x\_2 \lor \neg x\_3)$ can be expressed as the IP constraint

$x\_1 + x\_2 + (1 - x\_3) \ge 1 ~~~ (A)$,

where each $x\_i$ is an integer in $\{0, 1\}$.

FO is contained in $L$, LP is poly-time solvable and IP is $NP$-complete -- so there should be reductions from a given FO instance to both LP and IP. $~~$ A special case of SO, which is SO-Krom (every CNF clause has at most 2 literals) captures $NL$ -- so again, SO-Krom instances can be reduced to LP and IP.

When you write your formulation as in (A) above, if the coefficient matrix on the left side "behaves" well, your integer programming formulation could be solved in polynomial time (e.g. if the matrix is totally unimodular).

ESO (existential SO) $= NP$ by Fagin's theorem, so you should be able to reduce an ESO instance to IP.

Does this answer your question?

> **Comments:**
> **username_0**: Thanks for the comment. I am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP? I will add an example to the question.  

---

