X


Constructing New Logical Equivalences






Q. Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences.



Show that (p ∧ q) → (p ∨ q) is a tautology.






Propositional Satisfiability




Q. Determine whether each of the compound propositions (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p), (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r), and (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is satisfiable.






Predicates and Quantifiers




Q. Let P(x) denote the statement “x>3.” What are the truth values of P(4) and P(2)?



Q. Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)?



Q. Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Q(1, 2) and Q(3, 0)?






Quantifiers




THE UNIVERSAL QUANTIFIER





THE EXISTENTIAL QUANTIFIER



Quantifiers.


Statement When True? When False?
∀ x P(x) P(x) is true for every x. There is an x for which P(x) is false.
∃ x P(x) There is an x for which P(x) is true. P(x) is false for every x



Q. Let P(x) be the statement “x + 1 > x.” What is the truth value of the quantification ∀xP(x), where the domain consists of all real numbers?



Q. Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀ x Q(x), where the domain consists of all real numbers?



Q. What is the truth value of ∀xP(x), where P(x) is the statement “x2 < 10” and the domain consists of the positive integers not exceeding 4?





Q. Let P(x) denote the statement “x>3.” What is the truth value of the quantification ∃xP(x), where the domain consists of all real numbers?



Q. Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification ∃xQ(x), where the domain consists of all real numbers?



Precedence of Quantifiers





De Morgan’s laws for quantifiers : Rules for negations for quantifiers



Q. Every student in your class has taken a course in calculus. The negation of this statement is



Q. There is a student in this class who has taken a course in calculus. The negation of this statement is the proposition :





Q. What are the negations of the statements “There is an honest politician” and “All Americans eat cheeseburgers”?



Q. What are the negations of the statements ∀x(x2 > x) and ∃x(x2 = x)is the statement?





Nested Quantifiers and their Meaning


Previous Next