The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
189 views

Minesweeper is a single-player computer game invented by Robert Donner in 1989. A unary predicate mine is defined, where $\text{mine}(x)$ means that the cell $x$ contains a mine

$$\exists x_1, \dots , \exists x_n \left(\bigwedge_{i=1}^{n} \text{mine}(x_i) \wedge \forall y \left( \text{mine}(y) \to \bigvee_{i=1}^{n} y = x_i\right) \right)$$

Which of the following statements is the correct interpretation of the above formula?

  1. There are exactly $n$ mines in the game
  2. There are at least $n$ mines in the game
  3. There are at most $n$ mines in the game
  4. None of the above
asked in Mathematical Logic by Boss (13.7k points)
edited by | 189 views
0
If 2nd term OR operator replaced with AND, will it change anything .

1 Answer

+4 votes
The given logical statement is saying that all $x_1,x_2,\dots x_n$ are mines and if any $y$ is a mine it is one among $x_i.$ This means there cannot be more than $n$ mines but some of the $x_is$ can be the same. So we may have less than $n$ mines. Hence, option C.
answered by Veteran (379k points)
0

The problem is from: http://cse.iitkgp.ac.in/~pallab/FOCS_Autumn2016/logic_problemSet.pdf

There, the answer mentioned is A - exactly n mines.

And it makes sense too. The first part of the braces say that there are at least n mines present and the second part says that if there is a mine, it is present in any of the n locations mentioned.

I don't think it's true that some of the $x_i$s can be the same. 

0
If that makes sense to you you can follow that :)
0
But I am not sure, hence I asked which should be the correct solution or if you can find a flaw in what I wrote. That way, it'd help other people too.
+1

Okay, the correct answer is C, I was wrong. For future reference, people can check this link: https://math.stackexchange.com/questions/3021264/formalisation-of-a-given-sentence-using-quantiifiers?noredirect=1#comment6230364_3021264

Thank you @Arjun sir. 

0
You are welcome :)
0

@Arjun sir. What if there are 0 mines in the game?
I think the first-order statement is not taking care of it. 

0
You mean the correct interpretation should be at least one mine and at most n mines?
0

@Arjun sir... Yes. Am I missing something?

0

@Soumya29-I think there would be no formula if $n=0$.No Mines.

@Arjun-Sir,

Suppose I taken $n=3$

Formula becomes

$\exists x_1 \exists x_2 \exists x_3 \Biggl(\bigl(mine(x_1)\land mine(x_2)\land mine(x_3) \bigr) \land \forall y \biggl(mine(y) \rightarrow \bigl((y=x_1)\lor (y=x_2)\lor (y=x_3) \bigr) \biggr) \Biggr)$

Now suppose I have a domain in which only one mine is present say cell 'a' contains mine.

So, let $x_1=x_2=x_3=a$ and for all y in this domain, this domain contains only one cell and which has mine, and so the above expression becomes true.

So, this also says the Game has atleast 1 mine.

If suppose an option were there, that at least 1 mine and atmost n mines, would that have been a better choice here?

0
Got it Arjun sir.

Atmost n already implies atleast 1.

$\leq n=\{1,2,3,4......n\}$

Till N allowed.

Yes (C) is best here.
+1

@Arjun Sir

I am not able to figure it out that some mines $x_i$ are same. As it contains $\exists x_1 , \dots , \exists_n$ means there are exactly n mines which are under consideration and $\forall y $ specify that if $y$ is a mine then it is among one of $x_i$.

Please guide me where i am commiting mistake

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,003 questions
51,323 answers
177,490 comments
66,668 users