check the formulas for satisfiability and validity

Question

Could perhaps somebody explain me how to define if a formula is valid, satisfiable, or not satisfiable if

For a first-order model M and a variable assignment g we write M,g |= y. 
A formula is 
satisfiable iff for some model M and some assignment g: M,g |= y.
valid iff for all models M and all assignments g: M,g |=y.

I have some examples but I cannot apply the rules to them.

(P(x) v ¬P(x)) valid

(∀xP(x) v ∀x¬P(x)) satisfiable (not valid)

 ∃x(P(x) ^ ¬P(x))  not satisfiable

(∃x∀yR(x,y) -> ∀y∃xR(x,y)) valid

(∀y∃xR(x,y)) -> ∃x∀yR(x,y)) satisfiable (not valid)

Answer 1

You have to construct a model in which your formulas are mapped to truths; a model is a specification of a "universe", which is the set of objects on which your formulas apply (e.g., people, numbers, sets, and a list of all these that are in the universe ), a list of the predicates you use (i.e., the P(x), properties of the elements of the universe), and a specification of which predicates are satisfied by which members of the universe. Now, try constructing different universes so that your formulas are satisfied in all of them or some of them. You can also show that a sentence is valid by arriving at a contradiction when you assume its negation.

For example, for 2), we can have your universe be the set {$1,2$}, and $P(x)$:= "x is even". Then your sentence is not satisfied, because it is neither the case that all x's are even, nor all x's are odd ( but it is the case that all the x's live in Texas.)

You can also use truth trees, to help you see if counterexamples exist : http://en.wikipedia.org/wiki/Truth_tree. where you break down a sentence using the connectives. You try to see if there is an interpretation of the negation of the sentence where the negation is true. If there is no such interpretation, then your original sentence is a tautology, i.e., it is valid.

Answer 2

You have not "to define if a formula is valid, satisfiable, or not satisfiable"; those are simply the definition you have stated, e.g. :

For a first-order formula $\varphi$ we start with some basic clauses defining what means for a model $M$ to satisfy $\varphi$ with a variable assignment $g$ ; in symbols :

$M,g \vDash \varphi$.

Then we say that a formlua $\varphi$ is valid iff for all models $M$ and all assignments $g$, $M$ satisfy $\varphi$ with $g$.

Note. For the details, you have to check on your textbook; for some hints [regarding Enderton's book] you can see the answer to this post.

What the problem ask us to do is to apply the above definitions to the five examples.

Thus, to show that a formula $\varphi$ is valid [see examples 1 and 4] we have to provide an "argument" showing that for a model $M$ whatever the formula is satisfied with a variable assignement whatever.

To show that a formula is satsfiable (but not valid) [see examples 2 and 5] we have to provide a suitable interpretation such that the formula is true in it (i.e. a model for the formula] : this show satisfiability, but also another interpretation which falsify it : this in turn shows that it is not valid.

To show that a formula $\varphi$ is not satisfiable [see example 3] we have to show that its negation : $\lnot \varphi$ is valid, due to the fact that a formula is valid iff its negation is not satisfiable.

---

Example 1 :

To show that : $(P(x) \lor \lnot P(x))$ is valid.

In this case, the "informal" proof is quite simple.

Consider a model $M$ whatever (the details do not matter) and consider a variable assignment $g$ such that $g(x)=a \in M$, i.e. $a$ is an object wahtever in $M$ wich $g$ assign to the variable $x$ as its reference.

Finally, consider a property $\mathcal P$ whatever as "meaning" for the predicate letetr $P$.

Clearly, $\mathcal P$ holds for $a$ or it does not holds for $a$; thus, we have that $P(x)$ is true for $a$ or it is false for $a$. But if $P(x)$ is false for $a$, then $\lnot P(x)$ is true for $a$.

In every case, $P(x) \lor \lnot P(x)$ is true for $a$.

In conclusion, being $a$ whatever in $M$, we have that every variable assignment $g$ will satisfy the formula in $M$.

But also $M$ is a model whatever; thus for every model $M$ and every variable assignement $g$, we have that : $M,g \vDash (P(x) \lor \lnot P(x))$.

In conclusion, the formula is valid

---

Example 2 :

for the formula :

$(∀xP(x) \lor ∀x \lnot P(x))$

we can follow user99680's suggestion.

Consider an interpretation with domain the set $\mathbb N$ of natural numbers and interpret the predicate $P(x)$ as meaning the property : "$x$ is even".

Clearly, in $\mathbb N$ it is not true that all numbers are even; thus $\forall x P(x)$ is false.

But is false either that all numbers are odd (i.e.not even).

Thus, both disjuncts into $(∀xP(x) \lor ∀x \lnot P(x))$ are false and we can conclude, by truth-functional properties of $\lor$, that the formula is false in this interpretation.

Having found an interpretation which falsify the formula, we have that the formula is not valid.

But we want also to show that it is satisfiable.

For doing this, we need a different interpretation; consider again $\mathbb N$ and interpret the predicate $P(x)$ as "$x \ge 0$".

Clearly, all natural numbers are greater or equal to $0$. Thus, in this interpretation $\forall x P(x)$ is true and, again by truth-functional properties of $\lor$, we conclude that the formula is true in this interpretation.

Having found an interpretation which satisfy the formula, we have that the formula is satisfiable.