CIS 607: Mathematical Basis for Computing
SOLUTIONS OF HOMEWORK 1
Homework 1 -- Propositional Logic, Predicate Logic and Proofs
Due Date: February 14, 2017
怎么戒酒最快最好In this homework, you will answer the following questions. Prepare a pdf file for your solutions and upload that pdf file into the blackboard system.
Q1)
Let p and q be the propositions
p : I bought a lottery ticket this week.
q : I won the million dollar jackpot.
Express each of the propositions as an English ntence.
∙p →q
o If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
∙￢p ∨(p ∧q)
o Either I did not buy a lottery ticket this week, or el I did buy one and won the million dollar jackpot on Friday.
∙￢p →￢q
o If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.
Q2)学业
Let p and q be the propositions
p : It is below freezing.
q : It is snowing.
Write the propositions using p and q and logical connectives (including negations).
∙It is not below freezing and it is not snowing.
o(￢p ∧￢q)
名利场
∙If it is below freezing, it is also snowing.
o p →q
∙Either it is below freezing or it is snowing, but it is not snowing if it is below freezing.
o(p ∨ q) ∧ ( p →￢q)
Q3)
Construct a truth table for each of the compound propositions.
∙p →(￢q ∨r)
∙(p →q) ∧(￢p →r)
∙(￢p ↔￢q) ↔(q ↔r)
∙Show that ￢(p ↔q) and p ↔￢q are logically equivalent.
o p q ￢(p ↔q) p ↔￢q
o T T F F
o T F T T
o F T T T
o F F F F
∙Show that (p →q) →r and p →(q →r) are not logically equivalent.
o p q r (p →q) →r p →(q →r)
o F F F F T
Q5)
Determine the truth value of each of the statements if the domain consists of all integers.
∙∀n(n + 1 > n)
o T
∙∃n(2n = 3n)
o T (when n=0)
∙∃n(n = −n)
o T (when n=0)
钢筋骨架∙∀n(3n ≤4n)
o F (when n is a negative integer)
Q6)
Suppo that the domain of the propositional function P(x) consists of the integers 1, 2, and 3. Write out each of the propositions using disjunctions, conjunctions, and negations.
∙∃xP(x)
o P(1) ∨P(2) ∨P(3)
∙∀xP(x)
o P(1) ∧P(2) ∧P(3)
∙￢∃xP(x)
o￢ (P(1) ∨P(2) ∨P(3))
∙￢∀xP(x)
o￢ (P(1) ∧P(2) ∧P(3))
Express the negations of each of the statements so that all negation symbols immediately precede predicates.
∙∀x∃y∀zT (x, y, z)
o∃x∀y∃z￢T (x, y, z)
∙∀x∃yP(x, y) ∨∀x∃yQ(x, y)
o∃x∀y￢P(x, y) ∧∃x∀y￢Q(x, y)
∙∀x∃y(P(x, y) ∧∃zR(x, y, z))
o∃x∀y(￢P(x, y) ∨∀z￢R(x, y, z))
∙∀x∃y(P(x, y) →Q(x, y))
o∃x∀y(P(x, y) ∧￢Q(x, y))
Q8)
∙Determine whether ∀x(P(x) →Q(x)) and ∀xP(x) →∀xQ(x) are logically equivalent. Justify your answer.
白茶的主要功效o NOT
如何缓解工作压力o P: is even number, Q: is odd number
o∀x P(x) →∀xQ(x) is true since ∀xP(x) is fal and ∀xQ(x) is fal
o But ∀x(P(x) →Q(x)) is fal
∙Determine whether ∀x(P(x) ↔Q(x)) and ∀x P(x) ↔∀xQ(x) are logically equivalent. Justify your answer.
o NOT
o P: is even number, Q: is odd number
o∀x P(x) ↔∀xQ(x) is true since ∀xP(x) is fal and ∀xQ(x) is fal
o But ∀x(P(x) ↔Q(x)) is fal
∙Show that ∃x(P(x) ∨Q(x)) and ∃xP(x) ∨∃xQ(x) are logically equivalent.
o if ∃x(P(x) ∨Q(x)) is true
o P(a) ∨Q(a) is true for a constant ‘a’ (∃-inst)
o If P(a) is true →∃xP(x)is true →∃xP(x) ∨∃xQ(x) is true
o If Q(a) is true →∃xQ(x)is true →∃xP(x) ∨∃xQ(x) is true
o
o if ∃x(P(x) ∨Q(x)) is fal
o→ there is no constant such that P(a) ∨Q(a) is true
o→ there is no constant such that P(a) is true or there is no constant such that Q(a) is true
o→∃xP(x) is fal and ∃xQ(x) is fal
o→∃xP(x) ∨∃xQ(x) is fal
Q9)
∙U rules of inference to show that if ∀x(P(x) →(Q(x) ∧S(x))) and ∀x(P(x) ∧R(x)) are true, then ∀x(R(x) ∧S(x)) is true.
Step Reason
1.∀x(P(x) → (Q(x) ∧ S(x))) Premi
2.∀x(P(x) ∧ R(x)) Premi
摄影入门教程3.P(a) ∧ R(a) for arbitrary a UI from 2
4.P(a) for arbitrary a Simplification from 3
5.R(a) for arbitrary a Simplification from 3
临江仙滚滚长江东逝水
6.P(a) → (Q(a) ∧ S(a))) for arbitrary a UI from 1
7.(Q(a) ∧ S(a)) for arbitrary a MP from 4 and 6
8.S(a) for arbitrary a Simplification from 7
9.R(a) ∧ S(a) for arbitrary a Conjunction from 5 and 8
10.∀x(R(x) ∧ S(x)) UG from 9
∙U rules of inference to show that if ∀x(P(x) ∨Q(x)), ∀x(￢Q(x) ∨S(x)), ∀x(R(x)→￢S(x)), and ∃x￢P(x) are true, then ∃x￢R(x) is true.
Step Reason
1.∀x(P(x) ∨ Q(x)) Premi
2.∀x(￢Q(x) ∨ S(x)) Premi
3.∀x(R(x) →￢S(x)) Premi
4.∃x￢P(x) Premi
5.￢P(a) for some a EI from 4
6.P(a) ∨ Q(a) UI from 1
7.Q(a) for some a Disjunctive Syllogism from 5 and 6
8.￢Q(a) ∨ S(a) UI from 2
9.S(a) for some a Disjunctive Syllogism from 7 and 8
10.R(a) →￢S(a) UI from 3
11.￢R(a) for some a Modes Tollens from 9 and 10
12.∃x￢R(x) Existential Generalization (EG) from 11
Q10)
∙U a direct proof to show that every odd integer is the difference of two squares.
Direct Proof
o Let n be an odd integer such that n=2k+1 where k is an integer (definition of odd integers) o Let squares of two integers k and (k+1) such as k2 and (k+1)2= k2+2k+1
o(k+1)2 - k2 = 2k+1
o So, n is the difference of two squares.
o QED
∙Show that if n is an integer and n3+ 5 is odd, then n is even using a proof by contraposition.
Proof by Contraposition
o Assume n is an odd integer (negation of even is odd)
o So, n=2k+1 where k is an integer (definition of odd integers)
o n3 + 5 = (2k+1)3 + 5 = 8k3+12k2 +6k+1+5 = 2(4k3+6k2 +3k+3)
o So, n3 + 5 = 2m where m is an integer such that m = (4k3+6k2 +3k+3)
o Thus, n3 + 5 is an even integer (negation of “n3 + 5 is odd”)
o Then, n is even (not odd)
o QED.
∙Prove that if n is an integer and 3n + 2 is even, then n is even using a proof by contradiction.
Proof by Contradiction
o Assume that n is an odd integer (negation of even is odd)
o So, n=2k+1 where k is an integer (definition of odd integers)
o3n+2 = 3(2k+1)+2 = 6k+5 = 2(3k+2)+1
o So, 3n+2 = 2m+1 where m is an integer such that m=3k+2
o Thus, 3n+2 is odd (contradiction with our assumption “3n + 2 is even”)
o So, n is even
o QED.
