13 Pages
Unlock Document

Computer & Information Science
CIS 1166

Propositional Logic This note contains some material on propositional logic. It is not intended to be a substitute for your textbook or the class lectures. It is instead a supplement and to some extent a guide to what is important. 1 Propositions A proposition is something that has a de▯nite truth value, true or false. Thus commands or questions or exclamations are not propositions. Nor is something like x + 1 = 5 a proposition if we do not know the value of x. What x + 1 = 5 is is a propositional formula; if we specify the value of certain variables, then a propositional formula becomes a proposition. A proposition, for our purposes is not vague or ambiguous. So something like "I went to the bank" is not a proposition unless it is known which meaning of bank (▯nancial institution or riverbank) is intenced. Just as in algebra we use symbols like x, y, z to refer to unknown quanti- ties, in propositional logic we can use symbols like p, q, r to refer to propo- sition whose truth values we might not know. 1.1 Propositional Operators There are several important operators (also called connectives) that take one or more propositions as input and output a proposition. These connectives are truth-functional in the sense that if we know the truth values of the inputs, then we know the truth values of the output. 1.1.1 Negation The symbol : is used to represent negation. :P is true if P is false and :P is false if P is true. If you are building a circuit and want to represent your combinatorial circuit (combinatorial in the sense that you only care about which input signals reach your gates rather than the timing of when they reach the logic gates), there is a standard symbol for an invertor which implements negation (see section 1.2). 1 The proposition :P has the English language translation: It is not the case that P. The resulting translation might be very unsmooth, unnatural and unidiomatic. So you might want to use a clearer and more colloquial translation if P is complicated. Instead of It is not the case that George was late for his appointment George was not late for his appointment. Instead of It is not the case that Laura ate at least three frankfurters Laura did not eat at least three frankfurters or Laura ate fewer than three frankfurters. Instead of It is not the case that George was not early for his appointment George was early for his appointment. This last translation uses the rule that ::P has the same truth value as P. 1.1.2 Conjunction The symbol ^ is used to represent conjunction. P ^ Q is true if both P and Q are true. P ^ Q is false if P is false. P ^ Q is false if Q is false. (In section 1.1 of your textbook, you will see a truth table for this con- nective.) The simplest translation of P ^ Q is P and Q. But natural language is tricky. In formal logic I can say P ^ Q without there being any suggestion that P and Q have anything to do with each other; all I am doing is asserting that they are both true. Moreover, in English if there is a contrast between P and Q, then the word "but" rather than "and" might be used as in I do not like most hot, humid, cities but I like New Orleans. In designing circuits, there is a special simple for a logic gate that im- plements the and operation. In general, this gate might allow for more than two inputs (but just one output). The rule is that the output is output rep- resenting true whenever all the inputs represent true but if any input signal represents false the output is false. Your textbook displays a truth table for the and operator. 2 1.1.3 Disjunction The symbol _ is used to represent disjunction. P _ Q is false if both P and Q are false. P _ Q is true if P is true. P _ Q is true if Q is true. Notice the similarity with the rules for ^. Start with the rules for ^ and then convert ^ to _, and change true to false and false to true and you get the rules for _. We have the De Morgan Rules :(P ^ Q) has the same true value as :P _ :Q because the only way :(P ^Q) can be true is if P ^Q is false and that only happens if either P or Q is false (or both are false) and that means that not P or not Q (or both) is true and clearly if not P is true, then P ^ Q is false so :(P ^ Q) is true and a similar statement can be made about Q. (Note the proof technique I am using here to show that A and B always have the same truth value, it is enough to show that whenever A is true, then B is true and whenever B is true, A is true. So I start with the assumption A is true and ask myself what could possibly make A true and then see if I am forced to conclude that B is true and then I do the same thing in the reverse direction.) I have just stated only one of the De Morgan rules but the other De Morgan rule is :(P _ Q) has the same true value as :P ^ :Q. Because of the De Morgan rules we can always rewrite P _Q as :(:P ^:Q) (you might use a truth table or some other method to prove this) and we can always rewrite P ^ Q as :(:P _ :Q). Thus we do not really need both conjunction and disjunction operators but it is convenient to be able to use both. The usual translation of P _ Q is P or Q; however one should be careful. In English the word "or" is ambiguous. It might be exclusive or (P or Q but not both; in this situation one might say Either P or Q with an emphasis on either) or inclusive or (P or Q or BOTH). _ is used for inclusive or. For exclusive or, we have P ▯ Q, which is true i▯ exactly one of the propositions P and Q is true. 3 There is a symbol that is used to represent an or gate. This or gate can have two or more inputs and will have one output. The output signal will represent true i▯ at least one of the input signals represents true. 1.1.4 Conditionals P ! Q is true if P is true and Q is true. P ! Q is true if P is false regardless of the value of Q. P ! Q is false if P is true and Q is false. P ! Q is translated as if P then Q. or as P implies Q. Here we refer to the P part of P ! Q as the antecedent and the Q part as the consequent. But this translation is perhaps a bit misleading. Natural language is subtle. First point to keep in mind is that a sentence like If 2 + 2 = 5, then snow is white is true because an implication is true whenever the antecedent is false. So If I am the Emperor of Antarctica, then mammoths inhabit the ▯rst oor of the White Hourse is also a true proposition. This might seem like a strange kind of if-then. But keep in mind that the truth value of P ! Q depends only on the truth values of P and Q; there is no implicature that P and Q have anything to do with each other. So we also have If I live in the United States of America, then water is H20 is a true proposition. Aside from the relevancy issue, if you are still wondering why P ! Q is true whenever P is false. consider that one application of prop[ositional logic is system speci▯cation. We might specify a rule that whenever P is true, Q must be true. If it turns out that P is false, then it does not matter what Q is; we have not violated the rule. The rule is still true. But conditionals really are a little trickier to translate than other con- nectives. In English I might say if-then and mean much more than just if-then: 4 If you give me ten dollars, I will give you the widget might be said by a salesperson who also intends to mean that if you do not give the ten dollars, you do not get the widget. Consider now a situation in which to obtain a certain job, you have to pass a certain exam. Then I might say that a necessary condition for you to obtain the job is that you pass the exam or that it is necessary for you to pass the exam in order to obtain the job. Or I could say that you will obtain the job only if you pass the exam. If you do obtain the job, then you have passed the exam. But I have not said that all you have to do to obtain the job is pass the exam. There might be other things you have to do. So that you pass the exam is NOT su▯cient for you to obtain the job. However, we know that if you obtained the job, you must have passed the exam. So in order for us to KNOW that you passed the exam, it su▯ces that we know you obtained the job. It is also clearly true that a su▯cient condition for you not to have obtained the job is that you did not pass the exam. If you think about examples like the job example, you should be able to make sense of the various translations of ! given on the bottom of page 6 of your textbook. Strictly speaking we do not need !, P ! Q and :P _ Q, which is interpreted as (:P) _ Q, have the same truth value. But ! is convenient. Numerous system requirements are very naturally expressed using if-then statements. 1.1.5 Biconditionals P $ Q is true if and only if P and Q have the same truth value (either both true or both false). Thus P $ Q has the same truth value as (P ! Q) ^ (Q ! P). P $ Q might be translated as If and only if P, then Q. A necessary and su▯cient condition for Q is P. P is necessary and su▯cient for Q. (and besides these three, many other translations are possible). 5 1.2 Complex Operators We can form more complex operations by taking two or more simple operators and letting outputs of some of the operators be inputs to other operators. What we have to be careful about (And do be careful; some students in previous classes were not careful and wrote things that taken literally were very wrong) is order of operations. If you think of : as being like the minus sign, ^ as being like multipli- cation, _ as being like addition, and ! as being like ▯ (because if P ! Q, then Q is at least as true as P), then you will see why the precence order is ▯rst do the negations, then the conjuncts, then the disjuncts, and then conditionals. And it turns out biconditionals are last. Of course, you have to pay attention to parentheses. You do what is within a parenthesis before you do any operation that mixes up input from within the parenthesis and from outside of the parenthesis. Thus :p _ q ^ r ! p $ s is really (((:p) _ (q ^ r)) ! p) $ s where we ▯rst do the negation, then we compute q ^ r and then we do the _ and ▯nally we do the ! and the $. We sometimes will add super uous parentheses in order to make the order of operations clear. You should at least be clear about the relative precedence of not, and, or, if-then. 1.3 A family of operations There are several related operations we can perform given two inputs P and Q. We start with the conditional P ! Q. then we take the converse Q ! P, then we take the inverse :P ! :Q and then we take the contrapositive :Q ! :P. The inverse is probably not as important to knwo as the converse and contrapositive. People will often say thing like: If P then Q and conversely in order to say that the implication works in both directions: If P then Q but also if Q, then P. People will often also say things like: If P then Q, but not conversely. That means if P then Q si true but if Q then P is not a true statement. 6 The contrapostive is important because the original implication and the contrapositive have the same truth value. If you know that it is true that if P then Q, it might be convenient to reason from the fact that you know Q to be false and hence not Q to be true|to reason from there to the conclusion that P cannot be true if the implication is to be true. So if we know that if you got the job, you passed the exam; we also know that if you did not pass the exam, you did not get the job. 2 Evaluating Propositional Formulae Given a complicated propositional formula containing many variables, we might want to ▯gure out when the formula is true, for what values of the inputs is the formula true. For this purpose we can use truth tables. This is illustrated in the textbook and was discussed in class. When you use truth tables you do have to be careful that you have covered all possible combinations of truth values for the input variables. In general if there are n inputs, there should be 2 rows in your truth table. Be careful that you have covered all possible cases. If a formula is true for all possible values of the inputs (all rows of the truth table result in output true), we say the formuila is a tautology. But if a formuia is false for all possible values of the inputs (all rows of the truth table result in false output), then the formula is a contradiction. The third alternative is a contingency. With a contingency, sometimes you obtain true and sometimes you get false. In addition to just working with one propositional formuia, we might be working with two formulae and we might be curious if the two formulae always have the same truth value. If they do, we say that they are equivalent. We can use a truth table (be sure you have checked all cases) to recognize whether two statements are equivalent. We write p ▯ q to mean that p is equivalent to q. We have many rules telling us which statements are equivalent to which other statements. We can program a computer to automatically recognize whether a formula is a tautology, a contradiction, or neither or to automatically recognize if two formulae are equivalent. The computer (or you) could use truth tables. B
More Less

Related notes for CIS 1166

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.