Logic with Linear Programming

Question

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)

Answer 1

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

Answer 2

"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?