6. Logic and Action Flashcards
What does x := y say?
That the value of x is the value of y, x gets value y
What is a sequence? give an example
Performing actions after another action i.e.: a;b;a
What is a test condition? give an example
To check if a fact holds, self loop, ?ϕ
translate: if ϕ then α1 else α2
?ϕ; α1 ∪ ?¬ϕ; α2
How to reverse an action?
Use the Converse aˇ
The converse of a;b ?
bˇ;aˇ
What is the set of all pairs S?
S x S or S^2
Describe relational composition
Ra ◦ Rb = {(s, s’) | there is some s0 ∈ S : (s, s0) ∈ Ra and (s0, s’) ∈ Rb}
Describe the choice relation
Ra ∪ Rb = {s1, . . . , sn} ∪ {s’1, . . . , s’m}
Describe the test relationship
Identity I = {(s, s) | s ∈ S}.
The subset ?ϕ is interpreted as:
R?ϕ = {(s, s) | s ∈ S, s |= ϕ}
What is the relational converse?
Rˇ = {(y, x) ∈ S^2| (x, y) ∈ R}.
Converse of a composition?
(R1 ◦ R2)ˇ = R2ˇ◦ R1ˇ
What is transitive closure?
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
Translate: while ϕ do a
(R?ϕ ◦ Ra)* ◦ R?¬ϕ.
Definition of <a>ϕ</a>
<α>ϕ is true in a state s if for some s' with (s, s') in the interpretation of α it holds that ϕ is true in s'
</α>
Definition of [a]ϕ
[α]ϕ is true in a state s if for every s’ with (s, s’) in the interpretation of α it holds that ϕ is true in s’
The difference between transitivity and transitive closure?
the main difference is that transitivity is a property of a relation, while transitive closure is a way to extend a given relation.
Give the transitive closure of R = {(1,2), (2,3), (3,4)} on the set {1, 2, 3, 4}
R* = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
What is the set of: ?ϕ
R?ϕ = {(s, s) | s ∈ S, s |= ϕ}
