2

A formula is valid if it is true for all values of its terms. Satisfiability refers to the existence of a combination of values to make the expression true. So in short, a proposition is satisfiable if there is at least one true result in its truth table, valid if all values it returns in the truth table are true.

Even given these definitions it is still not clear to me what sentences are valid or not.

What are some examples of sentences that are valid or (un)satisfiable?

Helosy
  • 143

2 Answers2

3

One way of thinking of sentences is as functions. For example, the sentence $P\land\lnot P$ can be thought of as the function $f(P)=P\land\lnot P$, and the sentence $P\lor Q$ can just as well be thought of as the function $g(P,Q)=P\lor Q$.

That's all well and good, but all we've done is add a little notation, and you're probably still wondering why this matters to you. The main advantage that thinking of sentences as functions brings is that you're already familiar with functions from your other mathematical experiences, and now we can analyze validity and satisfiability in a more familiar setting.

  • A function is valid if it is true everywhere in its domain.
  • A function is satisfiable if it is true somewhere in its domain (note that all valid functions are satisfiable).

So, what would some of these sentences/functions look like?

  • Take $f(P)=P\lor\lnot P$. Every proposition is either true or false, so no matter what $P$ happens to be, $f(P)$ is true. This makes $f$ valid and satisfiable.
  • Consider $f(P)=P\land\lnot P$. No proposition can be both true and false, so $f$ is never true anywhere. Hence $f$ is not satisfiable.
  • We can work with more propositions as well. Define instead $f(P,Q)=P\lor Q$. In this case, if $P$ and $Q$ are both false then $f$ is also false, so the $f$ is not valid. However, if $P$ and $Q$ are both true then $f$ is true. Since there is some input making $f$ true, we know $f$ is satisfiable.
Hans Musgrave
  • 1,979
  • So is the sentence If mars is made of blue cheese, then cats fly valid or invalid? – Helosy Sep 12 '18 at 05:49
  • Breaking it down, the sentence is $P\implies Q$ where $P$ is "mars is made of blue cheese" and $Q$ is "cats fly". If $P$ is true and $Q$ is false, the implication is false. Since some combination of inputs makes the sentence false, the sentence is invalid. The ridiculous choices of $P$ and $Q$ exist to highlight that their values don't matter -- or just to throw you off if you're feeling cynical ;) – Hans Musgrave Sep 12 '18 at 05:52
  • I see thanks for your answer :)
    What would a valid sentence look like then?     – Helosy Sep 12 '18 at 06:07
  • An easy way to construct such a sentence is to start with a true logical proposition and then plug some things into it. For example, we know $P\lor\lnot P$ is valid, and turning that into a sentence we can say something like Either Elon Musk will take Tesla private or he will leave it publicly traded. – Hans Musgrave Sep 12 '18 at 06:21
0

If $A$ is a propositional variable, $ A\lor \lnot A$ is a valid sentence, since whatever value $A$ takes, this is true. Another is $A\to (B\to A).$ As you can check, whatever value $A$ and $B$ take, this is true.

A sentence that is satisfiable but not valid is the very simple sentence of just $$A,$$ which is true when $A$ is true and false if $A$ is false. Another is $A\land B.$ As you probably know, the truth table for $A\land B$ has both zeros and ones in it.

Finally, $ A\land \lnot A$ is unsatisfiable. You can see it's false regardless if $A$ is true or false. Another unsatisfiable sentence is $$ (A \lor B)\land \lnot A \land \lnot B,$$ which you can check is false for any truth values of $A$ and $B.$

spaceisdarkgreen
  • 58,508