# Horn Formulas as Linear Inequalities and Nonlocality Paradoxes

Tobias Fritz ( ICFO, Barcelona )

- 14:00 21st January 2011 ( week 1, Hilary Term 2011 )Lecture Theatre B

Abstract: A Horn formula can be interpreted as a system of linear

inequalities over the Boolean semiring. Similarly, a union-closed set

system is the Boolean version of a polytope. I will show how a

resolution-like Fourier-Motzkin algorithm can be used to compute a Horn

formula determining a union-closed set system from its generating sets and

describe the output of some sample computations. In particular, one can

use the software to calculate all Hardy-type nonlocality paradoxes as Bell

inequalities over the Boolean semiring. Everything is work in progress,

and I will mention the problem of redundancy elimination as a major

obstacle towards further progress.