Info

Solution

1. $a^M\in P^M$ so $\nu(P(a))=1$ and $b^M\in P^M$ so $\nu(P(b))=1$. Then for the full formula we have $\nu(P(a)\land P(b))=\nu(P(a))\times\nu(P(b))=1\times 1=1$

2. On any assignment $\alpha$ we have $\nu_\alpha(P(\mathbf{o_3}))=0$. Then for the full formula we have $\nu_\alpha(\forall xP(x))=\Pi_{\mathbf{o}\in D}(P(\mathbf{o}))=0$

3. On any assignment $\alpha$ we have $\nu_\alpha(P(\mathbf{o_1}))=1$ and so for the quantified formula $\nu_\alpha(\exists xP(x))=\Sigma_{\mathbf{o}\in D}(P(\mathbf{o}))=1$. Similarly we have $\nu_\alpha(\neg P(\mathbf{o_3}))=-\nu_\alpha(P(\mathbf{o_3}))=-0=1$ and so for the quantified formula $\nu_\alpha(\exists x\neg P(x))=\Sigma_{\mathbf{o}\in D}(\neg P(\mathbf{o}))=1$. Then for the full formula we have $\nu_\alpha(\exists xP(x)\land \exists x\neg P(x)=1)$

4. $\forall x\exists yR(x,y)$

The formula is true.

Here’s the calculation:

We know:

$$\nu(\forall x\exists yR(x,y))= \nu(\exists yR(\mathbf{o_1},y)) \times \nu(\exists yR(\mathbf{o_2},y)) \times \nu(\exists yR(\mathbf{o_3},y))$$

For each $i=1,2,3$, we have: $\nu(\exists yR(\mathbf{o_i},y))= \nu(R(\mathbf{o_i},{o_1})) +\nu(R(\mathbf{o_i},{o_2})) +\nu(R(\mathbf{o_i},{o_3}))$

