6. Logic and Action

Question 1

What does x := y say?

Answer 1

That the value of x is the value of y, x gets value y

Question 2

What is a sequence? give an example

Answer 2

Performing actions after another action i.e.: a;b;a

Question 3

What is a test condition? give an example

Answer 3

To check if a fact holds, self loop, ?ϕ

Question 4

translate: if ϕ then α1 else α2

Answer 4

?ϕ; α1 ∪ ?¬ϕ; α2

Question 5

How to reverse an action?

Answer 5

Use the Converse aˇ

Question 6

The converse of a;b ?

Answer 6

bˇ;aˇ

Question 7

What is the set of all pairs S?

Answer 7

S x S or S^2

Question 8

Describe relational composition

Answer 8

Ra ◦ Rb = {(s, s’) | there is some s0 ∈ S : (s, s0) ∈ Ra and (s0, s’) ∈ Rb}

Question 9

Describe the choice relation

Answer 9

Ra ∪ Rb = {s1, . . . , sn} ∪ {s’1, . . . , s’m}

Question 10

Describe the test relationship

Answer 10

Identity I = {(s, s) | s ∈ S}.

Question 11

The subset ?ϕ is interpreted as:

Answer 11

R?ϕ = {(s, s) | s ∈ S, s |= ϕ}

Question 12

What is the relational converse?

Answer 12

Rˇ = {(y, x) ∈ S^2| (x, y) ∈ R}.

Question 13

Converse of a composition?

Answer 13

(R1 ◦ R2)ˇ = R2ˇ◦ R1ˇ

Question 14

What is transitive closure?

Answer 14

the smallest transitive relation S that contains R.
S is the transitive closure of R if:
(1) R ⊆ S
(2) S ◦ S ⊆ S
(3) if R ⊆ T and T ◦ T ⊆ T then S ⊆ T

Question 15

Translate: while ϕ do a

Answer 15

(R?ϕ ◦ Ra)* ◦ R?¬ϕ.

Question 16

Definition of <a>ϕ</a>

Answer 16

<α>ϕ is true in a state s if for some s' with (s, s') in the interpretation of α it holds that ϕ is true in s'
</α>

Question 17

Definition of [a]ϕ

Answer 17

[α]ϕ is true in a state s if for every s’ with (s, s’) in the interpretation of α it holds that ϕ is true in s’

Question 18

The difference between transitivity and transitive closure?

Answer 18

the main difference is that transitivity is a property of a relation, while transitive closure is a way to extend a given relation.

Question 19

Give the transitive closure of R = {(1,2), (2,3), (3,4)} on the set {1, 2, 3, 4}

Answer 19

R* = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

Question 20

What is the set of: ?ϕ

Answer 20

R?ϕ = {(s, s) | s ∈ S, s |= ϕ}