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.Proofs
Previewing pages 1, 2, 3, 25, 26, 27, 28, 50, 51, 52 of actual document.
View the full content.View Full Document
Proofs
0 0 70 views
Other
 Pages:
 52
 School:
 University of NebraskaLincoln
 Course:
 Csce 235  Introduction to Discrete Structures
Introduction to Discrete Structures Documents

105 pages

77 pages

19 pages

77 pages

82 pages

10 pages

85 pages

15 pages

2 pages

38 pages

3 pages

8 pages

19 pages

10 pages

14 pages

16 pages

Predicates Quantifiers Handout
21 pages

13 pages

51 pages

25 pages

25 pages

44 pages

82 pages

6 pages

19 pages

16 pages

4 pages

8 pages

71 pages

50 pages

6 pages

54 pages

7 pages

10 pages

16 pages

16 pages

56 pages

15 pages

10 pages

32 pages

7 pages

8 pages

10 pages

Predicate Logic and Quantifies
39 pages

Predicate Logic and Quantifiers
11 pages

20 pages

3 pages

13 pages

8 pages

44 pages

13 pages

14 pages

CSCE 235 – Discrete Mathematics Syllabus
3 pages

5 pages

Discrete Mathematics: Introduction
5 pages

10 pages

14 pages

8 pages

60 pages

10 pages

80 pages

109 pages

81 pages

41 pages

51 pages

105 pages

72 pages

25 pages

9 pages

16 pages

16 pages

7 pages

Introduction to Discrete Structures
13 pages

52 pages

19 pages

Predicate Logic and Quantifiers
61 pages

26 pages

Algorithms: A Brief Introduction
6 pages

8 pages

59 pages

3 pages

60 pages

41 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
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