Wednesday, June 27, 2007

The first chapter- truth tables, and the 'language of maths'.

I think I've been jumping from one topic to another, but I can't help that. We've previously discussed the importance of proofs and also proof by induction. (Analysis can wait for a while). From the comments in that post I've realised that knowing the language of maths is crucial. If you're going to stay in some other country then it's necessary that you can communicate with the residents of that place. In certain languages pronunciation is crucial. If you say a word differently it can be taken in some other context. The same applies to the language of maths. It's important that we know when we can use certain things and basically understand what them things are.

Definition1
A declarative sentence is a sentence that ‘declares’ a fact or facts.

A statement is an assertion which is typically expressed by a declarative sentence. Examples of declarative sentences are:

'The grass is green.
1=0.
\pi=100'

Then we move onto propositions.

Definition1
A proposition is a declarative sentence to which we can assign a truth value of either true or false, but not both.

All of the examples above are propositions. 'The grass is green' is true; 1=0 and \pi=100 are false. Declarative sentences can also be predicates. A predicate is of the type: m < n. They involve free variables, and once these are given values they become propositions e.g. if m=10 and n=9 then 10 < 9 is a proposition (a false one). From now on I will use the word statement to mean either a proposition or predicate. (Simply because it's smaller than 'declarative sentence'!)

Generally propositions or predicates are denoted by P, Q, R, S or p, q, r, s. Simple propositions are combined by logical connectives to form composite statements (arguments), which can be quite complex at times. So to deduce the truth value of a complicated statement we have to determine the truth value of the simple statements which it is made up off. In this post we'll be looking at the logical connectives 'and', 'or' and 'not' (implications will be done next). Initially my all famous 'shrek face' may surface however it is vital that these are understood since they may(do?) aid your understanding of other things like proofs.

Now in different text books and notes you'll find various notation. For propositions p, q:

  • p \wedge q is the proposition 'p and q i.e. the conjunction of p and q.
  • p \vee q is the proposition 'p or q or both' i.e. the disjunction of p and q or the inclusive or.
  • p' or '~p' is the proposition 'not p'. i.e the negation.
I won't be using that notation, but you may come across it. 'P and Q', 'P or Q' and 'not P' will be what I'll be using. Moving on:

Definition1
A propositional form is an expression involving logical variables (i.e. the letters denoting propositions) and connectives such that, if all the variables are replaced by propositions then the form becomes a proposition.

An example of propositional form is '(P and Q) or R' (for propositions P, Q and R). {(P \wedge Q) \vee R} and(?) 'P and Q'.

Truth tables are used to give propositional forms truth-values (the propositions which are used naturally have truth values). I believe that there is a standard way of writing the truth tables, and if you have an exam on such material it's important to know how your lecturer likes them to be, in fear of being marked incorrectly.

The truth tables for 'P or Q', 'P and Q' and 'not P' follow respectively:

Table 1
Table 2
Table 3
So if we were to look at the second line in table one, it indicates that if P was a true statement and Q was a false statement, then the statement 'P or Q 'is true. As I've said in a previous post, in everyday speech we tend to 'or' in the exclusive sense, eg do you want the paper or the pen? However, in maths we use it inclusively, and you probably will have to mention otherwise. 'Or' occurs in many mathematical statements and we never realise this. We know that a \le b, means that a is less than or equal to b, but notice the hidden or there. The inequality a \le b is not telling us that a single inequality is true, but it's saying that one or both of the following are true: a < b, or a=b. Which is why both the statements 9 \le 10 \text { and } 10 \le 10 are true. (from the 'or' truth table').

From table two, for an 'and' statement to be true, both the statements P and Q must be true. Once again, we probably have used this connective without being aware of it. . The following: 2 <>2 and e<3, hence the 'hidden' and is there. If one of the statements in false then 'P and Q' is false.

The negation of a statement is true when the statement itself is false, as can be seen from table 3. To negate a statement P, we can simply write 'not P' or we can usually obtain a negation by sticking 'not' at the start of the sentence. However, sometimes we have to be careful as to what the actual sentence is saying. I believe to fully be able to negate sentences like 'all my pens are in the pencil case' you have to have some understanding of quantifiers (or be good with words!). I think the negation to that is, 'One of my pen is not in the pencil case' since for the statement 'not' to be true we only need one counterexample you could say. (Sorry if I'm not making sense- I'm still a little iffy with this whole business!). So a question: negate 'If no one else cares, then I don't either.' (Yes you guessed it- I couldn't). A strategy is required for sentences with words like 'all' and 'every', and if I do ever post on quantifiers this will surely be resurrected.

It's important to understand negation and this whole 'not' business, since I think it helps explain proof by contradiction. I wouldn't worry so much about quantifiers at the moment, but they did help me to some extent. Negations will be looked at in more detail in the 'chapter' on proofs. [Am I not shutting up about negations because I couldn't get my head around them? All I'll say is: negations- to be continued... and leave it at that!]

Before I do an example, I forgot to mention that two propositional forms are equivalent if they have the same truth table. I'll end by doing two examples. One example1 with three statements and the second a truth table for P and (not Q).

Example 11
Write the truth table for ((not P) or Q) and (not R). (you might want to try it before scrolling down! ;) )

First we draw a table with columns P, Q and R as follows:
I suppose that's the 'generic' way of assigning truth values with three statements involved. Now we look to the question and add the columns which we require i.e. first '(not P)', then '(not P) or Q' and then '(not R)'. Then make a final column which has the question in it. E.g. the first row would be found by the following process.

