## Propositional Logic

…is the basic form of logic whose atoms (or the basic structures upon which it acts) are propositions. A proposition is nothing more than a sentence in some language that states something. Within propositional logic, each sentence can have one of two different truth-values: True or False.

Propositional Logic comes from a more basic kind of logic called Aristotelian Logic. In Aristotelian Logic, you had only some sentences and conclusions that followed from those sentences. You had:

• Universal and affirmative sentences: All men are mortal;
• Particular and affirmative sentences: Some men are mortal;
• Universal and negative sentences: All gods are immortal;
• Particular and negative sentences: Some gods are immortal.

And then you also had particular sentences, such as “Socrates is a man.” And you applied logic in steps:

1. All men are mortal;
2. Socrates is a man;
3. Socrates is mortal.

When following Aristotelian Logic, you can’t believe propositions (1) and (2) above and disbelieve proposition (3). It is a logical consequence of the former.

Propositional Logic, then, is a structural form of Aristotelian Logic. Each proposition is represented by a symbol, and you operate on many propositions by using a number of operators. Because of the nature of this kind of logic, which will be clear soon, it is frequently called Propositional Calculus.

Propositional Logic is a system of reasoning. As such, it is not designed to, nor can it, tell the truth. It cannot reliably distinguish truth from falsehood on itself. All it does is take the things you already believe in (the axioms) and tell you what their consequences are. It is, of course, impossible to automatically infer all the consequences of everything you believe. There is no process that can compute all of them. However, logic does help you getting from A to B, when A is an axiom.

Therefore, we start with axioms which we know to be true (or, conversely, know to be false) and repeatedly apply the rules of the system to arrive at things that we should know.

Let’s be more concrete. Suppose I have a proposition P = ‘It is raining outside.’ That is a proposition that can either be true or false at any given time. However, knowing its truth or falsehood does not matter. Suppose we have the proposition Q = ‘The ground outside is wet.’ The propositions P and Q, then, are thus linked:

$P\rightarrow Q$

This is a proposition itself, and can be either true or false, depending on the particular P and Q we’re talking about. But what does it mean? It means (and is read) ‘if P then Q.’ Condition is a logical connection which states that, whenever the left-hand proposition (P, in this case) is true, so is the right-hand proposition (Q, in this case).

In the example given, for these specific P and Q, the proposition $P\rightarrow Q$ is true: ‘If it is raining outside then the ground outside is wet.’

A common representation of truth and falsehood in Propositional Calculus is 1 and 0 respectively. And we sometimes represent the meaning of our propositions by something called truth-tables. But I’ll talk about those later. Let’s develop further our connectives and operators.

• $P\rightarrow Q$: Conditional. If P then Q;
• $\bar P$: Negation. This unary operation creates a proposition that’s true whenever P is false, and false whenever P is true;
• $P\land Q$: Conjunction. This is a binary operation that’s true if and only if both P and Q are true;
• $P\lor Q$: Disjunction. This is a binary operation that’s true if and only if at least one of P or Q is true. If both are true this is also true.

No other rules are required. In fact, I’ll soon show that all of these four rules can be in fact derived by repeated application of a single rule. And even some of these operations are equivalent amongst themselves.

Let’s get back to logical implication $P\rightarrow Q$. This proposition can be true regardless of the independent values of P or Q. However, it creates a logical constraint on the mutual values of P and Q. What do I mean by that?

$\begin{array}{rl} 1. & P \rightarrow Q \\ 2. & P \\ \hline \therefore & Q \end{array}$

The above reasoning is called modus ponens. If I believe that $P\rightarrow Q$ is true and that P is also true, it is impossible for me to believe Q to be false. That is inconsistent. Therefore, we might create a truth-table for the proposition $P\rightarrow Q$ of which I spoke earlier.

Can you see at a glance why this table has these values? If P is true and Q is true, then $P\rightarrow Q$ is true, too. If P is true and Q is false, however, $P\rightarrow Q$ cannot be. I just said that: I cannot believe that P is true (‘It is raining outside.’) and Q is untrue (‘The ground outside is not wet.’) if I believe that $P\rightarrow Q$ is true (‘If it is raining outside then the ground outside is wet.’)

If P is false and Q is true, our proposition $P\rightarrow Q$ can still be true. Think again about the example: it is trivially true that ‘If it is raining outside then the ground outside is wet.’ However, just because it isn’t raining outside doesn’t mean the ground outside can’t be wet: ‘if it is not raining outside I cannot affirm that the ground outside is or isn’t wet.’ Someone could have just thrown a bucket of water on the ground and then we’d have that Q is true but P is not. And finally, if both are false, $P\rightarrow Q$ is still true for the same reason.

