Discrete Mathematics: Propositions & Logic

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What logical expression correctly represents that getting an A on the final and doing every exercise is sufficient for getting an A in the class?

(p ∧ q) → r (correct)

r → (p ∧ q)

(p ∨ q) → r

(p ∧ q) ↔ r

Which of the following propositions states that getting an A in this class is necessary if you get an A on the final exam?

q → p (correct)

p → q

¬p → ¬q

q ↔ p

Which logical implication is false?

If 2 + 3 = 6, then God exists. (correct)

If 2 + 3 = 5, then pigs can fly.

If 2 + 3 = 4, then 3 + 3 = 5.

If pigs can fly, then 1 + 3 = 5.

What is the expression that indicates that it is not snowing if it is below freezing?

p → ¬q Signup and view all the answers

Which logical statement represents that if it is snowing, then it must be below freezing?

q → p Signup and view all the answers

Which of the following correctly expresses that you don't get an A in class unless you get an A on the final?

¬p → ¬q Signup and view all the answers

If both propositions p and q are true, what can be concluded about p ∧ q?

It is true. Signup and view all the answers

What does the expression (p ∧ q) ↔ r imply?

p and q together lead to r, and r implies p and q. Signup and view all the answers

Which of these expresses the proposition (𝑝𝑝 ∨ 𝑞𝑞) ∧ (𝑝𝑝 → ¬𝑞𝑞) as an English sentence?

It is either below freezing or it is snowing, but it is not snowing if it is below freezing. Signup and view all the answers

What English sentence represents the proposition ¬𝑝𝑝 ↔ 𝑞𝑞?

If you don’t miss the final examination then you pass the course, and conversely. Signup and view all the answers

What is necessary for a compound proposition to be classified as a tautology?

It is always true, no matter what the truth values of the propositions that occur in it. Signup and view all the answers

Which condition signifies that the propositions p and q are logically equivalent?

They must always produce the same truth values regardless of their input. Signup and view all the answers

Identify the expression that represents a tautology.

(𝑝𝑝 → 𝑞𝑞) ↔ (¬𝑞𝑞 → 𝑝𝑝) Signup and view all the answers

What is the union of sets A and B?

The set containing elements that are in A, B, or both Signup and view all the answers

Which statement accurately describes the intersection of sets A and B?

It includes elements that are in both A and B. Signup and view all the answers

Which of the following statements correctly describes the conditions of a contradiction?

It is always false, no matter what the truth values of the propositions that occur in it. Signup and view all the answers

Which option represents a distributive law in logic?

𝑝𝑝 ∧ (𝑞𝑞 ∨ 𝑟𝑟) = (𝑝𝑝 ∧ 𝑞𝑞) ∨ (𝑝𝑝 ∧ 𝑟𝑟) Signup and view all the answers

What is the complement of set A when U = {1, 2, 3, 4, 5, 6, 7, 8} and A = {1, 3, 4, 5, 8}?

{2, 6, 7} Signup and view all the answers

In the context of functions, what is the codomain of a function f from set A to set B?

The set B Signup and view all the answers

What is the codomain of a function that assigns the first three bits of a bit string of length 3 or greater?

The set {000, 001, 010, 100, 011, 101, 110, 111} Signup and view all the answers

For sets A and B, given the mapping of function f, what is the image of set S = {c, d, e, g}?

{2, 0, 5, 1} Signup and view all the answers

Which of these describes the relationship between the elements within set A = {1, 3, 4, 5, 8} and the elements in the universal set U = {1, 2, 3, 4, 5, 6, 7, 8}?

Elements in A are a subset of U. Signup and view all the answers

Identify the incorrect statement regarding the function f based on the provided outputs of A to B.

f(e) = 4 Signup and view all the answers

Which logical expression best represents the statement that there is a student at the university who can speak Kazakh but does not know Delphi?

∃x(P(x) ∧ ¬Q(x)) Signup and view all the answers

Which statement is true regarding the integers and the relation S(x, y) defined as x + y = x · y?

∀x∃yS(x, y) Signup and view all the answers

What is the correct logical representation of the statement encapsulating x + 3y = 3x – y for all integers?

∀y∃xS(x, y) Signup and view all the answers

Which expression correctly rewrites ¬∃y∀xS(x, y) so that negations are only within predicates?

∃y∀x¬P(x, y) Signup and view all the answers

Which of the following statements is true if the universe of discourse is the set of all integers?

∀n(n^2 ≥ 1) Signup and view all the answers

Which statement is true if the universe of discourse for each variable is the set of real numbers?

∃x(x^2 = 8) Signup and view all the answers

When is the statement ∀y∃xS(x, y) considered false?

There is a y such that P(x, y) is false for every x. Signup and view all the answers

