Constructing a model for formula in propositional logic

279 Views Asked by At

Construct a model for fomula $F = \forall x \exists y(p(x,y) \land \lnot q(y,x)) \land \forall x \exists y \lnot p(x,y)$.

So if i want to construct a model i need my formula $F$ to be true in all valuations $F=_v1$. But i fail to see how can this formual be true.

Let $A = \forall x \exists y(p(x,y) \land \lnot q(y,x)) $ and $B = \forall x \exists y \lnot p(x,y)$ This formula is in form $ A \land B$ so i need both $A = _v1$ and $B = _v1$. But if i constct $p$ such that $\forall x \exists y( p(x,y))=_v0$ then when i negate it( since in $B$ i have $\lnot$) i get $B = _v1$ as needed. But then $ A = ( \forall x \exists y p(x,y) \land \forall x \exists \lnot q(y,x))$. Since i have consturcted $p$ such that $\forall x \exists y( p(x,y))=_v0$ and i consturct $q$ such that $ \forall x \exists \lnot q(y,x)=_v1 $, then i get $A = (0 \land 1 ) = 0$ i.e. $ F = A \land B = 0 \land 1 = 0$. Thus i cant construct a model for $F$. I could constuct a counter model if i let both $p$ and $q$ be rleation $\ge$. Am i missing here something or there is mistake in probelm.

1

There are 1 best solutions below

1
On BEST ANSWER

Just take $q$ to be never satisfied. Now for $p$ take a linear order on a set with no minimal or maximal element. So every $x$ will have a $y$ larger than it, and also a $y$ not larger than it.