COS1501/102/0/2022
Tutorial letter 102/0/2022
Theoretical Computer Science 1
COS1501
Semesters 1 and 2
School of Computing
CONTENTS:
1. TUTORIAL MATTER & CAI TUTORIAL
2. DISCUSSION OF SELF-ASSESSMENT QUESTIONS FOR
ASSIGNMENT 02
3. DISCUSSION OF SELF-ASSESSMENT QUESTIONS FOR
ASSIGNMENT 03
4. EXTRA QUESTIONS & SOLUTIONS
5. EXTRA QUESTIONS & SOLUTIONS similar
to QUESTIONS IN ASSIGNMENTS 01, 02 AND 03
, CONTENTS
1 TUTORIAL MATTER & CAI TUTORIAL ................................................................................................................. 3
2 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENT 02 ........................................................... 4
2.1 Assignment 02 Section 1 ............................................................................................................................................................. 4
2.2 Assignment 02 Section 2 ...........................................................................................................................................................12
3 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENTS 03 ...................................................... 20
3.1 Assignment 03 Section A...........................................................................................................................................................20
3.2 Assignment 03 Section B...........................................................................................................................................................28
3.3 Assignment 03 Section C ...........................................................................................................................................................31
4 EXTRA EXAMPLES & SOLUTIONS ......................................................................................................................... 35
5 EXTRA EXAMPLES & SOLUTIONS SIMILAR TO QUESTIONS IN ASSIGNMENTS 01, 02 AND 03 ....... 50
2
, COS1501/102/0/2022
Dear Students,
This tutorial letter contains information on tutorial matter and the CAI tutorial, solutions to self-assessment
questions, assignments 02 and 03, and extra examples and solutions. You are welcome to contact the
COS1501 team if you have any academic queries.
If there are any of the tutorial letters listed below that you have not received in good time before the
examination, or if you have any administrative queries, consult the brochure my Studies @ Unisa for the
required procedures that you should follow.
Everything of the best with your studies this year!
Regards,
The COS1501 team
1 TUTORIAL MATTER & CAI TUTORIAL
TUTORIAL MATTER: We provide a list of tutorial letters that you should receive during the semester:
COSALLP/301/4/2022 General information about the school and names and telephone numbers of
lecturers
COS1501/101/0/2022 General information and assignments
COS1501/102/0/2022 This tutorial letter
COS1501/103/0/2022 Answers to activities in the study guide
CAI TUTORIAL: This is a computer-aided instruction (CAI) tutorial. It is downloadable and you can find the
instructions in the Tutorial letter 101. This interactive tutorial with theory, examples and interactive
exercises will lead you to understand “sets” and “relations”. There will be no exam questions directly on the
content of the CAI.
3
, 2 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENT 02
2.1 Assignment 02 Section 1
Note: Although the examination paper is an MCQ paper, it is very important to attempt all these self-
assessment questions, as you will still have to draw a Venn diagram or truth table etc on rough ,
or do a proof on rough before you will be able to answer a question in the exam. First attempt
the solutions on your own and then compare your solutions to the model solutions to see
whether you left out some detail.
Question A
Draw Venn diagrams to show that (A + B) = (B C) A is not an identity for all subsets A, B and C of
U. Draw the diagrams step-by-step.
Left-hand side: A’ B
A B A B
C C
The grey areas are the same for both the above diagrams. In the grey areas the elements live in both A and
B, i.e. these areas represent A B. For the diagram of A + B: Take all the coloured areas in the above
diagrams, then remove the grey area (i.e. A B):
A’ + B
A B
C
The above should remind you that A + B = (A B) – (A B) (Refer to study guide, activity 4-3).
This confirms the definition of symmetric difference: x A + B iff x A or x B, but not both.
4
Tutorial letter 102/0/2022
Theoretical Computer Science 1
COS1501
Semesters 1 and 2
School of Computing
CONTENTS:
1. TUTORIAL MATTER & CAI TUTORIAL
2. DISCUSSION OF SELF-ASSESSMENT QUESTIONS FOR
ASSIGNMENT 02
3. DISCUSSION OF SELF-ASSESSMENT QUESTIONS FOR
ASSIGNMENT 03
4. EXTRA QUESTIONS & SOLUTIONS
5. EXTRA QUESTIONS & SOLUTIONS similar
to QUESTIONS IN ASSIGNMENTS 01, 02 AND 03
, CONTENTS
1 TUTORIAL MATTER & CAI TUTORIAL ................................................................................................................. 3
2 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENT 02 ........................................................... 4
2.1 Assignment 02 Section 1 ............................................................................................................................................................. 4
2.2 Assignment 02 Section 2 ...........................................................................................................................................................12
3 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENTS 03 ...................................................... 20
3.1 Assignment 03 Section A...........................................................................................................................................................20
3.2 Assignment 03 Section B...........................................................................................................................................................28
3.3 Assignment 03 Section C ...........................................................................................................................................................31
4 EXTRA EXAMPLES & SOLUTIONS ......................................................................................................................... 35
5 EXTRA EXAMPLES & SOLUTIONS SIMILAR TO QUESTIONS IN ASSIGNMENTS 01, 02 AND 03 ....... 50
2
, COS1501/102/0/2022
Dear Students,
This tutorial letter contains information on tutorial matter and the CAI tutorial, solutions to self-assessment
questions, assignments 02 and 03, and extra examples and solutions. You are welcome to contact the
COS1501 team if you have any academic queries.
If there are any of the tutorial letters listed below that you have not received in good time before the
examination, or if you have any administrative queries, consult the brochure my Studies @ Unisa for the
required procedures that you should follow.
Everything of the best with your studies this year!
Regards,
The COS1501 team
1 TUTORIAL MATTER & CAI TUTORIAL
TUTORIAL MATTER: We provide a list of tutorial letters that you should receive during the semester:
COSALLP/301/4/2022 General information about the school and names and telephone numbers of
lecturers
COS1501/101/0/2022 General information and assignments
COS1501/102/0/2022 This tutorial letter
COS1501/103/0/2022 Answers to activities in the study guide
CAI TUTORIAL: This is a computer-aided instruction (CAI) tutorial. It is downloadable and you can find the
instructions in the Tutorial letter 101. This interactive tutorial with theory, examples and interactive
exercises will lead you to understand “sets” and “relations”. There will be no exam questions directly on the
content of the CAI.
3
, 2 DISCUSSION OF SELF-ASSESSMENT QUESTIONS, ASSIGNMENT 02
2.1 Assignment 02 Section 1
Note: Although the examination paper is an MCQ paper, it is very important to attempt all these self-
assessment questions, as you will still have to draw a Venn diagram or truth table etc on rough ,
or do a proof on rough before you will be able to answer a question in the exam. First attempt
the solutions on your own and then compare your solutions to the model solutions to see
whether you left out some detail.
Question A
Draw Venn diagrams to show that (A + B) = (B C) A is not an identity for all subsets A, B and C of
U. Draw the diagrams step-by-step.
Left-hand side: A’ B
A B A B
C C
The grey areas are the same for both the above diagrams. In the grey areas the elements live in both A and
B, i.e. these areas represent A B. For the diagram of A + B: Take all the coloured areas in the above
diagrams, then remove the grey area (i.e. A B):
A’ + B
A B
C
The above should remind you that A + B = (A B) – (A B) (Refer to study guide, activity 4-3).
This confirms the definition of symmetric difference: x A + B iff x A or x B, but not both.
4
