Wednesday, September 7, 2011

More propositional logic

1Propositional formulas continued¶

1.1Propositional equivalence¶

Two propositional formulas $\Phi$ and $\Psi$ are considered propositionally equivalent if their valuations are the same for every valuation, or rather, if $V(\Phi) = V(\Psi)$ for every valuation $V$ (so any values of the symbols used). Another way of putting it is that they have the same truth tables.

For example, the following formulas are equivalent¹:

$p \to q$ and $(\neg p) \lor q$

The equivalence can be represented in a formula using the $\iff$ sign, as follows:

$(p \to q) \iff ((\neg p) \lor q)$

Since the above formula is a tautology², the formulas $p \to q$ and $(\neg p) \lor q$ are pairwise equivalent.

Another pair of equivalent formulas are $\neg (p \land q)$ and $(\neg p) \lor (\neg q)$, with their joint truth table shown below³:

1.2Functional completeness¶

A set of connectives is considered functionally complete if it is possible to generate every single truth table imaginable using just that connective. An example of a functionally complete set using the connectives we've studied so far is $\{ \neg, \land \}$; later on we'll encounter a binary⁴ connective that is functionally complete by itself.

2Propositional arguments¶

A propositional argument appears in the form

$\Phi_1, ... \Phi_n \vdash \Psi$

with the $\vdash$ symbol meaning "entails"⁵. You can think of it as saying "if we accept the premises $\Phi_1$ and $\Phi_2$ ... and $\Phi_n$, then the conclusion $\Psi$ logically follows. Note that $n$ can be 0 - it's perfectly acceptable to have nothing on the left side of the $\vdash$, in which case you're just saying that everything entails $\Psi$, which is only true if $\Psi$ is a tautology.

2.1Validity of propositional arguments¶

A propositional argument can be said to be either valid or invalid. An argument is valid if, for any valuation $V$ that results in $V(\Phi_1) = ... = V(\Phi_n) = \top$, we have $V(\Psi) = \top$. This can also be thought of in terms of the $\to$ connective - $\Phi_1, ... \Phi_n \vdash \Psi$ is valid if and only if $(\Phi_1 \land ... \land \Phi_n) \to \Psi$ is a tautology..

In other words, for an argument to be valid, whenever the left side evaluates to true, the right side does as well. An argument is invalid if it's possible to have all the premises being true with the conclusion being false.

2.2Independence from valuation¶

Propositional arguments are not propositional formulas. Unlike the latter, they are statements, and can be either true or false. They are independent of the values of the variables.

For example, $p \vdash q$ is an invalid (untrue) propositional argument, since $p \to q$ is not a tautology: if $V(p) = \top$ and $V(q) = \bot$, $V(p \to q) = \bot$. However, you don't need to refer to those particular values of $p$ and $q$ to state that the argument is invalid; the fact that such a valuation exists is enough to invalidate the argument. Unlike the value of a propositional formula, validity is an inherent property of a propositional argument.

In any case, the take-home message is that you can ignore the truth or falsehood of the premises or conclusion in the "real world"; it's only necessary to look at their relation to each other.

2.3Converting informal arguments into propositional form¶

An informal argument given as a series of (English) statements can be transformed into propositional form by allowing each distinct statement to be represented by a variable. For example, given the following set of sentences:

If the princess is pink, then the quince⁶ is quizzical. The princess is pink. Therefore, the quince is quizzical.

we first assign variables to the two statements found above, namely, "the princess is pink" and "the quince is quizzical". In this contrived example, we can use $p$ for "the princess is pink" and $q$ for "the quince is quizzical", for obvious reasons. The propositional equivalent can be written as follows:

$$p, \, p \to q \vdash q$$

where $\Phi_1 = p$, $\Phi_2 = p \to q$, and $\Psi = q$. That's it.

2.4Determining the validity of an argument¶

