Section 1

Question 1

What is a proposition

Answer 1

A statement that is either True or False

Question 2

Explain ‘P XOR Q’

Answer 2

This is similar to an OR statement but excludes the possibility of both being true

Question 3

Explain ‘P implies Q’

Answer 3

This is true when any of the following occur:
-Both P and Q are true
-Both P and Q are false
-Q is true
An implication is true exactly when the if part is false or the then part is true

Question 4

Explain ‘P IFF Q’

Answer 4

IFF stands for ‘if and only if’. The proposition is only T if both P and Q are false or both are true. This kind of statement also means that P and Q are logically equivalent.

Question 5

What is the symbolic notation of ‘Not(P)’

Answer 5

¬P

Question 6

What is the symbolic notation of ‘P and Q’

Answer 6

P A Q

Question 7

What is the symbolic notation of P or Q

Answer 7

P V Q

Question 8

What is the symbolic notation of P implies Q

Answer 8

P —> Q

Question 9

What is the symbolic notation of ‘If P then Q’

Answer 9

P —> Q

Question 10

What is the symbolic notation of ‘P IFF Q’

Answer 10

P Q

Question 11

What is the contrapositive of the implication ‘P implies Q’ and how is it related with the implication?

Answer 11

The contrapositive is ‘Not Q implies not P’.

This is just a different way of saying the original implication and they are equivalent.

Question 12

What is the ‘Converse’ of ‘P implies Q’ and is it equivalent?

Answer 12

The converse is ‘Q implies P’

They are not equivalent

Question 13

What type of statement is equivalent when you combine an implication and its converse? i.e ‘If I am grumpy, then I am hungry, AND if I am hungry then I am grumpy’

Answer 13

This results in the equivalent implication of:

I am grumpy IFF I am hungry

Question 14

What is the key concept to remember when dealing with a proposition with a variable in an infinite set?

Answer 14

You cant check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set.

Question 15

Explain how this statement reads

(Upside down A)n € N. p(n) is prime:

Answer 15

• Upside down A = ‘For All’
• N= nonnegative integers
• €= is a member of
• For every nonnegative integer n the value of n^2 + n + 41 is prime

Question 16

How can you rewrite a^4+b^4+c^4 = d^4 has no solution when a.b.c.d are positive integers? What is the name of this proposition and is it true?

Answer 16

• (upside down A) a,b,c,d € Z+ . a^4+b^4+c^4 != d^4
• Z+ is a symbol for positive integers
• Strings of (upside down A) are combined
• Euler Conjecture and it is false

Question 17

What is a Predicate

Answer 17

A proposition whose truth depends on the value of one or more variables
P(N) = n is a perfect square
DO NOT CONFUSE with: p(n) which is an ordinary function and is a numerical quantity

Question 18

What are some examples of Always True propositions

Answer 18

• For all n, P(n) is true

- P(n) is true for every n

Question 19

What are some examples of Sometimes True propositionis

Answer 19

P(n) is true for some n

there exists an n such that p(n) is true

Question 20

What is a universally quantified statement?

Answer 20

A sentence that quantifies how often a predicate is true. Specifically an assertion that a predicate is always trye

Question 21

What is an existentially quantified statement

Answer 21

An assertion that a predicate is sometimes true

Question 22

How do you notate the following: P(x) is true for all values of x in some set D

Answer 22

(upside down A) x €D. P(x)

• read as ‘For all x in D, P(x) is true.
• This is a universal quantifier

Question 23

How do you notate P(x) is true for at least one value of x in D?

Answer 23

(backward E)x € D. P(x)

• Read as ‘there exists an x in D such that P(x) is true
• This is an existential quantifier

Question 24

What does the notation (backward E) stand for

Answer 24

There exists…

Question 25

When is it conventional to omit the mention of a non empty set?

Answer 25

When all the variables in a formula are understood to take values from the same non empty set it is conventional to omit the mention of the set.

-‘(upside down A) x € D (backwards E) y € D. (Q(x, y)’ is the same as ‘(Upside down A) x(backwards E)y. Q(x, y)’

Question 26

When is a proposition called valid

Answer 26

When it evaluates to T no matter what truth values are assigned to the individual propositional variables.

Question 27

Explain how the distributive law applies to P and (Q or R)

Answer 27

This is the same as saying (P and Q) or (P and R)

Question 28

When is a proposition satisfiable?

Answer 28

If some setting of the variables makes the proposition true