How to simplify logical expressions?

Discussion in 'Java' started by Gerhard Rapp, Jul 29, 2003.

  1. Gerhard Rapp

    Gerhard Rapp Guest

    Hello all.

    I'm writing a program that identifies some kind of objects in a data
    repository. These objects have conditions. For instance ((r=NN) and (x=AR))
    or something like that. In some cases the conditions of two or more objects
    should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
    with (x=L) should evalutate to ((r=NN) or (x=L)).

    Has anyone solved a problem like that before? May be someone can at least
    give a hint?

    Thanks
    Gerhard
     
    Gerhard Rapp, Jul 29, 2003
    #1
    1. Advertising

  2. Gerhard Rapp

    Chris Smith Guest

    Gerhard Rapp wrote:
    > I'm writing a program that identifies some kind of objects in a data
    > repository. These objects have conditions. For instance ((r=NN) and (x=AR))
    > or something like that. In some cases the conditions of two or more objects
    > should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
    > with (x=L) should evalutate to ((r=NN) or (x=L)).
    >
    > Has anyone solved a problem like that before? May be someone can at least
    > give a hint?


    I did in fact solve a similar problem recently. Roedy is right, of
    course: working with a semantic form such as an expression tree, as
    opposed to a flat text format, is absolutely essential.

    My advice is to get yourself a good book on boolean algebra. In
    particular, DeMorgan's law, and the properties of distributability of
    boolean operators should be useful. Using those two properties plus
    some form of sorting of terms, it's possible to transform any logical
    statement into a single canonical form with only three levels of
    operators: OR, AND, and NOT. That makes it easier to eliminate
    redundant subexpressions, recognize logical inverses and equivalencies
    (which make for contradictions or tautologies, and are immensely helpful
    in simplifying).

    It's also important to note (and I initially forgot when approaching the
    problem) that (A and B) is equivalent to (A and (B, if A is true)), and
    that (A or B) is equivalent to (A or (B, if A is false)). That
    simplifies a lot of things away by producing tautologies and
    contradictions in subexpressions.

    --
    www.designacourse.com
    The Easiest Way to Train Anyone... Anywhere.

    Chris Smith - Lead Software Developer/Technical Trainer
    MindIQ Corporation
     
    Chris Smith, Jul 30, 2003
    #2
    1. Advertising

  3. "Gerhard Rapp" <> wrote in message news:<bg6re1$df7$01$-online.com>...
    > Hello all.
    >
    > I'm writing a program that identifies some kind of objects in a data
    > repository. These objects have conditions. For instance ((r=NN) and (x=AR))
    > or something like that. In some cases the conditions of two or more objects
    > should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
    > with (x=L) should evalutate to ((r=NN) or (x=L)).
    >
    > Has anyone solved a problem like that before? May be someone can at least
    > give a hint?
    >
    > Thanks
    > Gerhard


    Do a search on Karnaugh Map. It's a method of minimizing a boolean
    expression from an n-variable truth table.
     
    Peter Schoaff, Jul 30, 2003
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Juan Carlos Allica
    Replies:
    2
    Views:
    677
    Noway2
    Jan 25, 2006
  2. deltaa5
    Replies:
    1
    Views:
    396
    Jim Langston
    Jan 2, 2007
  3. deltaa5
    Replies:
    2
    Views:
    364
    Ondra Holub
    Jan 2, 2007
  4. deltaa5
    Replies:
    0
    Views:
    353
    deltaa5
    Jan 2, 2007
  5. mingze zhang
    Replies:
    4
    Views:
    1,127
    aadilsabri
    Oct 22, 2011
Loading...

Share This Page