Is division by zero included in QF_NRA?

2019-07-30 07:11发布

问题:

Is division by zero included in QF_NRA?

The SMT-LIB standard is confusing in this matter. The paper where the standard is defined simply does not discuss this point, in fact NRA and QF_NRA do not appear anywhere in that document. Some information is provided on the standard website. Reals are defined as including:

- all terms of the form (/ m n) or (/ (- m) n) where 
  - m is a numeral other than 0,
  - n is a numeral other than 0 and 1,
  - as integers, m and n have no common factors besides 1.

This explicitly excludes zero from the denominator when it comes to constant values. However, later, division is defined as:

- / as a total function that coincides with the real division function 
  for all inputs x and y where y is non-zero,

This is followed up by a note:

Since in SMT-LIB logic all function symbols are interpreted as total
  functions, terms of the form (/ t 0) *are* meaningful in every 
  instance of Reals. However, the declaration imposes no constraints
  on their value. This means in particular that 
  - for every instance theory T and
  - for every closed terms t1 and t2 of sort Real, 
  there is a model of T that satisfies (= t1 (/ t2 0)). 

This is seemingly contradictory, because the first quote says that (/ m 0) is not a number in QV_NRA, but the latter quote says that / is a function such that (= t1 (/ t2 0)) is satisfiable for any t1 and t2.

The de-facto reality on the ground is that division by zero seems to be included in SMT-LIB, despite the statement that (/ m n) is only a Real number if n is nonzero. This is related to a previous question of mine: y=1/x, x=0 satisfiable in the reals?

回答1:

the first quote says that (/ m 0) is not a number

No, but it does not say what number it is.

but the latter quote says that / is a function such that (= t1 (/ t2 0)) is satisfiable for any t1 and t2

This is correct.

You need to get away from the school mentality that says "division by zero is not allowed!". It is undefined. Undefined means that there is no axiom that specifies what values this is. (And this is true in school as well.)

What is f(1234)? It's undefined, so Z3 is allowed to pick any number at all. There is no difference between a / 0 and f(a) where f is some uninterpreted function. Z3 can fill in any function it likes.

Therefore, a / 0 == b is satisfiable and any a and b are OK. But (a / 0) == (a / 0) + 1 is false.

Mathematical operators are just functions. The standard partially specifies those functions.