sympy/core/logic.py

   1 """Logic expressions handling
   2
   3 NOTE
   4 ----
   5
   6 at present this is mainly needed for facts.py , feel free however to improve
   7 this stuff for general purpose.
   8 """
   9
  10 def fuzzy_not(v):
  11     """'not' in fuzzy logic"""
  12     if v is None:
  13         return v
  14     else:
  15         return not v
  16
  17
  18 def name_not(k):
  19     """negate a name
  20
  21        >>> name_not('zero')
  22        '!zero'
  23
  24        >>> name_not('!zero')
  25        'zero'
  26     """
  27     if k[:1] != '!':
  28         return '!'+k
  29     else:
  30         return k[1:]
  31
  32
  33 class Logic(object):
  34     """Logical expression"""
  35
  36     __slots__ = ['args']
  37
  38     # {} 'op' -> LogicClass
  39     op_2class = {}
  40
  41
  42     def __new__(cls, args):
  43         obj = object.__new__(cls)
  44         obj.args = tuple(args)
  45
  46         # XXX do we need this:
  47         #print 'L: %s' % (obj.args,)
  48         assert not isinstance(obj.args[0], tuple)
  49
  50         return obj
  51
  52
  53     def __hash__(self):
  54         return hash( (type(self).__name__, self.args) )
  55
  56
  57     def __eq__(a, b):
  58         if not isinstance(b, type(a)):
  59             return False
  60         else:
  61             return a.args == b.args
  62
  63     def __ne__(a, b):
  64         if not isinstance(b, type(a)):
  65             return True
  66         else:
  67             return a.args != b.args
  68
  69
  70     def __cmp__(a, b):
  71         if type(a) is not type(b):
  72             return cmp( str(type(a)), str(type(b)) )
  73
  74         else:
  75             return cmp(a.args, b.args)
  76
  77
  78
  79
  80     # XXX later, we may want to change how expressions are printed
  81     def __str__(self):
  82         return '%s(%s)' % (self.op, ', '.join(str(a) for a in self.args))
  83
  84     # XXX this is not good ...
  85     __repr__ = __str__
  86
  87
  88     @staticmethod
  89     def fromstring(text):
  90         """Logic from string
  91
  92            e.g.
  93
  94            !a & !b | c
  95         """
  96         # XXX this is not general, but good enough
  97         terms = text.split()
  98
  99         lexpr   = None  # current logical expression
 100         schedop = None  # scheduled operation
 101
 102         while True:
 103             # pop next term and exit loop if there is no terms left
 104             try:
 105                 term = terms.pop(0)
 106             except IndexError:
 107                 break
 108
 109             # operation symbol
 110             if term in '&|':
 111                 if schedop is not None:
 112                     raise ValueError('double op forbidden: "%s %s"' % (term, schedop))
 113
 114                 if lexpr is None:
 115                     raise ValueError('%s cannot be in the beginning of expression' % term)
 116
 117                 schedop = term
 118                 continue
 119
 120
 121             # already scheduled operation, e.g. '&'
 122             if schedop:
 123                 lexpr   = Logic.op_2class[schedop] ( *(lexpr, term) )
 124                 schedop = None
 125                 continue
 126
 127             # this should be atom
 128             if lexpr is not None:
 129                 raise ValueError('missing op between "%s" and "%s"' % (lexpr, term))
 130
 131             lexpr = term
 132
 133
 134         # let's check that we ended up in correct state
 135         if schedop is not None:
 136             raise ValueError('premature end-of-expression in "%s"' % text)
 137         if lexpr is None:
 138             raise ValueError('"%s" is empty' % text)
 139
 140         # everything looks good now
 141         return lexpr
 142
 143
 144 # XXX better name?
 145 class AndOr_Base(Logic):
 146
 147     __slots__ = []
 148
 149     def __new__(cls, *args):
 150         if len(args) == 0:
 151             raise TypeError('%s requires at least one argument' % cls.__name__)
 152
 153         # process bool args early
 154         bargs = []
 155
 156         for a in args:
 157             # &(F, ...) -> F
 158             # |(T, ...) -> T
 159             if a == cls.op_x_notx:
 160                 return a
 161
 162             # &(T, ...) -> &(...)
 163             # |(F, ...) -> |(...)
 164             elif a == (not cls.op_x_notx):
 165                 continue    # skip this argument
 166
 167
 168             bargs.append(a)
 169
 170
 171         args = bargs
 172
 173         # &(a, !a) -> F
 174         # |(a, !a) -> T
 175         # XXX suboptinal
 176         for a in args:
 177             if Not(a) in args:
 178                 return cls.op_x_notx
 179
 180         args = cls.flatten(args)
 181
 182         # canonicalize arguments
 183         # XXX do we always need this?
 184         # NB: this is needed to reduce number of &-nodes in beta-network
 185         args = sorted(args)
 186
 187         # now let's kill duplicate arguments, e.g. &(a,a,b) -> &(a,b)
 188         prev = None
 189         uargs= []
 190         for a in args:
 191             if a != prev:
 192                 uargs.append(a)
 193                 prev = a
 194
 195         args = uargs
 196
 197         # &(a) -> a
 198         # |(a) -> a
 199         if len(args) == 1:
 200             return args[0]
 201
 202         # when we are at this stage, it means that _all_ arguments were T/F and
 203         # all arguments were accepted as "let's see what follows next", so at
 204         # _this_ point the rule is:
 205         # |()  -> F  (*not* T)
 206         # &()  -> T  (*not* F)
 207         elif len(args) == 0:
 208             return not cls.op_x_notx
 209
 210         return Logic.__new__(cls, args)
 211
 212
 213     @classmethod
 214     def flatten(cls, args):
 215         # quick-n-dirty flattening for And and Or
 216         args_queue = list(args)
 217         res = []
 218
 219         while True:
 220
 221             try:
 222                 arg = args_queue.pop(0)
 223             except IndexError:
 224                 break
 225
 226             if isinstance(arg, Logic):
 227                 if arg.op == cls.op:
 228                     #print 'flattening...', fargs, i, arg.args
 229                     args_queue.extend( arg.args )
 230                     continue
 231
 232
 233             # another op -- leave it as is
 234             res.append( arg )
 235
 236         args = tuple(res)
 237         return args
 238
 239 expand_lvl=0
 240
 241 class And(AndOr_Base):
 242     op = '&'
 243     op_x_notx = False
 244
 245     __slots__ = []
 246
 247     def _eval_propagate_not(self):
 248         # !(a&b&c ...) == !a | !b | !c ...
 249         return Or( *[Not(a) for a in self.args] )
 250
 251
 252     # (a|b|...) & c == (a&c) | (b&c) | ...
 253     def expand(self):
 254
 255         # first locate Or
 256         for i in range(len(self.args)):
 257             arg = self.args[i]
 258             if isinstance(arg, Or):
 259                 arest = self.args[:i] + self.args[i+1:]
 260
 261                 orterms = [And( *(arest + (a,)) ) for a in arg.args]
 262                 for j in range(len(orterms)):
 263                     if isinstance(orterms[j], Logic):
 264                         orterms[j] = orterms[j].expand()
 265
 266                 res = Or(*orterms)
 267                 return res
 268
 269         else:
 270             return self
 271
 272     def dbg_expand(self):
 273         global expand_lvl
 274         print '%sexpand %s' % (' '*expand_lvl, self)
 275
 276         expand_lvl += 1
 277         try:
 278             return self.old_expand()
 279         finally:
 280             expand_lvl -= 1
 281
 282
 283     #old_expand = expand
 284     #expand = dbg_expand
 285
 286 class Or(AndOr_Base):
 287     op = '|'
 288     op_x_notx = True
 289
 290     __slots__ = []
 291
 292     def _eval_propagate_not(self):
 293         # !(a|b|c ...) == !a & !b & !c ...
 294         return And( *[Not(a) for a in self.args] )
 295
 296 class Not(Logic):
 297     op = '!'
 298
 299     __slots__ = []
 300
 301     def __new__(cls, arg):
 302         if isinstance(arg, str):
 303             return name_not(arg)
 304
 305         elif isinstance(arg, bool):
 306             return not arg
 307
 308         elif isinstance(arg, Logic):
 309             # XXX this is a hack to expand right from the beginning
 310             arg = arg._eval_propagate_not()
 311             return arg
 312
 313             obj = Logic.__new__(cls, (arg,))
 314             return obj
 315
 316         else:
 317             raise ValueError('Not: unknow argument %r' % (arg,))
 318
 319
 320
 321
 322
 323 Logic.op_2class['&'] = And
 324 Logic.op_2class['|'] = Or
 325 Logic.op_2class['!'] = Not
 326