So the only combination of truth-values for P and Q that makes $P\rightarrow Q$ untrue is P true and Q false. Keep this result in mind, it will come up again soon.

The following simple truth table represent just the operation $\bar P$. Quite straightforward.

And then we have $P\land Q$ and $P\lor Q$:

Hmmm… now hold on just a minute. In the above $P\lor Q$ there is exactly one combination that yields false: P and Q both being false. But in the $P\rightarrow Q$ case, there is also one combination that yields false: P true and Q false. So $P\rightarrow Q$ has the exact same truth table as $\bar P\lor Q$:

Why is that? Because $P\lor Q$ is true when P being true implies Q being true. So if P is true and Q is false, $P\lor Q$ can’t be true. Now what about we make a table for $\bar Q\rightarrow \bar P$?

…again the same. So we have the following equivalences: $(P\rightarrow Q)\leftrightarrow (\bar Q\rightarrow \bar P)\leftrightarrow (\bar P\lor Q)$. And so this reasoning:

$\frac{P \to Q, \neg Q}{\therefore \neg P}$

is the “reverse” of modus ponens and is called modus tollens: if P implies Q and Q is false, then it cannot be the case that P is true.

Now hold on a minute. What does $\leftrightarrow$ mean? It’s the symmetric version of $\rightarrow$: $P\leftrightarrow Q$ means that ‘If P then Q and if Q then P.’ It is a stronger assertion, which has the following truth table:

Anyway, I’m digressing here. What I mean is that those three different propositions have the same truth tables, and are therefore equivalent. This equivalence means that whenever one is used the other can, too, without loss of meaning. Thus, as promised, that list of four rules can be reduced to a list of three rules, because $\rightarrow$ can be obtained from a clever combination of $\bar P$ and $\lor$.

—-

Okay, so far I’ve introduced the main rules and the truth tables. This is basic Propositional Logic. However, I haven’t actually given you any axioms in the system on which we can apply these rules.

Here’s the trick: there aren’t any. Other than the axioms which define the rules and link them with the truth-tables, Propositional Logic doesn’t deal with anything else. Rather, it asks you for your axioms and tells you what can be said about them.

And now I’m going to prove new rules which we can use as shortcuts when finding things out. For that, though, I’ll need a way of creating new truths based on the ones I already have. Hofstadter in GEB calls it a “fantasy.”

It goes like this: first, I assume something is an axiom. Then I apply the rules I already know. When I’m done, whatever conclusion I get will be a logical implication of the axiom I assumed. To use Hofstadter’s notation, all “fantasies” are going to start with a [ and end with a ]. Also, everything that’s true outside of a fantasy is also true inside it.

[

(1) $P\land Q$ : Axiom 1

(2) P : Definition of logical conjunction

]

(3) $(P\land Q) \rightarrow P$ : Result of fantasy

This is a very simple example. First, I opened a fantasy. Then, I invented an axiom. What does it mean, though, to invent a fantasy in this context? It means I take some proposition I like (in this case, the proposition I chose was $P\land Q$) and pretend it’s true until the end of the fantasy.

After that, I used the definition of logical conjunction to say that P is true. After all, I assumed that $P\land Q$ is true, and the definition of logical conjunction says that $P\land Q$ is true if and only if both P and Q are true at the same time. So while I was inside that fantasy where I just assumed $P\land Q$, P was necessarily true.

Then I ended the fantasy. After I end the fantasy, I can take the axiom $P\land Q$ and the conclusion P and say that the axiom necessarily implies the conclusion. So the rule of fantasy is a way of creating new rules inside Propositional Logic. This rule I derived $(P\land Q) \rightarrow P$ is called “Simplification.” It’s pretty obvious, really, but it’s just an example.

I’ll give another example of a nested fantasy.

[

(1) $(P \rightarrow Q)\land(Q\rightarrow R)$ : Axiom 1

(2) $(P \rightarrow Q)$ : Simplification of Axiom 1

(3) $(Q\rightarrow R)$ : Simplification of Axiom 1

[

(4) $P$ : Axiom 2

(5) $Q$ : Consequence of (2) and (4)

(6) $R$ : Consequence of (3) and (5)

]

(7) $P\rightarrow R$ : Result of fantasy’s axiom (4) and conclusion (6)

]

