Part 2 - solving problems as human nature

In the last chapter, we have a discussion on some abstract logic concepts, especially the difference between (syntactic) proof with rules and (semantic) check with evaluation.

But we can not go far without even knowing what propositional logic is. Propositional logic is a logic branch, which focuses on reasoning with atom statements and their simple combinations.

For example, ’it is raining outside and I am taking an umbrella’ can be abstracted to be a single statement, and it will be either right or wrong. But it does not give much information to look at a single statement.

Luckily, propositional logic allows us to see it in a slightly different way. I will say ’it is raining outside’ is a single statement, and ’I am taking an umbrella’ is another one. They are connected with a conjungation, ’and’, to form a compound statement.

Now, if I say the compound statement is true, are the two single ones true or false? What if they are connected by ’or‘?

Good! In logic, we usually need to separate a statement in the logic system, and one out of the system and in we humans’ mind.

In the system, we have a set of statements, or literals or variables, like ’it is raining outside’ and ’I am taking an umbrella’; we have some conjungations, or operators, like ’and’, ’or,’ and ’not’; and we have deducing rules, compound statements, etc.

However, note that the operators do not all connect two things together. A not only affect one statement. In general, an operator is a mixer, you add any number of items, and get one thing out.

As to the logical or, people agree that it produces ‘true’ if one or two statements are true. In the case above, we only know it is raining outside and I am taking an umbrella are not both false.

Semantically, an operator is with an enumeration of values of its ingredients. Who can tell me how many possibilities are values for or?

It is effective. We can now even get a good representation of the puzzle in chapter 1!

However, as humans, we mostly want to derive conclusions of interest with simple rules. What are the most elegant rules in your experience?

‘You stole my answer!’

Am I going to say that? If you think I would spend the whole class introducing these laws, then you are wrong. They are by no means equivalence to Newton’s laws in physics anyway.

For those who have not heard ‘the laws of thought’, I’m giving a brief yet rough introduction.

• The law of identity states that, you should stick to something where you admitted it.

• The law of (non-)contradiction says, some statement can not be both true or false in the same place.

• The law of excluded middle tells us that a statement should be nothing else than true or false.

However, these laws are mostly related to simple propositional logic, while modern logicians focus more on other things. Even inside propositional logic itself, there are more useful rules to reason with.

For example, some of you might see that there is a redundency to provide 3 operators in our system. A rule widely known as “De Morgan rule” states that, given two arbitrary statement A and B,

• A OR B
  is equivalent to
  NOT ((NOT A) AND (NOT B)).

Thus, any occurrence of OR could be replaced by AND and NOT.

Then the following should come a little harder, belt up!

We are introducing an important rule called “resolution”:

is equivalent to

. If B and C are compound, they should not contain any same single variables.

Or if it seems too overwhelming, there is a plain-text example of it, given

• if it is raining outside then I am taking an umbrella

• if not it is raining outside then I am wearing a coat

, we will have

• either I am taking an umbrella or I am wearing a coat

. Note that this if-statement is one of the explanations of the formula. Please check that after class.

Using the resolution rule, let’s actually derive something from the puzzle we see before.

Let’s introduce propositional variables A, B and C, each representing the sentences of kid 1, 2 and 3 is a truth, and a variable D to indicate “kid 3 broke the window”.

In this practice, we see how hard reasoning is, and simply think when there are thousands of variables in a more practical scene! Next chapter, we are looking at a more mechanical approach. You can also halt and refer to our appendix on various logical systems.

Exercise:

1. the ‘and’ operator can be replaced with ‘or’ and ‘not’, and can ‘or’ be replaced by ‘and’ and ‘not’? What about ‘not’ by ‘and’ and ‘or’? Is there an operator that can alone represent them all?

2. explain De Morgan law to your friends in a plain manner.