COS3761 Exam 10 Sept 2021 PDF

Preview

Summary

UNIVERSITY EXAMINATIONSSep/Nov 2021COSFormal Logic III100 Marks 2 H 15 MinInstructions: Examination is for 100 marks. Answer all questions.  The paper consists of 6 pages. Do all rough work in the answer book  IRIS invigilation tool is used for the exam  Number your answers and label your rough ...

Description

UNIVERSITY EXAMINATIONS

Sep/Nov 2021

COS3761 Formal Logic III 100 Marks 2 H 15 Min

Instructions:        

Examination is for 100 marks. Answer all questions. The paper consists of 6 pages. Do all rough work in the answer book IRIS invigilation tool is used for the exam Number your answers and label your rough work clearly The mark for every question appears in brackets next to the question Student should do the Honesty Declaration. Follow the UNISA instructions for uploading your script Closed book Examination.

EXAMINATION PANEL: First examiner: S Vallabhapurapu Second examiner: Mr K Halland External examiner: Dr C Du (Tshwane University of Technology, Pretoria)

ALL THE BEST!

[TURN OVER]

2 COS3761 Sep/Nov 2021

QUESTION 1

[25]

Question 1.1 Consider the following propositional symbols and their intended meanings: p : it rains q: the sun shines r: a rainbow will appear (i)

Express the following declarative sentence in propositional logic using the propositional symbols as given above: If it rains while the sun shines then a rainbow will appear (2)

(ii)

Express the following propositional logic formula in English where the propositional symbols have the meanings given above: r→(q∨p)

(2)

Question 1.2 Use the basic natural deduction rules for propositional logic to prove the validity of the following sequents: (i)

(p → r) ∨ (q → r)├ (p  q)  r

(7)

(ii)

p  r  q,  r, s  t ├

(6)

p  t

Question 1.3 Show that the following sequent is not valid by giving an appropriate valuation. p → q ⊢ (p  q) → r Explain why your valuation proves that the sequent is not valid.

(3) [TURN OVER]

3 COS3761 Sep/Nov 2021

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

(5)

QUESTION 2

[37]

Question 2.1 Consider the following predicate and constant symbols and their intended meanings: D(x): S(x): R(x): (i)

x is a day x is sunny x is rainy

Express the following predicate logic formula in English, where the symbols have the meanings as given above: x[S(x)  D(x)   R(x)  D(x)]

(ii)

(3)

Express the following declarative sentence in predicate logic using the symbols as given above: There is a sunny day which is rainy

(3)

Question 2.2 Let  

P be a predicate symbol with one argument and Q a predicate with two arguments, respectively x, y are variables

State which of the following are well formed formulas: (i)

∀x x P(x)

(1)

(ii)

x P(x)

(1) [TURN OVER]

4 COS3761 Sep/Nov 2021 (iii)

(P(x)  Q(x, y)))

(1)

(iv)

x (P(x)  Q(x,y))

(1)

Question 2.3 Consider the following formula where P and Q are both predicate symbols with one argument, and g is a function symbol with one argument: ∀x (P(x)  Q(x)) ( P (f(x,y) ∨ Q(y)) (i)

Draw the parse tree of .

(5)

(ii)

Mark the free and bound variables on the tree.

(3)

(iii)

Is g(x) free for y in ? Explain your answer

(2)

Question 2.4 Using the basic natural deduction rules for predicate logic, prove the validity of the following sequent: (i) (ii)

∀x(P(x)  Q(x)), ∃xP(x) ├ xQ(x))

(7)

x (P(x)  Q(x)), x (¬ Q(x)) ├ x (¬ P(x))

(10)

QUESTION 3 [38] Question 3.1 Consider the following Kripke model with worlds x1,x2and x3: x2

x1

p

x3 p, q

¬q

[TURN OVER]

5 COS3761 Sep/Nov 2021

a)

For each of the following relations, determine whether it holds in the above Kripke model and give reasons for your answer: Please note : Reason carries 2 marks

(i)

x1 ╟

(ii)

x2 ╟ □ p → □ q

(3)

(iii)

x3 ╟ ◊ p ∨ ◊ q

(3)

b)

□ (p  q)

(3)

Find a Kripke model that does not satisfy the modal logic formula below. Also explain why the Kripke model does not satisfy the formula. (Assume there are two worlds x 1 and x2) □p→◊¬q

(5)

Question 3.2 (i)

If we interpret □  as "It is necessarily true that  ", why should the formula scheme □    hold in this modality? (3)

(ii)

If we interpret □  as "Agent A believes  ", what is the English translation of the formula □ p  ¬ □ q?

(3)

Question 3.3 Say we interpret the modal operators □ and ◊ to represent the temporal notions "necessary" and "possible" respectively, and say we interpret the propositional letters p , q, to mean "The old lady down the street own forty cats", "The old lady down the street probably have many cats" respectively (i)

Express the following modal logic formula in English:

(3)

◊p¬q (ii)

Translate the following declarative sentence into modal logic:

(3)

The fact that the old lady down the street probably has many cats doesn’t necessarily mean that she owns forty cats. [TURN OVER]

6 COS3761 Sep/Nov 2021

Question 3.4 (i)

Express the following modal logic formula in English where K i is read as “Agent i knows that”. (Assume there are 2 agents). K₁¬ p  ¬ K2 p

(ii)

(2)

Express the following sentence in modal logic where K i is read as “Agent i knows that” (Assume there are 4 agents) If agent 1 knows that agent 2 knows not p, then q.

(2)

Question 3.5 Using the basic natural deduction rules, the □ introduction and elimination rules of the basic modal logic K as well as the following three additional rules for KT45 □ □ □  T 4 5  □□ □ □  Prove the validity of the following sequent:

(8)

├KT45 □ ¬ □ ¬ □ p  □ □ p

© UNISA 2021...