计算理论复习

Q1

Find the error in the following proof that all horses are the same color. Claim: In any set of h horses, all horses are the same color.
Proof: By induction on h.
Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.
Induction step: For k ≥ 1, assume that the claim is true for h = k and provethatitistrueforh=k+1. TakeanysetH ofk+1horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H1 are the same color. Now replace the removed horse and remove a different one to obtain the set H2. By the same argument, all the horses in H2 are the same color. Therefore, all the horses in H must be the same color, and the proof is complete.

Answer

Author

preccrep

Posted on

2021-11-07

Updated on

2021-11-07

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.