Conversion of English Sentence into First Order Logic & Proof using rules of inference.

I am solving some problems from the book Discrete Mathematics & its applications with combinatorics & Graph Theory by Kenneth H Rosen. I have difficulty solving these three problems:

1. Is the assertion "This statement is false" a proposition?
2. Express the following statement in FOL: "A student must take at least 60-course hours, or at least 45-course hours and write a master's thesis, and receive a grade no lower than a B in all required courses, to receive a master's degree".
3. Does the given mathematical argument is valid:
\begin{align} \forall x (P(x) \implies \lnot Q(x))\\ \forall x (Q(x) \implies R(x))\\ \hline\\ \therefore \forall x (P(x) \implies \lnot R(x)) \end{align}

In the (1), how to prove the assertion is a paradox. As statement itself is talking about its truth value i.e. False, assigning true to the statement introduces paradox, how do I prove it?

For (2), if I assume predicates as:
$$H(x) \text{: Student takes at-least 'x' course hours.}\\ T: \text{Student wrote a master's thesis.}\\ G(y,z): \text{Student received 'y' grade or higher in 'z' course.}\\ M: \text{Student received a master's degree}\\ Domain: \text{All students.}$$

Answer which I got:
$$(((H(60) \lor (H(45) \land T)) \land \forall zG(B,z)) \implies M$$
Answer given is:
$$M \implies ((H(60) \lor (H(45) \land T)) \land \forall zG(B,z))$$
If I change the domain to all people, then how would the answer change.

For (3) how do I prove using the Rules of Inference for Quantifiers or if the argument is not valid, then how can I check the validity of argument in FOL.

• The three questions are not related. Please, ask just one question per post. Commented Aug 7, 2019 at 3:49
• @Taroccoesbrocco Okay :) Commented Aug 7, 2019 at 8:05

1 Answer

As is mentioned in the comments, these are totally unrelated questions, so please ask them in several different questions, instead of all in one.

Here are some answers to the three questions

1. I'm not sure which definition of proposition is being used by Rosen, but I would say a proposition is a statement that can be assigned a truth value (so it is either true or false, not both). The assertion "This statement is false" cannot be assigned a truth value, hence it is not a proposition.
2. If your domain is all students, then the variables (i.e. your $$x$$) should denote students. In your examples it denotes hours of taken courses, so you should use hours of taken courses as domain.

The answer you gave has the implication in the wrong direction: the required things are requirements, hence you cannot get a degree if you don't fulfil those requirements. Therefore if a student receives a degree, they will fulfil those requirements.

Your solution implies that anybody who fulfils those requirements gets a degree. This is not what is being stated. For example, someone receiving a B grade in 45 hours spent on several completely unrelated courses and writing a disappointing master's thesis should not get a degree, yet this person fulfils the requirements.

As a sidenote: it is difficult to truly translate the semantical meaning of the sentence, since it is not possible to translate deontic verbs such as "must" adequately using first-order logic. In my opinion, the meaning of this sentence is better translated using deontic modal logic.

3. To prove statements are valid, you have to just try proving it. You'll get better with practice. It also highly depends on your proof system, some of them being relatively easy to see how to continue (e.g. Tableaux or Sequent Calculus), others being difficult (e.g. Hilbert systems). Note that there is no general recipe for creating proofs, as first-order logic is undecidable.

To prove statements are invalid you have to give a countermodel. Once again, the best tactic is to just try finding models that invalidate the statement, and once again, you'll get better with practice.

As for this statement, suppose we have some $$x$$ for which $$P(x)$$ holds, then also $$\lnot Q(x)$$ holds by the first premise. However, the second premise then does not give us anything: since $$Q(x)$$ is false, the implication is true by the antecedent being false. The truth value of the consequence can therefore be anything it wants (in particular $$R(x)$$ may be true).