DOC PREVIEW
UCF COT 3100 - Truth Tables

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Truth TablesNow, given a particular compound statement, we can use atruth table to determine which values of the boolean variablesresult in the statement being true.The idea here is to simply make a table, listing all the possiblecombinations of values for each of the boolean variables in astatement. Then, plug these values into the statement and see ifit is true or not with these values. This is probably easiest seenwith an example.Consider the statement: p  (q  r). Here is a truth table:p q r q  r p(qr)0 0 0 1 00 0 1 0 00 1 0 1 00 1 1 1 01 0 0 1 11 0 1 0 01 1 0 1 11 1 1 1 1Thus there are three possible combinations of values for p, q,and r that make p  (q  r) true. To see an example, let p, q and r be the following statements:p: I have taken out the trash.q: I have finished cleaning the dishes.r: I have watched 5 hours of TV.Assume that a child is a good one if p  (q  r) holds true, andbad otherwise. Under what conditions is a child good?If it turns out that a statement is always true (such as p  p),then it is called a tautology. If a statement is always false (such as make p  p), then it iscalled a contradiction.EXERCISE: Make a truth table for the statement: (p q)r.Algebra of PropositionsIt would be nice if we had some methodology for determining iftwo logical expressions are equal, or a method of simplifying agiven logical expression.Perhaps the most obvious way to check for the equality of twological expressions it to write out truth tables for both.However, this could be quite tedious. (But it does alwayswork...)Two statements s and t are considered to be logically equivalentif s  t.We will need some laws to simplify logical expressions. Here isthe list of laws from the text:1) p  p (Law of Double Negation)2) (p  q)  p  q (De Morgan’s Laws)3) (p  q)  p  q4) p  q  q  p (Commutative Laws)5) (p  q)  r  p  (q  r) (Associative Laws)6) p  (q  r)  (p  q)  (p  r) (Distributive Laws)7) p  (q  r)  (p  q)  (p  r)6) p  p  p (Idempontent Laws)7) p  F  p, p  T  p (Identity Laws)8) pp  T, pp  F (Inverse Laws)9) p  T  T, p  F  F (Domination Laws)10) p  (p  q)  p (Absorption Laws)11) p  (p  q)  pWe can use these laws to simplify a statement. Consider thefollowing statement:(p  q)  (p  q)  (p  q)  (p  q) (DeMorgans)  (p  q)  (p  q) (Double Neg.)  p  (q  q) (Dist. Law)  p  F (Inverse)  p (Identity)Something else that will be helpful to us will be to expressionimplications using just and’s and or’s. By writing out truthtables, we find that(p  q)  (p  q) (We’ll call this the implication identity.)Using this, we can also come up for an expression withoutimplications that is equivalent to p  q.As an exercise, simplify the following expression, giving thereason for each simplification.(p  q)  [q  (r  q) ]Methods to Prove Logical ImplicationsThe standard form of an argument (or theorems) can berepresented using the logical symbols we have learned so far:(p1 p2  p3  ... pn) qEssentially, to show that this statement is always true (atautology), we must show that if all of p1 through pn are true,then q must be true as well.Another way to look at this is that we must show that if q isever false, then at least ONE of p1 through pn must be false aswell. (This is the contrapositive of the original assertion.)Let’s look at an example of how you might go about proving astatement in a general form, given some extra information.Let p, q, are r be the following statements:p: Rudy loses the immunity challenge.q: Kelli lets go of the pole during the immunity challenge.r: Rich will win Survivor.Let the premises be the following:p1 : If Kelli does not let go of the pole during the immunitychallenge, then Rudy will lose the immunity challenge.p2 : If Rudy loses the immunity challenge, then Rich will winSurvivor.p3 : Kelli did not let go of the pole during the immunitychallenge.Now, I want to show that(p1  p2  p3)  rFirst, I must express p1, p2, and p3 in terms of p, q, and r.p1 : q  pp2 : p  rp3 : q Thus, we are trying to show the following:[([q  p)  (p  r)  (q)]  rWe can prove that this is a tautology by using a truth table andverifying that this expression is true for all 8 possible sets ofvalues for p, q and r.Another way we can show this statement is to use the laws oflogic to simplify the statement as follows:[(q  p)  (p  r)  (q)]  r (Identity for implication)[(q  p)  (p  r)  (q)]  r (Double Negation) [((q  p)  (p  r))  (q)]  r (Identity for implication)((q  p)  (p  r))   (q)  r (De Morgan’s Law)((q  p)  (p  r))  q  r (Double Negation)(q  p)  (p  r)  q  r (De Morgan’s Law)(q  p)  (p  r)  q  r (De Morgan’s Law)(q  p)  (p  r)  q  r (Double Negation)(r  (p  r))  (q  (q  p)) (Associate+Commutative)((r  p)  (r  r))  ((q  q)  (q  p)) (Distributive)((r  p)  T)  (T  (q  p)) (Inverse Laws)(r  p)  (q  p) (Identity Laws)(p  p)  (r  q) (Associate+Commutative)T  (r  q) (Inverse Laws)T (Domination Laws)When p q is a tautology, we say that the statement is alogical implication. This implication is equivalent to thefollowing:q  p, which is the contrapositive as mentioned before. Incertain situations, it will be easier to prove the contrapositivethan the original statement.Getting back to the example we just went over, we have shownthat any set of statements p1 , p2 , and p3 of the form aboveimply the statement r. Now, you might notice that proving the example above byeither using the truth table method or using the laws of logictook a great deal of effort for a relatively intuitive result. (Justby hearing the premises, you probably already knew


View Full Document

UCF COT 3100 - Truth Tables

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download Truth Tables
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Truth Tables and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Truth Tables 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?