Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes
Question 7. a) What would a path satisfying S2 = XXG((a ⊕ Xa) ∧ (b ⊕ XXb)) look like?

(Not from the Exam paper). What is a & Fa? Is the answer a or Fa?
in # Study-Organisation (Master) by (300 points)

2 Answers

0 votes

(a & F a) is equivalent to  a since a implies F a.

Here is a path made by the teaching tool satisfying S2 = XXG((a ⊕ Xa) ∧ (b ⊕ XXb)) where

    q0 = X a
    q1 = X b
    q2 = X X b
    q3 = G((a ⊕ Xa) ∧ (b ⊕ XXb))
    q4 = X G((a ⊕ Xa) ∧ (b ⊕ XXb))
    q5 = X X G((a ⊕ Xa) ∧ (b ⊕ XXb))

by (166k points)
0 votes
  1. There are multiple paths. Let's just look at G((a ⊕ Xa) ∧ (b ⊕ XXb)) (the XX before it just means that the formula is evaluated from the third step on): The first part in the conjunct that has to hold globally, is (a ⊕ Xa). It just means that a is alternating every step, like a, ¬a, …. (b ⊕ XXb) means that b alternates compared to the next-next step, like b, ¬b, ¬b, b, or b, b, ¬b, ¬b, …. Together, that's a cycle among these four states: {}, {a}, {b}, {a,b}. (Either in this order or backwards)
  2. a → F a (in words: When you satisfy a in the first step, then you have already satisfied a after finitely many steps). Thus, in the conjunction F a is redundant. As it is a conjunction, any satisfying assignment needs to satisfy both a and F a. Due to the implication, an assignment that satisfies a also satisfies F a. Hence, a ∧ F a = a.
by (25.6k points)

Related questions

0 votes
1 answer
0 votes
1 answer
asked Jan 13, 2021 in * TF "Emb. Sys. and Rob." by MS (1.1k points)
0 votes
1 answer
asked Aug 19, 2020 in # Study-Organisation (Master) by skkumar (300 points)
0 votes
1 answer
asked Aug 17, 2020 in # Study-Organisation (Master) by RS (770 points)
0 votes
1 answer
asked Aug 14, 2020 in # Study-Organisation (Master) by RS (770 points)
Imprint | Privacy Policy
...