Propositional Logic PDF

IT2212 Propositional Logic What is a proposition? Defined as a statement to be proved, explained, or discussed It is a declarative sentence that is either false or true (NOT both) When represented in tables, capital letters are usually used for proposition. Example: P = To...

IT2212 Propositional Logic What is a proposition? Defined as a statement to be proved, explained, or discussed It is a declarative sentence that is either false or true (NOT both) When represented in tables, capital letters are usually used for proposition. Example: P = Today is January 1 The letter P will represent the statement in tables. Also, we use the letter T to represent a true statement and F to represent a false statement. Using numerical symbols, 1 represents true while 0 represents false. Hence for the example: P Today is January 1 T or 1 True, today is January 1 F or 0 False, today is not January 1 Bases for Propositional Logic During the 18th, 19th, and early 20th Century, scholars who saw themselves as carrying on the Aristotelian and Medieval tradition in logic, often pointed to the “laws of thought” as the basis of all logic. The three (3) laws are as follows: Law of Identity or “Logical Identity” It is the notion that things must be, of course, identical with themselves. P = P If water is water, then by the law of identity, anything we discover to be water must possess the same properties. Law of Excluded Middle It is the idea that every proposition must be either true or false, not both and not neither. If the date today is January 1, the proposition P is true only; it cannot also be false. Law of Non-Contradiction Logically correct propositions cannot affirm and deny the same thing Is it January 1 today? The answer could only be yes or no and not both. Examples Statement? Proposition? Truth Value (Y/N) (Y/N) (T/F) A : Chickens can fly. Y Y F B : 2022 < 100 Y Y F C : x > 10 Y N -- D : Today is January 1 and 1 < 0. Y Y F E : Please keep your phones on silent mode. N -- -- F : If chickens could fly, it would be harder to eat them. Y Y ~F G : x < y if and only if y > x. Y Y T Note: C is not a proposition since the truth value of the statement will depend on the value of x. x = 15 > 10 is a True proposition x = 5 > 10 is a False proposition E is not a statement; it is a request. Only statements could be propositions. Although F is a proposition, its truth value cannot be ascertained unless proven. Truth Table (Levin) It is a chart to keep track of all the possibilities in the proposition. The idea is on each row, we list a possible combination of T’s and F’s (for true and false) for each of the variables and then mark down whether the statement in question is true 01 Handout 1.1 *Property of STI Page 1 of 6  IT2212 or false in that case. We do this for every possible combination of T’s and F’s. Then we can clearly see in which cases the statement is true or false. Example: Condition: You can only go out of the house if you are in the 18-65 years old range and fully vaccinated. Proposition A: Are you in the 18-65 years old range? Proposition B: Are you Fully Vaccinated? Truth Table: (includes all possibilities) Sample A B C Can go out? 1 T T You are within the age limit and fully vaccinated. T and T = Yes (T) 2 T F You are within the age range but not fully vaccinated. T and F = No (F) 3 F T Not within the age range but fully vaccinated. F and T = No (F) 4 F F Not within the age range and not fully vaccinated. F and F = No (F) Because the condition is that you have to answer yes (True) to both statements; therefore only sample 1 will be allowed to go out. Logical Connectives Compound Proposition - It is a proposition constructed by combining one (1) or more existing propositions. Example: Proposition 1: You are 18 years old. Proposition 2: You are fully vaccinated. Compound Proposition: You are 18 years old and fully vaccinated. Types of Logical Connectives: 1. Negation - Combines propositions using the keyword not. It states the opposite of the proposition. We use the symbol ( ~ ) or ( ¬ ) attached to the representation of the proposition to indicate that it is the negation of the said proposition. Example: Proposition P: It is raining. Negation of P (~P): It is not raining. Truth Table: P ~P True (T) or 1 False (F) or 0 False (F) or 0 True (T) or 1 2. Conjunction – Combines propositions using the keyword and. The conjunction would only be true if both initial propositions are true. The symbol (^) is used to represent the word and in a conjunction. Example: Proposition A: Today is January 1. Proposition B: It is raining. Conjunction: Today is January 1 and it is raining. Truth Table: A B A^B T T T T F F F T F F F F 3. Disjunction – Combines proposition using the keyword or. The combined proposition called a disjunction will be true if one of the propositions is true. The symbol (v) is used to represent the word or in a disjunction. 01 Handout 1.1 *Property of STI Page 2 of 6  IT2212 Example: Proposition A: The person is below 18 years old. Proposition B: The person is a senior citizen. Disjunction: Either the person is below 18 years old or a senior citizen. Truth Table: A B AvB T T T T F T F T T F F F 4. Implication – The combined propositions are formed as if-then statements. The order of which proposition comes first is important. The first proposition is called the antecedent and the second proposition is the consequence. The symbol used to represent an implication is an arrow (→) from the ‘if-statement’ (antecedent) to the ‘then- statement’ (consequence). Example: Proposition A: The sky is overcast. Proposition B: The sun cannot be seen. Implication: If the sky is overcast, then the sun cannot be seen. Truth Table: A B A→B T T T T F F F T T F F T Other implications that can be formed from A → B Converse – The reverse of the implication. The second statement is now the antecedent, hence B → A If the sun cannot be seen, then the sky is overcast. Contrapositive – The propositions are negated and interchanged. ~B → ~A If the sun can be seen, then the sky is not overcast. Inverse – The propositions are negated. ~A → ~B If the sky is not overcast, then the sun can be seen. 5. Biconditional – A statement combining a conditional statement with its converse. The words if and only if is used in this proposition and the symbol is (→). For the biconditional to be true, both propositions should have the same truth value (TT or FF). Example: Proposition A: The sky is overcast. Proposition B: The sun cannot be seen. Biconditional: The sky is overcast if and only if the sun cannot be seen. Truth Table: A B A → B T T T T F F F T F F F T 6. XOR – Read as exclusive or is a version of a disjunction that does not allow both propositions to be true simultaneously. The symbol used is (⊕). It is often used for bitwise operations, particularly in computer science. Examples: 1 ⊕ 1 = 0 0⊕0=0 1⊕0=1 Truth Table: A B A⊕B 01 Handout 1.1 *Property of STI Page 3 of 6  IT2212 T T F T F T F T T F F F In computer science, XOR has several uses: - It tells whether two bits are unequal. - It is an optional bit-flipper. - It tells whether there is an odd number of 1 bit. - In logical circuits, a simple adder can be made with an XOR gate to add the numbers and a series of AND, OR, and NOT gates to create the carry output. - It is sometimes used as a simple mixing function in cryptography - It is also used to detect an overflow in the result of a signed binary arithmetic operation. Truth Table Reference - Use the table below as a guide when working with truth tables. The truth values for the logical connectives discussed are summarized in this table. TRUTH TABLE (exclusive disjunction) A if and only if B (biconditional) (conjunction) a proposition a proposition a proposition (implication) (disjunction) If A then B (negation) A XOR B A and B A or B not P P ~P A B A^B AvB A⊕B A→B A→B T F T T T T F T T F T T F F T T F F F T F T T T F F F F F F T T Precedence of Logical Operators - Similar to the order of operations in arithmetic, there is a set order to be observed when solving for complex propositions. Level Operator 1 Negation (~) 2 Conjunction (^) 3 Disjunction (v) 4 Implication (→) 5 Biconditional (→) Example: 1. ~A ^ B Since negation first before conjunction, do ~A first, then ~A ^ B 1st step 2nd step A B ~A ~A ^ B T F T F T F F F F T T T 01 Handout 1.1 *Property of STI Page 4 of 6  IT2212 F T F F 2. AvB^C Since conjunction takes precedence before disjunction, then (B ^ C) first before A v (B ^ C) 1st step 2nd step A B C B^C AvB^C T T T T T T F T F T F T F F F F F F F F Try these: 3. A^B^C^D 4. A^B→AvB 5. A→B→C Tautology Tautology – It is any statement that is TRUE regardless of the truth values of the constituent parts Example: Show in a truth table that the statement A v ~A is a tautology A ~A A v ~A T F T T F T F T T F T T Since each entry in the truth table for A v ~A is true, then it is a tautology Contradiction – It is any statement that is always false regardless of the truth values of the parts. It is the opposite of a tautology. Example: Show in a truth table that the statement A ^ ~A is a contradiction. A ~A A ^ ~A T F F T F F F T F F T F Since each entry in the truth table for A ^ ~A is true, then it is a contradiction. Contingency – It is any statement that is neither a tautology or a contradiction. Example: Show in a truth table that the statement A → ~A is a contradiction. A ~A A → ~A T F F T F F F T T F T T Since entries in the truth table for A → ~A is a mix of true and false, then it is a contingency. Logical Equivalence When two (2) different compound propositions have exactly the same truth value in every case, then the propositions are logically equivalent. The symbol used to denote logical equivalence is ≡ Example: Show in a truth table that the two (2) compound propositions are logically equivalent. A ≡ ~~A A ~A ~~A T F T T F T F T F 01 Handout 1.1 *Property of STI Page 5 of 6  IT2212 F T F Since column 1 (A) and column 3 (~~A) are exactly the same, then they are logically equivalent. Exercises: 1. (A → B) ≡ (~A v B) 2. ~(A v B) ≡ (~A^ ~B) 3. ~(A^B) ≡ (~A v ~B) References: Busby, R. B. K. (2022). Discrete mathematical structures: Pearson New International (6th ed). Pearson Education Limited. de Troyer, O., Lindberg, R., & Sajjadi, P. (2019). TrueBiters, an educational game to practice the truth tables of propositional logic: Development, evaluation, and lessons learned. Smart Learning Environments, 6(1). https://doi.org/10.1186/s40561-019-0105-2 Fortney, J. P. (2021). Discrete mathematics for computer science: An example-based introduction. CRC Press, Taylor & Francis Group. Lewis, H.,& Zax, R. (2019). Essential Discrete Mathematics for Computer Science. Princeton University Press. “Naturalistic Epistemology,” by Chase B. Wrenn, The Internet Encyclopedia of Philosophy, ISSN 2161-0002, https://iep.utm.edu/, January 20, 2022 proposition. (n.d.). In Merriam-Webster. Retrieved January 28, 2022, from https://www.merriam - webster.com/dictionary/proposition Rosen, K. H. (2019). Discrete mathematics and its applications. McGraw-Hill Education. WISE Lab. (n.d). TrueBiters. Web & Information Systems Engineering. https://wise.vub.ac.be/project/truebiters 01 Handout 1.1 *Property of STI Page 6 of 6