What must be true for the statement ∃y∀xS(x, y) to be valid?

There is a y such that P(x, y) is true for every x. Signup and view all the answers

Which of the following correctly represents the quantifiers and logical connectives for the statement "for every y, there exists an x such that x > 0"?

∀y∃x(x > 0) Signup and view all the answers

What is the logical equivalence of the proposition $p \to q$?

¬$p$ ∨ $q$ Signup and view all the answers

Which statement correctly describes a contingency?

It is neither a tautology nor a contradiction. Signup and view all the answers

Identify the compound proposition that is true when $p$ and $q$ are false and $r$ is true.

¬$p$ ∧ ¬$q$ ∧ $r$ Signup and view all the answers

What is the compound proposition that is false when $p$ is false and $q$ and $r$ are true?

$p$ → ¬($q$ ∧ $r$) Signup and view all the answers

Which compound proposition is true when $p$ and $q$ are true and $r$ is false?

$p$ ∧ $q$ ∧ ¬$r$ Signup and view all the answers

Express the proposition $∃x¬P(x)$ in English where $P(x)$ means 'x spends less than three hours every weekday in class'.

There is a student who spends no less than three hours every weekday in class. Signup and view all the answers

What does the proposition $∃y∀xP(x, y)$ state given $P(x, y)$ means 'x has taken y'?

There is a computer course at your school taken by all students in your class. Signup and view all the answers

Which proposition logically represents ¬($p$ ∧ $q$)?

¬$p$ ∨ ¬$q$ Signup and view all the answers

What proposition holds when $p$ is true and $q$ is false?

$p$ ∧ ¬$q$ Signup and view all the answers

Which expression is a tautology?

$p$ ∨ ¬$p$ Signup and view all the answers

What defines an injective function?

f(x) ≠ f(y) implies that x ≠ y for all x and y Signup and view all the answers

Which statement is true about a surjective function?

For every b ∈ B, there is an a ∈ A with f(a) = b Signup and view all the answers

What is required for a function to be considered a bijection?

It is both one-to-one and onto Signup and view all the answers

What is the composition of the functions f(x) = 3x - 4 and g(x) = 4x - 3?

12x - 19 Signup and view all the answers

What is the range of the function that assigns the first digit to each positive integer?

{1, 2, 3, 4, 5, 6, 7, 8, 9} Signup and view all the answers

Which of the following functions from {a, b, c, d} to itself is one-to-one?

f(a) = d, f(b) = c, f(c) = b, f(d) = a Signup and view all the answers

Evaluate the expression ↱– 22, 333 ↰.

-3 Signup and view all the answers

Evaluate the expression ↱ 11/11 + ↳ 99/111 ↲.

9/10 Signup and view all the answers

Study Notes

Proposition

A proposition is a declarative sentence that is either true or false.
Examples of propositions include: 3 + 2 = 6, Take this pencil, Can you help me? are not propositions. x + 2 = 6, and Why should you study discrete mathematics? are not propositions.

Negation

The negation of a proposition p, denoted by ¬p, is the proposition that is true when p is false, and false when p is true.

Conjunction

The conjunction of two propositions p and q, denoted by p ∧ q, is the proposition that is true when both p and q are true, and is false otherwise.

Disjunction

The disjunction of two propositions p and q, denoted by p ∨ q, is the proposition that is true when at least one of p and q is true, and is false otherwise.

Conditional

The conditional of p and q, denoted by p → q, is the proposition that is false when p is true and q is false, and is true otherwise.

Biconditional

The biconditional of p and q, denoted by p ↔ q, is the proposition that is true when p and q have the same truth value, and is false otherwise.

Converse

The converse of p → q is q → p

Contrapositive

The contrapositive of p → q is ¬q → ¬p

Bitwise Operations

Bitwise AND: True if both bits are 1, False otherwise
Bitwise OR: True if at least one bit is 1, False otherwise
Bitwise XOR: True if the bits are different, False otherwise

Truth Table

A truth table systematically lists all possible truth values for the propositions in the statement and the corresponding truth value for the compound statement.

Tautology

A compound proposition that is always true, regardless of the truth values of its components.

Contradiction

A compound proposition that is always false, regardless of the truth values of its components.

Contingency

A compound proposition that is neither a tautology nor a contradiction.

Logical Equivalence

Two propositions are logically equivalent if they have the same truth value for all possible combinations of truth values of their simple propositions.

Quantifiers

Universal quantifier (∀): ∀x P(x) states that P(x) is true for every x in a given set.
Existential quantifier (∃): ∃x P(x) states that P(x) is true for at least one x in a given set.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

This quiz covers key concepts of propositions in discrete mathematics, including negation, conjunction, disjunction, conditional, and biconditional statements. Test your understanding of the truth values and logical relationships between different propositions.