(317) Homework 9(DUE 12/1)

6.1: 2, 6, 9(b), 14, 17

4.1: 4, 6, 8, 9, 10, 12

4.2: 3,5


(317)Homework 8(Due 11/17)

Here are the problems due on Thursday, 11/17. A quick reminder that we have our second quiz on 11/17, Thursday. It should cover the proof strategies.


3.4: 23

3.5: 1,2,10,26,28,30

3.6: 1,2

(317) Statements with/out variables

Here we will sum up statements with or without variables.

If P is a statement without variables, it has truth values. There are only two truth values: true or false.

On the other hand, P(x) is a statement with variable x. It has a truth set, where each x_0 is the set is a value that makes P(x_0) true. It is possible that all x in the universe makes P(x) true; or there are only some values that make it true.

For example:

P: ” 3 is a prime number.” is  a statement, and there is no variable. The truth value of P depends on itself and nothing else.

P(x): “x is a prime number.” is a statement, and x is the variable. The truth set of P(x) is the set of all prime numbers, which is a subset of \mathbb Z.

Quantifiers bind variables, and they only make sense for statements with variables. Both \forall xP(x) and \exists xP(x) have no free variable, and therefore become statements. They now have only truth values true and false.

As \forall xP(x) and \exists xP(x) are really the shorthand notation for \forall x\in UP(x) and \exists x\in UP(x), the truth value would depend on both P(x) and the universe U.

In our previous example ofP(x), adding the universal quantifier makes the statement into \forall xP(x), which means “all x are prime.” This statement is either true or false. It is true, if the universe we choose is the set of all prime numbers, and false if the universe is all integers \mathbb Z.

Similarly, the existential quantifier makes the statement into \exists xP(x), which means “there are some x that is prime.” This statement is either true or false. If the intersection of the universe and the set of prime numbers is non-empty, for example U=\{4.5, 5, \pi, e,18\}, then the statement is true. If the universe doesn’t contain any prime numbers, for example U=\{4,6,8,18\}, then the statement is false.

(317) Sum up of 1.1 and 1.2

Hi all,

This week we will talk about sections 1.3-1.5, and we will use everything we have learned last week. Here is a summary:

Proofs (or arguments) are about statements, composed of statements with logical connectives. We hope to make arguments/write down proofs that are valid, so when all premises are true, we can only say the conclusion must be true. Truth tables are nice ways of organizing information, and you can use truth tables to list all logical possibilities.

Statements: sentences that can only be either true or false. You might need more information to know the truth value of it. We use capital letters to represent statements.

To connect these statements, we use logical connectives. We have three so far: \wedge, \lor, \neg, and one more will be introduced in section 1.5. These connect the statements you make.

In an argument, you might see words like: therefore/then/hence/thus/we conclude, etc. Statements before these words are called premises, and statements after these words are called conclusions. An argument is invalid, if all premises are true, but the conclusion can be false. So if you want to judge the validity of an argument, try to see if you can come up with something that satisfies all the premises but doesn’t satisfy the conclusion. These are call counterexamples.

Remind you that logical forms (statements with logical connectives) are not unique, as you can see in the equivalent formulas on page 21 and 23.

Finally, truth table is a great tool for organizing information. Above equivalent formulas can be discovered via such tables.