Propositional Logic Using Algebra

As this wiki Propositional Logic explains, propositions are treated as atomic units. Such propositions can be denoted by letters such as \(P, Q, R,...\), which have a value of TRUE or FALSE. Expressions can be built up using the three primary logical operations AND, OR and NOT, commonly represented by symbols \(\wedge\), \(\vee\), and \(\sim\) (or \(\neg\)). and such expressions can be related by or even include conditionals and biconditionals represented by symbols \(\rightarrow \) and \(\leftrightarrow\). So, for example, we have the expression

\(\left( P\wedge Q \right) \rightarrow P\)

which is a logical identity, "decomposing a conjunction", meaning that if \(\left( P\wedge Q \right)\) is true, then \(P\) is true. We can have something more complicated,
such as

\(\left( P\leftrightarrow Q \right) \leftrightarrow \left( \left( P\rightarrow Q \right)\wedge \left( Q\rightarrow P \right) \right) \)

which in fact is the "definiton of the biconditional" \(\leftrightarrow\) being the symbol. Propositional Logic explains more in detail, and, in practice, one is expected to make use of such logical identities to prove any expression to be true or not. This can be a cumbersome exercise, for one not familiar working with this.

It seems much like algebra, so is there a way to work these things out algebraically? Yes, sort of, one can. First of all, all propositions and expressions necessarily have a value of either TRUE or FALSE. We can use numeric values \(1\) and \(0\) to mean the same thing (although other schemes are possible), and for this wiki, lowercase letters \(p, q, r...\) shall denote propositions and expressions that have numeric values. We can immediately see that AND and NOT are simply

\(P\wedge Q\Longleftrightarrow pq\)
\(\sim P\Longleftrightarrow 1-p\)

where the symbol \(\Longleftrightarrow\) means similar, or homologous, operations. Now, but the OR operation is a bit more cumbersome

\(\left( P\vee Q \right) \Longleftrightarrow p+q-pq\)

We round this out with the conditional and biconditional

\(\left( P\rightarrow Q \right) \leftrightarrow \left( \sim P\vee Q \right) \)
\(\left( \sim P\vee Q \right) \Longleftrightarrow 1-p+pq\)

\(\left( P\leftrightarrow Q \right) \leftrightarrow \left( \sim P\vee Q \right) \wedge \left( P\vee \sim Q \right) \)
\(\left( \sim P\vee Q \right) \wedge \left( P\vee \sim Q \right) \Longleftrightarrow 1-p-q+2pq\)

Now, let's try to put this into practice, say, Modus Ponens. Is it true?

\(\left( \left( P\rightarrow Q \right) \wedge P \right) \rightarrow Q\)

Using the algebraic equivalents given above, we can work out the corresponding algebraic expression

\(\left( \left( P\rightarrow Q \right) \wedge P \right) \rightarrow Q\Longleftrightarrow 1-p+{ p }^{ 2 }+pq-2{ p }^{ 2 }q+{ p }^{ 2 }{ q }^{ 2 }\)

Now, but here's we depart from usual algebraic convention. Every proposition and expression always have a value of either TRUE or FALSE, either \(1\) or \(0\). This means that all the exponents in the algebraic expression can be reduced to \(1\), and we're left with

\(1-p+{ p }+pq-2{ p }q+{ p }{ q }=1\)

which means it's always true, and therefore a logical identity.

While this "trick" could be a handy way of double-checking logical identities or working out complicated combinations of logic gates (see Logic Gates), this approach helps one understand that even a "If ... therefore ...." statement can be represented by a logical gate, as well as biconditionals. This puts all of these things on an equal footing, so that conditionals and biconditionals are not fundamentally any different from logical operations.

Example Question 1

DeMorgan's Law

\(\sim \left( P\vee Q \right) \leftrightarrow (\sim P\wedge \sim Q)\)

Find the equivalent algebraic expression for the logical expressions on both sides of the bicondtional.

Ans: \(1-p-q+pq\quad \)

Note that, when worked out, the algebraic form yields the same truth table as the logical expressions on either side of the biconditional, if we say that \(TRUE \Longleftrightarrow 1\) and \(FALSE \Longleftrightarrow 0\).

Also note that had the problem asked for the equivalent algebraic expression for the entire logical expression, including the biconditional, the result would have simply been \(1\), as it is a well-known logical identity.

Helpful note: Given an arbitrary truth table, say, of two variables \(P\) and \(Q\), the logical expression yielding this truth table can easily be found by performing an \(OR\) operation on all the instances of \(TRUE\), each one being an \(AND\) expression based on its location, each of which are \(\sim P \wedge \sim Q\), \(\sim P \wedge Q\), \(P \wedge \sim Q\), \(P \wedge Q\). So, for instance, for the biconditional, defined by a truth table where if \(P\) and \(Q\) are both \(TRUE\) or \(FALSE\), it returns \(TRUE\), otherwise it returns \(FALSE\), to generate the logical expression we simply write out

\(\left( \sim P\wedge \sim Q \right) \vee \left( P\wedge Q \right) \)

This might look different from the expression used above for the same thing, but in fact both are logically equivalent, and have the same simplest algebraic expression, which is \(1-p-q+2pq\).

This method of finding logical expressions for arbitrary truth tables can be generalized for any number of variables.

Here are algebraic equivalents for commonly used logic gates

\(NOT\Longleftrightarrow 1–p\)
\(AND\Longleftrightarrow pq\)
\(OR\Longleftrightarrow p+q-pq\)
\(NAND\Longleftrightarrow 1-pq\)
\(NOR\Longleftrightarrow 1-p-q+pq\)
\(XOR\Longleftrightarrow p+q-2pq\)
\(XNOR\Longleftrightarrow 1-p-q+2pq\)

so that it can be said that a biconditional is logically the same as \(XNOR\). Meanwhile, a conditional doesn't correspond to any of the classic logic gates, as it is asymmetrical with respect to the two inputs, having the algebraic equivalent of \(1-p+pq\).