Hello,
I'm excited to share a valuable resource for your COS3761 exam preparation - a merged and easily searchable PDF of Questions and Answers. This tool is especially useful if your exam allows open-book format, as it enables you to quickly navigate and find the information you need.
I pers...
This examination question paper remains the property of the University of South Africa and may nat be
removed from the examination venue
his paper consists of7 pages
INSTRUCTIONS.
Answer all eight questions
ND ee
Do all rough work im the answer book
BW
Number your answers and label your rough work clearly
The mark for every question appears in brackets next to the question
You may answer in English or Afrikaans
TA
ALL THE BEST'
[TURN OVER]
Open Rupe «
ete eg
, 2 COS3761
May/June 2015
QUESTION 1 [16]
Question 1(a)
The following propositional symbols and therr intended meanimgs are given
p the chef 1s a skilled person
q the ingredients are expired
r the muffin is delicious
s Susan Itkes muffins
() (2)
Express the following declarative sentence in propositional logic using the propositronal symbols p, q, r and s as
given above
If the chef 1s a skilled person and the ingredients are not expired then the muffin is delicious
(i)
Express the following propos:ttonal fogic tormula in English where the propositional symbols p, y, r and s have the
meanings given above Q)
(Aga vr > pv —-7s)
Question I(b)
The following predicates and constant symbols as well as their intended meanings are given
D(x) x 1s a dog
F(x, y) x 1s a friend ofy
OK, y) x owns y
h Harry
$ Susan
® 4)
Express the following sentence in predicate logic using the predicates and constant symbols given above
All of Harry’s friends are dog owners
(1) (3)
Express the following predicate logic formula in English where the predicates and constant symbols have the
meanings given above
ax (DX) A O(s, x) )
, 3 COS3761
May/June 2015
Question I(c)
@ (3)
Express the following sentence in modal logic where K, 1s read as “Agent 1 knows that”
Agent | knows p and agent | does not know that agent 2 knows q
Assume there are two agents
(a) (2)
Express the following modal logic formula in English where K, 1s read as ‘Agent 1 knows that”
Ki (p Aq) > AK Ki q a p)
QUESTION 2 16]
Consider the following summary of the HORN algorithm for determining the satisfiability of a Horn
formula >
| Go through the formula and mark every occurrence of T
2 While there 1s a clause im which everything 1n the left side has been marked but the thing
on the right side (call it p) has not been marked, mark every occurrence of p in the formula
3 If Lhas been marked, report “not satisfiable” else report “satisfiable”
Apply the above algorithm to the following formula to determine whether it 1s satisfiable or not
PAqarola(TTspaA@aTog
apn
QUESTION 3 17)
Consider the following formula ¢ where P_ and Q are predicate symbols with one argument and S 15 a predicate
symbol with two arguments
vx y(P(AX, y)) Vv OY) — Vz Sly.2)
(i) (3)
Draw the parse tree of
{ui} (2)
Mark the free and bound variables on the tree
(iii) (2}
Let g be a function with one argument Is g(a) free for y in 6? Explain your answer, but do not do any
substitution
, 4 COS3761
May/June 2015
QUESTION 4 133]
In this question you have to give forma! natural deduction proofs Note that it 1s important to number your
statements, indicate subproofs and at each step give the rule you are using
Question 4(a) (6)
Using the basic natural deduction rules, prove the validity of the followmg sequent
a(pv gy}k apanq
Question 4(b) (9)
Using the basic natural deduction rules, prove the valtdity of the following sequent
= 3x P(x) | vx 4 PO)
Question 4(c) (12)
Using the basic natural deduction rules and the 5 introduction and elimination rules of the basic modal logic K,
prove the validity of the following sequent
a(pag)k opaca
Question 4(d) (6)
Using the basic natural deduction rules, the o introduction and elimination rules of the basic modal logic K as well
as the following three additional rules for KT45
oa o oO > 70 b
—T 4 5
$ aoa¢ anoad
prove the validity of the following sequent
betas op—-~cx7no-p
QUESTION 5 13)
Prove by mathematical induction that
2" > wt
whenever # 1s an integer greater than 4
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 ExamMasteryHub. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R350,00. You're not tied to anything after your purchase.