(8) $((P \rightarrow Q)\land(Q\rightarrow R))\rightarrow (P\rightarrow R)$ : Result of fantasy’s axiom (1) and conclusion (7)

Anything you prove with a fantasy is a theorem of Propositional Logic.

—-

Now we have two methods of proof of theoremhood in Propositional Calculus: truth tables and fantasies. If two propositions have the same truth table, they are equivalent; if you can use a fantasy to get from one proposition to another, the latter is a logical implication of the former. So whenever you want to prove the equivalence of propositions you use truth tables, and whenever you want to prove the implications of a proposition you use a fantasy. Now let’s prove a few nice things.

First, let’s invent a proposition $P\land Q$. In that case $\overline{(P\land Q)}$ is its negation. Now let’s find the truth table.

Now if you got the gist of it, you’ll see that the kind of binary truth table that only has one false value and three true ones is the truth table for logical conjunction ($\lor$). Therefore, $\overline{(P\land Q)}$ must be equivalent to some logical disjunction. And indeed, it is: you see, the proposition $\overline{(P\land Q)}$ is only true when either P or Q is false. It must be a logical disjunction between the negations of P and Q then!

This is the first De Morgan’s Theorem: $\overline{(P\land Q)} \leftrightarrow (\bar P\lor\bar Q)$. I’ll leave it to you to prove the second De Morgan’s Theorem: $\overline{(P\lor Q)} \leftrightarrow (\bar P\land\bar Q)$.

Now I’m going to use another truth table to prove a property of PL’s rules. For that, though, I’ll want a better notation than $\land$ and $\lor$: whenever I have the logical connective and ($\land$), I’ll replace it with a multiplication. So, for instance, $P\land Q$ = PQ. Whenever I have the logical connective or ($\lor$) I’ll replace it with an addition. So, for instance, $P \lor Q$ = P + Q. If you’ve read my posts on Bayesian Reasoning and Probability Theory you’ll see that that’s my preferred notation.

P(Q + R) is a logical conjunction of P and (Q + R). So whenever P is true and (Q + R) is true, P(Q + R) is, too. But when is (Q + R) true? When either Q or R or both are true. And therefore we have the above truth table. Now, you can interpret that under a different light:

Now we have a new proposition: PQ + PR. When is that true? When either PQ or PR or both are true. And again, PQ is true only when both P and Q are true, and PR is true only when both P and R are true. So in the table I inserted all parts needed to find out whether PQ + PR is true. And what did we find?

Well, the truth table for PQ + PR is exactly like the one for P(Q + R). This is called the distributive property. It’s reminiscent of maths’ property: if you have a logical conjunction over a logical disjunction, you can distribute the conjunction over the disjunction.

Now, a property that maths doesn’t have is that in PL, the “multiplication” distributes over the “addition”: P + (QR) = (P + Q) (P + R). I’ll leave that one for you to prove, too. Now you have enough tools to prove whatever’s provable within PL.

—-

I mentioned that it’s possible to have only one operand instead of the aforementioned four (conjunction, disjunction, negation, implication). I’ll prove you that now.

There are, in fact, two possible operands that, on their own, can reconstruct all of the above ones. They are the NAND and the NOR operands:

• $P\uparrow Q$ is the NAND operand. It is logically equivalent to $\overline{(P\land Q)}$.
• $P\downarrow Q$ is the NOR operand. It is logically equivalent to $\overline{(P\lor Q)}$.

So, suppose you forgot about conjunction, negation, etc. You only know… NAND. Can you recover them with only NAND? Certainly:

• $P\uparrow P\equiv \bar P$ gets negation.
• $(P\uparrow P)\uparrow (Q\uparrow Q) \equiv (P\lor Q)$ gets disjunction.
• $(P\uparrow Q)\uparrow (P\uparrow Q) \equiv (P\land Q)$ gets conjunction.

And of course, since we know implication is just a combination of negation and disjunction, we’re done. We can recover all of the regular propositional operands from NAND alone. I’ll leave it to you to prove that we can do the same with NOR.

—-

Remember when I said Propositional Logic is a natural extension/formalisation of Aristotelian Logic? Well, I lied. AL is still a little bit more… flexible than PL. That’s because PL is restricted in what it can prove to single sentences. I have the sentences P = ‘Socrates is a man’ and Q = ‘Socrates is mortal’ but I can’t really talk about properties of “all men” and stuff like that. That’s actually covered by First-Order Logic, of which I’m going to speak at a later time. Seeya!