Discrete Structures LOGIC
Discrete Structures
Readings Check section 2.1
Read Section 2.1, pages 47 53, and answer the questions below:
Type in the answers below each question
1) What two types of sentences are not regarded as statements? (Can you name a third type?)
2) Under what conditions is the statement p q true?
3) What is the one case in which the statement p q is false?
4) Under what conditions is the statement p q true?
5) What connective is used in place of the word "but".
6) How many rows are in a truth table with three variables, like p, q, r?
7) Referring to example 2.6 and definition 2.1, what type of statement is p (p q) ?
Discrete Structures
Readings Check section 2.2
Read Section 2.2, pages 55 63, and answer the questions below: [ignore pages 64 65]
Type in the answers below each question
1) From table 2.6, give a statement that is logically equivalent to p q.
2) From table 2.7, give a statement that is logically equivalent to p q.
3) What are DeMorgan's Laws? [important]
4) What are the two Idempotent Laws?
5) What are the two Absorption Laws? [These will be very handy on homework and quiz.]
6) Using the Principle of Duality, write a logical equivalence based on the equivalence p p T0 ? [page 59]
7) What is the relationship between the tautology (p q) (q p) and the tautology
((r s) (u v)) ((u v) (r s)) ? [see the substitution rules on p. 60 and example 2.10]
8) List both the contrapositive, and the converse of the implication statement (r s) u. Which of the two is equivalent to the original implication statement? [see pages 62 63]
Discrete Structures
Readings Check section 2.3
Read Section 2.3, pages 67 79, 82 84, and answer the questions below:.
1) How many premises can an argument have? How many conclusions?
2) Is the argument presented in table 2.14 a valid argument? How do we know it is/isn't ?
3) Looking at page 69, if p q then what can we say about the statement p q ?
4) As explained at the top of page 70 what is the potential problem with using a truth table to establish the validity of an argument?
5) In the "tabular form" of an argument, what goes above the line? What goes below the line?
6) What rule of inference shows that the following argument is valid? "If x is an amanita muscaria then x is in the class agaricomycetes. If y is in the class agaricomycetes then y is in the Fungi kingdom. Therefore, amanita muscaria is in the Fungi kingdom."
7) What rule of inference establishes the validity of the following argument:
(r s) w
w
(r s)
8) Is the following argument valid? (See page 74)
r s
s
9) The argument in example 2.34 is invalid. Briefly summarize how this is shown (on page 83).
Weekly Summary, Week 2, Chapter 2, Discrete Structures
Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.
1)
a) Write out the contrapositive to the statement (p q ) (p q)
b) Is the result in part a) a tautology?
2) Using the Principle of Duality, write out the dual of the logical equivalence:
(p q) (p r) p (q r)
[Hint: you must first covert the statement on the right into a disjunction]
3) Write out a statement that gives exactly the same final result column (under the ?) as the following truth table:
4)
a) How many rows (not including column headers) are required to make a truth table for a statement that contains 10 different letters (primitive statements)?
b) How many different final result columns are possible in a truth table for a statement that contains 10 different letters? [Just set up the answer; do not reduce it to a single number.]
[For example, a truth table for a statement with 2 variables, such as p and q, would contain 4 rows. Each row can be 0 or 1 in the final result column. Therefore, using the product rule from section 1.1, there would be
24 = 16 possible ways to fill out the final result column.]
5) Negate and (greatly) simplify the following statement: (p (p q)) (p q).
6) Is the following argument valid or invalid? [(p s) (t (s r)) (q r) (p q t)] (r s)
[There is a small bonus if you can precisely explain your answer.]
7) The following argument is invalid. Assign logical values (0 or 1) to the individual letters in such a way that all of the premises are true and the conclusion is false, thus proving that the argument is invalid.
P Q
R S
W Q
R W
W P
P S
bonus: Write the following argument in symbolic notation. Is it a valid argument?
[Hint: for the primitive statements use the symbols a1 , a2 , a3 , b1 ,…, and also v1 v2 v3 .]
"If Alvarez supports issue 1 and supports issue 2 and opposes issue 3 then I will vote for Alvarez. I will vote for Alvarez or Brown or Chang. Brown supports issue 3 but opposes issue 2. Chang agrees with Alvarez on issues 1 and 2. Chang disagrees with Brown on issues 2 and 3. Alvarez supports issue 1. If Chang supports issue 1 then Alvarez will oppose issue 3. If I vote for Alvarez then I will not vote for Chang. If Brown supports issue 1 then I will vote for Chang. Therefore, I will vote for Chang.
