Compound Propositions Lecture Notes PDF

Compound Propositions Jagath Wujerathna Department of Mathematics University of Colombo June 22, 2023 1/10 Compound Propositions All logical operations can be applied to construct an arbitrarily complex compound propositions Any proposition ca...

Compound Propositions Jagath Wujerathna Department of Mathematics University of Colombo June 22, 2023 1/10 Compound Propositions All logical operations can be applied to construct an arbitrarily complex compound propositions Any proposition can become a term inside another proposition. Examples p, q.r , s are simple propositions. p ∧ q and r → t are compound propositions. (p ∧ q) → t and (p ∧ q) ∨ (t ∧ r ) are further complex compound propositions. Parenthesis indicate the order of evaluation. 2/10 Precedence of Logical Operations To reduce number of parenthesis use precedence rules Operation Precedence ¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5 Examples p ∨ q ∧ r means p ∨ (q ∧ r ) (p ∨ q) ∧ r requires the parenthesis. 3/10 Logical Equivalence A tautology is a proposition that is always true. Example p ∨ ¬p p ¬p p∨¬p T F T F T T A contradiction is a proposition that is always false Example p ∧ ¬p p ¬p p∧¬p T F F F T F 4/10 Equivalent Propositions Two propositions are logically equivalent if they always have a the same truth value. We denote it by p ≡ q Formally: p and q are logically equivalent if and only if(iff) p ↔ q is a tautology. 5/10 Equivalence Consider two compound propositions p → q and ¬p ∨ q. p q p→q ¬p ∨ q T T T T T F F F F T T T F F T T We can see that all truth values of the both compound propositions are are identical, therefore those propositions are equivalent. In other words (p → q) ↔ (¬p ∨ q) is a tautology. Remark: Proving equivalence via truth tables can be cumbersome for complex propositions. 6/10 Laws of Prepositional Logic Suppose you have to show that p ≡ q Then you ma use sequence of steps using propositional logic as follows p ≡ p1 p ≡ p2 p ≡ p3 p ≡ p4............. pn ≡ q Each step follows one of the equivalence laws. 7/10 Laws of Prepositional Logic 8/10 Laws of Prepositional Logic 9/10 Laws of Prepositional Logic 10/10