University Prof. and Prof. CS 330 Homework 4: Predicate Logic and Proofs with Predicates
Homework 4: Predicate Logic and Proofs with Predicates Submission policy. Submit your answers by 7pm on Friday, Feb. 25, 2022. No late submissions
accepted. Your submission MUST include the following:
1. A pdf file named as LastnameHW4.pdf with your answer to the required question. Hand written answers are fine but please make sure they are readable.
Copyright By PowCoder代写 加微信 powcoder
2. Your name should be printed at the very top of the document.
Administration. This assignment will be graded by .
Practice Questions – Do NOT submit those.
Textbook questions 4.8, 4.9, 4.11, 5.2, 5.3
Question that will be graded. Total Points 100
Exercise 1. Part (a) [42 points]. Let A and B each be sequences of letters: A = (a1,a2,…,an) and B = (b1,b2,…,bn). Let In be the set of integers: {1,2,…,n}. Make a formal assertion for each of thefollowingsituations,usingquantifierswithrespecttoIn. Forexample,∀i∈In :∀j∈In :ai =aj asserts that all letters in A are identical. You may use the relational operators “=”, “̸=”, and “≺”, as well as our usual operators: “∨”, “∧”. (≺ is “less than” for English letters: c ≺ d is true, and c ≺ c is false.) You may not apply any operators to A and B. For example: A = B is not allowed, and A ⊂ B is not allowed. (In any case, A and B are sequences, not sets. While we could define “⊂” to apply to sequences in a natural way, this defeats the purpose of the exercise.) Use some care! Some of these are not as simple as they first seem.
(a) Some letter appears at least twice in A.
(b) No letter appears more than once in A.
(c) A and B are identical: the same sequence of characters.
(d) The set of letters appearing in B is a subset of the set of letters appearing in A. (e) The letters of A are lexicographically sorted.
(f) The letters of A are not lexicographically sorted. (Do this without using ¬.)
Part (b) [58 points]. Formally prove via mathematical induction that
∀n ∈ N : ∑i2 = n(n+1)(2n+1)/6
Your proof needs to follow the inferences rules for predicate logic. You need to start by following
the template/framework for induction we saw in class.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com