1 - Logic

Question 1

What is a proposition? What is NOT a proposition?

Answer 1

A statement that is true or false.

Questions and commands (“have a nice day”) are NOT propositions

Question 2

True or False: A proposition’s truth value must be known.

Answer 2

False. A proposition is still a proposition regardless of whether the truth value is known to be true, known to be false, unknown, or a matter of opinion.
“Monday will be cloudy” and “the movie was funny” = STILL propositions

Question 3

What is a compound proposition?

Answer 3

Individual propositions connected by a logical operation (and, or)

Question 4

What is a conjunction operation? When is it true? What symbol is used?

Answer 4

p ∧ q = “p and q” = the conjunction of p and q

p ∧ q is true ONLY when both p and q are true

Question 5

What is a disjunction operation? When is it true? What symbol is used?

Answer 5

p ∨ q = “p or q” = disjunction of p and q

p ∨ q is true when either p or q is true

Question 6

What is this: p ⊕ q? When is it true?

Answer 6

Exclusive or - true ONLY when one proposition is true and the other proposition is false

Question 7

What is negation? What is its symbol?

Answer 7

negation operation reverses the truth value of the proposition
¬p = “not p”

Question 8

What is the order of operations for compound propositions?

Answer 8

Parentheses first, then “NAO” =
Not
And
Or

Question 9

How many rows in a truth table? How do you choose which truth values go where for the initial variables?

Answer 9

for n variables, 2 to the n rows. 3 variables = 8 rows.
First column: half T, half F
Second column: 1/4 T, 1/4 F, 1/4 T, 1/4 F
…last column: T F T F T F…

Question 10

What is the rule w/ symbol ∧ ?

Answer 10

“∧” = and = ONE F = F
lambda = lANDa

Question 11

What is the rule w/ symbol ∨ ?

Answer 11

“∨” = or = ONE T = T

vOR

Question 12

What is the converse of p → q ?

Answer 12

q → p

Question 13

What is the inverse of p → q ?

Answer 13

¬p → ¬q

Question 14

What is the contrapositive of p → q ?

Answer 14

¬q → ¬p

Question 15

When is p → q False?

Answer 15

p → q is false ONLY when p=T and q=F
T → F is FALSE
otherwise, TRUE!

Question 16

When is p ↔ q true?

Answer 16

When p and q have the same truth value

Question 17

What are some other ways to say “p if and only if q” in English?

Answer 17

“p is necessary and sufficient for q”
“if p then q, and conversely”
“p IFF q”

Question 18

What is order of operations with conditional, biconditional and logical operations?

Answer 18

NAO, then → or ↔

Question 19

What does ‘p is sufficient for q’ mean?

Answer 19

p → q

if p, then q

Question 20

What does ‘mars is necessary for jupiter’ mean?

Answer 20

jupiter → mars

if jupiter, then mars

Question 21

“a necessary condition for PURPLE is BLUE” - which way does the implication go?

Answer 21

PURPLE → BLUE

Question 22

“RED unless ¬YELLOW” - implication?

Answer 22

YELLOW → RED

Question 23

Describe what ‘p only if q’ means.

Answer 23

p cannot be true if q is not true
p → q
p implies q, q is necessary for p

Question 24

Tautology

Answer 24

A compound proposition that’s ALWAYS TRUE

p ∨ ¬p

Question 25

Contradiction

Answer 25

A compound proposition that’s ALWAYS FALSE | p ∧ ¬p

Question 26

Logical equivalence

Answer 26

They have the SAME truth values – doesn’t matter what individual propositions’ truth values are. p ≡ ¬¬p

Question 27

¬(p ∨ q) ≡ ???

Answer 27

¬p ∧ ¬q

Question 28

¬(p ∧ q) ≡ ???

Answer 28

¬p ∨ ¬q

Question 29

p → q ≡ ???

Answer 29

¬p ∨ q

Question 30

p ∧ ( q ∨ r ) ≡ ???

Answer 30

( p ∧ q ) ∨ ( p ∧ r )

Question 31

p ↔ q ≡

Answer 31

( p → q ) ∧ ( q → p )

Question 32

How do you turn a predicate P(x) into a proposition?

Answer 32

Bind the variable using quantifiers or assign a value to x

Question 33

True or False: If P(x) is true for all values in its domain, it's a proposition?

Answer 33

False. It has a FREE variable.

Question 34

Order of operations, including quantifiers

Answer 34

∀ and ∃ ¬, ∧, ∨ ('NAO') →, ↔

Question 35

¬∀x ∀y P(x, y) ≡ ???

Answer 35

¬∀x ∀y P(x, y) ∃x ¬∀y P(x, y) ∃x ∃y ¬P(x, y)

Question 36

Describe the nested quantifiers as loops: | ∀x∀y P(x, y)

Answer 36

Loop thru EVERY value of x, | then for EACH value of x, loop thru EVERY value of y

Question 37

Describe the nested quantifiers as loops: | ∀x∃y P(x, y)

Answer 37

We loop through EVERY value of x. | For each x, we loop through the values for y until we find a y for which P(x, y) is true.

Question 38

Describe the nested quantifiers as loops: | ∃x∀y P(x, y)

Answer 38

We loop through the values for x until we find an x for which P(x, y) is always true when we loop through all values for y For example, x=3, P(x,y) must be true for y=1, y=2, y=3,... all y! There exists an x for which EVERY last y, makes P(x,y) TRUE. MUST be TRUE for ALL y's and that ONE x.

Question 39

``` If M(x,y) = x sent an email to y How do you write 'every person sent an email to everyone ELSE (not including himself or herself)'? ```

Answer 39

∀x ∀y ( (x ≠ y) → M(x, y))

Question 40

``` If M(x,y) = x sent an email to y How do you write 'every person sent an email to someone else'? ```

Answer 40

∀x ∃y ((x ≠ y) ∧ M(x, y))

Question 41

L(x) = x was late to the meeting | How do you write 'there was ONLY ONE x that was late to the meeting'?

Answer 41

There exists an x that was late to the meeting: ∃x L(x) AND for ALL others, IF they are not x, THEN they were not late: ∃x L(x) ∧ ∀y ( (y ≠ x) → ¬L(y) )