0.3 Discrete structures logic  (Page 4/23)

For instance, instead of saying "If she smiles then she is happy", we can say "If she smiles, she is happy", "She is happy whenever she smiles", "She smiles only if she is happy" etc. without changing their truth values.

"Only if" can be translated as "then". For example, "She smiles only if she is happy" is equivalent to "If she smiles, then she is happy".

Note that "She smiles only if she is happy" means "If she is not happy, she does not smile", which is the contrapositive of "If she smiles, she is happy". You can also look at it this way: "She smiles only if she is happy" means "She smiles only when she is happy". So any time you see her smile you know she is happy. Hence "If she smiles, then she is happy". Thus they are logically equivalent.

Also "If she smiles, she is happy" is equivalent to "It is necessary for her to smile that she is happy". For "If she smiles, she is happy" means "If she smiles, she is always happy". That is, she never fails to be happy when she smiles. "Being happy" is inevitable consequence/necessity of "smile". Thus if "being happy" is missing, then "smile" can not be there either. "Being happy" is necessary "for her to smile" or equivalently "It is necessary for her to smile that she is happy".

From english to proposition

As we are going to see in the next section, reasoning is done on propositions using inference rules. For example, if the two propositions "if it snows, then the school is closed", and "it snows" are true, then we can conclude that "the school is closed" is true. In everyday life, that is how we reason.

To check the correctness of reasoning, we must check whether or not rules of inference have been followed to draw the conclusion from the premises. However, for reasoning in English or in general for reasoning in a natural language, that is not necessarily straightforward and it often encounters some difficulties. Firstly, connectives are not necessarily easily identified as we can get a flavor of that from the previous topic on variations of if_then statements. Secondly, if the argument becomes complicated involving many statements in a number of different forms twisted and tangled up, it can easily get out of hand unless it is simplified in some way.

One solution for that is to use symbols (and mechanize it). Each sentence is represented by symbols representing building block sentences, and connectives. For example, if P represents "it snows" and Q represents "the school is closed", then the previous argument can be expressed as

[ [ P → Q ] ⋀ P ]→ Q,

or

P → Q

P

-----------------------------

Q This representation is concise, much simpler and much easier to deal with. In addition today there are a number of automatic reasoning systems and we can verify our arguments in symbolic form using them. One such system called TPS is used for reasoning exercises in this course. For example, we can check the correctness of our argument using it.

To convert English statements into a symbolic form, we restate the given statements using the building block sentences, those for which symbols are given, and the connectives of propositional logic (not, and, or, if_then, if_and_only_if), and then substitute the symbols for the building blocks and the connectives. For example, let P be the proposition "It is snowing", Q be the proposition "I will go the beach", and R be the proposition "I have time".