Truth Tables Now given a particular compound statement we can use a truth table to determine which values of the boolean variables result in the statement being true The idea here is to simply make a table listing all the possible combinations of values for each of the boolean variables in a statement Then plug these values into the statement and see if it is true or not with these values This is probably easiest seen with an example Consider the statement p q r Here is a truth table p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q r 1 0 1 1 1 0 1 1 p q r 0 0 0 0 1 0 1 1 Thus 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 and bad 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 is called a contradiction EXERCISE Make a truth table for the statement p q r Algebra of Propositions It would be nice if we had some methodology for determining if two logical expressions are equal or a method of simplifying a given logical expression Perhaps the most obvious way to check for the equality of two logical expressions it to write out truth tables for both However this could be quite tedious But it does always work Two statements s and t are considered to be logically equivalent if s t We will need some laws to simplify logical expressions Here is the 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 q 4 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 p We can use these laws to simplify a statement Consider the following 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 expression implications using just and s and or s By writing out truth tables we find that p q p q We ll call this the implication identity Using this we can also come up for an expression without implications that is equivalent to p q As an exercise simplify the following expression giving the reason for each simplification p q q r q Methods to Prove Logical Implications The standard form of an argument or theorems can be represented using the logical symbols we have learned so far p1 p2 p3 pn q Essentially to show that this statement is always true a tautology 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 is ever false then at least ONE of p1 through pn must be false as well This is the contrapositive of the original assertion Let s look at an example of how you might go about proving a statement 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 immunity challenge then Rudy will lose the immunity challenge p2 If Rudy loses the immunity challenge then Rich will win Survivor p3 Kelli did not let go of the pole during the immunity challenge Now I want to show that p1 p2 p3 r First I must express p1 p2 and p3 in terms of p q and r p1 q p p2 p r p3 q Thus we are trying to show the following q p p r q r We can prove that this is a tautology by using a truth table and verifying that this expression is true for all 8 possible sets of values for p q and r Another way we can show this statement is to use the laws of logic 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 a logical implication This implication is equivalent to the following q p which is the contrapositive as mentioned before In certain situations it will be easier to prove the contrapositive than the original statement Getting back to the example we just went over we have shown that any set of statements p1 p2 and p3 of the form above imply the statement r Now you might notice that proving the example above by either using the truth table method or using the laws of logic took a great deal of effort for a relatively intuitive result Just by hearing the premises you probably already knew that statement r followed logically If we examine a truth table we will find that in most cases most of the rows at least one of the premises is false anyway If this is the case there is no need to even compute the value of the conclusion So we have an indication that we could trim some work Also it seems logical to have some rules of inference rather than having to turn each inference into an equivalent logical expression without an inference What we will do is verify these rules …
View Full Document
Unlocking...