CODEWITHSUNDEEP
algorithmmathlogicboolean-logic
Andrew Tomazos
Andrew Tomazos

Reputation: 68638

Algorithm For Intesection of Logical Expressions?

Given a set of n elements U, and a set of m properties P where each element of P defines a function from U to boolean.

Given two composite logical expressions of the form (recursively defined):

p1 : true iff p1(x) is true
e1 and e2 : means e1 and e2 are both true
e1 or e2 : means e1 and e2 are not both false
not e1 : true iff e1 is false
(e1) : true iff e1

These logical expressions are parsed into expression statements (parse trees).

Assume that for any p1, p2: All four sets (p1 and p2), (p1 and not p2), (not p1 and p2), (not p1 and not p2), are non-empty.

I want to determine if a logical expression L1 is a subset of L2. That is for every element x in U, if L1(x) is true then L2(x) is true.

So for example:

is_subset(not not p1, p1) is true
is_subset(p1, p2) is false
is_subset(p1 and p2 and p3, (p1 and p2) or p3) is true

I think I need to "normalize" the parse trees somehow and then compare them. Can anyone outline an approach or sketch an architecture?

Upvotes: 4

Views: 199

Answers (3)

starblue
starblue

Reputation: 56772

Since you don't do anything with the objects (x) it seems you want propositional logic, where all combinations of the truth values for p1 to pn are possible.

So essentially you want to do theorem proving in propositional logic.

Your is_subset(e1,e2) translates to a logical operator e1 implies e2, which is the same as not e1 or e2. To know if these hold universally you can check if the negation is unsatisfiable with an algorithm for satisfiability checking such as DPLL.

This is just a starting point, there are many other options to prove theorems in propositional logic.

Upvotes: 1

SAJ14SAJ
SAJ14SAJ

Reputation: 1708

I think your instructor essentially wants you to implement the Quine-McCluskey Algorithm Note that as the other answer implies, the execution time grows exceptionally fast because the problem is-NP Hard.

Upvotes: 0

Alexey Feldgendler
Alexey Feldgendler

Reputation: 1800

You can convert each formula to the disjunctive normal form and find if one contains a subset of the conjunctive clauses in the other. The complexity of this approach grows as the exponent of the number of pn mentioned.

Upvotes: 0

Related Questions