Nói chung, khi bạn thực hiện phân tích trường hợp trong một định lý, thì nhiều trường hợp đun sôi xuống thành "không thể xảy ra". Ví dụ, nếu bạn đang chứng minh một số thực tế về các số nguyên, bạn có thể cần phải làm một phân tích trường hợp cho dù số nguyên i là dương, không hoặc âm. Nhưng có thể có những giả thuyết khác nằm xung quanh trong bối cảnh của bạn, hoặc có lẽ một phần nào đó trong mục tiêu của bạn, điều đó mâu thuẫn với một trong những trường hợp. Bạn có thể biết từ một xác nhận trước đó, ví dụ, rằng i không bao giờ có thể là tiêu cực.
Tuy nhiên Coq không thông minh. Vì vậy, bạn vẫn phải đi qua cơ chế thực sự cho thấy rằng hai giả thuyết mâu thuẫn có thể được dán lại với nhau thành một bằng chứng về sự vô lý và do đó là bằng chứng về định lý của bạn.
Hãy suy nghĩ về nó như thế nào trong một chương trình máy tính:
switch (k) {
case X:
/* do stuff */
break;
case Y:
/* do other stuff */
break;
default:
assert(false, "can't ever happen");
}
Mục tiêu false = true là "không thể bao giờ xảy ra". Nhưng bạn không thể chỉ khẳng định theo cách của bạn trong Coq. Bạn thực sự phải đặt ra một thuật ngữ chứng minh.
Vì vậy, ở trên, bạn phải chứng minh mục tiêu ngớ ngẩn false = true. Và điều duy nhất bạn phải làm việc là giả thuyết H: andb false c = true. Suy nghĩ của một khoảnh khắc sẽ cho bạn thấy rằng thực sự đây là một giả thuyết ngớ ngẩn (bởi vì andb false y giảm sai cho bất kỳ y và do đó không thể có thể đúng). Vì vậy, bạn đập vào mục tiêu với điều duy nhất theo ý của bạn (cụ thể là H) và mục tiêu mới của bạn là false = andb false c.
Vì vậy, bạn áp dụng một giả thuyết ngớ ngẩn cố gắng đạt được mục tiêu vô lý. Và lo và nhìn thấy bạn kết thúc với một cái gì đó bạn thực sự có thể hiển thị bằng phản xạ. Qed.
CẬP NHẬT Chính thức, đây là những gì đang diễn ra.
Nhớ lại rằng mọi định nghĩa quy nạp trong Coq đều có nguyên tắc cảm ứng. Dưới đây là các loại các nguyên tắc quy nạp cho bình đẳng và False đề xuất (như trái ngược với thuật ngữ false loại bool):
Check eq_ind.
eq_ind
: forall (A : Type) (x : A) (P : A -> Prop),
P x -> forall y : A, x = y -> P y
Check False_ind.
False_ind
: forall P : Prop, False -> P
Đó nguyên tắc cảm ứng cho False nói rằng nếu bạn cho tôi một bằng chứng về False, tôi có thể cung cấp cho bạn bằng chứng về bất kỳ đề xuất nào P.
Nguyên tắc cảm ứng cho eq phức tạp hơn. Hãy xem xét nó giới hạn trong bool. Và cụ thể là false. Nó nói:
Check eq_ind false.
eq_ind false
: forall P : bool -> Prop, P false -> forall y : bool, false = y -> P y
Vì vậy, nếu bạn bắt đầu với một số đề xuất P(b) mà phụ thuộc vào một boolean b, và bạn có một bằng chứng về P(false), sau đó cho bất kỳ boolean y khác đó là bằng false, bạn có một bằng chứng về P(y).
Điều này không có vẻ kỳ lạ, nhưng chúng tôi có thể áp dụng cho bất kỳ đề xuất P nào mà chúng tôi muốn. Và chúng tôi muốn một người đặc biệt khó chịu.
Check eq_ind false (fun b : bool => if b then False else True).
eq_ind false (fun b : bool => if b then False else True)
: (fun b : bool => if b then False else True) false ->
forall y : bool,
false = y -> (fun b : bool => if b then False else True) y
Đơn giản hóa một chút, điều này nói là True -> forall y : bool, false = y -> (if y then False else True).
Vì vậy, điều này muốn có bằng chứng là True và sau đó một số boolean y mà chúng tôi nhận được để chọn. Vì vậy, hãy làm điều đó.
Check eq_ind false (fun b : bool => if b then False else True) I true.
eq_ind false (fun b : bool => if b then False else True) I true
: false = true -> (fun b : bool => if b then False else True) true
Và ở đây chúng tôi là: false = true -> False.
Kết hợp với những gì chúng tôi biết về nguyên tắc cảm ứng cho False, chúng tôi có: nếu bạn cho tôi bằng chứng là false = true, tôi có thể chứng minh bất kỳ đề xuất nào.
Quay lại andb_true_elim1. Chúng tôi có giả thuyết H là false = true. Và chúng tôi muốn chứng minh một số loại mục tiêu. Như tôi đã trình bày ở trên, có tồn tại một thuật ngữ bằng chứng để biến chứng minh của false = true thành bằng chứng về bất kỳ điều gì bạn muốn. Vì vậy, cụ thể H là bằng chứng của false = true, vì vậy bây giờ bạn có thể chứng minh bất kỳ mục tiêu nào bạn muốn.
Các chiến thuật về cơ bản là máy móc xây dựng thuật ngữ chứng minh.
Bạn có thể thử sử dụng: ['phân biệt đối xử'] (http://www.fing.edu.uy/inco/grupos/mf/man/Coq/node.1.2.8.html). (Tôi thấy đó là một bài cũ) – guest