Maggie Johnson Handout #14
CS103A
Conditionals
& Biconditionals
Key Topics
· Conditionals
· Biconditionals
· Informal Proofs Involving Conditionals and Biconditionals
· Formal Proofs Involving Conditionals and Biconditionals
What is a Conditional?
Conditional: P ® Q which denotes if P, then Q. P is called the hypothesis or antecedent, and Q is called the conclusion or consequent. The truth table for the conditional is:
P Q P® Q
T T T
T F F
F T T
F F T
P ® Q is equivalent to ~P v Q. Other interpretations besides if P, then Q for P ® Q:
P only if Q
Q provided P
Q if P
Logical Consequence: A sentence S is a logical consequence of a set of premises if it is impossible for the premises all to be true while the conclusion is false. Another way of saying this is it is impossible for (P1^…^Pn) to be true while Q is false. Or, Q is a logical consequence of P1, …, Pn if and only if the sentence (P1^…^Pn) ® Q is a logical truth.
What is a
Biconditional?
Biconditional: P « Q which denotes P if and only if Q. The truth table for the biconditional is:
P Q P « Q
T T T
T F F
F T F
F F T
P « Q is equivalent to (P ® Q) ^ (Q ® P).
Modus Ponens: From P ® Q and P, infer Q
Biconditional Elimination: From P and either P « Q or Q « P, infer Q.
Contrapositive: ~Q ® ~P ó P ® Q
Useful Equivalences involving Conditionals:
(p ® q) ó (~p v q)
(p ® q) ó (~q ® ~p)
(p ® q) ó ~(p ^ ~q)
(p « q) ó (p ® q) ^ (q ® p)
p v q ó ~p ® q
~p ® F ó p
Conditional Proof: A technique where we prove a conditional (A®B) by showing that the consequent B must be true when the antecedent A is true. Therefore, the proof consists of attempting to find a link between the statements we assume are true in the antecedent, and what we are trying to prove in the consequent.
Example 1:
Step 1: Recognize the antecedent and consequent parts of the statement to be proven and determine the frame of reference of the proof.
If the right triangle XYZ with sides of length x & y, and hypotenuse of length z, has an area of (z2)/4, then the triangle XYZ is isosceles.
A: right triangle XYZ with sides of length x & y, and hypotenuse of length z, has an area of (z2)/4.
B: XYZ is isosceles.
The frame of reference is the information we need about the subject matter described in the conditional. In this example, we need information about geometry, triangles and probably some basic algebra.
Step 2: Formulate the abstraction question:
Assume A is true and use this information to reach the conclusion that B is true. We can work forward from A or backward from B. We usually begin working backward by formulating the abstraction question: "How or when can I conclude that B is true?". This question must be phrased in a general way concerning the problem at hand. A good abstraction question for the example above is "How can I show that any triangle is isosceles?". Notice this is not in terms of triangle XYZ.
Step 3: Answer the abstraction question:
a) Show that two of the triangle's sides have equal length.
b) Show that x = y. (B1)
Now we have a new statement B1 (Show x=y) with the property that if you can prove B1 is true, then B is true. So, now we focus on proving B1 is true.
Step 4: Continue doing Steps 2 (formulate a new abstraction question based on B1) and (answer the abstraction question) until you find that you cannot answer the abstraction question posed, or you reach statement A.
How can I show that two real numbers are equal?
a) Show that their difference = 0.
b) Show that x - y = 0. (B2)
How can I show that x - y = 0?
We are going in circles now (show that x=y); we have posed a question that we cannot answer so this is a clue to start the forward process.
Step 5: Using the last abstraction answer (B2), use the information in A to come up with a statement A1 which is true because A is true. The goal is to find a way to match the final B abstraction answer.
A1: xy / 2 = (z2) / 4 (area of a right triangle = 1/2 base * height)
A2: x2 + y2 = z2 (Pythagorean theorem)
A3: xy/2 = (x2 + y2) / 4 (substitute: we need x and y not z)
(rewrite A3 to look like B2; A4: x2 - 2xy + y2 = 0 multiply both sides by 4 and
subtr. 2xy from both sides.)
A5: (x - y)2 = 0 (factor)
A6/B2 : x - y = 0 (square root of each side)
B1: x = y add y to both sides
Therefore, If the right triangle XYZ with sides of length x & y, and hypotenuse of length z, has an area of (z2)/4, then the triangle XYZ is isosceles.
Biconditional Proof: Same as a conditional proof but it must be proven in two ways: A®B and B®A. Sometimes they can be organized as a cycle, which can bring down the number of proofs that must be done.
Conditional Elimination: This is the formal counterpart of modus ponens. If we have proven both B and A®B, then we can assert B. The proof of A®B takes place in a subproof.
Conditional Introduction: This is the formal counterpart of a conditional proof. To prove a statement of the form A®B, A becomes our premise and B becomes the conclusion we must prove.
Given: (P ^ R) ® Q, P, R
Prove: R ® Q
Biconditional Elimination: You can conclude Q if you establish P and either P « Q or Q « P.
Biconditional Introduction: To introduce P « Q, you must give two subproofs, one showing that Q follows from P, and one showing that P follows from Q.
Prove: P ® Q « (~Q ® ~P)
The backward-forward example above is from:
D. Solow, How to Read and Do Proofs, New York: Wiley, 1982.