Formal and informal proofs - University of Pittsburgh
CS 441 Discrete Mathematics for CS Lecture 6
Formal and informal proofs
Milos Hauskrecht milos@cs.pitt.edu 5329 Sennott Square
CS 441 Discrete mathematics for CS
M. Hauskrecht
Announcements
? Homework assignment 2 due today ? Homework assignment 3:
? posted on the course web page ? Due on Monday February 4, 2013 ? Recitations on Wednesday: ? Practice problems related to assignment 3
CS 441 Discrete mathematics for CS
M. Hauskrecht
1
Theorems and proofs
? The truth value of some statement about the world is obvious and easy to assign
? The truth of other statements may not be obvious, ... .... But it may still follow (be derived) from known facts about the world
To show the truth value of such a statement following from other statements we need to provide a correct supporting argument - a proof
Important questions: ? When is the argument correct? ? How to construct a correct argument, what method to use?
CS 441 Discrete mathematics for CS
M. Hauskrecht
Theorems and proofs
? Theorem: a statement that can be shown to be true. ? Typically the theorem looks like this: (p1 p2 p3 ... pn ) q
Premises
conclusion
? Example: Fermat's Little theorem: ? If p is a prime and a is an integer not divisible by p, then: a p1 1 mod p
CS 441 Discrete mathematics for CS
M. Hauskrecht
2
Theorems and proofs
? Theorem: a statement that can be shown to be true. ? Typically the theorem looks like this: (p1 p2 p3 ... pn ) q
Premises
conclusion
? Example: Fermat's Little theorem:
Premises (hypotheses)
? If p is a prime and a is an integer not divisible by p,
then: a p1 1mod p
conclusion
CS 441 Discrete mathematics for CS
M. Hauskrecht
Formal proofs
Proof: ? Provides an argument supporting the validity of the statement ? Proof of the theorem:
? shows that the conclusion follows from premises ? may use:
? Premises ? Axioms ? Results of other theorems
Formal proofs:
? steps of the proofs follow logically from the set of premises and axioms
CS 441 Discrete mathematics for CS
M. Hauskrecht
3
Formal proofs
? Formal proofs: ? show that steps of the proofs follow logically from the set of hypotheses and axioms
premises
+
axioms
+
proved theorems
conclusion
In this class we assume formal proofs in the propositional logic
CS 441 Discrete mathematics for CS
M. Hauskrecht
Special case: equivalences
Proofs based on logical equivalences. A proposition or its part can be transformed using a sequence of equivalence rewrites till some conclusion can be reached. Important: Equivalences rewrite propositions whether they are True of False.
Example: Show that (p q) p is a tautology.
? Proof: (we must show (p q) p T)
(p q) p ?(p q) p
Useful
[?p ?q] p
DeMorgan
[?q ?p] p Commutative
?q [ ?p p ] Associative
?q [ T ]
Useful
CS 441 Discrete mathematics for CS
M. Hauskrecht
4
General proofs
? Infer new True statements from known True statements
premises
+
axioms
+
proved theorems
True
CS 441 Discrete mathematics for CS
conclusion
True ?
M. Hauskrecht
Rules of inference
Rules of inference: ? Allow us to infer from True statements new True statements ? Represent logically valid inference patterns
Example: ? Modus Ponens, or the Law of Detachment ? Rule of inference
p p q q
? Given p is true and the implication p q is true then q is true.
CS 441 Discrete mathematics for CS
M. Hauskrecht
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- formal proofs and boolean logic ii extending f with rules for
- formal verification of a modern sat solver
- a circuit based sat solver for logic synthesis
- logic and proof university of cambridge
- logic and proof lean
- formal and informal proofs university of pittsburgh
- lecture 8 predicate logic proofs university of washington
- formal veri cation with smt solvers why and how
- formal methods first order logic 3 3 proofs johns hopkins university
- chapter 8 hilbert proof systems formal proofs deduction theorem
Related searches
- formal and informal education pdf
- non formal and informal education
- formal and informal teaching
- formal and informal education
- formal and informal essays
- formal and informal words
- formal non formal and informal education
- formal and informal essay examples
- formal and informal education essay
- formal and informal education definition
- formal and informal words examples
- formal and informal letters examples