Since P has the truth value T, then (not P) will be F. (same applies for (not R). So looking at '(not P) or Q', with truth values 'F' and 'T' we see from table 1 that this corresponds to row three, and hence the statement '(not P) or Q' is true. Therefore, looking at the question we see that we effectively have a conjunction with truth values 'T' and 'F' (i.e. ((not P) or Q) is a true statement and (not R) is false). From table 2, row two, the truth value for this statement is F, giving:

And so the rest of the table is completed in the same way:


Posting at 3:30am is never a good idea, and so I will do example 2 tomorrow (I mean later on in the day)! You may notice that I started this post 'yesterday', but that was a busy day indeed. Obviously, due to the time my excuse for errors comes into place so once again please do let me know of any errors.(Reading over it at this time doesn't make sense!) BTW, I only intend to post the content of our first weeks lectures and after that I will go back to analysis. I'm just hopefully trying to show what is is necessary for us to understand before we go further. Hope I haven't made too stupid a mistake, or missed something out!

EDIT 1: time- too early. The darn post wouldn't post because of conflict of html tags. :( Using the strict inequalities got it in a jumble! So for any bloggers out there never use <

EDIT 2: editing this post has messed up the html tags again. :( I will just post the tex code for the second example in the comments. :( (I've lost bits and bobs of the post!)

1. Dr C's notes.
2. Bits and bobs from my lecture notes and Dr E's book.

12 comments:

beans said...

Photobucket doesn't seem to be working so I'll post the tex code:

\begin{array}{|cc|c|c|} \hline
P & Q & (\text{not }Q) & P\text{ and (not }Q) \\\hline
T & T & F & F \\
T & F & T & T \\
F & T & F & F \\
F & F & T & F\\\hline

(You can view the table if you copy and paste that into the texer:
http://www.artofproblemsolving.com/LaTeX/AoPS_L_TeXer.php)

steve said...

Guess what? A slight change will allow you to draw the same tables in your blog :)

The problem is the system doesn't like \hline but the good news is that it loves \cline.
Replace all \hline by \cline{1-4} and it works!

\cline{n-m} means draw a horizontal line from column n to column m so is more general.

Blogger also lets you get rid of the border round all images if you prefer that by editing the template.

beans said...

*high five* :D hehe, I did get quite frustrated when I realised \hline wouldn't work. (I'm convinced that it did work on one occasion and so stubbornly kept on trying it!)

Thanks! BTW what do I look out for when editing the html code of the blog, to get rid of the borders? (might as well do a little bit of experimenting). I saw: img {
border: none;
}
but going from this mornings experience with html codes I don't trust myself to edit anything!

beans said...

Oops- also realised that if you did copy and paste that code into the texer I forgot the last line. Sorry. :o

It is:
\begin{array}{|cc|c|c|} \cline{1-4}
P & Q & (\text{not }Q) & P\text{ and (not }Q) \\\cline{1-4}
T & T & F & F \\
T & F & T & T \\
F & T & F & F \\
F & F & T & F\\\cline{1-4}
\end{array}

(I'd forgetten the \end{array} on the previous one).

steve said...

To change the border round the images:
In Blogger go to Settings, Edit HTML.
In the box copy and save all the text (just in case!).
Look for Posts about half-way down then look for:
.post img {
padding:4px;
border:1px solid $bordercolor;
}
Change 1px to 0px
Use Preview to check all is OK, then Save Template

beans said...

It says:

.post img {
padding: 6px;
border-top: 1px solid #ddd;
border-left: 1px solid #ddd;
border-bottom: 1px solid #c0c0c0;
border-right: 1px solid #c0c0c0;
}

I've made all the 1px's to zero, but what exactly does the padding do?

(Wow- just seen the preview and it looks much better without the borders! Thanks.)

Anonymous said...

stop being a geek and have a rest . . .or ami the only one who does no work over the ols and everybody else is still revising last years material so they are on top form in september

beans said...

What do yu mean stop being a geek? I am by no means working- I'm blogging and enjoying doing so. The topics which I've been blogging about are those which I know about and enjoyed.

I have yet to 'revise' last years material (well the bits I intend to for PASS) and knowing last years material doesn't imply that I'm going to be in 'top form' in September. It'll just mean that I'm comfortable with what I've learnt. Whether or not you do work is your choice. I don't work by looking at what others around me are doing- I know what I have to do.

Also, I don't understand what you mean- a rest from what??

Like Jake said, 'university (for students) isn't work'. I've always loved doing maths and doing it is by no means doing a job. I don't know how many people you'll find 'working' in the holidays. :p

The holidays are an opportunity for me to look into maths which I couldn't during the year. (stuff about rubiks cubes etc). Funnily enough you sound like Noddy (are you Noddy?!!) I always enjoy winding Noddy about by saying that my holidays are going to be top and great fun because I'm going to be doing maths. :D I still stand by that claim! (hehe)

beans said...

BTW out of interest are you at university? If so, then why did you choose to do the degree that you're doing?

steve said...

I've made all the 1px's to zero, but what exactly does the padding do?

Yes it's different from what I've said as you are using a different template. But you've done the right thing. The padding is the distance between the image and surrounding text. If you look at the image for p or q you'll see a gap before 'is the proposition'. Try reducing the 6px and use the preview to find out what value (or even 0) looks best.

steve said...

Having removed some of the padding the images have now shifted down slightly, so you may need to adjust the LaTeX style="vertical-align:-4pt;" to say -2pt or whatever looks right to you.

beans said...

Ah yes, I didn't realise that. (I could always play around with the padding number or use the first link that you gave me.)

A test post is required. :) Maybe I could make it look like it's on a line!