Fundamentals of LogicStatements/Propositions – Sentences that are true or false butnot both. (Just like a simple boolean expression or conditionalexpression in a programming language.)For our purposes, statements will simply be denoted bylowercase letters of the alphabet, typically p, q, and r. I willrefer to these as boolean variables as well.Given simple statements, we can construct more complexstatements using logical connectives. Here are 4 logicalconnectives we will use:1) Conjunction: This is denoted by the ‘’ symbol. Thestatement p q is read as “p and q.” Only if both the valuesof 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 isread as “p or q.” As long as at least one of the values of p orq is true, the entire expression is true3) Implication: This is denoted by the ‘’ symbol. Thestatement p q is read as “p implies q”. Essentially, in aprogramming language, this logic is captured in an if thenstatement. If p is true, the q must be true. However, if p isnot true, there is no guarantee of the truth of q. Animportant observation to note: when statements arecombined with an implication, there is no need for there tobe a causal relationship between the two for the implicationto 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 Iwill 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 eatit.If Pluto is the largest planet in our solar system, then pigs willfly out of my butt. Wayne would actually be making a correct implication here,(assuming that we currently have accurate knowledge aboutour solar system...) Since the first part of our implication isfalse, the entire implication is automatically true.4) Biconditional: This is denoted by the ‘’ symbol, and thestatement p q is read “p if and only if q.” The phrase “ifand only if” is often abbreviated as “iff”. Breaking thisdown into pieces, this means that p q AND q p. Henceexactly when p is true, q is true. (And in all cases where p isfalse, 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 willattend my morning classes.From this statement we CAN deduce that if the alarm clockdoes NOT ring, then I will NOT go to my morning classes.Finally, it will be important to have a symbol to denote thenegation of a statement/proposition. We will use the ‘’ symbol.The statement p will be read “not p.” This statement willhave the opposite value of p.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(qr)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) pp T, pp 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
View Full Document
Unlocking...