{"id":1918,"date":"2017-03-20T03:05:18","date_gmt":"2017-03-20T03:05:18","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/?post_type=chapter&#038;p=1918"},"modified":"2019-06-13T02:26:23","modified_gmt":"2019-06-13T02:26:23","slug":"introduction-introduction-to-logic","status":"publish","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/chapter\/introduction-introduction-to-logic\/","title":{"raw":"1.3: Logic Basics","rendered":"1.3: Logic Basics"},"content":{"raw":"In this section, we will learn how to construct logical statements. We will later combine our knowledge of sets with what we will learn about constructing logical statements to analyze arguments with logic.\r\n<div class=\"textbox learning-objectives\">\r\n<h3>Learning Objectives<\/h3>\r\nIntroduction to Logic\r\n<ul>\r\n \t<li>Combine sets using Boolean logic, using proper notations<\/li>\r\n \t<li>Use statements and conditionals to write and interpret expressions<\/li>\r\n \t<li>Use a truth table to interpret complex statements or conditionals<\/li>\r\n \t<li>Write truth tables given a logical implication, and it\u2019s related\u00a0statements \u2013 converse, inverse, and contrapositive<\/li>\r\n \t<li>Determine whether two statements are logically equivalent<\/li>\r\n \t<li>Use DeMorgan\u2019s laws to define logical equivalences of a statement<\/li>\r\n<\/ul>\r\n<\/div>\r\nLogic is a systematic way of thinking that allows us to deduce new information\u00a0from old information and to parse the meanings of sentences.\u00a0You use logic informally in everyday life and certainly also in doing mathematics.\u00a0For example, suppose you are working with a certain circle, call it\u00a0\u201cCircle X,\u201d and you have available the following two pieces of information.\r\n<ol>\r\n \t<li>Circle X has radius equal to 3.<\/li>\r\n \t<li>If any circle has radius [latex]r[\/latex], then its area is [latex]\\pi{r}^{2}[\/latex]\u00a0square units.<\/li>\r\n<\/ol>\r\nYou have no trouble putting these two facts together to get:\r\n<ol start=\"3\">\r\n \t<li>Circle X has area [latex]9\\pi[\/latex] square units.<\/li>\r\n<\/ol>\r\nYou are using logic to combine existing information to\u00a0produce new information. Since a major objective in mathematics is to\u00a0deduce new information, logic must play a fundamental role. This chapter\u00a0is intended to give you a sufficient mastery of logic.\r\n<h2>Boolean Logic<\/h2>\r\nLogic is, basically, the study of valid reasoning. When searching the internet, we use Boolean logic \u2013 terms like \u201cand\u201d and \u201cor\u201d \u2013 to help us find specific web pages that fit in the sets we are interested in. After exploring this form of logic, we will look at logical arguments and how we can determine the validity of a claim.\r\n\r\nWe can often classify items as belonging to sets. If you went the library to search for a book and they asked you to express your search using unions, intersections, and complements of sets, that would feel a little strange. Instead, we typically using words like \u201cand,\u201d \u201cor,\" and \u201cnot\u201d to connect our keywords together to form a search. These words, which form the basis of <strong>Boolean logic<\/strong>, are directly related to set operations with the same terminology.\r\n<div class=\"textbox\">\r\n<h3>Boolean Logic<\/h3>\r\nBoolean logic combines multiple statements that are either true or false into an expression that is either true or false.\r\n<ul>\r\n \t<li>In connection to sets, a boolean search is true if the element in question is part of the set being searched.<\/li>\r\n<\/ul>\r\n<\/div>\r\nSuppose <em>M<\/em> is the set of all mystery books, and <em>C<\/em> is the set of all comedy books. If we search for \u201cmystery\u201d, we are looking for all the books that are an element of the set <em>M<\/em>; the search is true for books that are in the set.\r\n\r\nWhen we search for \u201cmystery <em>and<\/em> comedy\u201d we are looking for a book that is an element of both sets, in the intersection. If we were to search for \u201cmystery<em> or<\/em> comedy\u201d we are looking for a book that is a mystery, a comedy, or both, which is the union of the sets. If we searched for \u201c<em>not <\/em>comedy\u201d we are looking for any book in the library that is not a comedy, the complement of the set <em>C<\/em>.\r\n<div class=\"textbox\">\r\n<h3>Connection to Set Operations<\/h3>\r\n<em>A <\/em>and<em> B<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the intersection <em>A<\/em> \u22c2 <em>B<\/em>\r\n\r\n<em>A<\/em> or <em>B<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the union <em>A<\/em> \u22c3 <em>B <\/em>\r\n\r\nNot <em>A<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the complement <em>Ac<\/em>\r\n\r\n<\/div>\r\nNotice here that <em>or<\/em> is not exclusive. This is a difference between the Boolean logic use of the word and common everyday use. When your significant other asks \u201cdo you want to go to the park or the movies?\u201d they usually are proposing an exclusive choice \u2013 one option or the other, but not both. In Boolean logic, the <em>or<\/em> is not exclusive \u2013 more like being asked at a restaurant \u201cwould you like fries or a drink with that?\u201d Answering \u201cboth, please\u201d is an acceptable answer.\r\n\r\nIn the following video, You will see examples of how Boolean operators are used to denote sets.\r\n\r\nhttp:\/\/youtu.be\/ZOLinnoXEAw\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nSuppose we are searching a library database for Mexican universities. Express a reasonable search using Boolean logic.\r\n[reveal-answer q=\"912486\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"912486\"]\r\n\r\nWe could start with the search \u201cMexico <em>and <\/em>university\u201d, but would be likely to find results for the U.S. state New Mexico. To account for this, we could revise our search to read:\r\n\r\nMexico <em>and<\/em> university <em>not <\/em>\u201cNew Mexico\u201d\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\nIn most internet search engines, it is not necessary to include the word <em>and<\/em>; the search engine assumes that if you provide two keywords you are looking for both. In Google\u2019s search, the keyword <em>or<\/em> has be capitalized as OR, and a negative sign in front of a word is used to indicate <em>not<\/em>. Quotes around a phrase indicate that the entire phrase should be looked for. The search from the previous example on Google could be written:\r\n<p style=\"text-align: center\">Mexico university -\u201cNew Mexico\u201d<\/p>\r\n\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nDescribe the numbers that meet the condition:\r\n\r\neven and less than 10 and greater than 0\r\n[reveal-answer q=\"670488\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"670488\"]The numbers that satisfy all three requirements are {2, 4, 6, 8}\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=25592&amp;theme=oea&amp;iframe_resize_id=mom5[\/embed]\r\n\r\n<\/div>\r\n<h3>Which Comes First?<\/h3>\r\nSometimes statements made in English can be ambiguous. For this reason, Boolean logic uses parentheses to show precedent, just like in algebraic order of operations.\r\n\r\nThe English phrase \u201cGo to the store and buy me eggs and bagels or cereal\u201d is ambiguous; it is not clear whether the requestors is asking for eggs always along with either bagels or cereal, or whether they\u2019re asking for either the combination of eggs and bagels, or just cereal.\r\n\r\nFor this reason, using parentheses clarifies the intent:\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>Eggs and (bagels or cereal) means<\/td>\r\n<td>Option 1: Eggs and bagels, Option 2: Eggs and cereal<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>(Eggs and bagels) or cereal means<\/td>\r\n<td>\u00a0Option 1: Eggs and bagels, Option 2: Cereal<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nDescribe the numbers that meet the condition:\r\n\r\nodd number and less than 20 and greater than 0; and (a multiple of 3 or multiple of 5)\r\n[reveal-answer q=\"877489\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"877489\"]\r\n\r\nThe first three conditions limit us to the set {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}\r\n\r\nThe last grouped conditions tell us to find elements of this set that are also either a multiple of 3 or a multiple of 5. This leaves us with the set\r\n\r\n<strong>{3, 5, 9, 15}<\/strong>\r\n\r\nNotice that we would have gotten a very different result if we had written\r\n\r\n(odd number and less than 20 and greater than 0 and multiple of 3) or multiple of 5\r\n\r\nThe first grouped set of conditions would give {3, 9, 15}. When combined with the last condition, though, this set expands without limits:\r\n<p style=\"text-align: center\"><\/p>\r\n{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, \u2026}\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\nBe aware that when a string of conditions is written without grouping symbols, it is often interpreted from the left to right, resulting in the latter interpretation.\r\n<h3>Conditionals<\/h3>\r\nBeyond searching, Boolean logic is commonly used in spreadsheet applications like Excel to do conditional calculations. A <strong>statement<\/strong> is something that is either true or false.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nA statement like 3 &lt; 5 is true; a statement like \u201ca rat is a fish\u201d is false. A statement like \u201cx &lt; 5\u201d is true for some values of <em>x<\/em> and false for others.\r\nWhen an action is taken or not depending on the value of a statement, it forms a <strong>conditional<\/strong>.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Statements and Conditionals<\/h3>\r\nA <strong>statement<\/strong> is either true or false.\r\nA <strong>conditional<\/strong> is a compound statement of the form\r\n\u201cif <em>p<\/em> then <em>q\u201d<\/em> \u00a0or \u00a0\u201cif <em>p<\/em> then <em>q<\/em>, else <em>s<\/em>\u201d.\r\n\r\n<\/div>\r\nIn common language, an example of a conditional statement would be \u201cIf it is raining, then we\u2019ll go to the mall. Otherwise we\u2019ll go for a hike.\u201d\r\nThe statement \u201cIf it is raining\u201d is the condition\u2014this may be true or false for any given day. If the condition is true, then we will follow the first course of action, and go to the mall. If the condition is false, then we will use the alternative, and go for a hike.\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=108578&amp;theme=oea&amp;iframe_resize_id=mom5[\/embed]\r\n\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=108573&amp;theme=oea&amp;iframe_resize_id=mom[\/embed]\r\n\r\n<\/div>\r\n<h2>Truth Tables<\/h2>\r\nBecause complex Boolean statements can get tricky to think about, we can create a <strong>truth table<\/strong> to break the complex statement into\u00a0simple statements, and determine whether they are true or false. A table will help keep track of all the truth values of the simple statements that make up a complex statement, leading to an analysis of the full statement.\r\n<div class=\"textbox\">\r\n<h3>Truth Table<\/h3>\r\nA table showing what the resulting truth value of a complex statement is for all the possible truth values for the simple statements.\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nSuppose you\u2019re picking out a new couch, and your significant other says \u201cget a sectional <em>or<\/em> something with a chaise.\u201d Construct a truth table that describes the elements of the conditions of this statement and whether the conditions are met.\r\n[reveal-answer q=\"14714\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"14714\"]\r\n\r\nThis is a complex statement made of two simpler conditions: \u201cis a sectional,\u201d and \u201chas a chaise.\u201d For simplicity, let\u2019s use <em>S<\/em> to designate \u201cis a sectional,\u201d and <em>C<\/em> to designate \u201chas a chaise.\u201d The condition <em>S<\/em> is true if the couch is a sectional.\r\n\r\nA truth table for this would look like this:\r\n<table>\r\n<thead>\r\n<tr>\r\n<th><em>S<\/em><\/th>\r\n<th><em>C<\/em><\/th>\r\n<th><em>S<\/em> or\u00a0<em>C<\/em><\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nIn the table, T is used for true, and F for false. In the first row, if <em>S<\/em> is true and <em>C<\/em> is also true, then the complex statement \u201c<em>S <\/em>or<em> C<\/em>\u201d is true. This would be a sectional that also has a chaise, which meets our desire.\r\n\r\nRemember also that <em>or<\/em> in logic is not exclusive; if the couch has both features, it does meet the condition.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\nSome symbols that are commonly used for <em>and<\/em>, <em>or<\/em>, and <em>not<\/em> make using a truth table easier.\r\n<div class=\"textbox\">\r\n<h3>Symbols<\/h3>\r\nThe symbol [latex]\\wedge[\/latex] is used for <em>and<\/em>: <em>A<\/em> and <em>B<\/em> is notated [latex]A\\wedge{B}[\/latex].\r\n\r\nThe symbol [latex]\\vee[\/latex] is used for <em>or<\/em>: <em>A<\/em> or <em>B<\/em> is notated [latex]A\\vee{B}[\/latex]\r\n\r\nThe symbol [latex]\\sim[\/latex] is used for <em>not<\/em>: not <em>A<\/em> is notated [latex]\\sim{A}[\/latex]\r\n\r\n<\/div>\r\nYou can remember the first two symbols by relating them to the shapes for the union and intersection. [latex]A\\wedge{B}[\/latex]\u00a0would be the elements that exist in both sets, in [latex]A\\cap{B}[\/latex]. Likewise, [latex]A\\vee{B}[\/latex]\u00a0would be the elements that exist in either set, in [latex]A\\cup{B}[\/latex].\r\nIn the previous example, the truth table was really just summarizing what we already know about how the <em>or<\/em> statement work. The truth tables for the basic <em>and<\/em>, <em>or<\/em>, and <em>not<\/em> statements are shown below.\r\n<div class=\"textbox\">\r\n<h3>Basic Truth Tables<\/h3>\r\n<table width=\"40%&quot;\">\r\n<thead>\r\n<tr>\r\n<th>A<\/th>\r\n<th>B<\/th>\r\n<th>[latex]A\\wedge{B}[\/latex]<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>A<\/th>\r\n<th>B<\/th>\r\n<th>[latex]A\\vee{B}[\/latex]<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>A<\/th>\r\n<th>[latex]\\sim{A}[\/latex]<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=25467&amp;theme=oea&amp;iframe_resize_id=mom1[\/embed]\r\n\r\n<\/div>\r\nTruth tables really become useful when analyzing more complex Boolean statements.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nCreate a truth table for the statement [latex]A\\wedge\\sim\\left(B\\vee{C}\\right)[\/latex]\r\n[reveal-answer q=\"550652\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"550652\"]\r\n\r\nIt helps to work from the inside out when creating truth tables, and create tables for intermediate operations. We start by listing all the possible truth value combinations for <em>A<\/em>, <em>B<\/em>, and <em>C<\/em>. Notice how the first column contains 4 Ts followed by 4 Fs, the second column contains 2 Ts, 2 Fs, then repeats, and the last column alternates. This pattern ensures that all combinations are considered. Along with those initial values, we\u2019ll list the truth values for the innermost expression, [latex]B\\vee{C}[\/latex].\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>A<\/em><\/td>\r\n<td><em>B<\/em><\/td>\r\n<td><em>C<\/em><\/td>\r\n<td><em>B<\/em> \u22c1 <em>C<\/em><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nNext we can find the negation of [latex]B\\vee{C}[\/latex], working off the [latex]B\\vee{C}[\/latex] column we just created.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>A<\/em><\/td>\r\n<td><em>B<\/em><\/td>\r\n<td><em>C<\/em><\/td>\r\n<td>[latex]B\\vee{C}[\/latex]<\/td>\r\n<td>[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nFinally, we find the values of <em>A<\/em> <em>and<\/em>\u00a0[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>A<\/em><\/td>\r\n<td><em>B<\/em><\/td>\r\n<td><em>C<\/em><\/td>\r\n<td>[latex]B\\vee{C}[\/latex]<\/td>\r\n<td>[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]<\/td>\r\n<td>[latex]A\\wedge\\sim\\left(B{\\vee}C\\right)[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>\u00a0F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nIt turns out that this complex expression is only true in one case: if A is true, B is false, and C is false.\r\n\r\n[\/hidden-answer]\r\n\r\nIt may be helpful to add statements to your truth tables to help make sense of the situations. For example,\r\n<h3>Basic Truth Tables with statements<\/h3>\r\n<table width=\"40%&quot;\">\r\n<thead>\r\n<tr>\r\n<th>A (I have a pencil)<\/th>\r\n<th>B (I have paper)<\/th>\r\n<th>[latex]A\\wedge{B}[\/latex] (I have paper and pencil, meaning I can take notes)<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T (means I have pencil and paper, so I can take notes - true)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F\u00a0(means I have pencil and no paper, so I can not take notes - meaning false, I can't take notes)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F\u00a0(means I don't have pencil and but I do have paper, so I cannot take notes - meaning false, I cannot take notes)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F (means I don't have pencil and don't have paper, so I cannot take notes - meaning false, I can't take notes)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>A (I have a pencil)<\/th>\r\n<th>B (I have a pen)<\/th>\r\n<th>[latex]A\\vee{B}[\/latex] (I have either a pencil or a pen, meaning I can write on a worksheet)<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T (means I have both a pencil and a pen, so I can fill out the worksheet)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T (I have a pencil, but not a pen, but I can still fill out the worksheet)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T (I don't have a pencil, but I do have a pen, so I can fill out the worksheet)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F (I have no pencil and no pen, so I cannot fill out the worksheet)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=25595&amp;theme=oea&amp;iframe_resize_id=mom1[\/embed]\r\n\r\n<\/div>\r\nWhen we discussed conditions earlier, we discussed the type where we take an action based on the value of the condition. We are now going to talk about a more general version of a conditional, sometimes called an <strong>implication<\/strong>.\r\n<div class=\"textbox\">\r\n<h3>Implications<\/h3>\r\nImplications are logical conditional sentences stating that a statement <em>p<\/em>, called the antecedent, implies a consequence <em>q<\/em>.\r\n\r\nImplications are commonly written as [latex]p\\rightarrow{q}[\/latex]\r\n\r\n<\/div>\r\nImplications are similar to the conditional statements we looked at earlier; [latex]p\\rightarrow{q}[\/latex] is typically written as \u201cif p then q,\u201d or \u201cp therefore q.\u201d The difference between implications and conditionals is that conditionals we discussed earlier suggest an action\u2014if the condition is true, then we take some action as a result. Implications are a logical statement that suggest that the consequence must logically follow if the antecedent is true.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nThe English statement \u201cIf it is raining, then there are clouds is the sky\u201d is a logical implication. Is this a valid argument, why or why not?\r\n[reveal-answer q=\"913754\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"913754\"]\r\n\r\nIt is a valid argument because if the antecedent \u201cit is raining\u201d is true, then the consequence \u201cthere are clouds in the sky\u201d must also be true.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\nNotice that the statement tells us nothing of what to expect if it is not raining. If the antecedent is false, then the implication becomes irrelevant.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nA friend tells you that \u201cif you upload that picture to Facebook, you\u2019ll lose your job.\u201d Describe the possible outcomes related to this statement, and determine whether your friend's statement is invalid.\r\n[reveal-answer q=\"463067\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"463067\"]\r\n\r\nThere are four possible outcomes:\r\n<ol>\r\n \t<li>You upload the picture and keep your job.<\/li>\r\n \t<li>You upload the picture and lose your job.<\/li>\r\n \t<li>You don\u2019t upload the picture and keep your job.<\/li>\r\n \t<li>You don\u2019t upload the picture and lose your job.<\/li>\r\n<\/ol>\r\nThere is only one possible case where your friend was lying\u2014the first option where you upload the picture and keep your job. In the last two cases, your friend didn\u2019t say anything about what would happen if you didn\u2019t upload the picture, so you can\u2019t conclude their statement is invalid, even if you didn\u2019t upload the picture and still lost your job.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\nIn traditional logic, an implication is considered valid (true) as long as there are no cases in which the antecedent is true and the consequence is false. It is important to keep in mind that symbolic logic cannot capture all the intricacies of the English language.\r\n<div class=\"textbox\">\r\n<h3>Truth Values for Implications<\/h3>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>p<\/em><\/td>\r\n<td><em>q<\/em><\/td>\r\n<td><em>p<\/em> \u2192 <em>q<\/em><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nTRUTH VALUES FOR IMPLICATIONS WITH SENTENCES\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>p (If it is raining)<\/em><\/td>\r\n<td><em>q (then it is cloudy)<\/em><\/td>\r\n<td><em>p<\/em> \u2192 <em>q<\/em><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T (it is true that if it is raining, then it is cloudy)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F (it is not true that if it is raining, it is not cloudy)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T (it is true that if it is not raining, it could be cloudy)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T (it is true that if it is not raining, it could be not cloudy)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nConstruct a truth table for the statement [latex]\\left(m\\wedge\\sim{p}\\right)\\rightarrow{r}[\/latex]\r\n\r\n[reveal-answer q=\"6001\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"6001\"]\r\n\r\nWe start by constructing a truth table for the antecedent.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>m<\/em><\/td>\r\n<td><i>p<\/i><\/td>\r\n<td>[latex]\\sim{p}[\/latex]<\/td>\r\n<td>[latex]m\\wedge\\sim{p}[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nNow we can build the truth table for the implication\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><em>m<\/em><\/td>\r\n<td><i>p<\/i><\/td>\r\n<td>[latex]\\sim{p}[\/latex]<\/td>\r\n<td>[latex]m\\wedge\\sim{p}[\/latex]<\/td>\r\n<td><em>r<\/em><\/td>\r\n<td>[latex]\\left(m\\wedge\\sim{p}\\right)\\rightarrow{r}[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nIn this case, when <em>m<\/em> is true, <em>p<\/em> is false, and <em>r<\/em> is false, then the antecedent [latex]m\\wedge\\sim{p}[\/latex]\u00a0will be true but the consequence false, resulting in a invalid implication; every other case gives a valid implication.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=25597&amp;theme=oea&amp;iframe_resize_id=mom5[\/embed]\r\n\r\n<\/div>\r\nFor any implication, there are three related statements, the converse, the inverse, and the contrapositive.\r\n<div class=\"textbox\">\r\n<h3>Related Statements<\/h3>\r\nThe original implication is \u201cif <em>p<\/em> then <em>q<\/em>\u201d: [latex]p\\rightarrow{q}[\/latex]\r\n\r\nThe converse is \u201cif <em>q<\/em> then <em>p<\/em>\u201d: [latex]q\\rightarrow{p}[\/latex]\r\n\r\nThe inverse is \u201cif not <em>p<\/em> then not <em>q<\/em>\u201d: [latex]\\sim{p}\\rightarrow\\sim{q}[\/latex]\r\n\r\nThe contrapositive is \u201cif not <em>q<\/em> then not <em>p<\/em>\u201d: [latex]\\sim{q}\\rightarrow{p}[\/latex]\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nConsider again the valid implication \u201cIf it is raining, then there are clouds in the sky.\u201d\r\n\r\nWrite the related converse, inverse, and contrapositive statements.\r\n[reveal-answer q=\"746956\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"746956\"]\r\n\r\nThe converse would be \u201cIf there are clouds in the sky, it is raining.\u201d This is certainly not always true.\r\n\r\nThe inverse would be \u201cIf it is not raining, then there are not clouds in the sky.\u201d Likewise, this is not always true.\r\n\r\nThe contrapositive would be \u201cIf there are not clouds in the sky, then it is not raining.\u201d This statement is valid, and is equivalent to the original implication.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=25472&amp;theme=oea&amp;iframe_resize_id=mom10[\/embed]\r\n\r\n<\/div>\r\nLooking at truth tables, we can see that the original conditional and the contrapositive are logically equivalent, and that the converse and inverse are logically equivalent.\r\n<table>\r\n<thead>\r\n<tr>\r\n<th><\/th>\r\n<th><\/th>\r\n<th>Implication<\/th>\r\n<th>Converse<\/th>\r\n<th>Inverse<\/th>\r\n<th>Contrapositive<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<th><em>p<\/em><\/th>\r\n<th><em>q<\/em><\/th>\r\n<th>[latex]p\\rightarrow{q}[\/latex]<\/th>\r\n<th>[latex]q{\\rightarrow}p[\/latex]<\/th>\r\n<th>[latex]\\sim{p}\\rightarrow\\sim{q}[\/latex]<\/th>\r\n<th>[latex]\\sim{q}\\rightarrow\\sim{p}[\/latex]<\/th>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div class=\"textbox\">\r\n<h3>Equivalence<\/h3>\r\nA conditional statement and its contrapositive are logically equivalent.\r\n\r\nThe converse and inverse of a statement are logically equivalent.\r\n\r\n<\/div>\r\n<h2>DeMorgan's Laws<\/h2>\r\nThere are two pairs of logically equivalent statements that come up\u00a0again and again in logic. They are prevalent\u00a0enough to be dignified by a special name: <b>DeMorgan\u2019s laws.<\/b>\r\n\r\nThe laws are named after Augustus De Morgan (1806\u20131871),\u00a0who introduced a formal version of the laws to classical propositional logic. De Morgan's formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians.\u00a0For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his <i>Summulae de Dialectica<\/i>, also describes rules of conversion that follow the lines of De Morgan's laws.\u00a0Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic. De Morgan's laws can be proved easily, and may even seem trivial.\u00a0Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.\r\n<div class=\"textbox\">\r\n<h3>DeMorgan\u2019s Laws<\/h3>\r\n<ol>\r\n \t<li>[latex]\\sim\\left(P{\\wedge}Q\\right)=({\\sim}P)\\vee\\left(\\sim{Q}\\right)[\/latex]<\/li>\r\n \t<li>[latex]\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex]<\/li>\r\n<\/ol>\r\n<\/div>\r\nThe first of DeMorgan\u2019s laws is verified by the following table. You are\u00a0asked to verify the second in an\u00a0exercise.\r\n<table cellspacing=\"0\" cellpadding=\"0\">\r\n<tbody>\r\n<tr>\r\n<td><b>[latex]P[\/latex]<\/b><\/td>\r\n<td><b>[latex]Q[\/latex]<\/b><\/td>\r\n<td><b>[latex]\\sim{P}[\/latex]<\/b><\/td>\r\n<td><b>[latex]\\sim{Q}[\/latex]<\/b><\/td>\r\n<td>[latex]P\\wedge{Q}[\/latex]<\/td>\r\n<td><strong>[latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex]<\/strong><\/td>\r\n<td><b>[latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex]<\/b><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<td>F<\/td>\r\n<td>T<\/td>\r\n<td>T<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nDeMorgan\u2019s laws are actually very natural and intuitive. Consider the\u00a0statement [latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex], which we can interpret as meaning that it is not the\u00a0case that both <i>P<\/i> and <i>Q<\/i> are true. If it is not the case that both <i>P<\/i> and <i>Q<\/i>\u00a0are true, then at least one of <i>P<\/i> or <i>Q<\/i> is false, in which case [latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex]\u00a0is\u00a0true. Thus [latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex]\u00a0means the same thing as [latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex].\r\n\r\nDeMorgan\u2019s laws can be very useful. Suppose we happen to know that\u00a0some statement having form [latex]\\sim\\left(P\\vee{Q}\\right)[\/latex]\u00a0is true. The second of DeMorgan\u2019s\u00a0laws tells us that [latex]\\left(\\sim{Q}\\right)\\wedge\\left(\\sim{P}\\right)[\/latex]\u00a0is also true, hence [latex]\\sim{P}[\/latex] and [latex]\\sim{Q}[\/latex] are both true\u00a0as well. Being able to quickly obtain such additional pieces of information\u00a0can be extremely useful.\r\n\r\nHere is a summary of some significant logical equivalences. Those that\u00a0are not immediately obvious can be verified with a truth table.\r\n\r\n[latex]\\text{Contrapositive law}\\begin{array}{c}P\\rightarrow{Q}=(\\sim{Q})\\rightarrow(\\sim{P})\\end{array}[\/latex]\r\n\r\n[latex]\\text{DeMorgan's laws}\\begin{array}{c}{\\sim(P\\land{Q})=\\sim{P}\\lor\\sim{Q}}\\\\{\\sim(P\\lor{Q})=\\sim{P}\\land\\sim{Q}}\\end{array}[\/latex]\r\n\r\n[latex]\\text{Commutative laws}\\begin{array}{c}{(P\\land{Q})={P}\\land{Q}}\\\\{(P\\lor{Q})={P}\\lor{Q}}\\end{array}[\/latex]\r\n\r\n[latex]\\text{Distributive laws}\\begin{array}{c}{{P}\\land(Q\\lor{R})=({P}\\land{Q})\\lor(P\\land{R})}\\\\{P\\lor(Q\\land{R})=({P}\\lor{Q})\\land(P\\lor{R})}\\end{array}[\/latex]\r\n\r\n[latex]\\text{Associative laws}\\begin{array}{c}{P\\land(Q\\land{R})=(P\\land{Q})\\land{R}}\\\\{P\\lor(Q\\lor{R})=(P\\lor{Q})\\lor{R}}\\end{array}[\/latex]\r\n\r\nNotice how the distributive law [latex]P\\wedge\\left(Q\\vee{R}\\right)=\\left(P\\wedge{Q}\\right)\\vee\\left(P\\wedge{Q}\\right)\\vee\\left(P\\wedge{R}\\right)[\/latex]\u00a0has the\u00a0same structure as the distributive law [latex]p\\left(q+r\\right)=p\\cdot{q}+p\\cdot{r}[\/latex]\u00a0from algebra.\u00a0Concerning the associative laws, the fact that [latex]P\\wedge\\left(Q\\wedge{R}\\right)=\\left(P\\wedge{Q}\\right)\\wedge{R}[\/latex]\u00a0means\u00a0that the position of the parentheses is irrelevant, and we can write this as [latex]P\\wedge{Q}\\wedge{R}[\/latex]\u00a0without ambiguity. Similarly, we may drop the parentheses in\u00a0an expression such as [latex]P\\vee\\left(Q\\vee{R}\\right)[\/latex].\r\n\r\nBut parentheses are essential when there is a mix of [latex]\\wedge[\/latex]\u00a0and [latex]\\vee[\/latex], as in [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex]. Indeed, [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex] and [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex] and [latex]P\\vee\\left({Q}\\right)\\wedge{R}[\/latex]<i><\/i> are <b>not<\/b> logically equivalent.\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=109604&amp;theme=oea&amp;iframe_resize_id=mom2[\/embed]\r\n\r\n<\/div>\r\n<h3><b>Negating Statements<\/b><\/h3>\r\nGiven a statement <i>R<\/i>, the statement [latex]\\sim{R}[\/latex] is called the <b>negation<\/b> of <i>R<\/i>. If <i>R<\/i>\u00a0is a complex statement, then it is often the case that its negation [latex]\\sim{R}[\/latex]\u00a0can\u00a0be written in a simpler or more useful form. The process of finding this\u00a0form is called <b>negating<\/b> <i>R<\/i>. In proving theorems it is often necessary to\u00a0negate certain statements. We now investigate how to do this.\r\n\r\nWe have already examined part of this topic. <b>DeMorgan\u2019s laws<\/b>\r\n\r\n[latex]\\sim\\left(P\\wedge{Q}\\right)=\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)\\\\\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex]\r\n\r\n(from \"Logical Equivalence\") can be viewed as rules that tell us how to negate the\u00a0statements [latex]P\\wedge{Q}[\/latex]\u00a0and [latex]P\\vee{Q}[\/latex]. Here are some examples that illustrate how\u00a0DeMorgan\u2019s laws are used to negate statements involving \u201cand\u201d or \u201cor.\u201d\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nConsider negating the following statement.\r\n\r\n<i>R<\/i> : You can solve it by factoring or with the quadratic formula.\r\n\r\n[reveal-answer q=\"102469\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"102469\"]\r\n\r\nNow, <i>R<\/i> means (You can solve it by factoring) [latex]\\vee[\/latex]\u00a0(You can solve it with Q.F.),\u00a0which we will denote as [latex]P\\vee{Q}[\/latex]. The negation of this is [latex]\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex].\r\n\r\nTherefore, in words, the negation of <i>R<\/i> is\r\n\r\n[latex]\\sim{R}[\/latex] : You can\u2019t solve it by factoring and you can\u2019t solve it with\u00a0the quadratic formula.\r\n\r\nMaybe you can find [latex]\\sim{R}[\/latex]\u00a0without invoking DeMorgan\u2019s laws. That is good;\u00a0you have internalized DeMorgan\u2019s laws and are using them unconsciously.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nWe will negate the following sentence.\r\n\r\n<i>R<\/i> : The numbers x and y are both odd.\r\n\r\n[reveal-answer q=\"441993\"]Show Answer[\/reveal-answer]\r\n[hidden-answer a=\"441993\"]\r\n\r\nThis statement means [latex]\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)[\/latex], so its negation is\r\n<p style=\"text-align: center\">[latex]\\sim\\left[\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)\\right]=\\sim\\left(x\\text{ is odd}\\right)\\vee\\sim\\left(y\\text{ is odd}\\right)\\\\\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)=\\left(x\\text{ is even}\\right)\\vee\\left(y\\text{ is even}\\right)[\/latex]<\/p>\r\nTherefore the negation of <i>R<\/i> can be expressed in the following ways:\r\n\r\n[latex]\\sim{R}[\/latex]: The number x is even or the number y is even.\r\n[latex]\\sim{R}[\/latex]: At least one of x and y is even.\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try it now<\/h3>\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=109608&amp;theme=oea&amp;iframe_resize_id=mom1[\/embed]\r\n\r\n<\/div>","rendered":"<p>In this section, we will learn how to construct logical statements. We will later combine our knowledge of sets with what we will learn about constructing logical statements to analyze arguments with logic.<\/p>\n<div class=\"textbox learning-objectives\">\n<h3>Learning Objectives<\/h3>\n<p>Introduction to Logic<\/p>\n<ul>\n<li>Combine sets using Boolean logic, using proper notations<\/li>\n<li>Use statements and conditionals to write and interpret expressions<\/li>\n<li>Use a truth table to interpret complex statements or conditionals<\/li>\n<li>Write truth tables given a logical implication, and it\u2019s related\u00a0statements \u2013 converse, inverse, and contrapositive<\/li>\n<li>Determine whether two statements are logically equivalent<\/li>\n<li>Use DeMorgan\u2019s laws to define logical equivalences of a statement<\/li>\n<\/ul>\n<\/div>\n<p>Logic is a systematic way of thinking that allows us to deduce new information\u00a0from old information and to parse the meanings of sentences.\u00a0You use logic informally in everyday life and certainly also in doing mathematics.\u00a0For example, suppose you are working with a certain circle, call it\u00a0\u201cCircle X,\u201d and you have available the following two pieces of information.<\/p>\n<ol>\n<li>Circle X has radius equal to 3.<\/li>\n<li>If any circle has radius [latex]r[\/latex], then its area is [latex]\\pi{r}^{2}[\/latex]\u00a0square units.<\/li>\n<\/ol>\n<p>You have no trouble putting these two facts together to get:<\/p>\n<ol start=\"3\">\n<li>Circle X has area [latex]9\\pi[\/latex] square units.<\/li>\n<\/ol>\n<p>You are using logic to combine existing information to\u00a0produce new information. Since a major objective in mathematics is to\u00a0deduce new information, logic must play a fundamental role. This chapter\u00a0is intended to give you a sufficient mastery of logic.<\/p>\n<h2>Boolean Logic<\/h2>\n<p>Logic is, basically, the study of valid reasoning. When searching the internet, we use Boolean logic \u2013 terms like \u201cand\u201d and \u201cor\u201d \u2013 to help us find specific web pages that fit in the sets we are interested in. After exploring this form of logic, we will look at logical arguments and how we can determine the validity of a claim.<\/p>\n<p>We can often classify items as belonging to sets. If you went the library to search for a book and they asked you to express your search using unions, intersections, and complements of sets, that would feel a little strange. Instead, we typically using words like \u201cand,\u201d \u201cor,&#8221; and \u201cnot\u201d to connect our keywords together to form a search. These words, which form the basis of <strong>Boolean logic<\/strong>, are directly related to set operations with the same terminology.<\/p>\n<div class=\"textbox\">\n<h3>Boolean Logic<\/h3>\n<p>Boolean logic combines multiple statements that are either true or false into an expression that is either true or false.<\/p>\n<ul>\n<li>In connection to sets, a boolean search is true if the element in question is part of the set being searched.<\/li>\n<\/ul>\n<\/div>\n<p>Suppose <em>M<\/em> is the set of all mystery books, and <em>C<\/em> is the set of all comedy books. If we search for \u201cmystery\u201d, we are looking for all the books that are an element of the set <em>M<\/em>; the search is true for books that are in the set.<\/p>\n<p>When we search for \u201cmystery <em>and<\/em> comedy\u201d we are looking for a book that is an element of both sets, in the intersection. If we were to search for \u201cmystery<em> or<\/em> comedy\u201d we are looking for a book that is a mystery, a comedy, or both, which is the union of the sets. If we searched for \u201c<em>not <\/em>comedy\u201d we are looking for any book in the library that is not a comedy, the complement of the set <em>C<\/em>.<\/p>\n<div class=\"textbox\">\n<h3>Connection to Set Operations<\/h3>\n<p><em>A <\/em>and<em> B<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the intersection <em>A<\/em> \u22c2 <em>B<\/em><\/p>\n<p><em>A<\/em> or <em>B<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the union <em>A<\/em> \u22c3 <em>B <\/em><\/p>\n<p>Not <em>A<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 elements in the complement <em>Ac<\/em><\/p>\n<\/div>\n<p>Notice here that <em>or<\/em> is not exclusive. This is a difference between the Boolean logic use of the word and common everyday use. When your significant other asks \u201cdo you want to go to the park or the movies?\u201d they usually are proposing an exclusive choice \u2013 one option or the other, but not both. In Boolean logic, the <em>or<\/em> is not exclusive \u2013 more like being asked at a restaurant \u201cwould you like fries or a drink with that?\u201d Answering \u201cboth, please\u201d is an acceptable answer.<\/p>\n<p>In the following video, You will see examples of how Boolean operators are used to denote sets.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Boolean Set Operations\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/ZOLinnoXEAw?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Suppose we are searching a library database for Mexican universities. Express a reasonable search using Boolean logic.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q912486\">Show Answer<\/span><\/p>\n<div id=\"q912486\" class=\"hidden-answer\" style=\"display: none\">\n<p>We could start with the search \u201cMexico <em>and <\/em>university\u201d, but would be likely to find results for the U.S. state New Mexico. To account for this, we could revise our search to read:<\/p>\n<p>Mexico <em>and<\/em> university <em>not <\/em>\u201cNew Mexico\u201d<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>In most internet search engines, it is not necessary to include the word <em>and<\/em>; the search engine assumes that if you provide two keywords you are looking for both. In Google\u2019s search, the keyword <em>or<\/em> has be capitalized as OR, and a negative sign in front of a word is used to indicate <em>not<\/em>. Quotes around a phrase indicate that the entire phrase should be looked for. The search from the previous example on Google could be written:<\/p>\n<p style=\"text-align: center\">Mexico university -\u201cNew Mexico\u201d<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Describe the numbers that meet the condition:<\/p>\n<p>even and less than 10 and greater than 0<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q670488\">Show Answer<\/span><\/p>\n<div id=\"q670488\" class=\"hidden-answer\" style=\"display: none\">The numbers that satisfy all three requirements are {2, 4, 6, 8}<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=25592&#38;theme=oea&#38;iframe_resize_id=mom5\">https:\/\/www.myopenmath.com\/multiembedq.php?id=25592&amp;theme=oea&amp;iframe_resize_id=mom5<\/a><\/p>\n<\/div>\n<h3>Which Comes First?<\/h3>\n<p>Sometimes statements made in English can be ambiguous. For this reason, Boolean logic uses parentheses to show precedent, just like in algebraic order of operations.<\/p>\n<p>The English phrase \u201cGo to the store and buy me eggs and bagels or cereal\u201d is ambiguous; it is not clear whether the requestors is asking for eggs always along with either bagels or cereal, or whether they\u2019re asking for either the combination of eggs and bagels, or just cereal.<\/p>\n<p>For this reason, using parentheses clarifies the intent:<\/p>\n<table>\n<tbody>\n<tr>\n<td>Eggs and (bagels or cereal) means<\/td>\n<td>Option 1: Eggs and bagels, Option 2: Eggs and cereal<\/td>\n<\/tr>\n<tr>\n<td>(Eggs and bagels) or cereal means<\/td>\n<td>\u00a0Option 1: Eggs and bagels, Option 2: Cereal<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Describe the numbers that meet the condition:<\/p>\n<p>odd number and less than 20 and greater than 0; and (a multiple of 3 or multiple of 5)<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q877489\">Show Answer<\/span><\/p>\n<div id=\"q877489\" class=\"hidden-answer\" style=\"display: none\">\n<p>The first three conditions limit us to the set {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}<\/p>\n<p>The last grouped conditions tell us to find elements of this set that are also either a multiple of 3 or a multiple of 5. This leaves us with the set<\/p>\n<p><strong>{3, 5, 9, 15}<\/strong><\/p>\n<p>Notice that we would have gotten a very different result if we had written<\/p>\n<p>(odd number and less than 20 and greater than 0 and multiple of 3) or multiple of 5<\/p>\n<p>The first grouped set of conditions would give {3, 9, 15}. When combined with the last condition, though, this set expands without limits:<\/p>\n<p style=\"text-align: center\">\n<p>{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, \u2026}<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>Be aware that when a string of conditions is written without grouping symbols, it is often interpreted from the left to right, resulting in the latter interpretation.<\/p>\n<h3>Conditionals<\/h3>\n<p>Beyond searching, Boolean logic is commonly used in spreadsheet applications like Excel to do conditional calculations. A <strong>statement<\/strong> is something that is either true or false.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>A statement like 3 &lt; 5 is true; a statement like \u201ca rat is a fish\u201d is false. A statement like \u201cx &lt; 5\u201d is true for some values of <em>x<\/em> and false for others.<br \/>\nWhen an action is taken or not depending on the value of a statement, it forms a <strong>conditional<\/strong>.<\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Statements and Conditionals<\/h3>\n<p>A <strong>statement<\/strong> is either true or false.<br \/>\nA <strong>conditional<\/strong> is a compound statement of the form<br \/>\n\u201cif <em>p<\/em> then <em>q\u201d<\/em> \u00a0or \u00a0\u201cif <em>p<\/em> then <em>q<\/em>, else <em>s<\/em>\u201d.<\/p>\n<\/div>\n<p>In common language, an example of a conditional statement would be \u201cIf it is raining, then we\u2019ll go to the mall. Otherwise we\u2019ll go for a hike.\u201d<br \/>\nThe statement \u201cIf it is raining\u201d is the condition\u2014this may be true or false for any given day. If the condition is true, then we will follow the first course of action, and go to the mall. If the condition is false, then we will use the alternative, and go for a hike.<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=108578&#38;theme=oea&#38;iframe_resize_id=mom5\">https:\/\/www.myopenmath.com\/multiembedq.php?id=108578&amp;theme=oea&amp;iframe_resize_id=mom5<\/a><\/p>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=108573&#38;theme=oea&#38;iframe_resize_id=mom\">https:\/\/www.myopenmath.com\/multiembedq.php?id=108573&amp;theme=oea&amp;iframe_resize_id=mom<\/a><\/p>\n<\/div>\n<h2>Truth Tables<\/h2>\n<p>Because complex Boolean statements can get tricky to think about, we can create a <strong>truth table<\/strong> to break the complex statement into\u00a0simple statements, and determine whether they are true or false. A table will help keep track of all the truth values of the simple statements that make up a complex statement, leading to an analysis of the full statement.<\/p>\n<div class=\"textbox\">\n<h3>Truth Table<\/h3>\n<p>A table showing what the resulting truth value of a complex statement is for all the possible truth values for the simple statements.<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Suppose you\u2019re picking out a new couch, and your significant other says \u201cget a sectional <em>or<\/em> something with a chaise.\u201d Construct a truth table that describes the elements of the conditions of this statement and whether the conditions are met.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q14714\">Show Answer<\/span><\/p>\n<div id=\"q14714\" class=\"hidden-answer\" style=\"display: none\">\n<p>This is a complex statement made of two simpler conditions: \u201cis a sectional,\u201d and \u201chas a chaise.\u201d For simplicity, let\u2019s use <em>S<\/em> to designate \u201cis a sectional,\u201d and <em>C<\/em> to designate \u201chas a chaise.\u201d The condition <em>S<\/em> is true if the couch is a sectional.<\/p>\n<p>A truth table for this would look like this:<\/p>\n<table>\n<thead>\n<tr>\n<th><em>S<\/em><\/th>\n<th><em>C<\/em><\/th>\n<th><em>S<\/em> or\u00a0<em>C<\/em><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>In the table, T is used for true, and F for false. In the first row, if <em>S<\/em> is true and <em>C<\/em> is also true, then the complex statement \u201c<em>S <\/em>or<em> C<\/em>\u201d is true. This would be a sectional that also has a chaise, which meets our desire.<\/p>\n<p>Remember also that <em>or<\/em> in logic is not exclusive; if the couch has both features, it does meet the condition.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>Some symbols that are commonly used for <em>and<\/em>, <em>or<\/em>, and <em>not<\/em> make using a truth table easier.<\/p>\n<div class=\"textbox\">\n<h3>Symbols<\/h3>\n<p>The symbol [latex]\\wedge[\/latex] is used for <em>and<\/em>: <em>A<\/em> and <em>B<\/em> is notated [latex]A\\wedge{B}[\/latex].<\/p>\n<p>The symbol [latex]\\vee[\/latex] is used for <em>or<\/em>: <em>A<\/em> or <em>B<\/em> is notated [latex]A\\vee{B}[\/latex]<\/p>\n<p>The symbol [latex]\\sim[\/latex] is used for <em>not<\/em>: not <em>A<\/em> is notated [latex]\\sim{A}[\/latex]<\/p>\n<\/div>\n<p>You can remember the first two symbols by relating them to the shapes for the union and intersection. [latex]A\\wedge{B}[\/latex]\u00a0would be the elements that exist in both sets, in [latex]A\\cap{B}[\/latex]. Likewise, [latex]A\\vee{B}[\/latex]\u00a0would be the elements that exist in either set, in [latex]A\\cup{B}[\/latex].<br \/>\nIn the previous example, the truth table was really just summarizing what we already know about how the <em>or<\/em> statement work. The truth tables for the basic <em>and<\/em>, <em>or<\/em>, and <em>not<\/em> statements are shown below.<\/p>\n<div class=\"textbox\">\n<h3>Basic Truth Tables<\/h3>\n<table style=\"width: 40%&quot;\">\n<thead>\n<tr>\n<th>A<\/th>\n<th>B<\/th>\n<th>[latex]A\\wedge{B}[\/latex]<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>A<\/th>\n<th>B<\/th>\n<th>[latex]A\\vee{B}[\/latex]<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>A<\/th>\n<th>[latex]\\sim{A}[\/latex]<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=25467&#38;theme=oea&#38;iframe_resize_id=mom1\">https:\/\/www.myopenmath.com\/multiembedq.php?id=25467&amp;theme=oea&amp;iframe_resize_id=mom1<\/a><\/p>\n<\/div>\n<p>Truth tables really become useful when analyzing more complex Boolean statements.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Create a truth table for the statement [latex]A\\wedge\\sim\\left(B\\vee{C}\\right)[\/latex]<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q550652\">Show Answer<\/span><\/p>\n<div id=\"q550652\" class=\"hidden-answer\" style=\"display: none\">\n<p>It helps to work from the inside out when creating truth tables, and create tables for intermediate operations. We start by listing all the possible truth value combinations for <em>A<\/em>, <em>B<\/em>, and <em>C<\/em>. Notice how the first column contains 4 Ts followed by 4 Fs, the second column contains 2 Ts, 2 Fs, then repeats, and the last column alternates. This pattern ensures that all combinations are considered. Along with those initial values, we\u2019ll list the truth values for the innermost expression, [latex]B\\vee{C}[\/latex].<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>A<\/em><\/td>\n<td><em>B<\/em><\/td>\n<td><em>C<\/em><\/td>\n<td><em>B<\/em> \u22c1 <em>C<\/em><\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Next we can find the negation of [latex]B\\vee{C}[\/latex], working off the [latex]B\\vee{C}[\/latex] column we just created.<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>A<\/em><\/td>\n<td><em>B<\/em><\/td>\n<td><em>C<\/em><\/td>\n<td>[latex]B\\vee{C}[\/latex]<\/td>\n<td>[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Finally, we find the values of <em>A<\/em> <em>and<\/em>\u00a0[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>A<\/em><\/td>\n<td><em>B<\/em><\/td>\n<td><em>C<\/em><\/td>\n<td>[latex]B\\vee{C}[\/latex]<\/td>\n<td>[latex]\\sim\\left(B\\vee{C}\\right)[\/latex]<\/td>\n<td>[latex]A\\wedge\\sim\\left(B{\\vee}C\\right)[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>\u00a0F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>It turns out that this complex expression is only true in one case: if A is true, B is false, and C is false.<\/p>\n<\/div>\n<\/div>\n<p>It may be helpful to add statements to your truth tables to help make sense of the situations. For example,<\/p>\n<h3>Basic Truth Tables with statements<\/h3>\n<table style=\"width: 40%&quot;\">\n<thead>\n<tr>\n<th>A (I have a pencil)<\/th>\n<th>B (I have paper)<\/th>\n<th>[latex]A\\wedge{B}[\/latex] (I have paper and pencil, meaning I can take notes)<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T (means I have pencil and paper, so I can take notes &#8211; true)<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F\u00a0(means I have pencil and no paper, so I can not take notes &#8211; meaning false, I can&#8217;t take notes)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F\u00a0(means I don&#8217;t have pencil and but I do have paper, so I cannot take notes &#8211; meaning false, I cannot take notes)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F (means I don&#8217;t have pencil and don&#8217;t have paper, so I cannot take notes &#8211; meaning false, I can&#8217;t take notes)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>A (I have a pencil)<\/th>\n<th>B (I have a pen)<\/th>\n<th>[latex]A\\vee{B}[\/latex] (I have either a pencil or a pen, meaning I can write on a worksheet)<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T (means I have both a pencil and a pen, so I can fill out the worksheet)<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T (I have a pencil, but not a pen, but I can still fill out the worksheet)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T (I don&#8217;t have a pencil, but I do have a pen, so I can fill out the worksheet)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>F (I have no pencil and no pen, so I cannot fill out the worksheet)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=25595&#38;theme=oea&#38;iframe_resize_id=mom1\">https:\/\/www.myopenmath.com\/multiembedq.php?id=25595&amp;theme=oea&amp;iframe_resize_id=mom1<\/a><\/p>\n<\/div>\n<p>When we discussed conditions earlier, we discussed the type where we take an action based on the value of the condition. We are now going to talk about a more general version of a conditional, sometimes called an <strong>implication<\/strong>.<\/p>\n<div class=\"textbox\">\n<h3>Implications<\/h3>\n<p>Implications are logical conditional sentences stating that a statement <em>p<\/em>, called the antecedent, implies a consequence <em>q<\/em>.<\/p>\n<p>Implications are commonly written as [latex]p\\rightarrow{q}[\/latex]<\/p>\n<\/div>\n<p>Implications are similar to the conditional statements we looked at earlier; [latex]p\\rightarrow{q}[\/latex] is typically written as \u201cif p then q,\u201d or \u201cp therefore q.\u201d The difference between implications and conditionals is that conditionals we discussed earlier suggest an action\u2014if the condition is true, then we take some action as a result. Implications are a logical statement that suggest that the consequence must logically follow if the antecedent is true.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>The English statement \u201cIf it is raining, then there are clouds is the sky\u201d is a logical implication. Is this a valid argument, why or why not?<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q913754\">Show Answer<\/span><\/p>\n<div id=\"q913754\" class=\"hidden-answer\" style=\"display: none\">\n<p>It is a valid argument because if the antecedent \u201cit is raining\u201d is true, then the consequence \u201cthere are clouds in the sky\u201d must also be true.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>Notice that the statement tells us nothing of what to expect if it is not raining. If the antecedent is false, then the implication becomes irrelevant.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>A friend tells you that \u201cif you upload that picture to Facebook, you\u2019ll lose your job.\u201d Describe the possible outcomes related to this statement, and determine whether your friend&#8217;s statement is invalid.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q463067\">Show Answer<\/span><\/p>\n<div id=\"q463067\" class=\"hidden-answer\" style=\"display: none\">\n<p>There are four possible outcomes:<\/p>\n<ol>\n<li>You upload the picture and keep your job.<\/li>\n<li>You upload the picture and lose your job.<\/li>\n<li>You don\u2019t upload the picture and keep your job.<\/li>\n<li>You don\u2019t upload the picture and lose your job.<\/li>\n<\/ol>\n<p>There is only one possible case where your friend was lying\u2014the first option where you upload the picture and keep your job. In the last two cases, your friend didn\u2019t say anything about what would happen if you didn\u2019t upload the picture, so you can\u2019t conclude their statement is invalid, even if you didn\u2019t upload the picture and still lost your job.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>In traditional logic, an implication is considered valid (true) as long as there are no cases in which the antecedent is true and the consequence is false. It is important to keep in mind that symbolic logic cannot capture all the intricacies of the English language.<\/p>\n<div class=\"textbox\">\n<h3>Truth Values for Implications<\/h3>\n<table>\n<tbody>\n<tr>\n<td><em>p<\/em><\/td>\n<td><em>q<\/em><\/td>\n<td><em>p<\/em> \u2192 <em>q<\/em><\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>TRUTH VALUES FOR IMPLICATIONS WITH SENTENCES<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>p (If it is raining)<\/em><\/td>\n<td><em>q (then it is cloudy)<\/em><\/td>\n<td><em>p<\/em> \u2192 <em>q<\/em><\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T (it is true that if it is raining, then it is cloudy)<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F (it is not true that if it is raining, it is not cloudy)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T (it is true that if it is not raining, it could be cloudy)<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T (it is true that if it is not raining, it could be not cloudy)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Construct a truth table for the statement [latex]\\left(m\\wedge\\sim{p}\\right)\\rightarrow{r}[\/latex]<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q6001\">Show Answer<\/span><\/p>\n<div id=\"q6001\" class=\"hidden-answer\" style=\"display: none\">\n<p>We start by constructing a truth table for the antecedent.<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>m<\/em><\/td>\n<td><i>p<\/i><\/td>\n<td>[latex]\\sim{p}[\/latex]<\/td>\n<td>[latex]m\\wedge\\sim{p}[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Now we can build the truth table for the implication<\/p>\n<table>\n<tbody>\n<tr>\n<td><em>m<\/em><\/td>\n<td><i>p<\/i><\/td>\n<td>[latex]\\sim{p}[\/latex]<\/td>\n<td>[latex]m\\wedge\\sim{p}[\/latex]<\/td>\n<td><em>r<\/em><\/td>\n<td>[latex]\\left(m\\wedge\\sim{p}\\right)\\rightarrow{r}[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>In this case, when <em>m<\/em> is true, <em>p<\/em> is false, and <em>r<\/em> is false, then the antecedent [latex]m\\wedge\\sim{p}[\/latex]\u00a0will be true but the consequence false, resulting in a invalid implication; every other case gives a valid implication.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=25597&#38;theme=oea&#38;iframe_resize_id=mom5\">https:\/\/www.myopenmath.com\/multiembedq.php?id=25597&amp;theme=oea&amp;iframe_resize_id=mom5<\/a><\/p>\n<\/div>\n<p>For any implication, there are three related statements, the converse, the inverse, and the contrapositive.<\/p>\n<div class=\"textbox\">\n<h3>Related Statements<\/h3>\n<p>The original implication is \u201cif <em>p<\/em> then <em>q<\/em>\u201d: [latex]p\\rightarrow{q}[\/latex]<\/p>\n<p>The converse is \u201cif <em>q<\/em> then <em>p<\/em>\u201d: [latex]q\\rightarrow{p}[\/latex]<\/p>\n<p>The inverse is \u201cif not <em>p<\/em> then not <em>q<\/em>\u201d: [latex]\\sim{p}\\rightarrow\\sim{q}[\/latex]<\/p>\n<p>The contrapositive is \u201cif not <em>q<\/em> then not <em>p<\/em>\u201d: [latex]\\sim{q}\\rightarrow{p}[\/latex]<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Consider again the valid implication \u201cIf it is raining, then there are clouds in the sky.\u201d<\/p>\n<p>Write the related converse, inverse, and contrapositive statements.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q746956\">Show Answer<\/span><\/p>\n<div id=\"q746956\" class=\"hidden-answer\" style=\"display: none\">\n<p>The converse would be \u201cIf there are clouds in the sky, it is raining.\u201d This is certainly not always true.<\/p>\n<p>The inverse would be \u201cIf it is not raining, then there are not clouds in the sky.\u201d Likewise, this is not always true.<\/p>\n<p>The contrapositive would be \u201cIf there are not clouds in the sky, then it is not raining.\u201d This statement is valid, and is equivalent to the original implication.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=25472&#38;theme=oea&#38;iframe_resize_id=mom10\">https:\/\/www.myopenmath.com\/multiembedq.php?id=25472&amp;theme=oea&amp;iframe_resize_id=mom10<\/a><\/p>\n<\/div>\n<p>Looking at truth tables, we can see that the original conditional and the contrapositive are logically equivalent, and that the converse and inverse are logically equivalent.<\/p>\n<table>\n<thead>\n<tr>\n<th><\/th>\n<th><\/th>\n<th>Implication<\/th>\n<th>Converse<\/th>\n<th>Inverse<\/th>\n<th>Contrapositive<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<th><em>p<\/em><\/th>\n<th><em>q<\/em><\/th>\n<th>[latex]p\\rightarrow{q}[\/latex]<\/th>\n<th>[latex]q{\\rightarrow}p[\/latex]<\/th>\n<th>[latex]\\sim{p}\\rightarrow\\sim{q}[\/latex]<\/th>\n<th>[latex]\\sim{q}\\rightarrow\\sim{p}[\/latex]<\/th>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"textbox\">\n<h3>Equivalence<\/h3>\n<p>A conditional statement and its contrapositive are logically equivalent.<\/p>\n<p>The converse and inverse of a statement are logically equivalent.<\/p>\n<\/div>\n<h2>DeMorgan&#8217;s Laws<\/h2>\n<p>There are two pairs of logically equivalent statements that come up\u00a0again and again in logic. They are prevalent\u00a0enough to be dignified by a special name: <b>DeMorgan\u2019s laws.<\/b><\/p>\n<p>The laws are named after Augustus De Morgan (1806\u20131871),\u00a0who introduced a formal version of the laws to classical propositional logic. De Morgan&#8217;s formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan&#8217;s claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians.\u00a0For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his <i>Summulae de Dialectica<\/i>, also describes rules of conversion that follow the lines of De Morgan&#8217;s laws.\u00a0Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic. De Morgan&#8217;s laws can be proved easily, and may even seem trivial.\u00a0Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.<\/p>\n<div class=\"textbox\">\n<h3>DeMorgan\u2019s Laws<\/h3>\n<ol>\n<li>[latex]\\sim\\left(P{\\wedge}Q\\right)=({\\sim}P)\\vee\\left(\\sim{Q}\\right)[\/latex]<\/li>\n<li>[latex]\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex]<\/li>\n<\/ol>\n<\/div>\n<p>The first of DeMorgan\u2019s laws is verified by the following table. You are\u00a0asked to verify the second in an\u00a0exercise.<\/p>\n<table cellpadding=\"0\" style=\"border-spacing: 0px;\">\n<tbody>\n<tr>\n<td><b>[latex]P[\/latex]<\/b><\/td>\n<td><b>[latex]Q[\/latex]<\/b><\/td>\n<td><b>[latex]\\sim{P}[\/latex]<\/b><\/td>\n<td><b>[latex]\\sim{Q}[\/latex]<\/b><\/td>\n<td>[latex]P\\wedge{Q}[\/latex]<\/td>\n<td><strong>[latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex]<\/strong><\/td>\n<td><b>[latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex]<\/b><\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<td>F<\/td>\n<td>T<\/td>\n<td>T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>DeMorgan\u2019s laws are actually very natural and intuitive. Consider the\u00a0statement [latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex], which we can interpret as meaning that it is not the\u00a0case that both <i>P<\/i> and <i>Q<\/i> are true. If it is not the case that both <i>P<\/i> and <i>Q<\/i>\u00a0are true, then at least one of <i>P<\/i> or <i>Q<\/i> is false, in which case [latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex]\u00a0is\u00a0true. Thus [latex]\\sim\\left(P\\wedge{Q}\\right)[\/latex]\u00a0means the same thing as [latex]\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)[\/latex].<\/p>\n<p>DeMorgan\u2019s laws can be very useful. Suppose we happen to know that\u00a0some statement having form [latex]\\sim\\left(P\\vee{Q}\\right)[\/latex]\u00a0is true. The second of DeMorgan\u2019s\u00a0laws tells us that [latex]\\left(\\sim{Q}\\right)\\wedge\\left(\\sim{P}\\right)[\/latex]\u00a0is also true, hence [latex]\\sim{P}[\/latex] and [latex]\\sim{Q}[\/latex] are both true\u00a0as well. Being able to quickly obtain such additional pieces of information\u00a0can be extremely useful.<\/p>\n<p>Here is a summary of some significant logical equivalences. Those that\u00a0are not immediately obvious can be verified with a truth table.<\/p>\n<p>[latex]\\text{Contrapositive law}\\begin{array}{c}P\\rightarrow{Q}=(\\sim{Q})\\rightarrow(\\sim{P})\\end{array}[\/latex]<\/p>\n<p>[latex]\\text{DeMorgan's laws}\\begin{array}{c}{\\sim(P\\land{Q})=\\sim{P}\\lor\\sim{Q}}\\\\{\\sim(P\\lor{Q})=\\sim{P}\\land\\sim{Q}}\\end{array}[\/latex]<\/p>\n<p>[latex]\\text{Commutative laws}\\begin{array}{c}{(P\\land{Q})={P}\\land{Q}}\\\\{(P\\lor{Q})={P}\\lor{Q}}\\end{array}[\/latex]<\/p>\n<p>[latex]\\text{Distributive laws}\\begin{array}{c}{{P}\\land(Q\\lor{R})=({P}\\land{Q})\\lor(P\\land{R})}\\\\{P\\lor(Q\\land{R})=({P}\\lor{Q})\\land(P\\lor{R})}\\end{array}[\/latex]<\/p>\n<p>[latex]\\text{Associative laws}\\begin{array}{c}{P\\land(Q\\land{R})=(P\\land{Q})\\land{R}}\\\\{P\\lor(Q\\lor{R})=(P\\lor{Q})\\lor{R}}\\end{array}[\/latex]<\/p>\n<p>Notice how the distributive law [latex]P\\wedge\\left(Q\\vee{R}\\right)=\\left(P\\wedge{Q}\\right)\\vee\\left(P\\wedge{Q}\\right)\\vee\\left(P\\wedge{R}\\right)[\/latex]\u00a0has the\u00a0same structure as the distributive law [latex]p\\left(q+r\\right)=p\\cdot{q}+p\\cdot{r}[\/latex]\u00a0from algebra.\u00a0Concerning the associative laws, the fact that [latex]P\\wedge\\left(Q\\wedge{R}\\right)=\\left(P\\wedge{Q}\\right)\\wedge{R}[\/latex]\u00a0means\u00a0that the position of the parentheses is irrelevant, and we can write this as [latex]P\\wedge{Q}\\wedge{R}[\/latex]\u00a0without ambiguity. Similarly, we may drop the parentheses in\u00a0an expression such as [latex]P\\vee\\left(Q\\vee{R}\\right)[\/latex].<\/p>\n<p>But parentheses are essential when there is a mix of [latex]\\wedge[\/latex]\u00a0and [latex]\\vee[\/latex], as in [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex]. Indeed, [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex] and [latex]P\\vee\\left(Q\\wedge{R}\\right)[\/latex] and [latex]P\\vee\\left({Q}\\right)\\wedge{R}[\/latex]<i><\/i> are <b>not<\/b> logically equivalent.<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=109604&#38;theme=oea&#38;iframe_resize_id=mom2\">https:\/\/www.myopenmath.com\/multiembedq.php?id=109604&amp;theme=oea&amp;iframe_resize_id=mom2<\/a><\/p>\n<\/div>\n<h3><b>Negating Statements<\/b><\/h3>\n<p>Given a statement <i>R<\/i>, the statement [latex]\\sim{R}[\/latex] is called the <b>negation<\/b> of <i>R<\/i>. If <i>R<\/i>\u00a0is a complex statement, then it is often the case that its negation [latex]\\sim{R}[\/latex]\u00a0can\u00a0be written in a simpler or more useful form. The process of finding this\u00a0form is called <b>negating<\/b> <i>R<\/i>. In proving theorems it is often necessary to\u00a0negate certain statements. We now investigate how to do this.<\/p>\n<p>We have already examined part of this topic. <b>DeMorgan\u2019s laws<\/b><\/p>\n<p>[latex]\\sim\\left(P\\wedge{Q}\\right)=\\left(\\sim{P}\\right)\\vee\\left(\\sim{Q}\\right)\\\\\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex]<\/p>\n<p>(from &#8220;Logical Equivalence&#8221;) can be viewed as rules that tell us how to negate the\u00a0statements [latex]P\\wedge{Q}[\/latex]\u00a0and [latex]P\\vee{Q}[\/latex]. Here are some examples that illustrate how\u00a0DeMorgan\u2019s laws are used to negate statements involving \u201cand\u201d or \u201cor.\u201d<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Consider negating the following statement.<\/p>\n<p><i>R<\/i> : You can solve it by factoring or with the quadratic formula.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q102469\">Show Answer<\/span><\/p>\n<div id=\"q102469\" class=\"hidden-answer\" style=\"display: none\">\n<p>Now, <i>R<\/i> means (You can solve it by factoring) [latex]\\vee[\/latex]\u00a0(You can solve it with Q.F.),\u00a0which we will denote as [latex]P\\vee{Q}[\/latex]. The negation of this is [latex]\\sim\\left(P\\vee{Q}\\right)=\\left(\\sim{P}\\right)\\wedge\\left(\\sim{Q}\\right)[\/latex].<\/p>\n<p>Therefore, in words, the negation of <i>R<\/i> is<\/p>\n<p>[latex]\\sim{R}[\/latex] : You can\u2019t solve it by factoring and you can\u2019t solve it with\u00a0the quadratic formula.<\/p>\n<p>Maybe you can find [latex]\\sim{R}[\/latex]\u00a0without invoking DeMorgan\u2019s laws. That is good;\u00a0you have internalized DeMorgan\u2019s laws and are using them unconsciously.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>We will negate the following sentence.<\/p>\n<p><i>R<\/i> : The numbers x and y are both odd.<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q441993\">Show Answer<\/span><\/p>\n<div id=\"q441993\" class=\"hidden-answer\" style=\"display: none\">\n<p>This statement means [latex]\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)[\/latex], so its negation is<\/p>\n<p style=\"text-align: center\">[latex]\\sim\\left[\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)\\right]=\\sim\\left(x\\text{ is odd}\\right)\\vee\\sim\\left(y\\text{ is odd}\\right)\\\\\\left(x\\text{ is odd}\\right)\\wedge\\left(y\\text{ is odd}\\right)=\\left(x\\text{ is even}\\right)\\vee\\left(y\\text{ is even}\\right)[\/latex]<\/p>\n<p>Therefore the negation of <i>R<\/i> can be expressed in the following ways:<\/p>\n<p>[latex]\\sim{R}[\/latex]: The number x is even or the number y is even.<br \/>\n[latex]\\sim{R}[\/latex]: At least one of x and y is even.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try it now<\/h3>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=109608&#38;theme=oea&#38;iframe_resize_id=mom1\">https:\/\/www.myopenmath.com\/multiembedq.php?id=109608&amp;theme=oea&amp;iframe_resize_id=mom1<\/a><\/p>\n<\/div>\n\n\t\t\t <section class=\"citations-section\" role=\"contentinfo\">\n\t\t\t <h3>Candela Citations<\/h3>\n\t\t\t\t\t <div>\n\t\t\t\t\t\t <div id=\"citation-list-1918\">\n\t\t\t\t\t\t\t <div class=\"licensing\"><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Original<\/div><ul class=\"citation-list\"><li>Introduction and Learning Objectives. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Revision and Adaptation. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Shared previously<\/div><ul class=\"citation-list\"><li>Question ID 25462, 25592. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License CC-BY + GPL<\/li><li>Math in Society. <strong>Authored by<\/strong>: David Lippman. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\">http:\/\/www.opentextbookstore.com\/mathinsociety\/<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Question ID 108578, 108573, 109608, 109064. <strong>Authored by<\/strong>: Hartley, Josiah. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License CC-BY + GPL<\/li><li>Question ID 25472, 25467. <strong>Authored by<\/strong>: Shahbazian, Roy. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License CC-BY + GPL<\/li><li>Question ID 25595, 25597. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License CC-BY + GPL<\/li><li>DeMorgan&#039;s Laws. <strong>Authored by<\/strong>: Wikipedia. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/en.wikipedia.org\/wiki\/De_Morgan%27s_laws\">https:\/\/en.wikipedia.org\/wiki\/De_Morgan%27s_laws<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/\">CC BY-SA: Attribution-ShareAlike<\/a><\/em><\/li><\/ul><\/div>\n\t\t\t\t\t\t <\/div>\n\t\t\t\t\t <\/div>\n\t\t\t <\/section>","protected":false},"author":21,"menu_order":3,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Introduction and Learning Objectives\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Question ID 25462, 25592\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License CC-BY + GPL\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Question ID 108578, 108573, 109608, 109064\",\"author\":\"Hartley, Josiah\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License CC-BY + GPL\"},{\"type\":\"cc\",\"description\":\"Question ID 25472, 25467\",\"author\":\"Shahbazian, Roy\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License CC-BY + GPL\"},{\"type\":\"cc\",\"description\":\"Question ID 25595, 25597\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License CC-BY + GPL\"},{\"type\":\"cc\",\"description\":\"DeMorgan\\'s Laws\",\"author\":\"Wikipedia\",\"organization\":\"\",\"url\":\"https:\/\/en.wikipedia.org\/wiki\/De_Morgan%27s_laws\",\"project\":\"\",\"license\":\"cc-by-sa\",\"license_terms\":\"\"}]","CANDELA_OUTCOMES_GUID":"","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-1918","chapter","type-chapter","status-publish","hentry"],"part":3083,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapters\/1918","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":17,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapters\/1918\/revisions"}],"predecessor-version":[{"id":3839,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapters\/1918\/revisions\/3839"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/parts\/3083"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapters\/1918\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/wp\/v2\/media?parent=1918"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/pressbooks\/v2\/chapter-type?post=1918"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/wp\/v2\/contributor?post=1918"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/cccs-coreq-mathforliberalarts\/wp-json\/wp\/v2\/license?post=1918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}