Решение равенства/неравенства в цели, код coq

Как я могу доказать, что эти два утверждения равны:

  1. Вал.шру (Вал.а (Винт б)) (Винт в) = Винт ?3434/\?3434 ‹>d

  2. Вал.шру (Вал.а (Винт б)) (Винт в) ‹> д

Концепция довольно проста, но застряла в поиске правильной тактики для ее решения. На самом деле это лемма, которую я собираюсь доказать:

Require Import compcert.common.Values.
Require Import compcert.lib.Coqlib.
Require Import compcert.lib.Integers.

Lemma val_remains_int:
forall (a : val) (b c d: int),
(Val.shru (Val.and a (Vint b)) (Vint c)) <> (Vint d) ->
(exists (e : int), (Val.shru (Val.and a (Vint b)) (Vint c)) = (Vint e) /\ e <> d).

Proof.
  intros.
  eexists.
  ...
Admitted.

Спасибо,


coq formal-verification compcert
person saeed M    schedule 14.09.2016    source источник
comment
У вас есть лемма, утверждающая, что любой член формы Val.shru foo можно переписать в Vint bar? Основная проблема здесь в том, что вам нужно показать e с равенством, чтобы доказать левую часть вашей цели.   -  person Vinz    schedule 14.09.2016

Ответы (1)


arrow_upward
0
arrow_downward

Если вы можете создать значение типа int (i0 в приведенном ниже примере), то эта лемма неверна:

Require Import compcert.lib.Coqlib.
Require Import compcert.lib.Integers.
Require Import compcert.common.Values.

Variable i0 : int.

Fact counter_example_to_val_remains_int:
  ~ forall (a : val) (b c d: int),
      (Val.shru (Val.and a (Vint b)) (Vint c)) <> (Vint d) ->
      (exists (e : int),
          (Val.shru (Val.and a (Vint b)) (Vint c)) = (Vint e)
        /\ e <> d).
Proof.
  intro H.
  assert (Vundef <> Vint i0) as H0 by easy.
  specialize (H Vundef i0 i0 i0 H0); clear H0.
  simpl in H.
  destruct H as (? & contra & _).
  discriminate contra.
Qed.

Есть как минимум две причины:

  • Val.and и Val.shru возвращают Vundef для всех аргументов, отличных от Vint (это экземпляр GIGO принцип);
  • также вы не можете сдвигать биты слишком далеко в C - результат не определен (это примерно Val.shru).

Что касается модифицированной леммы, которую вы упомянули в своем комментарии, подойдет простой reflexivity:

Lemma val_remains_int: forall a b c d: int,
    Vint (Int.shru (Int.and a b) c) <> Vint d ->
    exists (e : int), Vint (Int.shru (Int.and a b) c) = Vint e /\ e <> d.
Proof.
  intros a b c d Hneq.
  eexists. split.
  - reflexivity.
  - intro Heq. subst. auto.
Qed.
person Anton Trunov    schedule 14.09.2016
comment
Спасибо, вы правы. Я наложил правильные ограничения на переменную сдвига и убедился, что мы не возвращаем Vundef. Я развернулся и добрался до этого места: - person saeed M; 15.09.2016
comment
Н0 : Винт (Инт.шру (Межд.а б) в) ‹› Винт д ___________________________________________(1/1) Винт (Инт.шру (Межд.а б) в) = Винт ?3443 /\ ?3443 ‹› д - person saeed M; 15.09.2016
comment
Как можно как-то избавиться от экзистенциального числа в цели? - person saeed M; 15.09.2016