Discrete Math Flashcards by Daniel Bowley

Assume propositions p, q, and r have the following truth values:

p is true
q is true
r is false

2)
¬r
True
False

true
Correct
The negation of a false proposition is true.

How well did you know this?

Not at all

Perfectly

p is true
q is true
r is false

3)
p ∧ r
True
False

false
Correct
Since r is false, the proposition is false.

How well did you know this?

Not at all

Perfectly

Assume the propositions p, q, r, and s have the following truth values:

p is false
q is true
r is false
s is true

What are the truth values for the following compound propositions?
(b)

p ∨ r

False

p ∨ q is false only when p and q are both false.

How well did you know this?

Not at all

Perfectly

Assume the propositions p, q, r, and s have the following truth values:

p is false
q is true
r is false
s is true

What are the truth values for the following compound propositions?

q ⊕ r

True

The exclusive or operation is usually denoted with the symbol ⊕. The proposition p ⊕ q is true if exactly one of the propositions p or q is true but not both. This question asks you to fill in the truth table for p ⊕ q.

How well did you know this?

Not at all

Perfectly

Indicate whether each statement is true or false, assuming that the “or” in the sentence means the inclusive or. Then indicate whether the statement is true or false if the “or” means the exclusive or.

(a)

February has 31 days or the number 5 is an integer.

Inclusive or: True. Exclusive or: True.

Note: evaluates to true when p is true and q is false or when q is true and p is false.
- only when one of the propositions is true, but not both.

Note: evaluates to true when one or both of the propositions are true.
- when at least one of the propositions is true.

How well did you know this?

Not at all

Perfectly

In this equation for logic math : TRUE ∧ ¬(FALSE ∧ TRUE), after following order of operations how to FALSE cancel out to equal the next step T ∧ ¬ T / F . Did it cancel out?

Let’s break it down step by step using logical operations:
- Start with the given expression:
[ TRUE \land \neg (FALSE \land TRUE) ]
- Evaluate the inner parentheses:
- FALSE ∧ TRUE evaluates to FALSE (since AND requires both to be true).
- Now the expression simplifies to:
[ TRUE \land \neg FALSE ]
- Apply negation (¬):
- ¬FALSE is TRUE (since NOT flips the truth value).
- Now the expression simplifies to:
[ TRUE \land TRUE ]
- Evaluate the final AND operation:
- TRUE ∧ TRUE evaluates to TRUE.
So, the FALSE didn’t “cancel out”—it was negated and transformed into TRUE. The final result is TRUE

How well did you know this?

Not at all

Perfectly

This question uses the following propositions:

p: I will share my cookie with you.
q: You will share your soda with me.

Select the conditional statement that has the same logical meaning as the English sentence given.

I will share my cookie with you only if you share your soda with me.
q → p
p → q

p only if q.
Correct

How well did you know this?

Not at all

Perfectly

Determine whether the following compound propositions are tautologies, contradictions, or neither.

1)
p ↔ ¬p
*Tautology
*Contradiction
*Neither a tautology or a contradiction

Contradiction

Correct
The proposition is always false, whether p is true or false. Regardless of p’s truth value, p can not have the same truth value as ¬p.

A compound proposition is a contradiction if the proposition is always false,

How well did you know this?

Not at all

Perfectly

Determine whether the following compound propositions are tautologies, contradictions, or neither.

2)
p → ¬p
*Tautology
*Contradiction
*Neither a tautology or a contradiction

Neither a tautology or a contradiction

Correct
There is a truth value for p that makes the proposition true, and a truth value for p that makes the proposition false.

How well did you know this?

Not at all

Perfectly

Select the English sentence that is logically equivalent to the given sentence.

1)
It is not true that the child is at least 8 years old and at least 57 inches tall.
The child is at least 8 years old and at least 57 inches tall.
The child is less than 8 years old or shorter than 57 inches.
The child is less than 8 years old and shorter than 57 inches.

l: The child is at least 8 years old
f: The child is at least 57 inches tall

Correct