And for each $i$, one of the summands here is true: for $i=1$, we have $\nu(R(\mathbf{o_1},\mathbf{o_2})=1$, for $i=2$, we have $\nu(R(\mathbf{o_2},\mathbf{o_3})=1$, and for $i=3$, we have $\nu(R(\mathbf{o_3},\mathbf{o_3})=1$. Hence: $\nu(\exists yR(\mathbf{o_i},y))= \nu(R(\mathbf{o_i},{o_1})) +\nu(R(\mathbf{o_i},{o_2})) +\nu(R(\mathbf{o_i},{o_3}))=1$.

And so the big product is $1$, too.

5. $\forall x\forall y((P(x)\land R(x,y))\to P(y))$

The formula is false: $\mathbf{o_2}$ and $\mathbf{o_3}$ provide the counterexample:

$$\nu(P(\mathbf{o_2}))=1$$ $$\nu(R(\mathbf{o_2},\mathbf{o_3}))=1$$ $$\nu(\mathsf{P}(\mathbf{o_3}))=0$$

Hence $$\nu(P(\mathbf{o_2})\land R(\mathbf{o_2},\mathbf{o_3})\to P(\mathbf{o_3}))=0$$

This makes any $\prod$-product involving this value $0$ as well.

6. We will observe a fact about the left object $\mathbf{o_1}$. On any assignment, if we choose any object $\mathbf{o}$ at all, we have $\nu_\alpha(R(\mathbf{o},\mathbf{o_1})=0$ and so $\nu_\alpha(R(\mathbf{o},\mathbf{o_1}\times P(\mathbf{o}))=0$. That means, if we sum over all objects in the $\mathbf{o}$ position we have $\Sigma_{\mathbf{o}\in D}(\nu_\alpha(R(\mathbf{o},\mathbf{o_1}))\times\nu_\alpha(P(\mathbf{o})))=0$. Since this sum comes out false for the particular object $\mathbf{o_1}$, if we then do a product calculation over all objects $\mathbf{o’}$ in that same position we get $\Pi_{\mathbf{o’}\in D}\Sigma_{\mathbf{o}\in D}(\nu_\alpha(R(\mathbf{o},\mathbf{o’}))\times\nu_\alpha(P(\mathbf{o})))=0$. And that is precisely how to calculate the value of our formula $\nu_\alpha(\forall x\exists y(R(y,x)\land P(y)))=0$.

Solution

BNF: We use ’left’ and ‘right’ as names of the lamps on each side, and use numeric terms as names of infinitely many points in time going forward. This comes with a built-in operation of ‘+1’ to refer to the next moment in time. Notice that predicates are restricted. They can only be combined with a lamp term in the first position and a time term in the second position.

$$ \langle{var}\rangle ::= x \mid y \mid z $$

$$ \langle{const_side}\rangle ::= \mathsf{left} \mid \mathsf{right} $$

$$ \langle{const_time}\rangle ::= n\in\mathbb{N} $$

$$ \langle{term_side}\rangle ::= \langle{var}\rangle \mid \langle{const_side}\rangle $$

$$ \langle{term_time}\rangle ::= \langle{var}\rangle \mid \langle{const_time}\rangle $$

$$ \langle{unop}\rangle ::= \neg $$

$$ \langle{binop}\rangle ::= \land \mid \lor \mid \rightarrow \mid \leftrightarrow $$

$$ \langle{quant}\rangle ::= \forall \mid \exists $$

$$ \langle{pred}\rangle^2 ::= \mathsf{On} \mid \mathsf{Off} \mid \mathsf{Switch} $$

$$ \langle{atom}\rangle ::= \langle{pred}\rangle^2(\langle{term_side}\rangle,\langle{term_time}\rangle) $$

$$ \langle{fml}\rangle ::= \langle{atom}\rangle \mid \langle{unop}\rangle\langle{fml}\rangle \mid (\langle{fml}\rangle\langle{binop}\rangle\langle{fml}\rangle) \mid \langle{quant}\rangle\langle{var}\rangle\langle{fml}\rangle $$

Task: Formalization

Setup

• $\mathsf{On}(\mathsf{left},1)$
• $\mathsf{Off}(\mathsf{right},1)$

Goals

• $\exists x\mathsf{Off}(\mathsf{left},x)$
• $\exists x\mathsf{On}(\mathsf{right},x)$

Rules

• $\forall x\forall y(\mathsf{Off}(x,y)\leftrightarrow\neg\mathsf{On}(x,y))$
• $\forall x\forall y((\mathsf{On}(x,y)\land\mathsf{Switch}(x,y))\to\mathsf{Off}(x,y+1))$
• $\forall x\forall y((\mathsf{Off}(x,y)\land\mathsf{Switch}(x,y))\to\mathsf{On}(x,y+1))$

Frames

• $\forall x\forall y((\mathsf{On}(x,y)\land\neg\mathsf{Switch}(x,y))\to\mathsf{On}(x,y+1))$
• $\forall x\forall y((\mathsf{Off}(x,y)\land\neg\mathsf{Switch}(x,y))\to\mathsf{Off}(x,y+1))$

Solution

a) $x+(y_1\times y_2\times\ldots)=(x+ y_1)\times(x+ y_2)\times\ldots$ follows from n-many applications of the Boolean law of absorption

relation to logical law???

b) First of all, this principle follows from repeated applications of the Boolean law of distributivity: $x\times(y_1+ y_2+\ldots)=(x\times y_1)+(x\times y_2)+\ldots$

Now, we can use this to verify the following inference.

$$\mathsf{Blue}(a)\land\exists x\mathsf{Round}(x)\vDash \exists x(\mathsf{Blue}(a)\land \mathsf{Round}(x))$$

Consider any model with assignment $\alpha$ where the premise is true:

$$\nu_\alpha(\mathsf{Blue}(a)\land\exists x\mathsf{Round}(x))=1$$

If we break down this calculation it is equivalent to:

$$\nu_\alpha(\mathsf{Blue}(a))\times\Sigma_{\mathbf{o}\in D} \nu_\alpha(\mathsf{Round}(\mathbf{o}))=1$$

The ‘big’ summation over all objects in the domain is equivalent to a list of individual sums over each object $\mathbf{o_i}$ in the domain:

$$\nu_\alpha(\mathsf{Blue}(a))\times(\nu_\alpha(\mathsf{Round}(\mathbf{o_1})+\nu_\alpha(\mathsf{Round}(\mathbf{o_2})+\ldots)=1$$

If we apply the Boolean principle that we started with, we get:

$$(\nu_\alpha(\mathsf{Blue}(a))\times\nu_\alpha(\mathsf{Round}(\mathbf{o_1}))+(\nu_\alpha(\mathsf{Blue}(a))\times\nu_\alpha(\mathsf{Round}(\mathbf{o_2}))+\ldots=1$$

This is equivalent to the following ‘big’ summation over all objects:

$$\Sigma_{\mathbf{o}\in D}(\nu_\alpha(\mathsf{Blue}(a))\times\nu_\alpha(\mathsf{Round}(\mathbf{o}))=1$$

Finally, the calculation above is the truth-value of our conclusion formula:

$$\nu_\alpha(\exists x(\mathsf{Blue}(a)\land\mathsf{Round}(x)))=1$$

We have shown that $[\mathsf{Blue}(a)\land\exists x\mathsf{Round}(x)]\subseteq[\exists x(\mathsf{Blue}(a)\land \mathsf{Round}(x))]$.

Solution

a) We need a set of swimmers $\mathsf{CanSwim}^M$ and a set of flyers $\mathsf{CanFly}^M$. We need one person/object that only belongs to the first set $a^M\in \mathsf{CanSwim}^M$ and $a^M\notin \mathsf{CanFly}^M$. Then we need another person/object that only belongs to the second set $b^M\notin \mathsf{CanSwim}^M$ and $b^M\in \mathsf{CanFly}^M$.

b) We construct a model with a domain with just two animals in it $D={ \mathbf{a_1,a_2} }$. One animal swims $\mathbf{a_1}\in \mathsf{CanSwim}^M$ but can’t fly $\mathbf{a_1}\notin \mathsf{CanFly}^M$. The other animal can’t swim $\mathbf{a_2}\notin \mathsf{CanSwim}^M$ but does fly $\mathbf{a_2}\in \mathsf{CanFly}^M$. Let $\alpha$ be any assignment in this model.

This universal formula is false in this model $\nu_\alpha(\forall x(\mathsf{CanSwim}(x))=\Pi_{\mathbf{o}\in D}\nu_\alpha(\mathsf{CanSwim}(\mathbf{o}))=0$ because of the properties of the second animal $\mathbf{a_2}\notin \mathsf{CanSwim}^M$. This universal formula is false in this model $\nu_\alpha(\forall x(\mathsf{CanFly}(x))=\Pi_{\mathbf{o}\in D}\nu_\alpha(\mathsf{CanSwim}(\mathbf{o}))=0$ because of the properties of the first animal $\mathbf{a_1}\notin \mathsf{CanFly}^M$. That means that $\nu_\alpha(\forall x(\mathsf{CanSwim}(x)\lor\forall x(\mathsf{CanFly}(x))=0$.

However, we always get $\nu_\alpha(\mathsf{CanSwim}(\mathbf{o})\lor\mathsf{CanFly}(\mathbf{o}))=1$ no matter which object we test it on, so we have $\nu_\alpha(\forall x(\mathsf{CanSwim}(x)\lor\mathsf{CanFly}(x))=\Pi_{\mathbf{o}\in D}\nu_\alpha(\mathsf{CanSwim}(\mathbf{o})\lor\mathsf{CanSwim}(\mathbf{o}))=1$. This makes it a counter-model to the intended inference.

Solution

Here are two phenomena that FOL can’t handle well:

1. Higher-order quantification: Statements like “Ada has all the properties of a good student”, which should be something like $$\forall F(\forall x(\mathsf{GoodStudent}(x)\to F(x))\to F(Ada)))$$

But this formula is not proper FOL syntax. A system that can handle this is second-order logic .

2. FOL lacks devices to handle many natural language phenomena, such as adverbial constructions: John failed badly.

We might be tempted to formalize this as $\mathsf{FailedBadly}(John)$, but then it doesn’t follow that John failed since $\mathsf{FailedBadly}(John)\nvDash\mathsf{Failed}(John).$

This paper develops an extension of FOL that can deal with adverbs.