Friday 26 September 2014

Week 3: Fancy Translations from English to Logic


Last week, we saw that a sentence in a natural language can be represented in the formal language of logic through predicates, implications and quantifiers.  Yet we can be a little fancier with our representations by introducing two new members to our zoo of logical symbols. 

Suppose that we want to represent these English statements in logic:

(1) Some student that is in CSC165 is both cool and likes math.
(2) All students that are CSC165 are either cool or like math.

Let $U$ be the set of all students.  Let $C(x)$ mean $x$ is in CSC165, $K(x)$ mean $x$ is cool and $M(x)$ mean $x$ likes math.  The conjunction symbol, which represents the English word “and”, and the disjunction symbol, which represents the word English “or”, allows the translation of statements (1) and (2) into logic:

                        (1) $\exists x \in U, C(x) \implies (K(x) \wedge M(x))$.
                        (2) $\forall x \in U, C(c) \implies (K(x) \vee M(x))$.

Now let us play a game of I-Spy.   See these statements:

                        (3) $\exists x \in U, C(x) \implies (K(x) \implies M(x))$.
                        (4) $\forall x \in U, C(x) \implies (K(x) \implies M(x))$.

I spy a nuance between statements (3) and (1) and statements (4) and (2).   What is this nuance?  It is the relation between predicates $K(x)$ and $M(x)$.  Replacing either the conjunction or disjunction symbol in a statement with an implication symbol changes the meaning of that statement.  Let us illustrate the difference between statements (1) and (3) and statements (2) and (4) with a CSC165 student named Bobby.

Bobby wants to take up the burden of satisfying statement (1).  Then he needs be cool and he has to like math.  Later Bobby decides that this is too much of a burden for him so he decides to satisfy statement (3) instead.  From last week`s post about implications, we know that he has a choice of either being uncool or keeping his fondness for math.  Hence, the implication is much more flexible than the conjunction.


Now Bobby wants to take up the burden of satisfying statement (2).  He campaigns to convince all his CSC165 classmates to either be cool or like math.  His classmates rebel and decide to neither be cool nor like math.  Yet Bobby is enterprising.  He decides to satisfy statement (4) instead.  Then he needs to get all his classmates to either be uncool or like math.  However, his CSC165 classmates are just as adept at defying Bobby and they decide to be both cool and dislike math.  Poor Bobby!  Hence, the implication and disjunction are different in how they are satisfied but they are the same in their flexibility.

Friday 19 September 2014

Week 2: Introducing... the Logical Zoo

The English Language


            Currently the most commonly used language in the developed world, the English language has a diverse vocabulary, a sophisticated grammar system and a rich history that dates back to the end of the Roman Empire.  Like all natural languages, English allows for ambiguity of expression.  Take a look at this sentence:
           
Panda mating fails: veterinarian takes over.

Either one of two things is being said:

(1) The veterinarian will investigate the pandas.
(2) The pandas will have to mate with the veterinarian.

Common sense is enough here to determine what the sentence-writer meant.  Yet there are occasions in which both interpretations are plausible.  What if you have a weird friend who said this to you:

"People are fashionably hungry unless they eat Satsumas"

Your friend means either one of two things:

(1) People that are fashionably hungry do not eat Satsumas.
(2) People that do not eat Satsumas are fashionably hungry.

Neither common sense nor the semantics of the English language tells us beyond doubt what your friend meant.  We need some other tool.


The Language of Logic


            Logic can solve the riddle of what your friend said.  The language of logic uses symbols to represent meaning just like English uses the alphabet the represent words.  Yet unlike English, logic communicates everything in terms of whether something is true or false.  The following table introduces common logical symbols:

Table of Logical Symbols for Dummies
Symbol
Meaning
Comments
$x, y, z, …$
Variable
A variable represents some real-world object.  It can be a person, word, number or any object you like.
$S, T, U, …$
Set
A set is an ordered collection of unique objects.  It can be a set of people, numbers, cars or any object you like.
$P(x), Q(x), R(x), …$
Predicate
A predicate is a function that maps some variable to the value “true” or the value “false”.  Think of it as telling the reader whether or not some real-world object has some attribute.
$\exists$
There Exists
A quantifier that conveys that at least one member of some set has some attribute.
$\forall$
For All
A quantifier that conveys that all members of some set have some characteristic.
$\implies$
If... then...
A composition of two sentences.  The first is an assumption, which is called the antecedent.  The second is a conclusion, called the consequent.  Its structure is as follows: if antecedent is true, then the consequent is true.
$\neg$
Negation
A negation is an operation that can be applied to a sentence.  A negated sentence is false if the original sentence is true and vice-versa.

These are all the symbols that we need to translate what your weird friend said from English to logic.  There is two mores hoops to jump however.  The English word “unless” is translated to logic as an implication that has a negated antecedent.  Additionally, since "unless" is in the middle of the sentence, then the overall sentence is in the form of "then... if...".  Now, we can translate the sentence:

Let $P$ be a set of all people and $H(x), S(x)$ be predicates with the following definitions:

$H(x): x$ is fashionably hungry
$S(x): x$ eats Satsumas

Then the sentence “People are fashionably hungry unless they eat Satsumas” is translated to logic as:

$\forall x \in P, \neg S(x) \implies H(x)$


The meaning of this logical statement in English is “People that do not eat Satsumas are fashionably hungry" so therefore, your weird friend meant (2).