Transcript Predicate Calculus - SIUE Computer Science

MATH 224 – Discrete Mathematics
Predicate Calculus
Some of the statements that are important in mathematics and computer science are not
propositions. For example, X % 2 == 0 is not true for all integers, but only even
integers. In order to make statements about the truth of this type of statement, it is
necessary to introduce the quantifiers for all
and there exists
. So for example,
we can make a statement about an array of integers such as the upper bound below.
Given an array of integers A, a statement such as
is of course true for every element of A.
4/9/2015
1
MATH 224 – Discrete Mathematics
Predicate Calculus
Predicate calculus allows us to make precise statements about the properties of a
specific data structure. Consider the example below. *
Can you rewrite the predicate above using the conditional connective?
*Note that the set of allowable values for i is called the domain. Thus in this
example, the domain is the set of integers for i between 0 and N – 2.
4/9/2015
2
MATH 224 – Discrete Mathematics
Predicate Calculus
Predicate calculus allows us to make precise statements about the properties of a
specific data during the execution of an algorithm. Consider the example below.
What is the domain for Y? What about the domain for X? How
would you quantify X?
4/9/2015
3
MATH 224 – Discrete Mathematics
Predicate Calculus
What are some values for n0 and c that will make the predicate clause above
true?
In the discussion above, what does the integer N refer to?
4/9/2015
4
MATH 224 – Discrete Mathematics
Substitution of Quantifiers
What are the equivalent predicates for the following with
replaced by
4/9/2015
replaced by
and
?
5
MATH 224 – Discrete Mathematics
Order of Quantifiers
Look back at Slide 1. How would express the fact that there is one upper
bound for all elements in the array A? Now look at Slide 3. How would
express the invariant for the bean algorithm using quantifiers for both X
and Y?
4/9/2015
6
MATH 224 – Discrete Mathematics
Order of Quantifiers
4/9/2015
7
MATH 224 – Discrete Mathematics
Proofs
In the predicate calculus, it is not possible to use truth tables to prove most results
since statements depend on one or more variables. This makes the job of proving
results quite a bit more difficult. Would it be possible to use truth tables if the
domain(s) of the variable(s) are finite?
Logical systems consists of a set of definitions, axioms, and rules of inference. The
axioms, also called postulates, are taken to be true without proof. The rules of
inference tell us how to derive new results from axioms and from theorems that have
already been proven. This mimics the way people make decisions about the “real”
world. We have already seen examples of the use of inference in deriving a sequence
of equivalences in order to show that a compound proposition is a tautology.
4/9/2015
8
MATH 224 – Discrete Mathematics
Proofs
Let’s consider a simple example. We observe that whenever water is boiling if we
measure it’s temperature it will be 100o C. This then becomes one of our axioms.
Later we find a pot of water that is boiling. Without measuring its temperature we
conclude that the temperature is 100o C. This is an example of the rule of inference
called modus pones.
In table 1, on Page 66, 8 rules of inference for the propositional calculus are listed,
but only the first one is needed if we start with an appropriate set of axioms. The
three axioms listed below are sufficient to prove any result in the propositional
calculus. Of course it is almost always easier to use truth table.
1. A → (B → A)
2. (A → (B → C)) → ((A → B) → (A → C))
3. (¬B → ¬A) → ((¬B → A) → B)
Show that each of these is a tautology using truth tables.
4/9/2015
9
MATH 224 – Discrete Mathematics
Proofs
With quantifiers additional axioms and rules of inference are needed. We will not
consider the technical details of the predicate calculus but will proceed to consider
several informal proofs using the rules of inference in Table 1 on page 66 and Table 2
on page 70 from our text book.
Modus pones states that given p is true and given that p → q it follows that q is true.
This rule corresponds to the definition of the conditional statement. In fact, all the
other rules of inference for the propositional calculus can be proved from this one and
the axioms.
Table 2 shows the additional rules needed for the predicate calculus.
4/9/2015
10
MATH 224 – Discrete Mathematics
Propositional Calculus Proof
Example 7 on page 67 - 68 from our textbook:
Given p → q, ¬p → r, r → s, prove that ¬q → s
1.
2.
3.
4.
5.
6.
p→q
¬q → ¬ p
¬p → r
¬q → r
r→s
¬q → s
4/9/2015
Given (or Hypothesis)
Contrapositve (an equivalence from section 1.2)
Given
Hypothetical syllogism from steps 2 and 3 (transitive)
Given
Hypothetical syllogism from steps 4 and 5
11
MATH 224 – Discrete Mathematics
Propositional Calculus Proof
Here is another example.
Given ¬p → ¬q, ¬p → q, prove p.
1.
2.
3.
4.
5.
6.
¬p→q
pvq
¬p → ¬q
p v ¬q
(p v p)
p
4/9/2015
Given (or Hypothesis)
Equivalence , Table 7, Page 25
Given
Equivalence , Table 7, Page 25
Resolution steps 2 and 4
Idempotent law, Table 6, Page 24
12
MATH 224 – Discrete Mathematics
Propositional Calculus Proof
Here is another proof for: Given ¬p → ¬q, ¬p → q, prove p.
(¬B → ¬A) → ((¬B → A) → B)
1.
2.
3.
4.
5.
¬p → ¬q
(¬p → ¬q) → ((¬p → q) → p)
(¬p → q) → p
¬p → q
p
4/9/2015
Given
Axiom 3, where p correspond to B and q to A
Modus Pones steps 1 and 2
Given
Modus Pones steps 3 and 4
13
MATH 224 – Discrete Mathematics
Proofs
Example of a direct proof: Prove that the sum of two even numbers is even.
1. Let X and Y be even numbers.
2. Then by the definition of even A(X = 2A) and B(Y = 2B).
3. Thus X + Y = 2A + 2B = 2(A+B).
4. By the definition of even, 2(A+B) is even and thus X plus Y is even.
Using formal notation we have
( X, Y)( X even Y even → X + Y is even)
4/9/2015
14
MATH 224 – Discrete Mathematics
Proof Strategies
Direct proofs are the most obvious, but sometimes other techniques are useful. These
include:
Indirect proofs – instead of p → q prove the contrapositive that ¬q → ¬p
Proof by contradiction – instead of proving that q is true assume that q is false. Then
show this leads to a contradiction. An example would be to show that the √2 is irrational
by assuming that it is rational. This will lead to a contradiction.
Proof by cases – here the proof is broken down in to separate cases. This is a common
techniques used with algorithms.
Existence proofs – prove that something is true by providing an example. For example,
prove that there is a prime number larger than 100 by giving an example. Or in some
other cases it is easier to prove that something exists, but difficult to find an example.
Counter examples – are used to prove that something is not true. For example, if asked
to prove that the square root of every rational number is rational, show that the integer 5
contradicts this statement
4/9/2015
15
MATH 224 – Discrete Mathematics
Examples
Direct Proof:
Proof that opposite angles of two intersection lines are equal. Use the premise that
angles forming a straight line are always 180O.
α
θ
β
λ
Angles α + β = 180O and angles α + θ = 180O.
Hypothesis
Angle β = 180O ─ α and angle θ = 180O ─ α .
Algebra
Therefore opposite angles β and θ are equal.
4/9/2015
16
MATH 224 – Discrete Mathematics
Examples
Proof by Contradiction:
Proof that opposite angles of two intersection lines are equal. Use the premise that
angles forming a straight line are always 180O.
α
θ
β
λ
Angles α + β = 180O and angles α + θ = 180O.
Hypothesis
Assume that β ≠ θ.
Assumption
Angle β = 180O ─ α and angle θ = 180O ─ α .
Algebra
Then 180O ─ α ≠ 180O ─ α.
Algebra
But the previous statement cannot be true and is a contradiction.
Therefore the opposite angles α and β must be equal.
4/9/2015
17
MATH 224 – Discrete Mathematics
Examples
Existence Proof (Non constructive): (Often non constructive proofs assume
something does not exist and then show a contradiction.)
Prove that there are computational problems that cannot be solved by a computer .
Computer memory can be viewed as one large integer, and thus the maximum number
of programs that may be constructed is equal to 2B, where B is the total number of bits
of memory. (Even with infinite memory, this number is countable as long as no program
uses an infinite number of bits.)
The number of different problems that require different programs to solve is infinite, and
in fact uncountable. In fact, there are an uncountable number of problems with a yes or
no answer.
Therefore, there exist problems that cannot be solved by a computer.
Here is an example of a problem that cannot be solved by a computer. Find a program
that takes as input a problem description and a student’s programming solution.
Determine if the student’s program is correct.
4/9/2015
18