Discrete Structures: Propositional Logic PDF

DISCRETE STRUCTURES Introduction This course studies the mathematical elements of information technology and computer science including propositional logic, set theory, functions and relations, graphs, trees and Boolean logic. In this module, students will learn to recognized and express the m...

DISCRETE STRUCTURES Introduction This course studies the mathematical elements of information technology and computer science including propositional logic, set theory, functions and relations, graphs, trees and Boolean logic. In this module, students will learn to recognized and express the mathematical ideas graphically, numerically, symbolically, and in writing. Course Intended Learning Outcomes At the end of the module, the students will be able to: 1. Perform the operations associated with Sets, Functions and Relations, and relate these operations to computer programming. 2. Construct sound arguments in propositional and predicate logic by applying appropriate rules of inference given sample intelligent software. 3. Construct valid mathematical proofs using mathematical induction, direct proof and proof by contradiction to simplify programs and prove program correctness. Unit 1. Propositional Logic Introduction Logic rules provide exact meaning to mathematical assertions. These criteria are used to differentiate between correct and incorrect mathematical arguments. This module will teach the learner how to understand and develop sound mathematical arguments. It includes the study of propositional logic. Aside from its importance in comprehending mathematical reasoning, logic has several applications in information technology. These rules are employed in the design and construction of computer programs, the verification of program correctness, and a variety of other computer applications. Furthermore, some software systems have been developed for constructing some types of proofs automatically. These logic applications will be covered in this unit, including topics on arguments and proofs. Learning Outcomes At the end of the unit, you will be able to: 1. Write English sentences for logical expressions and vice-versa. 2. Use standard notations of propositional logic. 3. Construct a complete and accurate truth tables for logical expressions involving logical connectives.  4. Show whether two propositions are logically equivalent. 5. Shoe that a compound proposition is a tautology, contradiction and contingency. 6. Identify the rule of inference in the compound proposition. 7. Evaluate the validity of an argument by identifying the critical rows. 1.1. Introduction to Discrete Structures Logic and Propositions The first topic we are going to deal with is about the basic building blocks of logic- propositions. Logic is the study of reasoning which is specifically concerned with whether reasoning is correct. It focuses on the relationship among statements as opposed to the content of any particular statement. Example: Sequence of statements: 1. All students take IT 123. 2. Anyone who takes IT 123 is BSIT. 3. Therefore, all students are BSIT. If (1) and (2) were true, the logic would assure that (3) is true. A proposition is a declarative sentence which is true or false, but not both. A propositional logic is a logic at the sentential level. It is a part of logic which deals with statements that are either true or false (but not both), hence, the smallest unit we deal with propositional logic is a sentence (proposition). Example 1: All the following statements are propositions 1. Washington, D.C. is the capital of the USA. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. Propositions 1 and 3 are true, whereas 2 and 4 are false. Example 2. Consider the following sentences. 1. Where are you going? 2. Read this carefully. 3. x + 1=2  4. x + y = 3 Sentence 1 and 2 are not propositions because they are not statements. Sentence 3 and 4 are not propositions because they are neither true or false, since the variables in these sentences have not been assigned values. Types of Propositions Primitive Propositions A proposition is said to be primitive if it cannot be broken down into simpler propositions, that is, if it is not composite. The propositions in Example 1 are all primitive propositions; they cannot be broken down into simpler propositions. Compound Propositions These are propositions that are composite, that is, composed of sub-propositions and various connectives. Such composite propositions are called compound propositions. Example: 1. “Roses are red and violets are blue” is a compound proposition with sub- propositions “Roses are red” and “violets are blue”. 2. “John is intelligent or studies every night” is a compound proposition with sub- propositions “John is intelligent” and “John studies every night”. 1.2. Propositions and Its Elements Logical Connectives The compound propositions are formed from existing propositions using logical connectives. For the given statements p and q: 1. Negation of p: ¬ p (not p) The proposition ¬ p is read “not p”. The truth value of the negation of p, ¬ p, is the opposite of the truth value of p. The relationships of the value of a proposition and those of its constituent variables can be represented by a table. This table tabulates the value of a proposition for all possible values of its variables and it is called a truth table.  The connective NOT simply negates the truth value of a proposition. If a proposition is true, the resulting value is false, if it’s true, then the resulting value is false. The truth table of NOT is given in table 1. p ¬p T F F T Table 1. The truth table for the Negation of a proposition Example: Find the negation of the proposition and express this in simple English. a. “Richard’s PC runs Linux” Solution: “It is not the case that Richard’s PC runs Linux”. This negation can be more simply expressed as: “Richard’s PC does not run Linux”. b. “Anna’s smartphone has at least 32GB of memory”. Solution: “It is not the case that Anna’s smartphone has at least 32GB of memory. Or “Anna’s smartphone does not have at least 32GB of memory”. 2. Conjunction, p ˄ q The conjunction of p and q, denoted by p ˄ q, is the proposition “p and q”. The conjunction p ˄ q is true when both p and q are true and is false otherwise. The truth value of the compound proposition p ˄ q is defined by the truth table in Table 2.  p q p˄q T T T T F F F T F F F F Table 2: The truth table for the conjunction of two propositions. Example: Let p: Rebecca’s PC has more than 16GB free hard disk space. q: The processor in Rebecca’s PC runs faster than 1 GHz. Solution: Rebecca’s PC has more than 16GB free hard disk space, and its processor runs faster than 1 GHz. For this condition to be true, both conditions given must be true. It is false, when one or both of these conditions are false. 3. Disjunction p ˅ q The disjunction of p and q, denoted by p ˅ q, is the proposition “p or q”. The disjunction p ˅ q is false when both p and q are false and is true otherwise. The truth table for p ˅ q is shown in table 3. p q p˅q T T T T F T F T T F F F Table 3. The Truth Table for the Disjunction of two propositions  Example: What is the disjunction of the propositions p and q Let p: Rebecca’s PC has more than 16GB free hard disk space. q: The processor in Rebecca’s PC runs faster than 1 GHz. Solution: “Rebecca’s PC has at least 16GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz”. This proposition is true when Rebecca’s PC has at least 16GB free hard disk space, when the PC’s processor runs faster than 1 GHz , and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16GB free hard disk space and the processor in her PC runs at 1 GHz or slower. 4. Conditional Statements, p → q The conditional statement p → q is the proposition “if p, then q”. The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called implication. The truth table for the conditional statement p → q is displayed in Table 4. Note that the statement p → q is true when both p and q are true and when p is false (no matter what truth value q has). P Q p q T T T T F F F T T F F T The following terminology is used to express p → q, for conditional statement play an essential role in mathematical reasoning. “if p, then q” “p implies q” “if p,q” “p only if q” “p is sufficient for q” “a sufficient condition for q is p” “q if p” “q whenever p” “q when p” “q is necessary for p” “a necessary condition for p is q” “q follows from p” “q unless ¬ p Example: Let p: Maria learns Discrete Structures and q: Maria will find a good job. Express the statement p → q as a statement in English. Solution: “If Maria learns Discrete Structures, then she will find a good job.” Other ways to express this conditional statement in English are: “Maria will find a good job when she learns discrete structures.” “For Maria to get a good job, it is sufficient for her to learn discrete structures.” “Maria will find a good job unless she does not learn discrete structures.” Converse, Contrapositive, and inverse For the conditional statement p → q, there are three related conditional statements that occur so often that they have special names. The proposition q → p is called the converse of p → q. The contrapositive of p → q is the proposition ¬q → ¬p. The proposition ¬p → ¬q is called inverse of p → q. Example: “If Bobcats win this game, then they will be number one.” Contrapositive: If Bobcats aren’t number one, then they didn’t win. Converse: If Bobcats are number one, then they won the game. Inverse: If Bobcats don’t win this game, then they will not be number one. The contrapositive of a proposition is always logically equivalent to the proposition. This means that they have the same truth value regardless of the values of their constituent variables. Example: “If it rains, then I get wet”. And “If I don’t get wet, then it does not rain” are logically equivalent. If one is true then the other is also true, and vice versa. 5. Biconditional statement p ↔q Another way to combine propositions that expresses that two propositions have the same truth value are biconditional statements. The biconditional statement p ↔q is the proposition “p if only q.” The biconditional statement p ↔q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The truth table of p ↔q is shown in Table 5. p q p q T T T T F F F T F F F T There are some common ways to express p ↔q such as: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q” Example: Let p: You can take the flight and q: You buy a ticket Then the p ↔q is the statement: You can take the flight if and only if you buy a ticket.  Precedence Rules The following precedence rules will be followed when forming statements using logical connectives. 1. Not ¬ 2. And, ˄ 3. Or, ˅ 4. If-then, → 5. If and only if, ↔ We can use parentheses to specify the order in which logical operators in a compound propositions are to be applied. To reduce the number of parentheses, the precedence order is defined for logical operators. Translating English Sentences into Symbolic Form The following examples demonstrate the process of converting English statements in symbolic form: Assume that we have the following propositions: p: I will go to Manila s: the topic is interesting q: I have money m: I will learn a lot r: I will attend a seminar n: the speaker is intelligent English Statement Symbolic Form 1. I will not go to Manila p 2. If I have money then I will go to Manila and I qp r will attend a seminar 3. Neither I will go to Manila nor I will attend a (p r) seminar 4. Either the topic is interesting or the speaker is (s n)m intelligent then I will learn a lot 5. I will go to Manila if and only if I have money p q The examples below translate symbolic propositions into words Symbolic Form English Statement 1. n r The speaker is not intelligent or I will attend a seminar  2. p (q r) I will go to manila if and only if I have money and I will attend a seminar 3. n sm If the speaker is intelligent and the topic is interesting then I will learn a lot 4. r p q I will attend a seminar or I will go to Manila and I have money 1.3. Truth Tables of Compound Propositions After introducing the four important logical connectives – conjunctions, disjunction, conditional statements, and bi-conditional statements, and also negations, we can now use these connectives to build up complicated compound propositions involving any number of propositional variables. A truth table can be used to determine the truth values of these compound propositions. The truth value of a proposition depends exclusively upon the truth values of its variables, that is the truth value of a proposition is known once the truth values of its variables are known. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table. Example #1: Construct the truth table of the compound proposition. (p ˅ ¬q) → (p ˄ q) p q ¬q p ˅ ¬q p˄q (p ∨￢q) → (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F The truth table above involves two propositional variables p and q, there are four rows in this truth tables, one for each of the pairs of truth values TT, TF, FT, and FF. The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of ¬q, needed to find the truth value of p v ¬q, found in the fourth column. The fifth column gives the truth value of p ᴧ q. Finally, the truth value of (p ˅ ¬q) → (p ˄ q) is found in the last column. EXERCISES #1: 1. Evaluate each proposition for the truth values. p = true, q = false, r= true a. (p q) ( p r) b. (r  q  p) ( p r) c. ( q  r )  (p r q) d. r p p q q r 2. Formulate the symbolic expression in words using P: Today is Thursday Q: It is raining R : It is hot a. P Q R b. (P Q ) (R P) c. QR P d. R Q (P R) e. (Q R) 3. Construct the truth tables of the following propositions: a. (p q) b. (p q) c. (p  q) d. p (p  q) Self-Assessment Test 1. Translate the given statement into propositional logic using the propositions provided. a. You cannot edit a protected Wikipedia entry unless you are an administrator. Express your answer in terms of: e: “You can edit a protected Wikipedia entry” and a: “You are an administrator” b. You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of: g: “You can graduate” m: “You owe money to the university” r: “You have completed the requirements of your major” b: “You have an overdue library book”  2. Express these system specifications using the propositions p “The message is scanned for viruses” and q “The message was sent from an unknown system” together with logical connectives (including negations). a. “The message is scanned for viruses whenever the message was sent from an unknown system.” b. “The message was sent from an unknown system but it was not scanned for viruses.” c. “It is necessary to scan the message for viruses whenever it was sent from an unknown system.” d. “When a message is not sent from an unknown system it is not scanned for viruses.” 1.4. Propositional Equivalences The substitution of one assertion with another that has the same truth value is a crucial type of step in a mathematical argument. As a result, techniques that result in propositions that have the same truth value as a particular compound statement are frequently utilized in the formulation of mathematical arguments. The expression created from propositional variables employing logical operators like p v q is referred to as a "compound proposition" in this section. We begin by categorizing compound propositions in accordance with their truth values. TAUTOLOGIES AND CONTRADICTION A tautology is a compound assertion that is always true, regardless of the truth values of the propositional variables it contains. A contradiction is a statement form which is false for all values of statement variables. In mathematical reasoning, tautologies and contradiction often play an important role. Let’s see how these compound propositions is being used in the example below. Example 1: p v ￢p is a tautology: p v ￢p ≡ t p ^ ￢p is a contradiction: p ^ ￢p = c p ￢p p v ￢p p ^ ￢p T F T F F T T F  Example 2: Verify that the proposition p v￢(p ^ q) is a tautology. Solution: First we will construct the truth table of the proposition and evaluate if the proposition is a tautology. p q p ^q ￢(p ^ q) p v￢(p ^ q) T T T F T T F F T T F T F T T F F F T T As we can see in the table, all truth values of p v￢(p ^ q) is T (true) for all values of p and q, therefore we can say that the proposition is a tautology. Example 3: Verify that (p ^ q) ^ ￢(p ^ q) is a contradiction. Solution: Construct first the truth table and evaluate the proposition by looking at the truth values for all the statement variables. p q p ^q ￢(p ^ q) (p ^ q) ^ ￢(p ^ q) T T T F F T F F T F F T F T F F F F T F Since the truth values of the proposition is F (false) for all values of p and q, the proposition (p ^ q) ^ ￢(p v q) is a contradiction. LOGICAL EQUIVALENCES Logically equivalent compound propositions are those whose truth values are the same across all cases of the statement variables. This is defined as follows. The compound propositions p and q are called logically equivalent if and only if they have identical truth values for each substitution of their component statement variables. This is denoted with the expression p ≡ q. Note: The symbol ≡ is not a logical connective, and p ≡ q is not a compound proposition but rather is the statement that p ↔q is a tautology. A truth table can be used to determine whether two compound propositions are equivalent. Example 1: Verify that ￢(p v q) ≡ ￢p ^ ￢q are logically equivalent. Solution: By constructing the truth table of the proposition we can verify if it is logically equivalent or not. p q ￢p ￢q pvq ￢(p v q) ￢p Λ ￢q T T F F T F F T F F T T F F F T T F T F F F F T T F T T As we can see on the truth table, both the proposition ￢(p v q) and ￢p Λ ￢q are the same for all statement variables, therefore we can say that the propositions are logically equivalent. Example 2: Show that p →q and ￢p v q are logically equivalent. Solution: Construct the truth table of p →q and ￢p v q. p q ￢p p →q ￢p v q T T F T T T F F F F F T T T T F F T T T Since the truth value for all the statement variable of p →q and ￢p v q are the same, then we can say that the propositions are logically equivalent. Exercise #2: 1. Determine whether ( ￢q ^ (p →q)) → ￢p is a tautology. 2. Show that ￢(p ↔q) and p ↔￢q are logically equivalent. 3. Show that p→q is logically equivalent to ￢p v q, that is p→q ≡ ￢p v q 4. Verify that (p˄q) →(p v q) is a tautology. 5. Prove that the conditional operation distributes over conjunction; that is p→(q ˄ r)≡ (p→q )˄(p→r) 1.5. Argument and Proofs Valid Arguments in Propositional Logic An argument is an assertion that a given set of propositions P1 , P2 ,…. Pn , called premises, yields another proposition Q, called the conclusion. An argument is valid if the truth value of all its premises implies that the conclusion is true. Such an argument is denoted by: P1 , P2 ,…. Pn ├ Q An argument is a sequence of statements such that: Statement 1; Statement 2; Therefore, Statement 3. Statement 1 and 2 are called premises and statement 3 is called the conclusion. Let’s try to evaluate the following argument involving propositions: If you have a password, then you can log in to the computer. You have a password. Therefore, you can log in to the computer. Here, let’s see if the argument is valid by looking into the conclusion “You can log in to the computer” is true when the premises “If you have a password, then you can log in to the computer” and “You have a password” are both true. Before we can determine the validity of this argument, let’s look first at its form. We will use p to represent the statement “You have a password “ and q to represent “You can log in to the computer”. Then, the argument has the form:  p→q p ______ q In this argument, when both p → q and p are true, we know that q must also be true. And we can assert that this form of argument is valid because whenever all the premises (in this case p → q and p) are true, the conclusion (q) must also be true. Checking the Validity of an Argument 1. Construct truth table for the premises and the conclusion; 2. Find rows in which all the premises are true (critical rows); 3. If in each critical row the conclusion is true, then the argument form is valid; 4. If there is a row in which conclusion is false, then argument form is valid; 5. If there is a row in which conclusion is false, then the argument is invalid or fallacy; Example: 1. Show that the following argument is valid: p, p → q ├ q p q p→q T T T T F F F T T F F T For p is true in row 1 and row 2, and p → q is true in row 1, 3, and 4, hence p and p → q is true simultaneously in row 1. Since in this row q is true, the argument is valid. 2. Show that the following argument is a fallacy: p → q, q ├ p p q p→q T T T T F F F T T F F T  Both p → q and q are true in row 3 in the table, but in this case the conclusion p is false. Exercise # 3 1. Show that the following argument is a fallacy: p → q, ~p ├ ~q 2. Determine the validity of the argument: p → q, ~q ├ ~p 3. Show that the following argument is valid: p ↔ q, q ├ p 4. Determine the validity of the argument ~p → q, p ├ ~q Rules of Inference for Propositional Logic To show that an argument form is valid a truth table can be use. However, when an argument form involves 10 different propositional variables it may become a tedious approach. We can then first establish the validity of an argument form, called rule of inference. These rules of inference can be used as building blocks to construct more complicated valid argument forms. The tautology (p ^ (p → q )) → q is the basis of the rule of inference called modus ponens, or the law of detachment (Modus ponens is Latin for mode that affirms). This tautology leads to the following valid argument as written below: p→q p ______ q With this notation, the hypotheses are written in a column, followed by a horizontal bar, followed by a line that begins with the therefore symbol and ends with the conclusion. In particular, modus ponens tells us that if a conditional statement and the hypothesis of this conditional statement are both true, then the conclusion must also be true. Example 1: Argument 1: If it snows today, then we will go skiing”. Argument 2: It is snowing today. Therefore: We will go skiing Solution: If argument 1 and 2 (which are the hypotheses) are true. Then by modus ponens, it follows that the conclusion of the conditional statement is true. As we mentioned earlier, a valid argument can lead to an incorrect conclusion if one or more of its premises is false. There are many useful rules of inference for propositional logic (see table 1). Example 2 State which rule of inference is the basis of the following argument. 1. It is below freezing now. Therefore, it is either below freezing or raining now. 2. It is below freezing and raining now. Therefore, it is below freezing now. 3. If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow. Exercise #3: