0
$\begingroup$

In propositional logic, we create well-formed formulas out of logical connective symbols and propositional variables. Then we can consider a valuation function that first assigns a true/false value to each propositional variable, and then assigns a true/false value to every well-formed formula by certain rules. If I'm not mistaken, all well-formed formulas of the form $$ \varphi \vee \neg\varphi $$ (where $\varphi$ is a well-formed formula) are true for all possible valuations, so they are tautologies. Thus, we can conclude that the law of excluded middle holds for propositional logic.

Now in first-order logic, I know that we need to assign an interpretation or structure to our language, and then based on certain rules we assign true/false values to the relevant well-formed formulas that are propositions.

Question: In FOL, does every wff of the form $\varphi \vee \neg\varphi$ (where $\varphi$ is a wff) always evaluate to being true? Truth assignment in first-order logic seems so different than in propositional logic that I am not able to reason through such a simple question.

$\endgroup$
3
  • 1
    $\begingroup$ Yes. If there aren’t any quantifiers then first-order logic reduces to propositional logic. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 4, 2022 at 22:05
  • 1
    $\begingroup$ It holds even when $\varphi$ is a formula with quantifiers. The easiest way to see that this must be true is the Completeness Theorem. There can be no model in which neither $\varphi$ nor $\lnot \varphi$ holds. $\endgroup$
    – Robert Shore
    Commented Sep 4, 2022 at 22:15
  • 3
    $\begingroup$ @RobertShore This is not a valid argument. The fact that there can be no model in which neither $\phi$ nor $\neg \phi$ holds only shows that $\models \neg (\neg \phi \land \neg \neg \phi)$, but it does not show $\models \phi \lor \neg \phi$. $\endgroup$
    – Mark Saving
    Commented Sep 4, 2022 at 23:51

1 Answer 1

Reset to default
3
$\begingroup$

Yes.

Every formula that is a first-order instance of a propositional tautology, i.e. one that can one get by substituting first-order formulas for propositional letters in a propositionally valid formula, is also valid in FOL.

$\endgroup$
2
  • $\begingroup$ Ok, I want to clarify a few things with some questions. So your answer holds even if $\varphi$ from $\varphi \vee \neg\varphi$ has quantifiers in it? And the way you prove this is essentially identical to the proof in propositional logic by treating all atomic formulas as propositional variables? Am I correct in these assertions? $\endgroup$
    – Maximal Ideal
    Commented Sep 4, 2022 at 22:36
  • 2
    $\begingroup$ Yes. Provided that it really is the same $\varphi$ left and right. E.g. $\forall x \exists y P(x,y) \lor \neg \forall x \exists y P(x,y)$. And as a proof you would typically say that it's valid because it's an instance of a propositional tautology, which can then be proved by means of your choice. If you write a proof arguing about valuations/interpretations, it will be sufficient to look at the truth functions of the connectives without looking into the predicates and quantifiers. $\endgroup$
    – Natalie Clarius
    Commented Sep 4, 2022 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .