code and the oracular

Propositional Logic and some Tautologies

with 4 comments

In the quest for the ultimate chatbot one may be well advised to take a diversion into formal logic. There are several types of logics but the simplest is usually known as “Propositional Logic”. I have a recommended book I am looking at called “Logic” by Wilfred Hodges.

At one point in the book the author gives a list of tautologies. I am interested by these because they encapsulate some of the self evident facts of reasoning. Any statement can be proved if it can be reduced to a tautology. Before I show the list to you we need to decide on notation. I have stuck with the basic options that html gives you for these. You could use LaTeX but it is more work.

The symbols are as follows

implication ->
equivalence <->
not ~ ˜
and &
or +
grouping ‘(‘,’)’ (,)

If you are used to writing code then most of this is common sense, since it is the hidden process behond Boolean variables and and, or, not, True, False etc in Python or any language. Still fun though !

I could point out that there are an infinite number of tautologies. If we think of the logical symbols as words in a language there is no limit to the length of a given statement in this language. But there are a finite number of the shortest and most memorable ones !

In logic we usually represent a proposition by a capital letter such as A or B, P or Q etc. Thus propositions can be combined into more complex statements by using the symbols above.

A common example would be as follows

P = “socrates is a man”
Q = “all men are mortal”
R = “socrates is mortal”

and the implication of P and Q taken together is R, so that in symbols it is written

(P ∧ Q) → R

It’s quite fun to play around with this stuff and come up with your own statements. It’s like writing code, and of course, as we’ve seen, Prolog is a bit like that code. Prolog is actually an embodiment of Predicate Logic or First Order Logic, which is richer and more powerful than propositional logic.

Here are the tautologies Hodges gives, see if you can work through and ‘get’ each one:

˜(P ∧ ˜P)
(P ∨ ˜P)
(P ↔ ˜˜P)
((P ∨ Q) ↔ ˜(˜P ∧ ˜Q))
((P ∨ Q) ↔ (˜P → Q))
((P ∨ Q) ↔ (Q ∨ P))
(((P ∨ Q) ∨ R) ↔ (P ∨ (Q ∨ R)))
((P ∨ P) ↔ P)
(P → (P ∨ Q))
((P → R) → ((Q → R) → ((P ∨ Q) → R)))
(˜P → ((P ∨ Q) ↔ Q))
((P ∧ Q) ↔ ˜(˜P ∨ ˜Q))
((P ∧ Q) ↔ ˜(P → ˜Q))
((P ∧ Q) ↔ (Q ∧ P))
(((P ∧ Q) ∧ R) ↔ (P ∧ (Q ∧ R)))
((P ∧ P) → P)
((P ∧ Q) → P)
((P ∧ Q) → Q)
(P → (Q → (P ∧ Q)))
((P → Q) → ((P → R) → (P → (Q ∧ R))))
(P → ((P ∧ Q) ↔ Q))
((P ∧ (Q ∨ P)) ↔ P)
((P ∨ (Q ∧ P)) ↔ P)
((P ∧ (Q ∨ R) ↔ ((P ∧ Q) ∨ (P ∧ R)))
((P ∨ (Q ∧ R)) ↔ ((P ∨ Q) ∧ (P ∨ R)))
(((P ∨ Q) ∧ ˜P) → Q)
(P ↔ ((P ∧ Q) ∨ (P ∧ ˜Q)))
(P ↔ ((P ∨ Q) ∧ (P ∨ ˜Q)))
((P → Q) ↔ (˜P ∨ Q))
((P → Q) ↔ ˜(P ∧ ˜Q))
(P → P)
(P → (Q → P))
(((P → Q) → P) → P)
((P → (Q → R)) → ((P → Q) → (P → R)))
((P → Q) → ((Q → R) → (P → R)))
(˜P → (P → Q))
((˜Q → ˜P) → (P → Q))
((P → (Q → R) ↔ ((P ∧ Q) → R))
((P ↔ Q) ↔ ((P ∧ Q) ∨ (˜P ∧ ˜Q)))
((P ↔ Q) ↔ (˜(P ∧ ˜Q) ∧ ˜(˜P ∧ Q)))
((P ↔ Q) ↔ ((P → Q) ∧ (Q → P)))
(P ↔ P)
((P ↔ Q) → (P → Q))
((P ↔ Q) ↔ (Q ↔ P))
((P ↔ Q) → ((Q ↔ R) → (P ↔ R)))
((P ↔ Q) ↔ (˜P ↔ ˜Q))
((P ↔ Q) ↔ ˜(P ↔ ˜Q))

Try and create “composite” tautologies by combining some of these and you’ll start to get a sense of how the universe of logical statements is infinite ! We sometimes find our ways though. In that sense isn’t formal logic a kind of compression of some aspects of language. This is why it is powerful and even aesthetically beautiful – because the compression is such a highly effective one. Is it lossless though ? I don’t understand but I presume the answer to that question may have some bearing on the future of the NLP project. Can we reduce every statement in language to a series of triples ? Triples are nice because they can be represented as a labelled graph, but what if the gods were more perverse ?


Written by Luke Dunn

September 13, 2010 at 5:20 pm

4 Responses

Subscribe to comments with RSS.

  1. To prove that one can form as many tautologies as one can form natural numbers, you only need 1. the rule of substitution, 2. a tautology, 3. a method to check and see if any string is either true or false (you don’t need to actually determine it’s truth value), and 4. mathematical induction (which you have on N anyways). At least if my reasoning works…

    Doug Spoonwood

    September 30, 2010 at 2:27 am

  2. Wed. Sept. 29, 2010

    Doug Spoonwood

    September 30, 2010 at 2:27 am

  3. Seems Wilfred Hodge has some legacy ! ……
    Is it the same person ? I guess so ! …… or otherwise the Hodges are a family like the Bernoullis ….


    Arkapravo Bhaumik

    October 20, 2010 at 7:06 am

  4. アベイシング

    エイプ ブランド

    September 12, 2013 at 1:45 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: