0 votes
Hello

Please may explain in simple word what is the idea for existential quantification? I studied on lecture video and also tried to find on previous exam but i am not sure what I understood is the right one.

My understanding is: "based on given variables e, we must try to see either in left or right branch of ϕ, after passing variables e, being true". Kindly elaborate on it? Thank you.
in * TF "Intelligent Systems" by (770 points)
edited by

1 Answer

0 votes

Formally, exists x. phi is defined as the disjunction of the co-factors, i.e., phi[x<-0] | phi[x<-1]. In simply words, we ask whether there is a value for x such that phi becomes true. Since there are only values 0 and 1 for x, this is the disjunction phi[x<-0] | phi[x<-1]. Hence, we need to find a variable assignment that satisfies phi[x<-0] or phi[x<-1], so that the models of exists x.phi are the models of phi where we just omit the assignment to x.

In contrast, forall x. phi is defined as the conjunction of the co-factors, i.e., phi[x<-0] & phi[x<-1]. Hence, we ask whether phi can become true for all values of x, i.e., we need to find a variable assignment that satisfies both phi[x<-0] and phi[x<-1]. Thus, we take the intersection of models of phi[x<-0] and phi[x<-1] as the models of forall x. phi.

Examples:

  • exists x. x = true
  • exists x. !x = true
  • exists x. x&y = y
  • exists x. x|y = true
  • exists x. x->y = true
  • exists x. x<->y = true
Feel free to make more examples using https://es.cs.uni-kl.de/tools/teaching/BDDAlgorithms.html with the Exists and Forall algorithm on the BDDs.
by (91.8k points)

Related questions

0 votes
2 answers
asked Aug 4, 2020 in # Study-Organisation (Master) by RS (770 points)
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Aug 27 in * TF "Intelligent Systems" by RS (770 points)
Imprint | Privacy Policy
...