To check if an argument is invalid, just try to invalidate it (that is, find a valuation $V$ such that the premises come out $\top$ and the conclusion comes out $\bot$. If you are able to, then the argument is invalid. (Note that even if you are not able to, the argument might still be valid, as the inability to invalidate an argument could be caused by personal shortcomings rather than some property of the argument itself. Be thorough and that should be avoided.) You could alternatively write out a truth table or provide reasoning based on the possible values of the variables and the roles of the connectives.

In the case of the previous example, we do indeed have a valid argument, as $(p \land (p \to q)) \to q$ is a tautology (which we can confirm by writing out the truth table if we so wished). An example of an invalid informal argument is given below:

The princess is pink. If the quince is quizzical, then the princess is pink. Therefore, the quince is quizzical.

Or, in propositional form:

$$p, \,q \to p \vdash q$$

This is not valid, as $V(p) = \top$ and $V(q) = \bot$ clearly results in both premises being satisfied and a conclusion that is untrue. It's not that the conclusion itself is never true, it's just that the premises being true does not guarantee that the conclusion is true. Since a propositional argument is really just saying that "whenever the premises are all true, so is the conclusion", then logically any counterexample invalidates the argument, as was done above.

Another, somewhat longer informal argument:

If the princess is pink, then either the quince is quizzical or the rat is not rotten. Either the rat is rotten or the princess is not pink. If the quince is quizzical, then the rat is not rotten. Therefore, either the princess is pink or the quince is quizzical.

In propositional form (where $r$ now stands for "the rat is rotten"):

$$p \to (q \lor \neg r),\, r \lor \neg p, \, q \to \neg r \vdash p \lor q$$

Translating it was easy enough, now let's try to invalidate it. Recall that we need to find a case where the premises come out $\top$ but the conclusion comes out $\bot$. For the conclusion to come out $\bot$, we must have $V(p) = \bot$ and $V(q) = \bot$. From the former, we are guaranteed that $V(\Phi_1) = V(p \to (q \lor \neg r)) = \top$, and from the latter, we are guaranteed that $V(\Phi_3) = V(q \to \neg r) = \top$. But $V(p) = \bot$ also means that $V(r \lor \neg p) = V(r \lor \top) = \top$ no matter what the value of $r$. So the argument is invalid.

Let's try this with a slightly different conclusion. Let $\Psi$ be instead $\neg p \lor \neg q$ ("either the princess is not pink or the quince is not quizzical"). Is this new argument also invalid? Let's check. Similarly to before, we have that the conclusion, $\Psi$, only comes out $\bot$ when $V(p) = V(q) = \top$. For $\Phi_3$ to come out $\top$, $V(r)$ must be $\bot$. But when $V(r) = \bot$, $V(\Phi_2) = \bot$ as well, and so there is no valuation $V$ such that the premises come out $\top$ and the conclusion comes out $\bot$. So this is a valid argument. We could also have written out the truth table for the "implies" formula (i.e. $\Phi_1 \land ... \land \Phi_n \to \Psi$ and seen that all the lines comes out $\top$, but this is quicker and possibly more elegant.

This type of question is likely to turn up on an exam, so make sure you have a good understanding of how this works. You can find references to appearances in assignments and past exams as well as an overview of how to answer this type of question on the HTSEFP page.

3Propositionally consistent formulas¶

Let $\Phi_1, ... \Phi_n$ be formulas. We say that $\{ \Phi_1, ... \Phi_n \}$ are propositionally consistent if there exists a valuation $V$ such that $V(\Phi_1) = ... = V(\Phi_n) = \top$. So if there is a way to make them all come out $\top$, then the set as a whole is consistent; otherwise, the set is inconsistent. (There may be a way to make some of the formulas come out $\top$ and some of them come out $\bot$, but that says nothing about a set's consistency.)

3.1Determining the consistency of a set of formulas¶

A set of formulas $\{ \Phi_1, ... \Phi_n \}$ if and only if there is at least one line in the truth table for $\Phi_1 \land ... \land \Phi_n$ that comes out $\top$. Writing out the truth table will therefore tell you if a set is consistent or not. You can also reason based on the interaction of the connectives or whatever that means.

Example: $\Phi_1 = (p \to (q \lor \neg r))$, $\Phi_2 = (r \lor \neg p)$, $\Phi_3 = (q \to \neg r)$, $\Phi_4 = (p \lor q)$. For $\Phi_4$ to come out $\top$, we need either $V(p) = \top$ or $V(q) = \top$. Let's start with the former. $V(r)$ must be $\bot$ for $V(\Phi_2) = \top$. $V(q)$ can be anything, and we would still have $V(\Phi_1) = V(\Phi_3) = \top$. So there you go - the set is consistent, and the valuation that makes all the formulas come out $\top$ consists of $V(p) = \bot$, $V(r) = \bot$ and $V(q) = $ either.