I am in trouble , I searched a lot about how to solve this kind of questions but I did not get any answers.

I understand how can I know when the sentences is valid and Unsatisfiable in propositional logic, but in FOL I can't.

Can someone help me how can I solve this kind of questions? Because it comes always in the past exams in AI.

Let us have the following:

1- ¬(Speed(Processor(MyPC))=Speed(Processor(MyPC))) 
2- ¬ ∃ x ( Speed(x) = Speed(MyPC) ) 
3- Speed(MyPC)=MyPC 
4- ∀ y ∃ x (Speed(x) ∧ Speed(y))= Speed(MyPC)

Note :

    a constant symbols that represents my PC.

    a function symbol that refers to speed of x

The answer for 1 is Syntactically wrong
2 is Unsatisfiable
3 is Neither valid nor unsatisfiable
4 is Syntactically wrong

  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Jan 1, 2017 at 20:04

1 Answer 1


1 uses a function symbol Processor which is not in the logic signature. Hence, it's outside the syntax.

4 tries to equate a proposition with Speed(MyPC). You can't equate propositions in FOL. Outside the syntax.

3 is not universally true for every function Speed and every argument MyPC. For instance interpret MyPC as the natural $0$, and Speed as the successor function to obtain $\mathsf{succ}(0)=0$ which is false. Hence the formula is not valid. However, it is satisfiable: now interpret MyPC as zero and Speed as the identity function to obtain $\mathsf{id}(0)=0$ which is true. The formula has a model and a countermodel: satisfiable and invalid.

2 ∃ x ( Speed(x) = Speed(MyPC) ) is always true, since we can take x to be MyPC. This holds no matter how we interpret Speed and MyPC. Hence is it valid. (Alternatively, we can even show it is a theorem of FOL using a proof system, and then rely on the correctness theorem to claim it is valid.) Since formula 2 is the negation of a valid formula, it is unsatisfiable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.