The sentence in the question is equivalent to is ¬(l ∧ f) which, by De Morgan’s law is equivalent to (¬l ∨ ¬f). The expression (¬l ∨ ¬f) means that the child is not at least 8 years old (is less than 8 years old) or is not at least 57 inches tall (is shorter than 57 inches).

How well did you know this?

Not at all

Perfectly

Simplify m∨(q∧¬q) to m

See feedback below.
m∨(q∧¬q)
m∨F
m

How well did you know this?

Not at all

Perfectly

Simplify ¬(¬q→(¬w∧¬q)) to ¬q∧w

See feedback below.
¬(¬q→(¬w∧¬q))
¬(¬¬q∨(¬w∧¬q))
¬(q∨(¬w∧¬q))
¬((q∨¬q)∧(q∨¬w))
¬(T∧(q∨¬w))
¬((q∨¬w)∧T)
¬(q∨¬w)
¬q∧¬¬w
¬q∧w

How well did you know this?

Not at all

Perfectly

For the following questions, the domain for the variable x is the set of all positive integers. The first three questions use predicates O and M which are defined as follows:

O(x): x is odd
M(x): x is an integer multiple of 4 (e.g., 4, 8, 12,...)

Indicate whether each quantified statement is true or false:

2)
∃x (¬O(x) ∧ ¬M(x))
True
False

Correct
The value x = 6 is an example of a positive integer that is not odd and is not a multiple of 4.

How well did you know this?

Not at all

Perfectly

For the following questions, the domain for the variable x is the set of all positive integers. The first three questions use predicates O and M which are defined as follows:

O(x): x is odd
M(x): x is an integer multiple of 4 (e.g., 4, 8, 12,...)

Indicate whether each quantified statement is true or false:
3)
∀x (M(x) → ¬O(x))
True
False

Correct
Every integer that is a multiple of 4 is even. Therefore, if x is a multiple of 4, then x is not odd.

How well did you know this?

Not at all

Perfectly

For the following questions, the domain for the variable x is the set of all positive integers. The first three questions use predicates O and M which are defined as follows:

O(x): x is odd
M(x): x is an integer multiple of 4 (e.g., 4, 8, 12,...)

4)
∀x ((x = 1) ∨ (x2 ≠ x))
True
False

Correct
The only positive integer x that is equal to x2 is 1, so every positive integer x is either equal to 1 or x2 ≠ x.

How well did you know this?

Not at all

Perfectly

1)
The expression ∃x P(x) is a proposition.
True
False

Correct
The variable x is bound, so the statement is either true or false.

How well did you know this?

Not at all

Perfectly

The expression (∃x S(x)) ∨ R(x) is a proposition.
True
False

Correct
The variable x in R(x) is a free variable, so the statement is not a proposition.

How well did you know this?

Not at all

Perfectly

3.3.2: Free and bound variables in quantified statements.
3)
The expression ∃x (S(x) ∨ R(x)) has a free variable.
True
False

Correct
Both occurrences of x are bound by the existential quantifier.

How well did you know this?

Not at all

Perfectly

Name N(x) D(x)
Happy F F
Sleepy F T
Grumpy T T
Bashful T T
2)
Is the statement “∀x (N(x) ∧ D(x))” true or false for the group defined in the table?
True
False

Correct
Happy and Sleepy are both are counterexamples to the statement. For example, N(Sleepy) ∧ D(Sleepy) is false.

How well did you know this?

Not at all

Perfectly

Name N(x) D(x)
Happy F F
Sleepy F T
Grumpy T F
Bashful T F

2)
Is the statement “∃x (N(x) → D(x))” true or false for the group defined in the table?
True
False

Correct
The logical statement N(x) → D(x) is true for x = Happy and x = Sleepy. For example, since N(Happy) is false, N(Happy) → D(Happy) is true.

How well did you know this?

Not at all

Perfectly

4)
The expression ∀x P(x) ∨ ∃x Q(x) is a proposition.
True
False

Correct
The quantifier ∀ binds the variable x in P(x). Therefore ∀x P(x) is a proposition. The quantifier ∃ binds the variable x in Q(x). Therefore ∃x Q(x) is a proposition. ∀x P(x) ∨ ∃x Q(x) is the disjunction of two propositions and is therefore a proposition.

