-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|330|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Article Home -> Advanced Techniques

Created : 31 January 2009
Edited : 31 January 2009

Logic (part 2)

Part of the Series on Discrete Structures

In this article I am going to go over "implies", double-implication, and also some of the rules of implication (you can find part 1 here).

To start out, let's go over "implies". The "implies" operator is denoted by an arrow ((8594)). Implication can be broken down to something as simple as an if-then statement. Think of it as a contract: The first part of the contract must be valid for the second part to activate (e.g. if you do all your chores, you will get a cookie-- using this metaphore, if you do not do your chores, no cookie can be guranteed). Let's look at the truth table for an implication of p and q:


Now, you may have noticed something kinda funny about this. If p is false, the implication will always be true. This sounds weird at first, but it makes sense if you think about it this way. Taking the chores/cookie example: if you don't do your chores, then whether you get a cookie or not is irrelevant. However, if you do do your chores, and you do not receive a cookie, then the statement must not be true, because the contract was broken. It's like doing work without getting paid, if you do the work you should get paid, if you don't do the work, then whether you get paid or not is irrelevant, because the contract is still not broken.

There is also such a thing as what's called "double implication" (denoted by a double arrow [(8596)]). The definition of this is essentially that both p(8594)q and q(8594)p. This topic may come up more in later articles.

The rules
Before I go over some of the rules of logic, I have to touch on the format they're displayed in. The following is one rule, Modus Ponens:


It can be assumed that the two statements before the line are true, and that any statements afterwhich are conclusions of the prior statements. Meaning that, this could be rewritten as (p(8594)q) (708) p (8594) q. Writing a variable alone in the statement denotes a variable which has the value of "true". Writing it as ¬[var] means that it is false.

  • Note: the character ((1566)) denotes "therefore", signifying the conclusion of a proof or lema.

  • Think about it: the only way for the statement "p" to be true is if p were true, and for the statement ¬p to be true, p would have to be false. For extra practice, try writing a truth table out for each of these cases.

  • Now that we know this, let's go over (most) of the rules of logic, all of which can be proven by truth tables. If you're adventurous, try it out on your own!

    Modus Ponens
    Modus Tollens
    Conjunctive Simplification
    Disjunctive Syllogism
    Disjunctive Amplification

    These rules can be used to solve many different logical problems, one method of which will be explained in the next article. I don't have any specific exercies for this, but go ahead and see if you can demonstrate via a truth table one or more of these!




    Sunday, 01 February 2009, 13:37
    Good article, although slightly concise. What is the point of all those different rules of logic?

    Tip: when you have those fancy characters, they are translated to something along the lines of "&xxxx;" in the HTML. This leaves a naughty semi-colon at the end, which in addition to a parenthesis gives you a misplaced smiley. So instead of typing (&xxxx;), type (&xxxx;[b][/b]).
    Monday, 02 February 2009, 07:46
    hmm... sounds like a glitch in jay's code! I'm not typing the unicode in directly, I'm just copying the character out of the character map in windows... I'll pm jay.

    I know this article is a bit concise, but I'll get along to what those rules are used for soon. I probably should have waited to post this one until after I finished the other part of it, but oh well. The second part may come in as an edit of this article, I'll look at flow and then set it up however it all comes together nicest.
    Monday, 02 February 2009, 08:01
    It's to do with the way around that the data's being processed.. To keep it all safe, I do the "Unicode"-->&xxxx; thing early on. Otherwise, if you try sticking Unicode through php, there's all kinds of security holes that turn up, and all sorts.. Then you've the smiley code that comes after it..
    You needn't have [b][/b], though.. a simple space will suffice!

    Now, to be honest, I read, and re-read the cookie example, and although I understand it, it still doesn't make any sense in my head!
    It's like the "Type" example in Blitz, with the chairs.. Although, technically, it makes sense, it really means bog all in my head!
    Like most thing, give this a coded purpose, and my head will probably wrap around the logic a whole lot better.
    I seem to be rubbish at learning from explainations!!
    Monday, 02 February 2009, 12:52
    Unfortunately the idea is that a lot of this isn't code, it's the theory behind the code. <@Phoenix> this is a lot of the reason I wanted a separate article, because implication is such a funny topic at first </@>. But, I suppose if you were to use a code example:

    Okay, in this example, we're testing a variable num to see if it is greater than or equal to 6. We'll take this as being equivalent to p(8594)q, where p is the "if (num >= 6)" and q is the "printf("Hello, World!");". If p, then q;.

    So, if p is true (p=1), then in order for the statement p implies q (p(8594)q) to be true, q must be true (must execute). This means that, the only way for p(8594)q to be false, is if "Hello, World!" is printed without num being greater than or equal to 6.

    Now, in the scenario where p=0 (num<6), it doesn't matter whether q is true or not ("Hello, World!" is printed or not). Therefore, for all values of q, where p=0, p(8594)q always evaluates to be true.

    With a computer, basically think of implies as "does the algorithm work or not".