Validity

A (well-formed) logical formula is valid if it is true under every model. Else it is invalid.

More causally, if a formula is always true, it is valid. If it false for even a single case, it is invalid

Definition §

Validity ^definition

A well-formed formula $P$ in a formal language $L$ is valid if it is true under every model. In that case, we write:

$$\models P$$

Else, it is non-valid or invalid. Equivalently, it is invalid if there exists a model, $M$ which does not satisfy $P$:

$$M/\models P$$

In Propositional Logic §

In propositional logic, a proposition is valid if:

• It is a tautology, that is, true under every valuation
• Equivalently, its corresponding truth table has a column of True’s

In Predicate Logic §

In predicate logic, validity is much harder to prove. Because a model in predicate logic is a combination of a universe and interpretation, to show a formula is valid, we must show that it holds for every universe and every interpretation.

Obviously, that’s not easy. So we check if if the negat#todo

Theorems §

T1: In propositional logic, a formula is valid iff its negation is unsatisfiable

Under propositional logic, we have:

$$(\models F)\text{ iff }(\neg F\models \perp )$$

• The expression on the left hand side of the iff says that $F$ is valid by definition.
• The expression on the RHS says $\neg F$ is unsatisfiable

In plain English, to show that $F$ is valid, we can equivalently show that any model that makes $F$ false also makes false true. That is, it would have to be some crazy model.

Examples §

Examples: Predicate Logic §

• $\forall xP(x)\vee \exists y(\neg P(y))$ is valid

Non-examples: Predicate Logic §

• $\forall y\exists xP(x,y)\to \exists x\forall yP(x,y)$ is invalid
  • However, its converse, $\exists x\forall yP(x,y)\to \forall y\exists xP(x,y)$ is valid

(Equivalent to $P\vee \neg P$)