CSI 2101AB, Winter 2018

Assignment 1 (5% of

final mark)

Prof. WonSook Lee

Name: Vedant Dubey

Student ID: 7736159

34

· Release Jan 19, 2018 — Due to

9am, Jan 29, 2018

· No email submission is accepted.

Please submit either to the assignment box in SITE or to the Virtual Campus

Q1)

(5 points) 1.1 Propositional Logic

exercise #42

Q2)

(2 points) 1.1 Propositional Logic

exercise #46

Q3)

(3 points) 1.2 Applications of

Propositional Logic #12

Q4)

(2 points) 1.3 Propositional

Equivalences #36

Q5)

(1 point) 1.3 Propositional

Equivalences #40

Q6)

(5 points) 1.4 Predicates and

Quantifiers #32

Q7)

(4 points) 1.4 Predicates and

Quantifiers #42

Q8)

(2 points) 1.4 Predicates and

Quantifiers #46

Q9)

(5

points) 1.5 Nested Quantifiers #18

Q10)

(1

point) 1.5 Nested Quantifiers #34

Q11)

(4

points) 1.5 Nested Quantifiers #38

Answers:

1. 1.1

Propositional Logic exercise #42

a.

If x=1, then (1+2=3) is true, so x:=x+1 is

executed. Final value of x is 2.

b.

If x=1, then (x+1=3) is false and (2x+2=3) is

false, which makes ((x+1=3)OR(2x+2=3)) false, so x:=x+1 is not executed. Final

value of x is 1.

c.

If x=1, then (2x+3=5) is true and (3x+4=7) is

true, which makes ((2x+3=5) AND (3x+4=7)) true, so x:=x+1 is executed. Final

value of x is 2.

d.

If x=1, then (x+1=2) is true and (x+2=3) is true,

so ((x+1=2)XOR(x+2=3)) is false, so x:=x+1 is executed. Final value of x is 1.

e.

If x=1, then (x<2) is true, so x:=x+1 is
executed. Final value of x is 2.
2. 1.1 Propositional Logic exercise #46
"Fred is happy."
– 0.8
"John is happy."
– 0.4
"Fred and John
are happy." – min(0.8, 0.4) = 0.4
"Neither Fred
nor John are happy." – min(1-0.8, 1-0.4) = min(0.2, 0.6) = 0.2
3. 1.2
Applications of Propositional Logic #12
Let w denote "the
file system is locked".
Let x denote "new
messages will be queued".
Let y denote "the
system is functioning normally, and conversely".
Let z denote "the
new messages will be sent to the message buffer".
Then these are
the specifications written with the variables above:
"If the file
system is not locked, then new messages will be queued." :
¬w à x
"If the file
system is not locked, then the system is functioning normally, and conversely."
:
¬w à y
"If new messages
are not queued, then they will be sent to the message buffer." :
¬x à z
"If the file
system is not locked, then the new messages will be sent to the message buffer."
:
¬w à z
"New messages
will not be sent to the message buffer."
¬z
The following
configuration can allow the system to be consistent: w is true, x is true, y is
false, and z is false.
Specification
Condition
Truth Value
¬w à x
F à T
T
¬w à y
F à F
T
¬x à z
F à F
T
¬w à z
F à F
T
¬z
T
T
4. 1.3
Propositional Equivalences #36
s*=s when s=p?T
because p?T
is equivalent to p. Meanwhile s*=p?F which is also equivalent to p.
Therefore, since p?T= p?F, s=s*.
5. 1.3
Propositional Equivalences #40
To make all
parts of a conjunction proposition true, we can negate the false values. Therefore,
the proposition would be p?q?¬r which is only true when p is true, q is true, and r is
false.
6. 1.4
Predicates and Quantifiers #32
a.
Let x represent dogs and P(x) represent "x has
fleas". So the given statement is ?xP(x), the negation is ?x¬P(x), and the
negated expression is "There is a dog that does not have fleas".
b.
Let x represent horses and P(x) represent "x can
add". So the given statement is ?xP(x), the negation is ?x¬P(x), and the
negated expression is "All horses cannot add".
c.
Let x represent koalas and P(x) represent "x can
climb". So the given statement is ?xP(x), the negation is ?x¬P(x), and the
negated expression is "There is a koala that cannot climb".
d.
Let x represent monkeys and P(x) represent "x can
speak French". So the given statement is ?x¬P(x), the negation is ?xP(x), and
the negated expression is "There is a monkey that can speak French".
e.
Let x represent pigs and P(x) represent "x can swim"
and Q(x) represent "x can catch fish". So the given statement is ?x(P(x)?Q(x)),
the negation is ?x¬(P(x)?Q(x)), and the negated expression is "There is no pig
that can swim and catch fish".
7. 1.4
Predicates and Quantifiers #42
a.
Let x represent users and P(x) represent "x has
access to an electronic mailbox". Then the given statement becomes ?xP(x).
b.
Let x represent the group members, y represent
the file system, P(x) represent "x has access to an electronic mailbox", and Q(y)
represent "y is locked". Then the given statement becomes Q(y)à?xP(x).
c.
Let x represent the firewall, y represent the
proxy server, and P(x) represent "x is in a diagnostic state". Then the given
statement becomes P(x)<->P(y).

d.

Let x represent routers, y represent the

throughput, z represent the proxy server, P(x) represent “x is functioning

normally”, Q(y) represent “y is between 100 kbps and 500 kbps”, and R(z)

represent “z is in diagnostic mode”. Then the given statement becomes (Q(y)?¬R(z))à?xP(x).

8. 1.4

Predicates and Quantifiers #46

9. 1.5

Nested Quantifiers #18

10. 1.5

Nested Quantifiers #34

11. 1.5

Nested Quantifiers #38