Logic Flashcards
1
Q
What is a predicate?
A
A predicate is a sentence that contains finitely many variables and becomes a statement if the variables are each assigned a value.
2
Q
What word defines the list of all possible values that may be assigned to each variable (in a predicate)
A
Domain
3
Q
True or false? The following is a predicate
“Is x and integer”
A
False.
When something is put into x, it will become a question, not a statement
4
Q
What is the meaning of a truth set of a predicate
A
The truth set, P(x), is the set of all values in the domain, that when assigned to x, will make P(x) true.
5
Q
What does ℤ mean?
A
It defines the list of all posible integers
It is a common domain
6
Q
What does ℤ+ mean?
A
It defines the list of all posible positive integers
It is a common domain
7
Q
What does ℤnonneg mean?
A
It defines the list of all posible integers that are not negative including zero
It is a common domain
8
Q
What does ℕ mean?
A
The list of all natural numbers which means numbers that are greater or equal to 1
It is a common domain
9
Q
What does ℚ mean?
A
The list of all rational numbers. Meaning numbers that divide into an integer
It is a common domain
10
Q
What does ℝ mean?
A
The list of all real numbers
It is a common domain
11
Q
True or false?
Predicates can be written as follows: P(x,y) = x is a student at y
A
True
12
Q
A
13
Q
A
14
Q
What does the symbol ∀ mean and what is it called?
A
The universal quantifier and it means “for all”
15
Q
When is the statement ∀ x ∈ D, Q(x) true?
A
If and only if, Q(x) is true for each individual x in D
16
Q
When is the statement ∀ x ∈D, Q(x) false?
A
If and only if, Q(x) is false for at least one x in D
17
Q
Let D = {1, 2, 3, 4, 5}, and consider the statement
∀ x ∈ D, x2 ≥ x
Write one way to write this sentence in full english
(no symbols)
A
“For every x in the set D, x2 is greater than or equal to x.
This statement is true
18
Q
Consider the statement
∀ x ∈ R, x2 ≥ x
Find a counterexample to show that this statement is false
A
x=1/2
19
Q
What is the method of exhaustion?
A
It is when you try proving the truth of a predicate for each and every individual element of a domain
20
Q
What the does symbol ∃ define and what is it called?
A
It denotes “there exists” and is called the existential quantifier
21
Q
When is the statement ∃ x ∈D, Q(x) true?
A
If and only if, Q(x) is true for at least one x in D
22
Q
Rewrite the following formal statement in a variety of equivalent but more informal ways.
a. ∀ x ∈ ℝ, x2 ≥ 0
b. ∀ x ∈ ℝ, x2 -1 ≠ 0
c. ∃m ∈ ℤ+ such that m2 = m
(Do note use the the symbol ∃ or ∀)
A
23
Q
What is meant by a quantifier ‘trailing’ a statement
A
Instead of writing with a quantifer at the start of the sentence (“For any real number x, x2 is nonnegative”), the quanitfer is changed to the end of the sentence (“x2 is nonnegtaive for any real number x“)
24
Q
A
25
26
27
Rewrite the folowing statement in the form ∀\_\_\_, if \_\_\_ then \_\_\_.
"If a real number is an integer, then it is a rational number"
28
Given a statement, "All bytes have eight bits", is it mathmatically correct to translate it to ∀x, if x is a bite, then x has eight bits (emitting the identification of the domain)
Yes this is mathmatically correct
29
# True or false?
In a universal condition statement (∀\_\_\_, if p then q.), if you know that the hypothesis (p) is false, you must still interpret it as true
True
30
How would you define a prime number in english?
An integer that is greater than 1 whose only positive integer factors are itself and 1.
31
# True or false?
The statement "The number 24 can be written as a sum of two even integers" is a existential quantification
True as it can be expressed formally as "**∃** even integers, m and n, such that 24 = m+n"
32
# What is the negation of the following statement?
Reverse the quantifer and negate Q(x)
33
# What is the negation of the following statement?
Reverse the quantifer and negate Q(x)
34
# Write formal negations for the following statements:
a) ∀ primes p, p is odd
b) ∃ a triangle T such that the sum of all the angles of T equals 200°
a) ∃ a prime p, such that p is not odd
b) ∀ triangles T, the sum of all the angles of T do not equal 200°
35
# Write the negation for the following statement:
∀ people p, if p is blonde then p has blue eyes
∃ a person p, such that p is blonde and p does not have blue eyes
36
# True or false?
∀ is just a generalisation of an 'and' statement
True
37
# True or false?
∃ is just a generalisation of an 'or' statement
True
38
# True or false? Consider the statement: ∀ x in D, if P(x) then Q(x)
If P(x) is false for all x in D, then statement is by default, true.
True. This is shown by the nature of if statements (if p is false, the statement will automatically/vacuously true)
39
# True or false?
The rules of conditional statements (contrapositive, inverse and converse) also apply to universal conditional statements
| (∀ x in C, if p then q)
True
40
# Write the formal contrapositive, converse and inverse of the following:
If a real number is greater than 2, then its square is greater than 4.
Original formal: ∀ x ∈ ℝ, if x>2 then x2>4
Contrapositive: ∀ x ∈ ℝ, if x2≤4 then x≤2
Converse: ∀ x ∈ ℝ, if x2>4 then x>2
Inverse: ∀ x ∈ ℝ, if x≤2 then x2≤4
41
42
43
The reciprocal of a real number, a, is a real number, b, such that ab = 1. The following statement is true. Rewrite it formally using quantifiers and variables:
"Every nonzero real number has a reciprocal"
∀ nonzero real numbers, u, ∃ a real number v such that uv=1
**or**
∀ u ∈ ℝnonzero, ∃ v ∈ ℝ such that uv=1
44
The reciprocal of a real number, a, is a real number, b, such that ab = 1. The following statement is true. Rewrite it formally using quantifiers and variables:
"There is a real number with no reciprocal"
∃ a real number, u, such that ∀ real numbers, v uv≠1
**or**
∃ u ∈ ℝ such that ∀ v ∈ ℝ uv≠1
45
# Consider the statemnet "There is a smallest positive integer"
Write this statement formally using both ∃ and ∀
∀ m ∈ ℤ+, ∃ n ∈ ℤ+ such that n ≤ m
## Footnote
Given two integers, n and m. There exists a postive integer (n) that is always less than or equal all the other integers (m)
46
# Consider the statemnet "There is no smallest positive real number"
Write this statement formally using both ∃ and ∀
∀ m ∈ ℝ+, ∃ n ∈ ℝ+ such that m > n
## Footnote
Given two integers, n and m. There exists a postive integer (n) that is always less than or equal all the other integers (m)
47
# True or false?
With negations of statements with more than one qualifier, you can apply the same rules as one qualifier
True
48
# True or false?
You can never change the order of quanitifiers
False. It is true that when there are different quanitifers in a statement, changing their order will change the meaning but if there are two of the same quantifiers, changing the order does not matter.
49
What does ~ mean?
"not"
50
What does ^ mean?
"and"
51
What does ∨ mean?
"or"
52
What does ~p translate to in english terms?
not p. It will make everything opposite; true statements will become false instead.
53
What does ~ p ^ q translate to in english terms?
(not p) and q
54
True or false? p ^ q ∨ r is ambiguous
True. It could either be "(p and q) or r" or "p and (q or r)"
55
Given h="it is hot" and s="It is sunny", "write it is not hot but it is sunny" in symbolic terms (like h ^ ~s)
~h ^ s
56
Given h="it is hot" and s="It is sunny", "write it is neither hot nor sunny" in symbolic terms (like ~h ^ s)
~h ^ ~s
57
Suppose x is a particular real number. Let p, q, r equal "0\
r ∨ q
58
Suppose x is a particular real number. Let p, q, r equal "0\
p ^ q
59
Suppose x is a particular real number. Let p, q, r equal "0\
p ^ (q ∨ r)
60
True or false? Given that p is false while q is true, does that mean that p^q is true in this situation?
False. With the "and" operator (^), both premises must be true for the conclusion to be true.
61
Is p ∨ q inclusive or exclusive?
It is inherently inclusive meaning it means "p or q or both" instead of "p or q but not both"
62
True or false? Given that p is false while q is true, does that mean that p ∨ q is true in this situation?
True. With the "or" operator (∨), either p or q must be true for the conclusion to be true.
63
What is the definition of a statement form?
A statement form (or propositional form) is an expression made up of variables (p, q, r) and logical connectives (~, ^, ∨), that becomes a statement when actual statements are substituted into the variables.
64
True or false? For an and statement to be true, both premises must be true.
True. For example, p ^ q when both p and q are true, the conclusion will be true.
65
True or false? For an or statement to be true, both premises must be true.
False. For example, p ∨ q when either p or q are true, the conclusion will be true.
66
Construct a truth table for the statement form (p ∨ q) ^ ~(p ^ q).
You should have columns labeled:
p, q, p∨q, ~(p^q), (p^q) and (p∨q)^~(p^q).
67
Construct a truth table for the statement form (p^q) ∨ ~r
You shoud have columns labeled:
p, q, r, p∨q, ~r and (p^q)∨~r.
You should also have 8 rows.
Refer to example 2.1.5
68
True or false? Not p and q is logically equivalent to not p or not q.
True. This is De Morgan's Law. It also works vice versa. It is basically saying that for p and q to be false, either p or q can be false.
69
Write the negation for the following statement: "John is 180cm tall and he weighs at least 90kg"
John is not 180cm or he weighs less than 90kg. This is De Morgan's law where in negation, and becomes or.
70
Write the negation for the following statement: "The bus was late or Tom's watch was slow"
The bus was not late and Tom's watch was not slow. This is De Morgan's law where in negation, and becomes or.
71
True or false? According to De Morgan's law, "Jim is tall and thin" is logically equivalent to "Jim is not tall and thin"
True. De Morgan's law says that not tall and thin turn into not tall and not thin. However, due to the English language, "not tall and thin" basically means "not tall and not thin"
72
What is a tautological statement?
A statement that is always true, no matter what is substituted into the statement variables
73
What is a contradictory statement?
A statement that is always false, no matter what is substituted into the statement variables
74
What does p→q mean?
If p then q, → means "then".
75
True or false? p→q is a conditional statement.
True. p→q means If p then q. Therefore the truth of q depends on the condition of p.
76
Suppose a store owner tells you "If you show up to work on Monday morning then you will get the job." Under what circumstances is this his promise false? (p is false? q is false?)
Only when p is true and q is false. This is because the statement only tells you that you will get the job if you show up on Monday but it says nothing about if you don't turn up. Meaning, not turning up doesn't necessarily mean you don't get the job.
77
Given operations →, ^, ~, ∨. Order the operations from first to last
~ then ^ and ∨ then finally →
78
Construct a truth table for the statement form p V ~q → ~p
79
Using a truth table, show that p V q → r is logically equivalent to (p→r)^(q→r)
80
True or false? p → q ≡ ~p V q.
True. For the statement p→q to be true, either p must not be fulfilled or q must be fufilled.
81
Rewrite the following into if-then form: Either you get to work on time or you are fired. Let ~p be "you get to work on time", and q be "you are fired.
"If you do not get to work on time, you are fired"
p→q
82
True or false? The negation of "if p then q" is logically equivalent to "not p and not q"
False. Note that p→q≡~p V q
83
Write a negation for the following statement: If my car is in the repair shop, then i cannot get to class.
"The car is in the repair shop and you can get to class". p=car in repair shop, q=cannot get to class.
~(p→q)≡~(~p V q)
~(p→q)≡p ^ ~q De Morgan's Law
84
What is a contrapositive of the conditional statement "If p then q"
If ~q then ~p.
85
True or false? The contrapositive of a conditional statement is logically equivalent to the original conditional statement.
(is ~q→~p≡p→q)
True.
86
Write the following statement in its contrapositive form: If Howard can swim across the lake, the he can swim to the island.
"If Howard cannot swim to the island, then he cannot swim across the lake".
(p→q≡~q→~p)
87
What is the converse of If p then q
If q then p
88
What is the inverse of if p then q?
If not p, then not q
89
Write the converse and inverse of the following statement: If Howard can swim across the lake, then he can swim to the island.
Converse: If Howard can swim to the island, then he can swim across the lake
Inverse: If Howard cannot swim across the lake, then he cannot swim to the island.
(Note that both are not logically equivalent to the original statement)
90
What does ↔ mean?
"only if". p↔q means p only if q. For p to occur, q must also occur.
91
When is p↔q true?
If p and q have the same truth value. **(Either both true or both false)**
## Footnote
Remeber, the statement is true, not the values. Say p occurs if and only if q occurs means both must occur or both must not. However, if you say that one occurs and the other doesn't, you are not following the statement and therefore the statement is false.
92
True or false? p↔q is logically equivalent to q→p
False.
93
True or false? p↔q≡(p→q)^(q→p)
True
94
Rewrite the following statement as a conjunction of two if-then statements: "This computer program is correct if, and only if, it produces correct answers for all possible sets of input data"
If this computer program is correct, then it produces correct answers for all possible sets of input data and if it produces correct answers for all possible sets of input data, then the program is correct.
95
What does the statement "r is a sufficient condition for s" mean? (in statement form)
If r then s. r is sufficient enough for s to occur.
96
What does the statement "r is a necessary condition for s" mean? (in statement form)
If not r then not s. s will not occur if r does not occur as it is a _necessary condition_
97
Rewrite the following statement in the form "If A then B": Pia's birth on U.S. soil is a sufficient condition for her to be a U.S. citizen.
If Pia was born on U.S. soil, then she is a U.S. citizen
98
Use the contrapositive to rewrite the following statement in two ways: "George's attaining age 35 is a necessary condition for his being president of the United States."
1. If George does not attain the age 35, then he cannot be the president of the United States.
2. If George is the president of the United States, then he has attained the age 35.
99
How would you test if an argument form is valid or not?
1. Construct a truth table
2. Look at the critical row(s), where all the premises (variables) are true. If In that row, the conclusion is false then the argument form is not valid
This is because as conclusions are inferred from the premises, if all premises are true, then the conclusion must be true
100
Determine whether the following argument is valid or invalid by drawing a truth table.
p→qV~r
q→p^r
Therfore, p→r
101
What is a syllogism, and what are its parts?
A syllogism is an argument form consisting of two premises and a conclusion. The first premise is called the **major premise** and the second is called a **minor premise**. Modus ponens is an example of a syllogism
102
What is a rule of inference?
Its just a form of argument that is valid. For example, modus ponens and modus tollens are both rule of inferences
103
True or false? The following argument form is valid
p
Therefore p V q
True. Note this is used for making generalisations
104
True or false? The following argument form is valid
p^q
Therefore p
True. Note this is used for specialization
105
What is a fallacy?
An error in reasoning (ambiguous premises, conclusion can't be inferred from premises etc)
106
What is converse error?
A type of fallacy. Its when the conclusion would be true if the premise "if p then q" were replaced with its converse which is not allowed. In the example, it is an error because if q occurring implies that p occurred, p occurring does not necessarily mean that q has occurred. (The converse is not logically equivalent)
107
What is inverse error?
A type of fallacy. Its when the conclusion would be true if the premise "if p then q" were replaced with its inverse which is not allowed. In the example, it is an error because even though q occurring implies the occurrence of p, p not occurring does not necessarily mean that q also has not occurred. (The inverse is not logically equivalent)
108
What is a sound argument?
An argument is called sound if, and only if, it is a valid argument form and all the premises are true
109
When can you be 100% sure that a conclusion is true?
When the argument is sound (all valid premises and valid argument form)
110
True or false? Premises must be true for a conclusion to be true.
False. False premises does not mean a false conclusion, the conclusion may still be true. It may be confused with the rule where "if all premises are true, the conclusion must be true": this does not work vice versa (meaning that it is possible that if all premises are false, the conclusion may still be true)
111
You arrive at an island consisting of two types of people, knights who always tell the truth and knaves who always lie. You approach two people and the conversation is as follows:
A says: B is a knight
B says: A and I are of opposite types
What are A and B?
## Footnote
The reasoning behind this is that if the solution does not work, then it must be a contradiction
-
Key Links
-
Subjects
-
Company
-
Find Us
-
