UNL CSCE 235 - Proofs (52 pages)

Previewing pages 1, 2, 3, 25, 26, 27, 28, 50, 51, 52 of 52 page document View the full content.
View Full Document

Proofs



Previewing pages 1, 2, 3, 25, 26, 27, 28, 50, 51, 52 of actual document.

View the full content.
View Full Document
View Full Document

Proofs

70 views

Other


Pages:
52
School:
University of Nebraska-Lincoln
Course:
Csce 235 - Introduction to Discrete Structures
Introduction to Discrete Structures Documents

Unformatted text preview:

Proofs Sections 1 5 1 6 and 1 7 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Motivation Terminology Rules of inference Modus ponens addition simplification conjunction modus tollens contrapositive hypothetical syllogism disjunctive syllogism resolution Examples Fallacies Proofs with quantifiers Types of proofs Trivial vacuous direct by contrapositive indirect by contradiction indirect by cases existence and uniqueness proofs counter examples Proof strategies Forward reasoning Backward reasoning Alerts CSCE 235 Fall 2008 Predicate Logic and Quantifiers 2 Motivation 1 Mathematical proofs like diamonds are hard and clear and will be touched with nothing but strict reasoning John Locke Mathematical proofs are in a sense the only true knowledge we have They provide us with a guarantee as well as an explanation and hopefully some insight CSCE 235 Fall 2008 Predicate Logic and Quantifiers 3 Motivation 2 Mathematical proofs are necessary in CS You must always try to prove that your algorithm terminates is sound complete optimal finds optimal solution You may also want to show that it is more efficient than another method Proving certain properties of data structures may lead to new more efficient or simpler algorithms Arguments may entail assumptions You may want to prove that the assumptions are valid CSCE 235 Fall 2008 Predicate Logic and Quantifiers 4 Terminology A theorem is a statement that can be shown to be true via a proof A proof is a sequence of statements that form an argument Axioms or postulates are statements taken to be self evident or assumed to be true A lemma plural lemmas or lemmata is a theorem useful withing the proof of a theorem A corollary is a theorem that can be established from theorem that has just been proven A proposition is usually a less important theorem A conjecture is a statement whose truth value is unknown The rules of inference are the means used



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Proofs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Proofs and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?