|
SoCoder -> Article Home -> Advanced Techniques |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Scherererer
|
Logic (part 1)Part of the Series on Discrete Structures |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This is the beginning of a series of articles on Discrete Structures and Computational Algorithms. Topics I hope to cover in the series' include:
Let's start with logic. Logic is a binary science, dealing only with true and false, there is no "gray area" here. Values can be represented by a 1 (true) or 0 (false), via their written out modes, or by the constants T and F (respectively). These values can be stored in variables, traditionally, p, q, r, and s are the variable names of choice for this type of math. In this math, it would behouve you to initialize your variables, where appropriate, in such a manner as this: Let p=true Let q=0 Let r=F etc... Alone, they don't do much, but we have different operators so that they can interact with one another. Logical AND ((708)) The AND operator, represented often times with a ^ sign, returns a true value only when the values on either side of it are also true. For example: 1 (708) 1 (8594) 1 T (708) T (8594) T true (708) true -> true if true and true then true however, if one or both values are false, then the returned value will be false aswell. 1 (708) 0 (8594) 0 0 (708) 0 (8594) 0 etc.. again, we can also incorporate the use of our variables, such as in the case of this example: Let p=T T (708) p (8594) T More extensive demonstration will be given during the section on truth tables Logical OR ((709)) The OR operator, represented with the (709) sign, is true when atleast one value is true. For example: 1 (709) 1 (8594) 1 1 (709) 0 (8594) 1 0 (709) 1 (8594) 1 0 (709) 0 (8594) 0 Logical NOT (¬) The NOT operator, represented by the ¬ sign, returns the opposite value of whatever it is operating on. So, true becomes false and false becomes true. For example: ¬1 (8594) 0 ¬0 (8594) 1 Putting it all Together Now that we know some of our basic operators, we can put them all together and make some more complex operations. For instance, for what values of p is this true ¬p (708) q? Here are some examples, and then I'll show one method of solving them. ¬p (708) q ¬(p (709) F) (708) q Solving Logic Problems with Truth Tables If only it were this easy to tell if things were true or not in real life. A truth table is just that, a table to determine the truth of a problem. These start off simple, list your variables. Let's take the first example: ¬p (708) q contains variables p, q Now we will list all possible value combinations for those variables in a table:
great, now let's break down our operators. Since there's no parethases, the next item in our order of operations is the NOT (¬) operator, so we'll do that first. For all given values of p in our table, write down the corresponding "not p" values.
Notice the values in our "¬p" column are just the opposite values of our "p" column. Now that we've done that, we can work on the (708) column, combining our two elements:
All we did was take the corresponding values from our "¬p" column, along with those from the "q" column, and did the AND operation row by row, giving us our final results. As you can see, there is only one row of ¬p (708) q that is true, therefore we can conclude that the values at p and q in that row (0 and 1 respectively), are the only values which make this operation true. Go ahead and try a few on your own now! I've made some practice problems for you all to try out: ¬p (709) q ¬(p (708) q) (hint: the parenthases change the order of operations, p (708) q goes first now!) ¬(p (709) F) (708) q (remember: F is a constant variable, it always equals 0) Extended Exercises (p (708) ¬q) (709) ¬r (p (708) q) (709) ¬(r (708) s) That's all for this article, in the next one I'll be covering the rules of implication, as I think that deserves a bit more explaining than any of the operators. That will also cover some of the other logical conclusions such as Modus Ponens, De Morgan's laws, and many others! ¬(708)(709)(8594)(8596) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Thursday, 29 January 2009, 12:31 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Phoenix
|
Keep them coming! I'll be a good student and then you can correct my answers  > Reveal 🔎 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Thursday, 29 January 2009, 20:42 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Scherererer
|
Great job Phoenix! > Reveal 🔎 
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Thursday, 29 January 2009, 21:26 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
blanko1324
|
Good article; a great refresher from my high school logic unit. Can't wait for more.
|
|
|
| |||
|
| ||||
Think about it: when you add more variables, what kind of relationship can you make between the number of rows and the number of variables? Hint: 2, 4, 8, 16, 32...
|edit|
!