How well did you know this?

Not at all

Perfectly

Consider the following argument:
¬q
p → q
∴ ¬p

2)
The proposition ¬q is:
a hypothesis
the conclusion
an argument

Correct
All the propositions except the last are hypotheses.

How well did you know this?

Not at all

Perfectly

Consider the following argument:
¬q
p → q
∴ ¬p

3)
The argument is valid if which proposition is a tautology:
((p → q) ∧ ¬q) → ¬p
¬p → ((p → q) ∧ ¬q)
¬p ↔ ( (p → q) ∧ ¬q )

Correct
The conjunction of the hypotheses implies the conclusion.

How well did you know this?

Not at all

Perfectly

Consider the argument below:
p → q
p ∨ q
∴ q

p q p → q p ∨ q
T T T T
T F F T
F T T T
F F T F

1)
In which rows are both the hypotheses true?
Row 1
Rows 1 and 3
Rows 1, 3, and 4

Correct
In rows 1 and 3, p → q and p ∨ q are both true. In the other rows, at least one of the two hypotheses is false

How well did you know this?

Not at all

Perfectly

Consider the argument below: p ∨ q p ∴ ¬q The truth table below shows the truth values for the two hypotheses and the conclusion for every possible truth assignment to p and q. p q p ∨ q ¬q T T T F T F T T F T T F F F F T Which truth assignment is a proof that the argument is invalid? p = q = T p = T and q = F p = F and q = T

Correct When p = q = T, both the hypotheses (p ∨ q and p) are true, but the conclusion ¬q is false.

(Valid) Argument form A: ¬q p → q ∴ ¬p (Invalid) Argument form B: ¬p p → q ∴ ¬q 6 is not a prime number. If 6 is a prime number, then 4 is a prime number. ∴ 4 is not a prime number. Valid Invalid

Correct The form of this argument is B, which is invalid

1) If it is sunny, then the ice cream stand will be open. It is sunny. Therefore, the ice cream stand is open. Conjunction Hypothetical syllogism Modus ponens

Correct Both hypotheses - the conditional statement and its hypothesis - are true. Symbolically, the hypotheses are p and p→q. Thus, the argument is valid by modus ponens.

2) If the city experiences a blizzard, the university will close. The university is not closed today. Therefore, the city did not experience a blizzard. Modus tollens Modus ponens Simplification

Correct The conclusion of the conditional statement is false. Symbolically, the hypotheses are ¬q and p→q. By modus tollens, the conclusion of the argument should be that the hypothesis of conditional statement is also false.

Good question! While a premise and a hypothesis share similarities, they serve different roles in logic and reasoning. - Premise: In short, a premise is something assumed to be true within an argument, while a

Hypothesis:

A hypothesis, on the other hand, is more of a testable statement or educated guess that requires verification through experimentation or observation. In science, a hypothesis predicts outcomes: "If Oliver gets regular exercise, then he will stay healthy." This suggests a possible relationship that needs evidence to confirm.

Premise

A premise is a foundational statement in an argument that is assumed to be true or accepted as a given. It's used to support a conclusion. For example, in "All dogs are cute, and Oliver is my dog. So Oliver is cute," both "All dogs are cute" and "Oliver is my dog" are premises that lead logically to the conclusion.

Predicates and are defined below. The domain of discourse is the set of all positive integers. P(x) : x is even T(x,y) : 2 sq.x = y E(x,y,z) : x sq.y = z Indicate whether each logical expression is a proposition. If the expression is a proposition, then give its truth value. T(5, x)

Not a proposition because x is a variable.

Exercise 3.2.2: Truth values for quantified statements about integers. In this problem, the domain of discourse is the set of all integers. Which statements are true? If an existential statement is true, give an example. If a universal statement is false, give a counterexample. ∃x (x + 2 = 1)

True. Example: x = -1.

In this problem, the domain of discourse is the set of all integers. Which statements are true? If an existential statement is true, give an example. If a universal statement is false, give a counterexample. ∀x (x2 − x ≠ 1)

True.

Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. The square of every number is at least 0.

∀x (x2 ≥ 0)

T(x): x is a member of the executive team B(x): x received a large bonus Sam did not get a large bonus even though he is a member of the executive team

¬B(Sam) ∧ T(Sam)

Predicates P and Q are defined below. The domain of discourse is the set of all positive integers. P(x): x is prime Q(x): x is a perfect square (i.e., x = y2, for some integer y) Indicate whether each logical expression is a proposition. If the expression is a proposition, then give its truth value ∀x Q(x) ∧ ¬P(x)

Not a proposition because the variable x in P(x) is not bound by the quantifier. In the statement (∀x P(x)) ∧ Q(x), the variable x in P(x) is bound by the universal quantifier, but the variable x in Q(x) is not bound by the universal quantifier. Therefore the statement (∀x P(x)) ∧ Q(x) is not a proposition. In contrast, the universal quantifier in the statement ∀x (P(x) ∧ Q(x)) binds both occurrences of the variable x. Therefore ∀x (P(x) ∧ Q(x)) is a proposition.

In the following question, the domain of discourse is a set of students at a university. Define the following predicates: E(x): x is enrolled in the class T(x): x took the test Translate the following English statements into a logical expression with the same meaning.

All students enrolled in the class took the test. ∀x (E(x) → T(x)) 3.3.3: Translating quantified statements from English to logic.

S(x): x was sick yesterday W(x): x went to work yesterday V(x): x was on vacation yesterday Everyone who missed work was sick or on vacation (or both).

∀x (¬W(x) → (S(x) ∨ V(x))) 3.3.4: Translating quantified statements from English to logic.

S(x): x was sick yesterday W(x): x went to work yesterday V(x): x was on vacation yesterday Everyone besides Ingrid was sick yesterday. (Note that the statement does not indicate whether or not Ingrid herself was sick yesterday. Also, for this question, you will need the expression (x ≠ Ingrid).) ∀x ((x ≠ Ingrid) → S(x))

∀x ((x ≠ Ingrid) → S(x)) 3.3.4: Translating quantified statements from English to logic.

indicate whether the statement is a proposition. ∃x M(x) ∧ D(x)

Not a proposition.

In the following question, the domain of discourse is a set of male patients in a clinical study. Define the following predicates: P(x): x was given the placebo D(x): x was given the medication A(x): x had fainting spells M(x): x had migraines Suppose that there are five patients who participated in the study. The table below shows the names of the patients and the truth value for each patient and each predicate: P(x) D(x) A(x) M(x) Frodo T F F T Gandal F T F F Gimli F T T F Aragorn T F T T Bilbo T T F F For each of the following quantified statements, indicate whether the statement is a proposition. If the statement is a proposition, give its truth value and translate the expression into English. ∀x ((M(x) ∧ A(x)) → ¬D(x))

Proposition. True. Every patient who had migraines and fainting spells did not take the medication.

Exercise 3.4.5: Using De Morgan's law for quantified statements to prove logical equivalence. Use De Morgan's law for quantified statements and the laws of propositional logic to show the following equivalences: ¬∃x (¬P(x) ∨ (Q(x) ∧ ¬R(x))) ≡ ∀x (P(x) ∧ (¬Q(x) ∨ R(x)))

¬∃x (¬P(x) ∨ (Q(x) ∧ ¬R(x))) ≡ ∀x (P(x) ∧ (¬Q(x) ∨ R(x))) ¬∃x (¬P(x) ∨ (Q(x) ∧ ¬R(x))) ∀x ¬(¬P(x) ∨ (Q(x) ∧ ¬R(x))) De Morgan's law ∀x (¬¬P(x) ∧ ¬(Q(x) ∧ ¬R(x))) De Morgan's law ∀x (P(x) ∧ ¬(Q(x) ∧ ¬R(x))) Double negation law ∀x (P(x) ∧ (¬Q(x) ∨ ¬¬R(x))) De Morgan's law ∀x (P(x) ∧ (¬Q(x) ∨ R(x))) Double negation law

Indicate whether each of the logical expressions is a proposition. If so, indicate whether the proposition is true or false. M(1,1) M(x,2) ∀y M (x,y) ∃x M (x,3)

Proposition. True because the value in row 1 column 1 is True. Not a proposition, because the variable x is not bound by a quantifier such as ∀x or ∃x. Not a proposition, because the variable x is not bound by a quantifier such as ∀x or ∃x. Proposition. True for x=1 and x=2 because the values in row 1, column 3 and row 2, column are 3 T. The logical expression is a proposition if all the variables are bound.

Yes! Here’s a quick tip to determine whether something is a logical proposition: What Makes a Statement a Logical Proposition? A proposition in logic is a declarative statement that is either true or false, but not both. Trick to Identify One - If the statement can be evaluated as either true or false, then it is a logical proposition. - If it’s ambiguous, subjective, or lacks clear truth conditions, then it’s not a logical proposition. Checking Your Statements: 1️⃣ ∀x ∃y Q(x, y, z) ❗❗❗❗❗ - This says "For all ( x ), there exists some ( y ) such that ( Q(x, y, z) ) holds." - This can be evaluated logically (true or false), so it is a proposition. 2️⃣ ∃x ∃y M(x, y) - This means "There exists at least one ( x ) and one ( y ) such that ( M(x, y) ) is true." - This can also be logically determined, so it is a proposition. When is a Statement NOT a Proposition? - A question ("Is this true?") is not a proposition. - A command ("Go to the store!") is not a proposition. - A vague statement ("Maybe it’s sunny today.") lacks clear truth conditions, so it is not a proposition. 💡 Quick Tip: If you can put “This statement is true” or “This statement is false” next to it, and it still makes logical sense, it’s a proposition! Want to try testing some examples together?

∀x ∃y P(x, y) - x and y are both bound ∀x P(x, y) x is bound and y is free ∃y ∃z T(x,y,z) y and z are bound. x is free 3.5.1: Which logical expressions with nested quantifiers are propositions?

If the predicate is true after all the variables are set, then the quantified statement is true. If the predicate is false after all the variables are set, then the quantified statement is false. Consider as an example the following quantified statement in which the domain is the set of all integers: ∀x ∃y (x + y = 0)

The universal player first selects the value of x. Regardless of which value the universal player selects for x, the existential player can select y to be -x, which will cause the sum x + y to be 0. Because the existential player can always succeed in causing the predicate to be true, the statement ∀x ∃y (x + y = 0) is true.

∃x ∃y ((x+y = x) ∧ (y ≠ 0) False

The only way for x+y=x is if y=0 . Therefore, no two integers x and y exist such that x + y = x and y ≠ 0 . 3.5.2: Nested quantifiers of the same type.

∀x ∀y ( x^2 ≠ y^2 ∨ |x| - |y|)

True. If the first part is false for some and (i.e., x^2 - y^2 ), then |x| - |y| is true.

Exercise 3.6.1: De Morgan's law and nested quantifiers. Write the negation of each of the following logical expressions so that all negations immediately precede predicates. In some cases, it may be necessary to apply one or more laws of propositional logic. ∀x ∃y (P(x, y) ∧ Q(x, y))

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

∀x ∃y (P(x, y) ∧❗❗ ¬Q(x, y))

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

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

4.2 Lesson: Logical reasoning An argument is valid if

the conclusion is true whenever the hypotheses are all true

4.2 Lesson: Logical reasoning An argument invalid if

the conclusion is false for at least one case where all the hypotheses are true."

4.2 Lesson: Logical reasoning ¬Q P → Q --------- ∴ ¬P

(Valid) Argument form A: ¬Q → "I do not have an umbrella." P → Q → "If it is raining, then I have an umbrella." ∴ ¬P → "Therefore, it is not raining."

4.2 Lesson: Logical reasoning ¬P P → Q --------- ∴ ¬Q

¬P → "It is not raining." P → Q → "If it is raining, then I have an umbrella." ∴ ¬Q → "Therefore, I do not have an umbrella."

4.2 Lesson: Logical reasoning p ↔ q

"It is raining if and only if I have an umbrella."

4.2 Lesson: Logical reasoning p ↔ q p ∨ q ∴ p

Valid. The only row in which the hypotheses p ↔ q and p ∨ q are both true is the first row, and the conclusion p is true in the first row. p q p ↔ q p ∨ q T T T T T F F T F T F T F F T F "If I have an umbrella exactly when it rains, and either it is raining or I have an umbrella, then it must be raining."

Rules of inference with propositions p p → q --------- ∴ q

Modus ponens "Since rain means I carry an umbrella, and it's raining, I must have my umbrella."

Rules of inference with propositions ¬q p → q -------- ∴ ¬p

Modus tollens "If I always carry an umbrella when it rains, and I don’t have an umbrella, it must not be raining."

Rules of inference with propositions p -------- ∴ p ∨ q

Addition "Since it's raining, I can say either 'It is raining' or 'I have an umbrella.'"

Rules of inference with propositions p ∧ q -------- ∴ p

Simplification "If I have an umbrella and it's raining, then I can conclude that it's raining."

Rules of inference with propositions p q --------- ∴ p ∧ q

Conjunction 'It is raining and I have an umbrella.'"

Rules of inference with propositions p → q q → r ---------- ∴ p → r

Hypothetical syllogism "Rain means I carry an umbrella, and an umbrella means I wear boots. So rain means I wear boots."

Rules of inference with propositions p ∨ q ¬p -------- ∴ q

Disjunctive syllogism "Since I either have an umbrella or it’s raining, and it’s not raining, I must have an umbrella."

Rules of inference with propositions p ∨ q ¬p ∨ r ---------- ∴ q ∨ r

Resolution "Since I always either have an umbrella or it rains, and I also either wear boots or it's not raining, it follows that I must either have an umbrella or wear boots."

Validating arguments through logical proofs Verify that the following argument is valid. p ∧ (p→q) ∴q

Solution 1. p ∧ (p→q) Hypothesis 2. p Simplification, 1 3. p→q Simplification, 1 4. q Modus ponens, 2, 3

Rules of inference with propositions P (It is raining) Q (I have an umbrella) ∴ P ∨ Q (It is raining or I have an umbrella) P (It is raining) Q (I have an umbrella) ∴ P ∧ Q (It is raining and I have an umbrella)

Commutative Law for OR (∨) "It is raining or I have an umbrella" means the same as "I have an umbrella or it is raining." Commutative Law for AND (∧) "It is raining and I have an umbrella" means the same as "I have an umbrella and it is raining."

Why Use Rules of Inference?

Rules of inference allow us to logically deduce new statements based on given premises. They help ensure that arguments are logically valid by following structured reasoning patterns, such as Modus Ponens, Modus Tollens, and Hypothetical Syllogism.

Rules of Inference Hint and tips

True Statement -----Reason 1.) ----------------Hypothesis 2.) True because rules of inference 3.) True because rules of inference 4.) Etc 5.) Conclusion

Is It Like Working Backward in Algebra?

Yes, working backward in logical proofs can feel like verifying solutions in algebra. - In algebra, when you solve for ( x ), you might plug your answer back into the original equation to check if it holds. - In logic, proving validity often involves tracing the steps backward to ensure the conclusion follows logically from the premises.

Exercise 3.5.1: Which logical expressions with nested quantifiers are propositions? Indicate whether each of the logical expressions is a proposition. M (1,1)

Proposition.

Indicate whether each of the logical expressions is a proposition. ∀y M(x,y)

Not a proposition, because the variable is not bound by a quantifier such as ∀x or ∃x

Proposition or Not? ∃x M(x,3)

Proposition

Proposition or Not? ∃x ∃y M(x,y)

Proposition

Proposition or Not? M(x,2)

Not a Proposition Not a proposition, because the variable is not bound by a quantifier such as or .

∃x ∀x M(x,y)

Discrete Math Flashcards

(78 cards)