## 1.1 Exercises on logic: basics and proof by induction

*A*,*B*, and*C*are statements. The following theorem is true:ifWhich of the following statements follow from this theorem?*A*is true and*B*is not true then*C*is true.- If
*A*is true then*C*is true. - If
*A*is not true and*B*is true then*C*is not true. - If either
*A*is not true or*B*is true (or both) then*C*is not true. - If
*C*is not true then*A*is not true and*B*is true. - If
*C*is not true then either*A*is not true or*B*is true (or both).

Only (e) follows from the theorem.- If
*A*and*B*are statements. The following theorem is true:Which of the following statements follow from this theorem?*A*is true if and only if*B*is true.- If
*A*is true then*B*is true. - If
*B*is true then*A*is true. - If
*A*is not true then*B*is not true. - If
*B*is not true then*A*is not true.

All four statements follow from the theorem.- If
- Let
*G*be a group of people. Assume thatfor every person

Is it true that*A*in*G*, there is a person*B*in*G*such that*A*knows a friend of*B*.for every person

*B*in*G*, there is a person*A*in*G*such that*B*knows a friend of*A*?Yes. In the first statement*A*and*B*are variables that can stand for any person; they may be replaced by any other two symbols---for example,*A*can be replaced by*B*, and*B*by*A*, which gives us the second statement. - Prove by induction that for every positive integer
*k*we have∑ *k**i*=11 *i*(*i*+ 1)= *k**k*+ 1. For*k*= 1, the left-hand side is 1/2, equal to the right-hand side. So the statement is true for*k*= 1.Now assume the statement is true for

*k*= 1, ...,*n*. We want to prove it is true for*k*=*n*+ 1. That is, we want to prove that∑ *n*+1*i*=11 *i*(*i*+ 1)= *n*+ 1*n*+ 2. *k*=*n*, the left-hand side of this equation is*n**n*+ 1+ 1 ( *n*+ 1)(*n*+ 2). *n*+ 1*n*+ 2*k*=*n*+ 1.