Exam Paper 2011 - my answers

Hi,

some feedback on the exam paper. Would like your inputs

1a i) Only if is read as P --> Q = P only if Q
Thus q --> r and S

1a) ii) if he drank to much AND drives a BMW, then he does not drive too fast

1b) i)
FORALLx (P(x) and (not G(f(m),x)) and G(m,x) --> E(m,x)

1b) ii) THEREEXISTS an x, such that x is a party AND Mary goes to the part AND Mary's mother goes to the party AND mary's mother enjoys the party

1 c) i) K1p ^ K2p ^ K3p ^ K4p (ie. Each agent knows p)

1 c) ii) Agent 1 knows p AND
Agent 1 does NOT know that / if Agent 2 knows p or does not know P

in better english: Agent 1 knows p, but does not know if Agent 2 knows P or not.

Question 2:
Grive propositional Logic, we can dsign a truth table and assign T or F to each term and then finally get the result of the formula in 2^n steps. If predicate logic, we are unable to devise a truth table, because we might have infinite number of variables to consider via FORALLx. Propositional logic will terminate in 2^n, predicate logic might not terminate for all worlds (unless the world only has 4 instances of the variable).

Question 3: i and ii
x under a is bound - left branch of -->
x under B is bound - left branch of -->
y under B is bound - right branch of -->

3 iii)
if f(x) free for Y?
Y under right branch does not get replaced, because it is bound
2x Y's under left branch are free of Y quantifier, thus
substituting with F(x) would create problem, it would introduct x under THEREEXISTS x
THus it is NOT free.

Question 4
a)

1. p OR (q --> p) AND q --premise
2. p OR (q --> p) --or elim 1
3. q --or elim 1
BOX1
4. p --assumption
5. p --copy 4
BOX2
6. q -->p --assumption
7 q --copy 3
8. p -- --> elim 6
9. p OR elim, 2, 4-5, 6-8

4b)

1. ForALLx S(x) OR T(x) premise
2. ForALLx S(x) --> C(x) premise
3. ThereExistsx not C(x)

BOX1 x0
4. not C(x0) Assumption (actually by elim ThereExists of line 3, but the book says assumption for the reason)
5. S(x0) OR T(x0) -- forAll elim line 1
6. S(x0) --> C(x0) --for all elim line 2
BOX 2
7. S(x0) -- assumption
8. C(x0) -- --> elim line 6
9. CONTADICTION -- not elim line 4,8
10. T(x0) -- CONTRADICTION elim line 9
BOX 3
11. T(x0) assumption
12. T(x0) Copy line 11
13. T(x0) OR elim lines 5, 7-10, 11-12 still inside BOX1

14. ThereExists T(x) -- There exists INTRO, Lines 4 - 13

4(c) NOT QUITE SURE

still busy with the rest

Danie van Eeden
------------------------

About to start with this one... I'll post my answers back here when I'm done (probably around 8... got to close off some issues with the work between 5 and 6).

my answers for question 1:

QUESTION 1(a):

(i)
(r AND s) -> q

(ii)
If he drives a BMW and drank too much, then he will drive slowly (ie: not drive very fast).

QUESTION 1(b):

(i)
FORALLx [ (P(x) AND G(m,x) AND NOT( G(f(m),x) ) ) -> E(m,x) ]

(ii)
Maggie's mother did not enjoy a party she went to with Maggie

QUESTION 1(c):

(i)
(K1p OR NOT K1p) AND (K2p OR NOT K2p) AND (K3p OR NOT K3p)

(ii)
Agent 1 knows p but does not know whether Agent 2 knows p or not.

QUESTION 2:

In propositional logic, the atoms making up some formula @ can be assigned truth values, which can be used to obtain a truth value for @. The statement provided is a tautology, and will always evaluate to true no matter the truth value of its atoms. It can be shown to do as such by constructing a truth table, for example. Therefore, it has a decided 'output', regardless of the input.

With predicate logic though, the use of variables to represent actual objects means that the objects represented by the variables are required to be known before deciding whether a particular formula is valid or not. Thus a tautology is based on a particular set of concrete objects that can be represented by the specified variables. Hence a formula is dependent on this additional knowledge, and can then be said to be undecidable in a general context.

QUESTION 3:

Cant redraw the diagram here, so I'm not answering (i) and (ii) here.

