Concept

How do logical connectives combine propositions?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"So things are pretty boring so far. We can define and label propositions, but none of them have any connections to the others. We change that by introducing logical operators (also called logical connectives) with which we can build up compound constructions out of multiple propositions. The six connectives we’ll learn are:\n\n∧ — “and”\n\n¬ — “not”\n\n∨ — “or”\n\n⇒ — “implies” (or “if…then …”)\n\n⊕ — “xor” (exclusive “or”)\n\n⇔ — “equiv” (equivalent)\n\nJust as the ordinary algebraic operators (+, -, etc.) can be used to join numbers and produce another number, and just as the set operators can be used to join sets and produce another set, the logical operators can be used to join propositions and produce another proposition. The expression “34 + 59” produces the number 93. The expression “{X,Y} ∪ {Y,Z}” produces the set {X,Y,Z}. And the expression “A ∧ B” produces the value false, since although UMW is located in Virginia, the King is not female.\n\n∧ (“and”)\n\nThe proposition X ∧ Y is true when both X and Y are true propositions. “A ∧ C” represents the proposition “UMW is in Virginia and dogs are carnivores,” which has a truth value of true since both components are true. This operation is sometimes called a conjunction. Notice that the “∧” sign somewhat resembles the “∩” sign for set intersection. This is not an accident. An element is in the intersection of two sets if it is a member of the first and the second set. Hence mathematicians have chosen symbols which reinforce this connection.\n\n∨ (“or”)\n\nThe proposition X ∨ Y is true when either X or Y (or both) are true propositions. “B ∨ C” represents the proposition “The King of England is female or dogs are carnivores,” which has a truth value of true since the second component is true. This operation is sometimes called a disjunction. The ∨ looks somewhat like the “∪” sign for set union, since an element is in the union of two sets if it is an element of the first set or the second set (or both). This operator is sometimes called an “inclusive or” since it is true if both propositions are true.\n\n⊕ (“xor”)\n\nThe ⊕ operator is just like ∨ except that it’s exclusive: the proposition X ⊕ Y is true when either X or Y (but not both) are true propositions. “B ∨ C” and “B ⊕ C” are both true, but “A ⊕ C” is false, since UMW is in Virginia and dogs are carnivores.\n\n¬ (“not”)\n\nThis operator is different from the others in that it’s unary, which means that it only operates on one proposition instead of two. All it does is flip the value from true to false (or vice versa.) The proposition “A” is true, but the proposition “¬ A” is false. “¬ B,” on the other hand, is true. This operation is sometimes called a negation."

Related Ideas

How do logical connectives combine propositions? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm