GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/theory/arith/nl/transcendental/proof_checker.cpp Lines: 20 262 7.6 %
Date: 2021-09-29 Branches: 2 2282 0.1 %

Line Exec Source
1
/******************************************************************************
2
 * Top contributors (to current version):
3
 *   Gereon Kremer, Aina Niemetz
4
 *
5
 * This file is part of the cvc5 project.
6
 *
7
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
8
 * in the top-level source directory and their institutional affiliations.
9
 * All rights reserved.  See the file COPYING in the top-level source
10
 * directory for licensing information.
11
 * ****************************************************************************
12
 *
13
 * Implementation of proof checker for transcendentals.
14
 */
15
16
#include "theory/arith/nl/transcendental/proof_checker.h"
17
18
#include "expr/sequence.h"
19
#include "theory/arith/arith_utilities.h"
20
#include "theory/arith/nl/transcendental/taylor_generator.h"
21
#include "theory/rewriter.h"
22
23
using namespace cvc5::kind;
24
25
namespace cvc5 {
26
namespace theory {
27
namespace arith {
28
namespace nl {
29
namespace transcendental {
30
31
namespace {
32
33
/**
34
 * Helper method to construct (t >= lb) AND (t <= up)
35
 */
36
Node mkBounds(TNode t, TNode lb, TNode ub)
37
{
38
  NodeManager* nm = NodeManager::currentNM();
39
  return nm->mkAnd(std::vector<Node>{nm->mkNode(Kind::GEQ, t, lb),
40
                                     nm->mkNode(Kind::LEQ, t, ub)});
41
}
42
43
/**
44
 * Helper method to construct a secant plane:
45
 * ((evall - evalu) / (l - u)) * (t - l) + evall
46
 */
47
Node mkSecant(TNode t, TNode l, TNode u, TNode evall, TNode evalu)
48
{
49
  NodeManager* nm = NodeManager::currentNM();
50
  return nm->mkNode(Kind::PLUS,
51
                    nm->mkNode(Kind::MULT,
52
                               nm->mkNode(Kind::DIVISION,
53
                                          nm->mkNode(Kind::MINUS, evall, evalu),
54
                                          nm->mkNode(Kind::MINUS, l, u)),
55
                               nm->mkNode(Kind::MINUS, t, l)),
56
                    evall);
57
}
58
59
}  // namespace
60
61
3
void TranscendentalProofRuleChecker::registerTo(ProofChecker* pc)
62
{
63
3
  pc->registerChecker(PfRule::ARITH_TRANS_PI, this);
64
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_NEG, this);
65
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_POSITIVITY, this);
66
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_SUPER_LIN, this);
67
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_ZERO, this);
68
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_APPROX_ABOVE_POS, this);
69
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_APPROX_ABOVE_NEG, this);
70
3
  pc->registerChecker(PfRule::ARITH_TRANS_EXP_APPROX_BELOW, this);
71
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_BOUNDS, this);
72
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_SHIFT, this);
73
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_SYMMETRY, this);
74
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_TANGENT_ZERO, this);
75
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_TANGENT_PI, this);
76
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_APPROX_BELOW_POS, this);
77
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_APPROX_BELOW_NEG, this);
78
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_APPROX_ABOVE_POS, this);
79
3
  pc->registerChecker(PfRule::ARITH_TRANS_SINE_APPROX_ABOVE_NEG, this);
80
3
}
81
82
Node TranscendentalProofRuleChecker::checkInternal(
83
    PfRule id, const std::vector<Node>& children, const std::vector<Node>& args)
84
{
85
  NodeManager* nm = NodeManager::currentNM();
86
  auto zero = nm->mkConst<Rational>(0);
87
  auto one = nm->mkConst<Rational>(1);
88
  auto mone = nm->mkConst<Rational>(-1);
89
  auto pi = nm->mkNullaryOperator(nm->realType(), Kind::PI);
90
  auto mpi = nm->mkNode(Kind::MULT, mone, pi);
91
  Trace("nl-trans-checker") << "Checking " << id << std::endl;
92
  Trace("nl-trans-checker") << "Children:" << std::endl;
93
  for (const auto& c : children)
94
  {
95
    Trace("nl-trans-checker") << "\t" << c << std::endl;
96
  }
97
  Trace("nl-trans-checker") << "Args:" << std::endl;
98
  for (const auto& a : args)
99
  {
100
    Trace("nl-trans-checker") << "\t" << a << std::endl;
101
  }
102
  if (id == PfRule::ARITH_TRANS_PI)
103
  {
104
    Assert(children.empty());
105
    Assert(args.size() == 2);
106
    return nm->mkAnd(std::vector<Node>{nm->mkNode(Kind::GEQ, pi, args[0]),
107
                                       nm->mkNode(Kind::LEQ, pi, args[1])});
108
  }
109
  else if (id == PfRule::ARITH_TRANS_EXP_NEG)
110
  {
111
    Assert(children.empty());
112
    Assert(args.size() == 1);
113
    Node e = nm->mkNode(Kind::EXPONENTIAL, args[0]);
114
    return nm->mkNode(
115
        EQUAL, nm->mkNode(LT, args[0], zero), nm->mkNode(LT, e, one));
116
  }
117
  else if (id == PfRule::ARITH_TRANS_EXP_POSITIVITY)
118
  {
119
    Assert(children.empty());
120
    Assert(args.size() == 1);
121
    Node e = nm->mkNode(Kind::EXPONENTIAL, args[0]);
122
    return nm->mkNode(GT, e, zero);
123
  }
124
  else if (id == PfRule::ARITH_TRANS_EXP_SUPER_LIN)
125
  {
126
    Assert(children.empty());
127
    Assert(args.size() == 1);
128
    Node e = nm->mkNode(Kind::EXPONENTIAL, args[0]);
129
    return nm->mkNode(OR,
130
                      nm->mkNode(LEQ, args[0], zero),
131
                      nm->mkNode(GT, e, nm->mkNode(PLUS, args[0], one)));
132
  }
133
  else if (id == PfRule::ARITH_TRANS_EXP_ZERO)
134
  {
135
    Assert(children.empty());
136
    Assert(args.size() == 1);
137
    Node e = nm->mkNode(Kind::EXPONENTIAL, args[0]);
138
    return nm->mkNode(EQUAL, args[0].eqNode(zero), e.eqNode(one));
139
  }
140
  else if (id == PfRule::ARITH_TRANS_EXP_APPROX_ABOVE_POS)
141
  {
142
    Assert(children.empty());
143
    Assert(args.size() == 4);
144
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
145
           && args[0].getConst<Rational>().isIntegral());
146
    Assert(args[1].getType().isReal());
147
    Assert(args[2].isConst() && args[2].getKind() == Kind::CONST_RATIONAL);
148
    Assert(args[3].isConst() && args[3].getKind() == Kind::CONST_RATIONAL);
149
    std::uint64_t d =
150
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
151
    Node t = args[1];
152
    Node l = args[2];
153
    Node u = args[3];
154
    TaylorGenerator tg;
155
    TaylorGenerator::ApproximationBounds bounds;
156
    tg.getPolynomialApproximationBounds(Kind::EXPONENTIAL, d / 2, bounds);
157
    Node evall = Rewriter::rewrite(
158
        bounds.d_upperPos.substitute(tg.getTaylorVariable(), l));
159
    Node evalu = Rewriter::rewrite(
160
        bounds.d_upperPos.substitute(tg.getTaylorVariable(), u));
161
    Node evalsecant = mkSecant(t, l, u, evall, evalu);
162
    Node lem = nm->mkNode(
163
        Kind::IMPLIES,
164
        mkBounds(t, l, u),
165
        nm->mkNode(Kind::LEQ, nm->mkNode(Kind::EXPONENTIAL, t), evalsecant));
166
    return Rewriter::rewrite(lem);
167
  }
168
  else if (id == PfRule::ARITH_TRANS_EXP_APPROX_ABOVE_NEG)
169
  {
170
    Assert(children.empty());
171
    Assert(args.size() == 4);
172
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
173
           && args[0].getConst<Rational>().isIntegral());
174
    Assert(args[1].getType().isReal());
175
    Assert(args[2].isConst() && args[2].getKind() == Kind::CONST_RATIONAL);
176
    Assert(args[3].isConst() && args[3].getKind() == Kind::CONST_RATIONAL);
177
    std::uint64_t d =
178
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
179
    Node t = args[1];
180
    Node l = args[2];
181
    Node u = args[3];
182
    TaylorGenerator tg;
183
    TaylorGenerator::ApproximationBounds bounds;
184
    tg.getPolynomialApproximationBounds(Kind::EXPONENTIAL, d / 2, bounds);
185
    Node evall = Rewriter::rewrite(
186
        bounds.d_upperNeg.substitute(tg.getTaylorVariable(), l));
187
    Node evalu = Rewriter::rewrite(
188
        bounds.d_upperNeg.substitute(tg.getTaylorVariable(), u));
189
    Node evalsecant = mkSecant(t, l, u, evall, evalu);
190
    Node lem = nm->mkNode(
191
        Kind::IMPLIES,
192
        mkBounds(t, l, u),
193
        nm->mkNode(Kind::LEQ, nm->mkNode(Kind::EXPONENTIAL, t), evalsecant));
194
    return Rewriter::rewrite(lem);
195
  }
196
  else if (id == PfRule::ARITH_TRANS_EXP_APPROX_BELOW)
197
  {
198
    Assert(children.empty());
199
    Assert(args.size() == 2);
200
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
201
           && args[0].getConst<Rational>().isIntegral());
202
    Assert(args[1].getType().isReal());
203
    std::uint64_t d =
204
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
205
    Node t = args[1];
206
    TaylorGenerator tg;
207
    TaylorGenerator::ApproximationBounds bounds;
208
    tg.getPolynomialApproximationBounds(Kind::EXPONENTIAL, d, bounds);
209
    Node eval =
210
        Rewriter::rewrite(bounds.d_lower.substitute(tg.getTaylorVariable(), t));
211
    return nm->mkNode(
212
        Kind::GEQ, std::vector<Node>{nm->mkNode(Kind::EXPONENTIAL, t), eval});
213
  }
214
  else if (id == PfRule::ARITH_TRANS_SINE_BOUNDS)
215
  {
216
    Assert(children.empty());
217
    Assert(args.size() == 1);
218
    Assert(args[0].getType().isReal());
219
    Node s = nm->mkNode(Kind::SINE, args[0]);
220
    return nm->mkNode(AND, nm->mkNode(LEQ, s, one), nm->mkNode(GEQ, s, mone));
221
  }
222
  else if (id == PfRule::ARITH_TRANS_SINE_SHIFT)
223
  {
224
    Assert(children.empty());
225
    Assert(args.size() == 3);
226
    const auto& x = args[0];
227
    const auto& y = args[1];
228
    const auto& s = args[2];
229
    return nm->mkAnd(std::vector<Node>{
230
        nm->mkAnd(std::vector<Node>{
231
            nm->mkNode(Kind::GEQ, y, nm->mkNode(Kind::MULT, mone, pi)),
232
            nm->mkNode(Kind::LEQ, y, pi)}),
233
        nm->mkNode(
234
            Kind::ITE,
235
            nm->mkAnd(std::vector<Node>{
236
                nm->mkNode(Kind::GEQ, x, nm->mkNode(Kind::MULT, mone, pi)),
237
                nm->mkNode(Kind::LEQ, x, pi),
238
            }),
239
            x.eqNode(y),
240
            x.eqNode(nm->mkNode(
241
                Kind::PLUS,
242
                y,
243
                nm->mkNode(Kind::MULT, nm->mkConst<Rational>(2), s, pi)))),
244
        nm->mkNode(Kind::SINE, y).eqNode(nm->mkNode(Kind::SINE, x))});
245
  }
246
  else if (id == PfRule::ARITH_TRANS_SINE_SYMMETRY)
247
  {
248
    Assert(children.empty());
249
    Assert(args.size() == 1);
250
    Assert(args[0].getType().isReal());
251
    Node s1 = nm->mkNode(Kind::SINE, args[0]);
252
    Node s2 = nm->mkNode(
253
        Kind::SINE, Rewriter::rewrite(nm->mkNode(Kind::MULT, mone, args[0])));
254
    return nm->mkNode(PLUS, s1, s2).eqNode(zero);
255
  }
256
  else if (id == PfRule::ARITH_TRANS_SINE_TANGENT_ZERO)
257
  {
258
    Assert(children.empty());
259
    Assert(args.size() == 1);
260
    Assert(args[0].getType().isReal());
261
    Node s = nm->mkNode(Kind::SINE, args[0]);
262
    return nm->mkNode(
263
        AND,
264
        nm->mkNode(
265
            IMPLIES, nm->mkNode(GT, args[0], zero), nm->mkNode(LT, s, args[0])),
266
        nm->mkNode(IMPLIES,
267
                   nm->mkNode(LT, args[0], zero),
268
                   nm->mkNode(GT, s, args[0])));
269
  }
270
  else if (id == PfRule::ARITH_TRANS_SINE_TANGENT_PI)
271
  {
272
    Assert(children.empty());
273
    Assert(args.size() == 1);
274
    Assert(args[0].getType().isReal());
275
    Node s = nm->mkNode(Kind::SINE, args[0]);
276
    return nm->mkNode(
277
        AND,
278
        nm->mkNode(IMPLIES,
279
                   nm->mkNode(GT, args[0], mpi),
280
                   nm->mkNode(GT, s, nm->mkNode(MINUS, mpi, args[0]))),
281
        nm->mkNode(IMPLIES,
282
                   nm->mkNode(LT, args[0], pi),
283
                   nm->mkNode(LT, s, nm->mkNode(MINUS, pi, args[0]))));
284
  }
285
  else if (id == PfRule::ARITH_TRANS_SINE_APPROX_ABOVE_NEG)
286
  {
287
    Assert(children.empty());
288
    Assert(args.size() == 6);
289
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
290
           && args[0].getConst<Rational>().isIntegral());
291
    Assert(args[1].getType().isReal());
292
    Assert(args[2].getType().isReal());
293
    Assert(args[3].getType().isReal());
294
    Assert(args[4].isConst() && args[4].getKind() == Kind::CONST_RATIONAL);
295
    Assert(args[5].isConst() && args[5].getKind() == Kind::CONST_RATIONAL);
296
    std::uint64_t d =
297
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
298
    Node t = args[1];
299
    Node lb = args[2];
300
    Node ub = args[3];
301
    Node l = args[4];
302
    Node u = args[5];
303
    TaylorGenerator tg;
304
    TaylorGenerator::ApproximationBounds bounds;
305
    tg.getPolynomialApproximationBounds(Kind::SINE, d / 2, bounds);
306
    Node evall = Rewriter::rewrite(
307
        bounds.d_upperNeg.substitute(tg.getTaylorVariable(), l));
308
    Node evalu = Rewriter::rewrite(
309
        bounds.d_upperNeg.substitute(tg.getTaylorVariable(), u));
310
    Node lem = nm->mkNode(
311
        Kind::IMPLIES,
312
        mkBounds(t, lb, ub),
313
        nm->mkNode(
314
            Kind::LEQ, nm->mkNode(Kind::SINE, t), mkSecant(t, lb, ub, l, u)));
315
    return Rewriter::rewrite(lem);
316
  }
317
  else if (id == PfRule::ARITH_TRANS_SINE_APPROX_ABOVE_POS)
318
  {
319
    Assert(children.empty());
320
    Assert(args.size() == 5);
321
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
322
           && args[0].getConst<Rational>().isIntegral());
323
    Assert(args[1].getType().isReal());
324
    Assert(args[2].getType().isReal());
325
    Assert(args[3].getType().isReal());
326
    std::uint64_t d =
327
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
328
    Node t = args[1];
329
    Node c = args[2];
330
    Node lb = args[3];
331
    Node ub = args[4];
332
    TaylorGenerator tg;
333
    TaylorGenerator::ApproximationBounds bounds;
334
    tg.getPolynomialApproximationBounds(Kind::SINE, d / 2, bounds);
335
    Node eval = Rewriter::rewrite(
336
        bounds.d_upperPos.substitute(tg.getTaylorVariable(), c));
337
    return Rewriter::rewrite(
338
        nm->mkNode(Kind::IMPLIES,
339
                   mkBounds(t, lb, ub),
340
                   nm->mkNode(Kind::LEQ, nm->mkNode(Kind::SINE, t), eval)));
341
  }
342
  else if (id == PfRule::ARITH_TRANS_SINE_APPROX_BELOW_POS)
343
  {
344
    Assert(children.empty());
345
    Assert(args.size() == 6);
346
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
347
           && args[0].getConst<Rational>().isIntegral());
348
    Assert(args[1].getType().isReal());
349
    Assert(args[2].getType().isReal());
350
    Assert(args[3].getType().isReal());
351
    Assert(args[4].isConst() && args[4].getKind() == Kind::CONST_RATIONAL);
352
    Assert(args[5].isConst() && args[5].getKind() == Kind::CONST_RATIONAL);
353
    std::uint64_t d =
354
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
355
    Node t = args[1];
356
    Node lb = args[2];
357
    Node ub = args[3];
358
    Node l = args[4];
359
    Node u = args[5];
360
    TaylorGenerator tg;
361
    TaylorGenerator::ApproximationBounds bounds;
362
    tg.getPolynomialApproximationBounds(Kind::SINE, d / 2, bounds);
363
    Node evall =
364
        Rewriter::rewrite(bounds.d_lower.substitute(tg.getTaylorVariable(), l));
365
    Node evalu =
366
        Rewriter::rewrite(bounds.d_lower.substitute(tg.getTaylorVariable(), u));
367
    Node lem = nm->mkNode(
368
        Kind::IMPLIES,
369
        mkBounds(t, lb, ub),
370
        nm->mkNode(
371
            Kind::GEQ, nm->mkNode(Kind::SINE, t), mkSecant(t, lb, ub, l, u)));
372
    return Rewriter::rewrite(lem);
373
  }
374
  else if (id == PfRule::ARITH_TRANS_SINE_APPROX_BELOW_NEG)
375
  {
376
    Assert(children.empty());
377
    Assert(args.size() == 5);
378
    Assert(args[0].isConst() && args[0].getKind() == Kind::CONST_RATIONAL
379
           && args[0].getConst<Rational>().isIntegral());
380
    Assert(args[1].getType().isReal());
381
    Assert(args[2].getType().isReal());
382
    Assert(args[3].getType().isReal());
383
    std::uint64_t d =
384
        args[0].getConst<Rational>().getNumerator().toUnsignedInt();
385
    Node t = args[1];
386
    Node c = args[2];
387
    Node lb = args[3];
388
    Node ub = args[4];
389
    TaylorGenerator tg;
390
    TaylorGenerator::ApproximationBounds bounds;
391
    tg.getPolynomialApproximationBounds(Kind::SINE, d / 2, bounds);
392
    Node eval =
393
        Rewriter::rewrite(bounds.d_lower.substitute(tg.getTaylorVariable(), c));
394
    return Rewriter::rewrite(
395
        nm->mkNode(Kind::IMPLIES,
396
                   mkBounds(t, lb, ub),
397
                   nm->mkNode(Kind::GEQ, nm->mkNode(Kind::SINE, t), eval)));
398
  }
399
  return Node::null();
400
}
401
402
}  // namespace transcendental
403
}  // namespace nl
404
}  // namespace arith
405
}  // namespace theory
406
22746
}  // namespace cvc5