首页 >
> 详细

MATH1090 B Problem Set No1 September 2021

Department of EECS

MATH1090 B. Problem Set No1

Posted: Sept. 19, 2021

Due: Oct. 5, 2021, by 2:00pm; in eClass.

Q: How do I submit?

A:

(1) Submission must be ONLY ONE file

(2) Accepted File Types: PDF, RTF, MS WORD,

ZIP

(3) Deadline is strict, electronically limited.

(4) MAXIMUM file size = 10MB

It is worth remembering (from the course outline):

The homework must be each individual’s own work. While consultations

with the instructor, tutor, and among students, are part of the learning

process and are encouraged, nevertheless, at the end of all this consultation

each student will have to produce an individual report rather than a copy

(full or partial) of somebody else’s report.

The concept of “late assignments” does not exist in this course.

1. (3 MARKS) Prove that no wff can be λ.

Hint. Analyse formula-constructions, or use induction on formulas.

Page 1 G. Tourlakis

MATH1090 B Problem Set No1 September 2021

2. (3 MARKS) Prove that the complexity of a well-formed-formula equals

the number of its right brackets.

Hint. Analyse formula-constructions, or use induction on formulas.

3. (3 MARKS) Prove that (p) is not a wff.

Hint. One way is to analyse formula-constructions.

4. (1 MARK) Prove that ((¬(p → r)) ≡ (r → p)) is a wff.

5. (6 MARKS) Recall that a schema is a tautology iff all its instances are

tautologies.

Which of the following six schemata are tautologies? Show the whole

process that led to your answers, including truth tables or equivalent short

cuts, and words of explanation.

I note that in the six sub-questions below I am not using all the formally

necessary brackets.

Therefore be mindful of connective priorities and associativities!

• A → B → (A → ⊥) ∨ B

• A ≡ B → (A → ⊥) ∨ B

• (A ≡ B) → A ∧ B

• A → B → ¬B → ¬A

• (¬A) ∧ B ≡ A → B

• A ∨ B → A → B

6. (3 MARKS) Prove that if we have > |=taut A, then we also have B |=taut A

for any B.

7. (6 MARKS) By using truth tables, or using related shortcuts, examine

whether or not the following tautological implications are correct.

In order to show that a tautological implication that involves meta-variables

for formulas —i.e., it is a schema— is incorrect you must consider a special

case that is incorrect (since some other special cases might work).

Page 2 G. Tourlakis

MATH1090 B Problem Set No1 September 2021

Show the whole process that led to each of your answers.

• p ∧ ¬p |=taut ⊥

• p ∨ q ∧ r → r

00 |=taut >

• p |=taut p ∨ B

• A, A → B |=taut B

• A ≡ B |=taut A ∧ B

• A ∧ B |=taut A ≡ B

8. (6 MARKS) Write down the most simplified result of the following substitutions,

whenever the requested substitution makes sense. Whenever a

requested substitution does not make sense, explain exactly why it does

not.

Show the whole process that led to each of your answers in each case.

Remember the priorities of the various connectives as well as that of

the meta-expression “[p := . . .]”! The following formulas have not been

written with all the formally required brackets.

• (q → p)[q := r]

• (q → p)[r := r

00]

• p → >[p := ⊥]

• p → >[p := f]

• (⊥ → r → q)[⊥ := p]

• p ∨ (q ∧ r)[p := r]

Page 3 G. Tourlakis

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23