|
SoCoder -> Article Home -> Advanced Techniques |
||||||||||||||||||
|
|
||||||||||||||||||
Scherererer
|
Logic (part 3)Part of the Series on Discrete Structures |
|||||||||||||||||
|
Logic (part 3) What it all means I left my last article on a kind of a short note, leaving a few questions in the comment area as to what the point of it all was. Well, here we go. The rules of logic outlined in my last article (which can be found here) can be used to do what are called logical proofs. Proofs can be used to do everything from proving that someone is talking in circles to simplifying (or condensing) logical operations. i.e. changing a huge block of "if" statements into only a few statements. All proofs are written in the form <premise 1> <premise 2> ... <premise n> ___________ (1566) <conclusion> The point is to assume that the premises are true, and from them, derive the conclusion. Technically, these can also be written in the form: <premise 1> (708) <premise 2> (708) ... (708) <premise n> (8594) <conclusion> So, let's start out with an example: p(8594)¬q q _____ ¬p(708)q So let's examine this, in order for the statement ¬p(708)q to be true, we know that p must be false, and q must be true (remember, and operations ((708)) are only true when both statements return true.) But, we need to come to this conclusion via the given premises. Here's the best way to do that:
alright great, we've established our premises, now let's use some of our rules of implication in order to determine whether the conclusion is true or not (remember, we don't know if the conclusion is true yet, we only know that the premises are.)
Here we have used the definition of the "not" operation to state that (based on statement 2), ¬q is false. If you don't get how we got here, look at statement #2, and you'll see that it just says "q". because we know all premises are true, the only way for "q" to be true, is for "q" to be true. Thus, if it instead said "¬q", the only way for "¬q" to be true is if q were to be false. Anyway, since we know that q is true, we also know that "not q" is false.
Now we state, "since not q is false, and p implies not q, based on the rule of Modus Tollens, p must be false (not p is true)". If you can't remember the rule of Modus Tollens, please reference the last article.
Finally, since we know that (based on 2) q is true, and (based on 4) ¬p is true, we can safely say that both q and ¬p are true, or, written mathematically, ¬p(708)q. We call this conjunction, and is just a fancy way of saying "we know both of these things are true, so we're grouping them with an and operation". You'll find that these can get a bit tricky some times, as they get more and more complicated. Before I finish this article, I want to show one more law that becomes a very important tool in doing logic proofs, De Morgan's Laws. Here's what they look like: ¬(p (708) q) = (¬p) (709) (¬q) ¬(p (709) q) = (¬p) (708) (¬q) These are helpful if you need to change between and and an and or operation, or need to "distribute" some pesky not symbols. I've found a few sites with practice problems that y'all can try out (note: some places may use a tilde (~) as the not symbol). mat101.pbwiki.com/f/mat101takehome.pdf www.csus.edu/indiv/n/nogalesp/SymbolicLogicGustason/SymbolicLogicOverheads/Phil60GusCh3DeductiveMethods/ConditionalProof/PracticeCondiProofs.doc (Answers) - (bad form, uses (61641) as "implies", V as "or", & as "and", not bad form, but confusing: (8801) is double implication ((8596))) ¬(708)(709)(8594)(8596)(1566) |
||||||||||||||||||
|
|
||||||||||||||||||
Comments |
|
| |||
|
| ||||