Feb 18 13:15:45 well, let's begin with this first Logic lecture. Feb 18 13:15:45 First of all, the word "logic" comes from the greek word "logos". Feb 18 13:15:45 "logos" is usually translated as "word", and, indeed, logic studies 'speeches', Feb 18 13:15:45 and, more particularly, 'reasonings' Feb 18 13:15:45 So, first of all, Feb 18 13:15:45 we'll study 'sentential logic'. Feb 18 13:15:45 We use the term of 'statement', or 'proposition' for an declarative sentence. Feb 18 13:15:45 For example, these are statements : Feb 18 13:15:45 Today is Saturday. Feb 18 13:15:45 I live in France. Feb 18 13:16:29 But, sometimes, a statement can be made of two 'simple' statements, for example : Feb 18 13:17:00 I either can code in C++ or I can code in PHP. Feb 18 13:17:46 You see that what I've written is a statement, since it's true, but, it's made of two 'single' statements, namely : Feb 18 13:17:57 'I can code in C++' Feb 18 13:17:58 and Feb 18 13:18:05 'I can code in PHP' Feb 18 13:18:58 In propositional logic, there are connective words, such as "and", "or", etc. Feb 18 13:19:38 An example of logical sentence is the 'syllogism'. Feb 18 13:19:56 I'll just recall the well-known example : Feb 18 13:20:05 Men are mortals. Feb 18 13:20:13 Socrates is mortal. Feb 18 13:20:21 So, Socrates is a man. Feb 18 13:20:36 This is a syllogism. Feb 18 13:20:48 And, you can see its structure : Feb 18 13:20:58 A statement Feb 18 13:21:05 An 'if' condition Feb 18 13:21:12 A 'then' condition Feb 18 13:21:46 this 'if', 'then' structure, is called an implication, and, it's denoted by the symbol '==>' Feb 18 13:22:19 This is a first example of logic sign. Feb 18 13:22:27 What are others? Feb 18 13:23:15 well, there are : Feb 18 13:24:07 <==>, which is read 'if and only if' Feb 18 13:24:18 for example : Feb 18 13:24:33 2 + x = 4 <==> x = 2 Feb 18 13:24:47 * qwertydawom sets mode -m #lecture Feb 18 13:24:55 no problem thus far? Feb 18 13:24:59 well Feb 18 13:25:01 hehe Feb 18 13:25:14 where do we use these logical operators? Feb 18 13:25:45 er Feb 18 13:25:47 logic signs Feb 18 13:26:16 isn't logic useless? Feb 18 13:26:19 for example in a math proof Feb 18 13:26:28 logic is used when you code ;) Feb 18 13:26:43 what are those 'or', 'and', 'xor', etc. Feb 18 13:26:49 Logic operators. Feb 18 13:27:08 They help to communicate. Feb 18 13:27:09 yeah Feb 18 13:27:12 But according to Godel's theorem, all statements cannot be proven through logic alone. Feb 18 13:27:24 we haven't gotten that far yet ;) Feb 18 13:27:50 whats the discussion about Feb 18 13:28:32 indeed, Godel's undecidability will be discussed in another lecture ;) Feb 18 13:28:32 logic Feb 18 13:28:45 Logic Lecture, Part 1, by qwertydawon [ 9 PM GMT +0 on Saturday, February 18th 2006 ] <---- Feb 18 13:28:49 undecidability theorem* Feb 18 13:28:57 We can't decide. Feb 18 13:29:32 let's stick with this lecture for now please. Future lectures will be given as, uhm, _future_ lectures :) Feb 18 13:29:45 * qwertydawom sets mode +m #lecture Feb 18 13:30:25 Well, the study of Logic as a separate discipline began with Aristote. Feb 18 13:30:57 He introduced 'quantifiers', such as 'all', 'some', etc. Feb 18 13:31:23 These quantifiers do not belong to propositional logic though. Feb 18 13:32:01 But! in his writings, Aristote clarified two main things in propositional logic. Feb 18 13:32:48 The first one says that every proposition is either 'true' or 'false'. Feb 18 13:33:15 And, the second thing is that no proposition can be both 'true' and 'false'. Feb 18 13:34:08 * qwertydawom gives voice to riftor Feb 18 13:34:37 But, a deeper approach on the logic operators was made by the Stoicians (philosophers) Feb 18 13:35:45 Why? Because noone ignores that there were great orators at the time. Feb 18 13:35:53 sorry I'm late! Feb 18 13:36:32 And, to make a good speech, you have to use these links. Feb 18 13:37:21 Well, in fact, until the 19th century, logic was only used in speeches. Feb 18 13:38:07 But, in the 19th century, the 'symbolic logic' has born, thanks to 'De Morgan'. Feb 18 13:38:27 And... the so-known "George Boole" Feb 18 13:38:54 Boole introduced a math style in logic. Feb 18 13:39:29 Indeed, he's used '1' to represent the 'universal class' and '0' for the empty class. Feb 18 13:39:38 1 and 0, rings a bell? :) Feb 18 13:39:53 Yeah, that's thanks to Boolean logic that computers work! Feb 18 13:39:57 * qwertydawom sets mode -m #lecture Feb 18 13:40:12 any comments? Feb 18 13:40:24 good to go :) Feb 18 13:40:29 which stuff have you covered so far? Feb 18 13:40:35 'ello Feb 18 13:41:04 already done? Feb 18 13:41:13 not much riftor, just an intro on what 'propositional logic' was at the time of the greeks ;) Feb 18 13:41:15 immortal, no. Feb 18 13:41:21 aha okay Feb 18 13:41:28 you going to get to propositional logic operators now? Feb 18 13:41:49 Well, I've already introduced 'and', 'or'. Feb 18 13:42:12 You forgot `not', Feb 18 13:42:24 okay cool :D Feb 18 13:43:13 so.. Feb 18 13:43:20 are we ready to continue? :P Feb 18 13:43:23 * qwertydawom sets mode +m #lecture Feb 18 13:44:33 Okay Feb 18 13:44:44 so lets look at some propositional logic operators eb 18 13:44:51 some of you will probably have seen these before in programming Feb 18 13:44:56 but I will go through them anyway Feb 18 13:45:48 As qwerty was saying, boole suggested the use of 1 to mean the "universal class" and 0 to mean the empty class. These can also be thought of as True (1) and False (0) Feb 18 13:46:04 The direct opposite of True is False, and the direct opposite of False is True. Feb 18 13:46:50 The "not" operation is used to switch between the two Feb 18 13:47:01 so "not True" = "False" and "not False" = "True" Feb 18 13:47:24 fairly obvious stuff, and in a few languages this is represented with an exclaimition point Feb 18 13:47:31 e.g. !true = false Feb 18 13:47:33 !false = true Feb 18 13:47:34 great Feb 18 13:47:37 now onto "and" Feb 18 13:47:53 and can be thought of as a function that takes two inputs, and has one output Feb 18 13:48:08 it will only ever return true, if both its inputs are also true Feb 18 13:48:22 so its saying input1 has to be true AND input2 has to be true Feb 18 13:48:29 any other combination produces a false output Feb 18 13:48:30 * irc.binaryuniverse.net gives channel operator status to riftor Feb 18 13:48:53 A good reference right now would be to check out this diagram I once created:- Feb 18 13:48:54 http://riftor.g615.co.uk/content/general/adder/gates.gif Feb 18 13:49:03 which shows equivalent circuis Feb 18 13:49:05 *circuits Feb 18 13:49:17 but this may be pretty confusing at the moment Feb 18 13:49:21 so don't worry too much about that yet. Feb 18 13:49:32 So we have two propositional operators, Feb 18 13:49:36 and Feb 18 13:49:38 & not Feb 18 13:50:10 Another important one is "or" that also takes two inputs Feb 18 13:50:26 an or statement is true if either one of its inputs is true, or both Feb 18 13:51:05 In mathematics you will be familiar with statements such as 1+1 = 2 Feb 18 13:51:14 where + is an operator that takes two inputs. Feb 18 13:51:25 This operator is said to be an "infix" operator as it sets inbetween its two inputs Feb 18 13:51:43 You can also have postfix and prefix operators Feb 18 13:51:52 postfix means the operator is after its arguments Feb 18 13:51:58 and prefix means the operator is before its arguments Feb 18 13:52:01 e.g. Feb 18 13:52:04 + 1 1 = 2 in prefix Feb 18 13:52:05 or Feb 18 13:52:09 1 1 + = 2 in postfix Feb 18 13:52:21 In propositional logic it is standard to deal with operators in infix notation Feb 18 13:52:22 so Feb 18 13:52:25 true and true = true Feb 18 13:52:29 true and false = false Feb 18 13:52:33 false and true = false Feb 18 13:52:35 false and false = false Feb 18 13:52:52 and that is the complete set of states that describes the operation of the and operator. Feb 18 13:53:10 The or operator (which is true if either of its inputs are true, or both) would behave as such Feb 18 13:53:13 true or true = true Feb 18 13:53:19 true or false = true Feb 18 13:53:23 false or true = true Feb 18 13:53:27 false or false = false Feb 18 13:53:57 If you now cast your eyes over to this diagram:- http://riftor.g615.co.uk/content/general/adder/gates.gif Feb 18 13:54:37 and look at the table at the bottom, we can see that it is describing the same "and" & "or" operators, but using 1 & 0 to represent True & False. Feb 18 13:55:29 So we have "and" and "or" and "not", and in turns out that those are the only logical operators that we actually need, and any other operators can be derived by chaining these together. Feb 18 13:56:30 in propositional logic it is standard to use a V style character to mean or (sometimes called disjunction) Feb 18 13:56:49 and an upside down V (looking like a pointy 'n') to represent and Feb 18 13:57:00 a not is often written as a ¬ symbol - Show quoted text - Feb 18 13:57:43 'and' is called conjunction Feb 18 13:57:59 and 'not' .. the negation! Feb 18 13:58:09 Indeed Feb 18 13:59:14 now the table we can see in the diagram is called a "truth table" where we write down all the possible states for A & B, and then to the right, write down operations performed on them Feb 18 13:59:36 this can be useful for combining operators, as we can then look at the columns produced and performed operations on them Feb 18 13:59:59 for instance, in this diagram there is an "A and B" column and a "A OR B" column Feb 18 14:00:16 we could then "and" these together, to get "(A and B) and (A or B)" Feb 18 14:00:50 so.. now for a little exercise,.. Feb 18 14:01:48 write down a propositional statment that uses A and B as boolean variables (variables that are either true or false) that is true, apart from when A is true and B is false Feb 18 14:01:54 so the truth table would be Feb 18 14:02:22 A B A something B Feb 18 14:02:22 0 0 1 Feb 18 14:02:22 0 1 1 Feb 18 14:02:22 1 0 0 Feb 18 14:02:22 1 1 1 Feb 18 14:02:54 where something is our operation that we are going to try and define by combining conjunctions (ands), disjunctions (or) and negations (not) . Feb 18 14:03:06 * qwertydawom sets mode -m #lecture Feb 18 14:03:19 Anyone willing to try? Feb 18 14:03:29 it helps if you can write on paper Feb 18 14:10:05 <@riftor> i'll give you a hint, you can do it with one "and", one "or" Feb 18 14:10:07 and one "not" Feb 18 14:10:09 Not A or B Feb 18 14:10:17 Which is the classical statement. Feb 18 14:10:20 I think therefore I am. Feb 18 14:10:30 Which is the same as A => B. Feb 18 14:10:39 which we will soon define Feb 18 14:10:56 tocsin is correct Feb 18 14:11:00 ¬A or B Feb 18 14:11:13 =s Feb 18 14:11:23 now that my mind is short-circuited Feb 18 14:11:26 hehe Feb 18 14:11:44 well try it out on paper Feb 18 14:11:54 no i get it Feb 18 14:11:56 :) write down the truth table! :) Feb 18 14:12:23 * qwertydawom sets mode +m #lecture Feb 18 14:13:28 So, now, seeing that tocsin really wants this to be covered (:P) we'll study the implication! Feb 18 14:13:59 Like I've previously stated, this is the common syllogism. Feb 18 14:14:32 The main idea of that A => B is that, if A is true, then B must be true. Feb 18 14:15:05 Consequently, if B is false, it means that A is false. Feb 18 14:15:38 But! If A is false, B can be either true or false. Feb 18 14:16:21 From this, we see the relation between the implication and riftor's exercise. Feb 18 14:17:04 Like mentioned by tocsin, A => B, is the same thing as ¬A V B. Feb 18 14:19:20 And this "not A or B" can only be false if A is true and B false. Feb 18 14:21:28 Since "not A or B" is the same as "B or not A" (we say that the operator 'or' is commutative), which is the same thing as 'not(not B) or not A', we see that A ==> B is the same as "not B ==> not A". Feb 18 14:21:57 The last statement is called the 'contrapositive' of A ==> B. Feb 18 14:22:53 So, just like we did for the 'and' and 'or' operators, we can build the truth table of the implication. Feb 18 14:22:58 * qwertydawom sets mode -m #lecture Feb 18 14:23:09 Is there anyone able to build it? Feb 18 14:23:10 ugh Feb 18 14:23:19 qwerty you totally lost me here Feb 18 14:23:26 14:13 <@qwertydawom> Since "not A or B" is the same as "B or not A" (we say Feb 18 14:23:26 that the operator 'or' is commutative), which is the same Feb 18 14:23:26 thing as 'not(not B) or not A', we see that A ==> B is the Feb 18 14:23:26 same as "not B ==> not A". Feb 18 14:24:12 uhm Feb 18 14:24:26 will you indulge me and put it all together in a sentence for me, pls? Feb 18 14:25:32 are you ok that A ==> B is the same as "not A or B"? Feb 18 14:25:39 yes Feb 18 14:25:55 no Feb 18 14:25:57 :S Feb 18 14:26:00 sorry Feb 18 14:26:56 so, let's take an example : Feb 18 14:27:05 I think therefore I am. Feb 18 14:27:21 In this case : A is 'I think' and B is 'I am'. Feb 18 14:27:32 :S Feb 18 14:27:42 l Feb 18 14:27:46 k* Feb 18 14:28:28 now, what would 'not A or B' represent? Feb 18 14:29:07 i do not think and i am not? Feb 18 14:29:19 mu: that would be not A or not B Feb 18 14:29:23 I do not think or I am? Feb 18 14:30:01 if I understand correctly, you're correct Narada ;) Feb 18 14:30:06 who agrees with Narada? Feb 18 14:30:11 i do Feb 18 14:30:43 any others? Feb 18 14:30:48 me, of course Feb 18 14:30:59 yes, ok :) Feb 18 14:30:59 i do not think what i am therfor i am not what i think. Feb 18 14:31:05 o.o Feb 18 14:31:14 i think i am confused Feb 18 14:31:16 * mu cries Feb 18 14:31:28 hmm Feb 18 14:31:33 =D Feb 18 14:31:36 lol Feb 18 14:31:40 qwerty, can I try explaining it to mu? ;\ Feb 18 14:31:44 sure Feb 18 14:31:47 ok, mu Feb 18 14:31:53 going back to 'I think therefore I am' Feb 18 14:32:00 'I think' implies that 'I am' Feb 18 14:32:00 ok Feb 18 14:32:05 so: Feb 18 14:32:06 yes Feb 18 14:32:09 I think ==> I am Feb 18 14:32:10 yes? Feb 18 14:32:14 yes Feb 18 14:32:28 but if I do not think, does that necessarily mean I am not? Feb 18 14:32:42 according to descartes, it does Feb 18 14:32:45 <_< Feb 18 14:32:52 =/ Feb 18 14:33:06 no! Feb 18 14:33:11 sorry, i took philosophty classes! Feb 18 14:33:20 ok Feb 18 14:33:21 mu, this is logic, not philosophy ;) Feb 18 14:33:21 so Feb 18 14:33:38 i do not think and i am?Feb 18 14:34:34 mu: so you agree that it is possible to be without thinking, yes? Feb 18 14:34:42 yeah Feb 18 14:34:43 at least in logic Feb 18 14:34:44 ok Feb 18 14:34:48 like schiavo Feb 18 14:34:50 now. If I am not, is it possible to think? Feb 18 14:34:54 no Feb 18 14:34:55 Ch4r: Sure, non-sentient animals do it. ;) Feb 18 14:35:01 lol Narada Feb 18 14:35:04 mu: correct Feb 18 14:35:09 hush,, narada! >:( Feb 18 14:35:26 so if you let A = 'I think' and B = 'I am' Feb 18 14:35:43 A ==> B is the same as not a or b Feb 18 14:35:45 d'you agree? Feb 18 14:35:51 yes! Feb 18 14:35:54 finally! Feb 18 14:35:57 thank you Feb 18 14:36:04 np Feb 18 14:36:05 :P Feb 18 14:36:14 => is not the same as algebraically saying "equals or is greater than" right? Feb 18 14:36:31 right Feb 18 14:36:37 o.O Feb 18 14:36:39 no, it's not Feb 18 14:36:41 O.o Feb 18 14:36:44 this isn't algebra Feb 18 14:36:46 this is logic Feb 18 14:36:54 ;) Feb 18 14:36:56 ==> is 'implies that' Feb 18 14:37:02 I know, I was just making sure that it didn't apply. Feb 18 14:37:03 what you mean is '>=' Feb 18 14:37:14 I wasn't aware that the order mattered? Feb 18 14:37:28 you learn something new every day ;D Feb 18 14:37:36 That would just make it is greater than or equal to instead of is equal to or greater than. Feb 18 14:37:39 greater (>) or equal (=) Feb 18 14:37:46 hmm Feb 18 14:37:47 but Feb 18 14:37:55 last time I checked this wasn't an algebra lecture =X Feb 18 14:38:03 lol, yes, you're right Feb 18 14:38:11 I'll shut up. >.< Feb 18 14:38:15 so, let's continue with this truth table Feb 18 14:38:29 if A and B are both true Feb 18 14:38:40 what can we say about "A ==> B" ? Feb 18 14:38:49 true Feb 18 14:38:53 yes Feb 18 14:38:57 because if A is true B has to be true Feb 18 14:39:12 Now, if A is true but B is false? Feb 18 14:39:19 false Feb 18 14:39:28 because you must be to think ;x Feb 18 14:39:35 :) Feb 18 14:39:43 A false and B true? Feb 18 14:39:54 true Feb 18 14:39:58 yep Feb 18 14:40:09 and, eventually : both A and B false? Feb 18 14:40:15 still true Feb 18 14:40:32 yep Feb 18 14:41:01 Now, from what we've said, "not A ==> not B" will have the same truth table. Feb 18 14:41:27 But, it is important to notice that p ==> q is definitely not the same as q ==> p Feb 18 14:41:49 Let's do its truth table : Feb 18 14:42:14 If A and B are both true, what can we say about B ==> A? Feb 18 14:42:49 I'll let someone else answer this, since I answered these a minute ago. :P Feb 18 14:43:05 I'm still not sure as to what ==> is. :/ Feb 18 14:43:17 it is 'implies that' Feb 18 14:43:20 for example : Feb 18 14:43:20 => is implication Feb 18 14:43:29 A=>B is the same as saying ¬A or B - Hide quoted text - Feb 18 14:43:31 Narada: remember... 'I think' IMPLIES THAT 'I am' Feb 18 14:43:36 If it rains, then I take an umbrella. Feb 18 14:44:05 or you can stay home and attend an IRC lecture =x Feb 18 14:44:11 hmm... I've never learned this part of logic. I always thought it was either on or off. Feb 18 14:44:44 Narada: right. The point of this is that you learn it now ;) Feb 18 14:45:05 ok, so I'll go for the B ==> A Feb 18 14:45:06 So it's saying if A is whatever, in all probability B is also whatever? Feb 18 14:45:21 it's not probability. Feb 18 14:45:25 Or is it a finite is? Feb 18 14:45:48 but to imply is to assume, not actually know. :/ Feb 18 14:45:50 If we have the A ==> B, it means that A is a sufficient condition for B. Feb 18 14:46:08 So A has to be something before B is true? Feb 18 14:46:16 no Feb 18 14:46:20 B can be true if A is false Feb 18 14:46:22 lol Feb 18 14:46:23 gah Feb 18 14:46:25 but if A is true B MUST BE true Feb 18 14:46:29 i'm glad it's not just me, narada Feb 18 14:46:31 <3 Feb 18 14:46:34 :P Feb 18 14:46:42 cause A is B's brother Feb 18 14:46:45 :/ Feb 18 14:46:47 I feel bad because I've already learned logic gates and crap but I don't know this. Feb 18 14:46:58 yes, you see Narada, the sense of the arrow --> Feb 18 14:47:02 Narada: don't feel badly. If everyone knew this we wouldnt' have a lecture Feb 18 14:47:08 A towards B. Feb 18 14:47:26 So if A is true, so B is. Feb 18 14:48:07 But, A can be false, and B true. Feb 18 14:48:18 always think about the example of Descartes ;) Feb 18 14:48:32 ok but Feb 18 14:48:43 if we flip the positions of a and b Feb 18 14:48:47 yes Feb 18 14:48:52 can b be false and a be true, still? Feb 18 14:48:59 ok, so B can be true or false and A can be false, but if A is true then B MUST be true? Feb 18 14:49:03 mu: no. Feb 18 14:49:10 ok, i didn't think so but Feb 18 14:49:12 mu: if you flip their positions, you're saying "I am therefore I think" Feb 18 14:49:14 i dunno why Feb 18 14:49:18 well, if we have B ==> A Feb 18 14:49:19 ok Feb 18 14:49:21 i gotcha Feb 18 14:49:31 if A and B are both true, this is true. Feb 18 14:49:39 ok Feb 18 14:49:52 if A is true and B false, this is also true. Feb 18 14:50:10 but! if A is false and B is true, then it is false Feb 18 14:50:18 ok Feb 18 14:50:21 if both are false, then it is true Feb 18 14:50:21 i see it now Feb 18 14:50:22 ty Feb 18 14:51:02 ok Feb 18 14:51:14 so Feb 18 14:51:17 so, now that we have seen the 'if ... then' statement. Feb 18 14:51:38 so <-- never mind that. Feb 18 14:51:43 We'll see the 'if and only if' statement. Feb 18 14:52:08 This one is more easily understandable. :) Feb 18 14:52:33 It is denoted by : A <==> B, and it means that A and B are 'equivalent'. Feb 18 14:53:05 so, if we have that 'A <==> B' is true, it'll mean that the truth values of A and B are the same. Feb 18 14:53:24 so THEN we can flip positions and the statement is still true Feb 18 14:53:32 yes! :) Feb 18 14:54:20 like, a=5 and b=4+1 Feb 18 14:54:36 so, we can see that 'A <==> B' is the same as '(A ==> B) and (B ==> A)' Feb 18 14:54:44 :D Feb 18 14:54:51 can you see it? Feb 18 14:54:55 yes sir Feb 18 14:54:56 yes i can Feb 18 14:55:45 Mu, try and build the truth table ;) Feb 18 14:55:53 ugh Feb 18 14:55:55 what if both A and B are true? Feb 18 14:56:14 hang on Feb 18 14:56:18 Isn't that what you were just talking about? Feb 18 14:56:32 if A and B are true, A=B? Feb 18 14:56:55 well, equivalent is not 'equal' Feb 18 14:57:08 um... it isn't? Feb 18 14:57:09 if A and B are true, then A <==> B is true. Feb 18 14:57:55 for example : x = 1 <==> x+1 = 2 Feb 18 14:58:17 but I thought that when A <==> B A=B? Feb 18 14:58:28 that's wrong :) Feb 18 14:58:37 for example : Feb 18 14:58:40 shit on my face. Feb 18 14:58:43 ahah Feb 18 14:58:54 I take my umbrella if and only if it rains. Feb 18 14:59:13 if it rains, you take your umbrella Feb 18 14:59:26 yes, but also, in this case : Feb 18 14:59:40 If I take my umbrella, it means it rains. :) Feb 18 14:59:47 if it doesn't rain, you don't take your umbrella Feb 18 14:59:59 yes Feb 18 15:00:04 "If I take my umbrella it means it rains" <-- and vice versa Feb 18 15:00:14 so that's equivalent but not the same Feb 18 15:00:19 Are A and B umbrella and rain? Feb 18 15:00:24 or, congruency Feb 18 15:00:29