(iii)
No. The free occurrences of y (two of them, namely the B(x,y) and A(y) formulas ) in the formula are both under the scope of a quantifier on x. Thus, substituting f(x) with the free occurrences of y will place the substituted x values under the scope of the quantifier, which is not intended.
Thus f(x0 is not free for y.

Can't quite seem to get the formatting perfect, but should be an idea of what I got...

QUESTION 4A:

1  (p OR (q -> p)) AND q            premise
2  p OR (q ->p)                            AND ELIM 1
3  q                                               AND ELIM 1
4    | p                                     assumption
5    | p                                     copy 4

6    | q->p                                   assumption
7    | p                                         -> e 6,3
8  p                                         OR ELIM 2, 4-5, 6-7

QUESTION 4B:

1   FORALLx (S(x) OR T(x))      premise
2   FORALLx (S(x) -> T(x))      premise
3   EXISTSx (NOT C(x))            premise
4     |x0  NOT(C(x0))            assumption
5     |      S(x0) OR T(x0)      FORALLx ELIM 1
6     |      S(x0) -> T(x0)      FORALLx ELIM 2
7     |       | S(x0)            assumption
8     |       | C(x0)             ->e 6,7
9     |       | CONT             NOT ELIM 4,8
10   |       | T(x0)             CONT ELIM 9
11   |      
12   |       | T(x0)             assumption
13   |       | T(x0)             copy 12
14   |      T(x0)                   OR ELIM 5, 7-10, 12-13
15   |      EXISTSx(T(x))       EXISTS INTRO 14
16  EXISTSx (T(x))             EXISTS ELIM 3, 4-15

Hi 4c and 4d kind of got me..

I have thoughts on them but not quite sure:

4c)

1.not ForAllx not P(x) --premise

BOX1---------------------------------------------------------------------
2. not ThereExists P(x) --assumption

3 .BOX2 with x0 ---------------------------------
BOX3-------------------------------------------------------------
4 .P(x0) --assumption
5. ThereExists P(x0) -- ThereExists intro Line 4
6. contradiction -- not elim line 2
BOX3--------------------------------------------------------------
7. not P(x0) -- contradiction elim line 6
BOX2-----------------------------------------------------------------

8. ForAllx Not P(x) -- ForALl intro 3-7
9. Contradiction -- Line 1
-----------------------------------------------------------------------------
10.ThereExistsx P(x)

Danie van Eeden
------------------------

Jumping to question 7 quick:

QUESTION 7A:

BLOCKp -> p

Its satisfiable, since it is true in this particular model. Every world that has a p, can be reached from a world that has a p.
Its not valid, since it does not hold for every world in every model.

QUESTION 7B:
(i)
Holds - world c makes this true.
(ii)
Does not hold - after "processing" the first 2 BLOCKS, world c is reached. DIAMOND states that "there is one world reachable", but there are no worlds reachable from c, thus this statement is false, regardless of what appears after the DIAMOND.
(iii)
Does not hold - d does not satisfy q, and the second conjunct requires that either a or c have at least one world that is reachable that satisfies q. This is not the case for a, and there are no worlds reachable from c (making this false in that world anyway).
(iv)
Holds - there are no worlds reachable from c (the only world reachable from b), and the statement is thus vacuously true.

dve83 Wrote:
-------------------------------------------------------
> Hi 4c and 4d kind of got me..
>
> I have thoughts on them but not quite sure:
>
> 4c)
>
> 1.not ForAllx not P(x) --premise
>
>
> BOX1----------------------------------------------
> -----------------------
> 2. not ThereExists P(x) --assumption
>
> 3 .BOX2 with x0
> ---------------------------------
>
> BOX3----------------------------------------------
> ---------------
> 4 .P(x0)
> --assumption
> 5. ThereExists P(x0) -- ThereExists
> intro Line 4
> 6. contradiction -- not elim
> line 2
>
> BOX3----------------------------------------------
> ----------------
> 7. not P(x0) --
> contradiction elim line 6
>
> BOX2----------------------------------------------
> -------------------
>
> 8. ForAllx Not P(x) -- ForALl
> intro 3-7
> 9. Contradiction -- Line 1
>
> --------------------------------------------------
> ---------------------------
> 10.ThereExistsx P(x)

Yep, I'd say that looks about right... had me stumped for quite some time there. I haven't done 4d yet, since I haven't got to going over proofs with modal logic yet...

Going to get me some practise on these other proofs quick... then off to do some mathematical induction

enjoy and goodluck

Danie van Eeden
------------------------