COS3761 EXAM PACK 2026 – QUESTION & ANSWERS

lOMoARcPSD|47389193




UNIVERSITY EXAMINATIONS




OCTOBER/NOVEMBER 2025

COS3761
Formal Logic III
2 HOURS 15 MINUTES


Welcome to the COS3761 exam.


Date: 04 November 2025
Time: 8:00 am-10:15 am
Duration: 2 Hours15 Minutes


First Examiner: Prof S Vallabhapurapu

Second Examiner: Mr K Halland
Instructions:

1. Examination is for 100 marks. Duration of exam is 2 hours 15 min.
2. The question paper consists of 7 pages including this page.
3. Answer all three questions.
4. Closed book Examination.
5. IRIS invigilation tool is used for the exam.
6. Do all rough work in the answer book.
7. Number your answers and label your rough work clearly.
8. The mark for every question appears in brackets next to the question.
9. Follow UNISA instructions for uploading scripts
10. Students experiencing technical challenges should immediately contact the SCSC telephonically on 080
000 1870 or via e-mail at .




[TURN OVER]




Downloaded by Dorothy Reyes ()

, lOMoARcPSD|47389193




2 COS3761
Oct/Nov 2025


QUESTION 1 [25]

Question 1.1

Consider the following propositional symbols and their intended meanings:

Propositional symbols Meanings
p It is raining
q Traffic is slow
r Roads are slippery

s Streets are wet


(i) Express the following declarative sentence in propositional logic using the propositional
symbols as given above:

It is not the case that if it is raining, then the roads are slippery and traffic is
slow.

(ii) Express the following propositional logic formula in English where the propositional symbols
p, q and r have the meanings given above:
(2)
ps qr


Question 1.2

Use the basic natural deduction rules for propositional logic to prove the validity of the following
sequent

(i) p → q, r→s ├ p  r → q  s (5)

(ii) p  q → r, p, q,  r ├  p   r (8)


Question 1.3

Show that the following entailment does not hold by giving an appropriate valuation.

(p  q )  r ╞ p  ( q   r)

Explain why your valuation proves that the entailment does not hold. (3)




Downloaded by Dorothy Reyes ()

, lOMoARcPSD|47389193




3 COS3761
Oct/Nov 2025



Question 1.4

Use the HORN algorithm to prove that the following Horn formula is satisfiable or not satisfiable.
Show each step.
(p  q  )  (q  s  T)  (T  q)  (q  p  r  s)  (q  p) (5)




QUESTION 2 [37]

Question 2.1

Consider the following predicate symbols and their intended meanings:


M(x) x is a Movie
G(x,y) x goes to y
E(x,y) x enjoys y
f(x) husband of x
b Becky


(i) Express the following predicate logic formula in English, where the symbols have the
meanings as given above:

x (M(x) ∧ G(f(b),x) → y(G(y,x) → E(y,x))) (2)

(ii) Express the following declarative sentence in predicate logic using the symbols as given above:

There is a movie that nobody who goes to enjoys. (2)


Question 2.2

Consider the following formula  where P and Q are predicate symbols with two and three arguments
respectively.

x [Q(x, y, z)  (y (P(y, z))  x P(z, x))]

(i) Draw the parse tree of . (5)

(ii) Mark the free and bound variables on the tree. (2)




Downloaded by Dorothy Reyes ()

, lOMoARcPSD|47389193




4 COS3761
Oct/Nov 2025


Question 2.4

Using the basic natural deduction rules for predicate logic, prove the validity of the following sequent:

(i) x (P(x) → Q(x)) , ∃x(P(x) ∧ R(x)) ├ ∃x ( Q(x) ∧ R(x)) (9)

(ii) ∃x(¬ P(x) ∧ ¬ Q(x) ├ ∃x (¬ (P(x) ∧ Q(x))) (9)



Question 2.5

Let  be the following formula:

∃x (P(x) ∧ Q(x)) → (x (P(x) → Q(x)))

(i) Show that  is not valid by constructing a mathematical model (where the universe A of concrete
values is the set of integers) Explain why your model falsifies . (4)

(ii) Show that  is not valid by constructing a non-mathematical model. Explain why your model
falsifies . (4)




QUESTION 3 [38]

Question 3.1

Consider the following Kripke model with worlds x1, x2, x3 and x4:

x2
p,q
qq


p p, q

x1 x3


p
x4




Downloaded by Dorothy Reyes ()