Other

COS1501 assignments with solutions, study guide with solutions, extra questions with solutions

0 purchase

Course
Theoretical Computer Science I (COS1501)

Institution
University Of South Africa (Unisa)

COS1501 study guide with self-assessment solutions. Assignments with solutions. Extra questions and solutions.

[Show more]

Last document update: 1 year ago

Preview 4 out of 419 pages

View example

Uploaded on October 18, 2023
File latest updated on October 18, 2023
Number of pages 419
Written in 2020/2021
Type Other
Person Unknown

cos1501 questions with solutions

Introduction COS1501/1

THEORETICAL COMPUTER SCIENCE 1

ONLY STUDY GUIDE FOR

COS1501

Author
T HÖRNE

Co-author
D BECKER

Critical reader
A E DU PREEZ

Editor
Carina Potgieter

Graphic designer
Ella Viljoen

Photographs
IlzeBotha (082 772 2482)
Shutterstock

SCHOOL OF COMPUTING
UNIVERSITY OF SOUTH AFRICA
PRETORIA

i

,Introduction COS1501/1

© 2013 University of South Africa

All rights reserved

COS1501/1/2014-2020

ACKNOWLEDGEMENTS

In previous years many lecturers played a role in the development of the COS1501
(previously COS101S) study material. Our sincere thanks go to Willem Labuschagne,
Martha Pistorius, Biffie Viljoen, Ruth de Villiers and Louise Leenen – some of whom
are no longer lecturers in the School of Computing. We also thank Jeanetta du Preez
for creating the mind map in study unit 1, the diagram for the worked example in
section 1.2.2, and figures 5.1, 5.2 and 5.3 in study unit 5.

This study guide for COS1501 was reviewed and approved by the following team:

ROLE NAME
Director, School of Computing Sheryl Buckley
Educational advice Hentie Wilson
Chair of Committee Hentie Wilson
Academic field specialists Sihem Belabbes
Biffie Viljoen (study units 9 and 10)
Layout format Hentie Wilson
Page layout School of Computing
Printed and published by the University of South Africa, Muckleneuk, Pretoria

ii

,Introduction COS1501/1

CONTENTS

Introduction v
1. What is Discrete Mathematics? v
2. The purpose of the module vi
3. Outcomes of the module vi
4. Syllabus vi
5. How to study this module vii
6. Acknowledgements xiv

Glossary of symbols xv

Study unit 1 The development of numbers systems: Z+, Z≥ and Z 1
1.1 Introduction to the study unit 1
1.2 Positive integers: Z+ 3
1.2.1 Commutative property 4
1.2.2 Associative property 5
1.2.3 Distributive property 6
1.2.4 Multiplicative identity 7
1.3 Non-negative integers: Z≥ 7
1.3.1 The existence of an additive identity 10
1.3.2 Multiplication by zero 10
1.4 Integers: Z 11
1.5 The additive inverse, absolute values and prime numbers 15
1.6 The nine laws for Z≥ 19
1.7 In summary of the study unit 20

Study unit 2 Rational and real numbers: Q and R 21
2.1 Introduction to this study unit 21
2.2 The rational numbers: Q 22
2.3 The 11th law of Q 25
2.4 The real numbers: R 25
2.5 In summary of the study unit 31

Study unit 3 Sets 33
3.1 Introduction to this study unit 33
3.2 Why do set theory? 34
3.3 How do we talk about sets? 34
3.4 How to build new sets from old ones 39
3.5 In summary of the study unit 46

Study unit 4 Proofs involving sets 47
4.1 Venn diagrams 48
4.2 Proofs 53
4.3 Working with (X ∩ Y)ʹand (X ∪ Y)ʹ 57
4.4 The Inclusion-exclusion principle 63
4.5 Proofs on specific sets 67
4.6 In summary of the study unit 68

iii

, Introduction COS1501/1

Study unit 5 Relations 69
5.1 Ordered pairs 70
5.2 Relations 71
5.3 Properties of relations 75
5.4 In summary of the study unit 82

Study unit 6 Special kinds of relation 83
6.1 Order relations 84
6.2 Some comments on proof strategies 89
6.3 Equivalence relations 90
6.4 n-ary relations 96
6.5 Functions 98
6.6 In summary of the study unit 102

Study unit 7 More about functions 103
7.1 Surjective functions 104
7.2 Injective functions 106
7.3 The composition of relations / functions 108
7.4 Bijective functions and inverses 112
7.5 In summary of the study unit 114

Study unit 8 Operations 115
8.1 Binary operations 116
8.2 The properties of binary operations. 119
8.3 Operations on vectors 122
8.4 Operations on matrices 125
8.5 In summary of the study unit 133

Study unit 9 Logic: Truth tables 135
9.1 Statements and connectives 136
9.2 Relationships between statements 145
9.3 In summary of the study unit 149

Study unit 10 Logic: quantifiers, predicates, and proof strategies 151
10.1 Quantifiers and predicates 152
10.2 Proof strategies 159
10.2.1 Direct proof 159
10.2.2 Proof by contradiction (reductio ad absurdum) 160
10.2.3 Proof by contrapositive 160
10.2.4 Proofs involving quantifiers 162
10.2.5 Vacuous proof 164
10.3 In summary of the study unit 165

Appendix A: Index
Appendix B: Bibliography

iv

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying this summary from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller PotatoArmor. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy this summary for R65,00. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

66184 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy summaries for 15 years now

Start selling

Seller

Summary ·