Section 1 Flashcards
Foundation of Discrete Maths
What is a proposition
A statement that is either True or False
Explain ‘P XOR Q’
This is similar to an OR statement but excludes the possibility of both being true
Explain ‘P implies Q’
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
Explain ‘P IFF Q’
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.
What is the symbolic notation of ‘Not(P)’
¬P
What is the symbolic notation of ‘P and Q’
P A Q
What is the symbolic notation of P or Q
P V Q
What is the symbolic notation of P implies Q
P —> Q
What is the symbolic notation of ‘If P then Q’
P —> Q
What is the symbolic notation of ‘P IFF Q’
P Q
What is the contrapositive of the implication ‘P implies Q’ and how is it related with the implication?
The contrapositive is ‘Not Q implies not P’.
This is just a different way of saying the original implication and they are equivalent.
What is the ‘Converse’ of ‘P implies Q’ and is it equivalent?
The converse is ‘Q implies P’
They are not equivalent
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’
This results in the equivalent implication of:
I am grumpy IFF I am hungry
What is the key concept to remember when dealing with a proposition with a variable in an infinite set?
You cant check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set.
Explain how this statement reads
(Upside down A)n € N. p(n) is prime:
- 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
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?
- (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
What is a Predicate
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
What are some examples of Always True propositions
- For all n, P(n) is true
- P(n) is true for every n
What are some examples of Sometimes True propositionis
P(n) is true for some n
there exists an n such that p(n) is true
What is a universally quantified statement?
A sentence that quantifies how often a predicate is true. Specifically an assertion that a predicate is always trye
What is an existentially quantified statement
An assertion that a predicate is sometimes true
How do you notate the following: P(x) is true for all values of x in some set D
(upside down A) x €D. P(x)
- read as ‘For all x in D, P(x) is true.
- This is a universal quantifier
How do you notate P(x) is true for at least one value of x in D?
(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
What does the notation (backward E) stand for
There exists…
When is it conventional to omit the mention of a non empty set?
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)’
When is a proposition called valid
When it evaluates to T no matter what truth values are assigned to the individual propositional variables.
Explain how the distributive law applies to P and (Q or R)
This is the same as saying (P and Q) or (P and R)
When is a proposition satisfiable?
If some setting of the variables makes the proposition true
