CSE20W21代写 assignment代写 HW代写

HW4 Propositional and Predicate Logic

CSE20W21

CSE20W21代写 HW4 Propositional and Predicate Logic In this assignment, You will use propositional and predicate logic to evaluate statements and arguments.

In this assignment, You will use propositional and predicate logic to evaluate statements and arguments.

 

1.  CSE20W21代写

Imagine a friend suggests the following argument to you: “The compound proposition

(x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)

is logically equivalent to

(x ∧ y) ∨ z

because I can transform one to the other using the following sequence of logical equivalences like distributivity and associativity:

(x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) ≡ ( x ∧ (y ∨ z) ) ∨ (y ∧ z) ≡ ( x ∧ (y ∧ z) ) ∧ (y ∨ z) ≡ ( x ∧ y ) ∨ z”

 

(a) (Graded for correctness³ )  CSE20W21代写

Prove to your friend that they made a mistake by giving a truth assignment to the propositional variables where the two compound propositions (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) and (x ∧ y) ∨ z have difffferent truth values. Justify your choice by evaluating these compound propositions using the defifinitions of the logical connectives and include enough intermediate steps so that a student in CSE 20 who may be struggling with the material can still follow along with your reasoning.

 

(b) (Graded for fair effffort completeness⁴ )

Help your friend fifind the problem in their argument by  pointing out which step(s) were incorrect.

 

(c) (Graded for fair effffort completeness)

Give three difffferent compound propositions that are actu-ally logically equivalent to (and not the same as)

(x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)

Justify each one of these logically equivalences either by applying a sequence of logical equiva-lences or using a truth table.

---

³ This means your solution will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.

⁴ This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers.

---

 

2.  CSE20W21代写

Consider the following predicates, each of which has as its domain the set of all bitstrings whose leftmost bit is 1

E(x) is T exactly when (x)₂ is even, and is F otherwise

L(x) is T exactly when (x)₂ < 3, and is F otherwise

M(x) is T exactly when (x)₂ > 256 and is F otherwise.

Sample response that can be used as reference for the detail expected in your answer: To prove that the statement

∀x L(x)

is false, we can use the counterexample x = 111, which is a bitstring whose leftmost bit is 1 (so is in the domain). Applying the defifinition of L(x), since (111)₂ = 1 · 2² + 1 · 2¹ + 1 · 2⁰ = 4 + 2 + 1 = 7 which is greater than 3, we have that L(111) = F and so the universal statement is false.

 

(a) (Graded for correctness)  CSE20W21代写

Use a counterexample to prove that the statement

∀x( E(x) → L(x) )

is false.

 

(b) (Graded for correctness)

Use a witness to prove that the statement

∃x( E(x) ∧ M(x) )

is true.

 

(c) (Graded for fair effffort completeness)

Translate each of the statements in the previous two parts to English.

 

3.  CSE20W21代写

Recall that S is defifined as the set of all RNA strands, nonempty strings made of the bases in B = {A, U, G, C}. Defifine the functions mutation, insertion, and deletion as described by the pseudocode below:

 

 

For this question, we will use the following predicates.

F_A with domain S is defifined recursively by:

Basis step: F_A(A) = T, F_A(C) = F_A(G) = F_A(U) = F

Recursive step: If s ∈ S and b ∈ B, then F_A(sb) = F_A(s)

P_AUC with domain S is defifined as the predicate whose truth set is the collection of RNA strands where the string AUC is a substring (appears inside s, in order and consecutively)

L with domain S × Z⁺ is defifined by, for s ∈ S and n ∈ Z⁺,

 

 

Mut with domain S × S is defifined by, for s₁ ∈ S and s₂ ∈ S,

Mut(s₁, s₂) = ∃k ∈ Z⁺∃b ∈ B( mutation(s₁, k, b) = s₂ )

Ins with domain S × S is defifined by, for s₁ ∈ S and s₂ ∈ S,

Ins(s₁, s₂) = ∃k ∈ Z⁺∃b ∈ B( insertion(s₁, k, b) = s₂ )

Del with domain S × S is defifined by, for s₁ ∈ S and s₂ ∈ S,

Del(s₁, s₂) = ∃k ∈ Z⁺( deletion(s₁, k) = s₂ )

 

(a) (Graded for correctness)

Use a witness to prove the following existential quantifification. Explain why your witness is in the appropriate domain and show the intermediate calculations and defifinitions needed to evaluate the predicate at this witness element.

∃_s ∈ S ( L(s, 3) ∧ F_A(s) ∧ ¬P_AUC(s) )

Hint: the sample response in Question 2 might give some helpful guidance on organizing your explanation.

 

(b)  CSE20W21代写

For each quantifified statement below, fifirst translate to an English sentence. Then, negate the whole statement and rewrite this negated statement so that negations appear only within predicates (that is, so that no negation is outside a quantififier or an expression involving logical connectives).

The translations are graded for fair effffort completeness.

The negations are graded for correctness. For negations: You do not need to justify your work for this part of the question. However, if you include correct intermediate steps, we might be able to award partial credit for an incorrect answer.

Bonus; not for credit (do not hand in): Is the statement or its negation true? How do you know?

______________________________

 

Sample response that can be used as reference for the detail expected in your answer:

Consider the statement

∃n ∈ Z⁺ ∀_s ∈ S ( L(s, n) → (P_AUC(s) → F_A(s) ) )

Solution: English translation is There is a positive integer such that all RNA strands of that length have the property that if they contain AUC as a substring, they must start with A.

We obtain the negation using multiple applications of DeMorgan’s rule and logical equivalences.

¬∃_n ∈ Z⁺∀_s ∈ S ( L(s, n) → (P_AUC(s) → F_A(s) ) )

≡∀_n ∈ Z⁺∃_s ∈ S ¬ ( L(s, n) → (P_AUC(s) → F_A(s) ) )

≡∀_n∈ Z⁺∃_s ∈ S ( L(s, n) ∧ ¬(P_AUC(s) → F_A(s) ) )

≡∀_n ∈ Z⁺∃_s ∈ S ( L(s, n) ∧ P_AUC(s) ∧ ¬F_A(s) )

i. First statement:

∀_s1∈ S ∃_s2∈ S ( Mut(s₁, s₂) ∧ F_A(s₂) )

ii. Second statement

∀_s1 ∈ S ∀_s2 ∈ S ( Ins(s₁, s₂) → Del(s₂, s1) )

iii.Third statement

∀_n ∈ Z⁺∃_s ∈ S ( L(s, n) ∧ Mut(s, s) ∧ Del(s, s) )

 

 

其他代写：homework代写 assignment代写 code代写 report代写 data代写 paper代写 作业加急 北美代写 CS代写  澳大利亚代写 essay代写 加拿大代写 英国代写 作业代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写