COS3761 Questions and Answers Exams Merged from 2015 to 2021 (Easily Searchable)

UNIVERSITY EXAMINATIONS UNIVERSITEITSEKSAMENS

=
UNISA fee unwversity




COS3761 May/June 2015


FORMAL LOGIC Il!
Duration 2 Hours 100 Marks

EXAMINATION PANEL AS APPOINTED BY THE DEPARTMENT

Closed book examination

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