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.
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”
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.
Help your friend fifind the problem in their argument by pointing out which step(s) were incorrect.
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.
3 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.
4 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.
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.
Use a counterexample to prove that the statement
∀x( E(x) → L(x) )
is false.
Use a witness to prove that the statement
∃x( E(x) ∧ M(x) )
is true.
Translate each of the statements in the previous two parts to English.
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.
FA with domain S is defifined recursively by:
Basis step: FA(A) = T, FA(C) = FA(G) = FA(U) = F
Recursive step: If s ∈ S and b ∈ B, then FA(sb) = FA(s)
PAUC 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+,
CSE20W21代写
Mut with domain S × S is defifined by, for s1 ∈ S and s2 ∈ S,
Mut(s1, s2) = ∃k ∈ Z+∃b ∈ B( mutation(s1, k, b) = s2 )
Ins with domain S × S is defifined by, for s1 ∈ S and s2 ∈ S,
Ins(s1, s2) = ∃k ∈ Z+∃b ∈ B( insertion(s1, k, b) = s2 )
Del with domain S × S is defifined by, for s1 ∈ S and s2 ∈ S,
Del(s1, s2) = ∃k ∈ Z+( deletion(s1, k) = s2 )
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) ∧ FA(s) ∧ ¬PAUC(s) )
Hint: the sample response in Question 2 might give some helpful guidance on organizing your explanation.
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?
______________________________
Consider the statement
∃n ∈ Z+ ∀s ∈ S ( L(s, n) → (PAUC(s) → FA(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.