Fundamentals of Logic Statements Propositions Sentences that are true or false but not both Just like a simple boolean expression or conditional expression in a programming language For our purposes statements will simply be denoted by lowercase letters of the alphabet typically p q and r I will refer to these as boolean variables as well Given simple statements we can construct more complex statements using logical connectives Here are 4 logical connectives we will use 1 Conjunction This is denoted by the symbol The statement p q is read as p and q Only if both the values of p and q are true does this expression evaluate to true Otherwise it is false 2 Disjunction This is denoted by the symbol The p q is read as p or q As long as at least one of the values of p or q is true the entire expression is true 3 Implication This is denoted by the symbol The statement p q is read as p implies q Essentially in a programming language this logic is captured in an if then statement If p is true the q must be true However if p is not true there is no guarantee of the truth of q An important observation to note when statements are combined with an implication there is no need for there to be a causal relationship between the two for the implication to be true Consider the following implications If my bread is green then I will not eat it Here if the bread is not green that does not guarantee that I will eat it Perhaps it is wheat bread and I hate wheat bread All I know is that if my bread is green I will definitely NOT eat it If Pluto is the largest planet in our solar system then pigs will fly out of my butt Wayne would actually be making a correct implication here assuming that we currently have accurate knowledge about our solar system Since the first part of our implication is false the entire implication is automatically true 4 Biconditional This is denoted by the symbol and the statement p q is read p if and only if q The phrase if and only if is often abbreviated as iff Breaking this down into pieces this means that p q AND q p Hence exactly when p is true q is true And in all cases where p is false q must be false as well Here is an example of a biconditional If and only if my alarm clock rings in the morning then I will attend my morning classes From this statement we CAN deduce that if the alarm clock does NOT ring then I will NOT go to my morning classes Finally it will be important to have a symbol to denote the negation of a statement proposition We will use the symbol The statement p will be read not p This statement will have the opposite value of p 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 …
View Full Document
Unlocking...