{"id":1082,"date":"2017-01-11T00:44:31","date_gmt":"2017-01-11T00:44:31","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/?post_type=chapter&p=1082"},"modified":"2021-02-05T23:51:34","modified_gmt":"2021-02-05T23:51:34","slug":"putting-it-together-set-theory","status":"web-only","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/chapter\/putting-it-together-set-theory\/","title":{"raw":"Putting It Together: Set Theory and Logic","rendered":"Putting It Together: Set Theory and Logic"},"content":{"raw":"[caption id=\"attachment_2379\" align=\"alignright\" width=\"285\"]\"A<\/a> George Boole[\/caption]\r\n\r\nIn this module we\u2019ve seen how logic and valid arguments can be formalized using mathematical notation and a few basic rules. \u00a0In fact when George Boole (1815-1864) first developed symbolic logic<\/strong> (or Boolean logic<\/strong>), he had the idea that his system could be used by lawyers, philosophers, and mathematicians alike to help put convoluted arguments on a firmer footing. \u00a0Little did he realize that his system of \u201cand<\/em>,\u201d \u201cor<\/em>,\u201d and \u201cnot<\/em>\u201d operations would one day transform the world by ushering in the Digital Revolution and modern day computing.\r\n\r\n \r\n\r\nWhat is the connection between logic and computers? \u00a0Instead of truth values T<\/strong> and F<\/strong>, digital computers rely on two states<\/strong>, either on<\/em>(1) or off<\/em>(0). \u00a0This is because a computer consists of many circuits<\/strong>, which are electrical pathways that can either be closed to allow the current to flow, or open to break the connection. \u00a0A \u201c1\u201d would signify a closed circuit while a \u201c0\u201d represents an open circuit.\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nCertain components called gates<\/strong> allow the computer to open or close circuits based on input. \u00a0For example, an AND gate has two input wires (A, B) and one output (C). \u00a0Electricity will flow at C if and only if both A and B have current. \u00a0Traditionally, the AND operation is written like multiplication; that is, A AND B = AB.\r\n\r\n\"AND<\/a>\r\n\r\n \r\n\r\nMultiplication seems to be a natural interpretation of AND when applied to the values 0 and 1. \u00a0Just think about the truth table for the operation [latex]\\wedge[\/latex], replacing T<\/strong> by 1 and F<\/strong> by 0.\r\n
\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
A<\/td>\r\nB<\/td>\r\nAB (A AND B)<\/td>\r\n<\/tr>\r\n
1<\/td>\r\n1<\/td>\r\n1<\/td>\r\n<\/tr>\r\n
1<\/td>\r\n0<\/td>\r\n0<\/td>\r\n<\/tr>\r\n
0<\/td>\r\n1<\/td>\r\n0<\/td>\r\n<\/tr>\r\n
0<\/td>\r\n0<\/td>\r\n0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n \r\n\r\nThere is also an OR gate. \u00a0Again, two inputs A and B determine the output C, however this time C = 1 if and only if either A or B (or both) is equal to 1. \u00a0This operation, which corresponds to the logical expression [latex]A \\vee B[\/latex], is often interpreted as a kind of addition (A OR B = A + B), however it\u2019s not a perfect analogy because [latex]1+1=1[\/latex] in Boolean logic.\r\n\r\n\"OR<\/a>\r\n\r\n \r\n
\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
A<\/td>\r\nB<\/td>\r\nA + B (A OR B)<\/td>\r\n<\/tr>\r\n
1<\/td>\r\n1<\/td>\r\n1<\/td>\r\n<\/tr>\r\n
1<\/td>\r\n0<\/td>\r\n1<\/td>\r\n<\/tr>\r\n
0<\/td>\r\n1<\/td>\r\n1<\/td>\r\n<\/tr>\r\n
0<\/td>\r\n0<\/td>\r\n0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n \r\n\r\nFinally, there is a gate whose output is the opposite state as its input. \u00a0So if the input (A) is 1, then the output (C) will be 0, and vice versa. \u00a0This is called the NOT gate. \u00a0You have encountered \u201cnot\u201d as the logical expression [latex]\\sim\\!\\textrm{A}[\/latex], but \u00a0the usual notation in computer science for NOT A is [latex]\\overline{\\textrm{A}}[\/latex]. \u00a0The gate along with its truth table shown below.\r\n\r\n\"NOT<\/a>\r\n\r\n \r\n
\r\n\r\n\r\n\r\n\r\n\r\n
A<\/td>\r\n[latex]\\overline{\\textrm{A}}[\/latex] (NOT A)<\/td>\r\n<\/tr>\r\n
1<\/td>\r\n0<\/td>\r\n<\/tr>\r\n
0<\/td>\r\n1<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n \r\n\r\nMoreover, numerical values can be represented by a string of 1\u2019s and 0\u2019s in what we call binary notation<\/strong>. \u00a0Then the basic operations of addition, subtraction, multiplication, and division of binary number can actually be accomplished using the right combination of gates, in other words by Boolean logical operations.\r\n\r\n \r\n\r\nHowever a proper discussion of binary arithmetical falls outside the scope of this discussion. \u00a0Instead, let\u2019s use Boolean logic and to find a simpler circuit equivalent to the one shown.\r\n

\"Diagram<\/a><\/p>\r\n \r\n\r\nThe given circuit has\u00a0three gates. \u00a0Can you find a circuit with only two gates that produces exactly the same output (Q) for all choices of input (A, B)?\r\n\r\n \r\n\r\nLet\u2019s translate the diagram into a Boolean expression. \u00a0First, both A and B are negated to obtain [latex]\\overline{\\textrm{A}}[\/latex] and [latex]\\overline{\\textrm{B}}[\/latex], respectively. \u00a0Those expressions in turn feed into the AND gate. \u00a0So [latex]\\textrm{Q} =\\overline{\\textrm{A}} \\cdot \\overline{\\textrm{B}}[\/latex]. \u00a0In terms of the logical operations you have studied in this module,\r\n

[latex]\\textrm{Q}=\\overline{\\textrm{A}}\\cdot\\overline{\\textrm{B}}=(\\sim\\!\\textrm{A})\\wedge(\\sim\\!\\textrm{B})[\/latex]<\/p>\r\n \r\n\r\nYou may recognize the expression as one side of De Morgan\u2019s Law. \u00a0Therefore, there is an equivalence,\r\n

[latex](\\sim\\!\\textrm{A})\\wedge(\\sim\\!\\textrm{B})= \\;\\sim\\!(\\textrm{A} \\vee \\textrm{B}) = \\overline{\\textrm{A} + \\textrm{B}}[\/latex]<\/p>\r\n \r\n\r\nFinally, the last expression corresponds to a circuit diagram with only two gates, an OR and a NOT.\r\n\r\n\"Diagram<\/a>\r\n\r\n ","rendered":"

\"A<\/a><\/p>\n

George Boole<\/p>\n<\/div>\n

In this module we\u2019ve seen how logic and valid arguments can be formalized using mathematical notation and a few basic rules. \u00a0In fact when George Boole (1815-1864) first developed symbolic logic<\/strong> (or Boolean logic<\/strong>), he had the idea that his system could be used by lawyers, philosophers, and mathematicians alike to help put convoluted arguments on a firmer footing. \u00a0Little did he realize that his system of \u201cand<\/em>,\u201d \u201cor<\/em>,\u201d and \u201cnot<\/em>\u201d operations would one day transform the world by ushering in the Digital Revolution and modern day computing.<\/p>\n

 <\/p>\n

What is the connection between logic and computers? \u00a0Instead of truth values T<\/strong> and F<\/strong>, digital computers rely on two states<\/strong>, either on<\/em>(1) or off<\/em>(0). \u00a0This is because a computer consists of many circuits<\/strong>, which are electrical pathways that can either be closed to allow the current to flow, or open to break the connection. \u00a0A \u201c1\u201d would signify a closed circuit while a \u201c0\u201d represents an open circuit.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Certain components called gates<\/strong> allow the computer to open or close circuits based on input. \u00a0For example, an AND gate has two input wires (A, B) and one output (C). \u00a0Electricity will flow at C if and only if both A and B have current. \u00a0Traditionally, the AND operation is written like multiplication; that is, A AND B = AB.<\/p>\n

\"AND<\/a><\/p>\n

 <\/p>\n

Multiplication seems to be a natural interpretation of AND when applied to the values 0 and 1. \u00a0Just think about the truth table for the operation [latex]\\wedge[\/latex], replacing T<\/strong> by 1 and F<\/strong> by 0.<\/p>\n

\n\n\n\n\n\n\n\n
A<\/td>\nB<\/td>\nAB (A AND B)<\/td>\n<\/tr>\n
1<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
0<\/td>\n1<\/td>\n0<\/td>\n<\/tr>\n
0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

 <\/p>\n

There is also an OR gate. \u00a0Again, two inputs A and B determine the output C, however this time C = 1 if and only if either A or B (or both) is equal to 1. \u00a0This operation, which corresponds to the logical expression [latex]A \\vee B[\/latex], is often interpreted as a kind of addition (A OR B = A + B), however it\u2019s not a perfect analogy because [latex]1+1=1[\/latex] in Boolean logic.<\/p>\n

\"OR<\/a><\/p>\n

 <\/p>\n

\n\n\n\n\n\n\n\n
A<\/td>\nB<\/td>\nA + B (A OR B)<\/td>\n<\/tr>\n
1<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
0<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

 <\/p>\n

Finally, there is a gate whose output is the opposite state as its input. \u00a0So if the input (A) is 1, then the output (C) will be 0, and vice versa. \u00a0This is called the NOT gate. \u00a0You have encountered \u201cnot\u201d as the logical expression [latex]\\sim\\!\\textrm{A}[\/latex], but \u00a0the usual notation in computer science for NOT A is [latex]\\overline{\\textrm{A}}[\/latex]. \u00a0The gate along with its truth table shown below.<\/p>\n

\"NOT<\/a><\/p>\n

 <\/p>\n

\n\n\n\n\n\n
A<\/td>\n[latex]\\overline{\\textrm{A}}[\/latex] (NOT A)<\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n<\/tr>\n
0<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

 <\/p>\n

Moreover, numerical values can be represented by a string of 1\u2019s and 0\u2019s in what we call binary notation<\/strong>. \u00a0Then the basic operations of addition, subtraction, multiplication, and division of binary number can actually be accomplished using the right combination of gates, in other words by Boolean logical operations.<\/p>\n

 <\/p>\n

However a proper discussion of binary arithmetical falls outside the scope of this discussion. \u00a0Instead, let\u2019s use Boolean logic and to find a simpler circuit equivalent to the one shown.<\/p>\n

\"Diagram<\/a><\/p>\n

 <\/p>\n

The given circuit has\u00a0three gates. \u00a0Can you find a circuit with only two gates that produces exactly the same output (Q) for all choices of input (A, B)?<\/p>\n

 <\/p>\n

Let\u2019s translate the diagram into a Boolean expression. \u00a0First, both A and B are negated to obtain [latex]\\overline{\\textrm{A}}[\/latex] and [latex]\\overline{\\textrm{B}}[\/latex], respectively. \u00a0Those expressions in turn feed into the AND gate. \u00a0So [latex]\\textrm{Q} =\\overline{\\textrm{A}} \\cdot \\overline{\\textrm{B}}[\/latex]. \u00a0In terms of the logical operations you have studied in this module,<\/p>\n

[latex]\\textrm{Q}=\\overline{\\textrm{A}}\\cdot\\overline{\\textrm{B}}=(\\sim\\!\\textrm{A})\\wedge(\\sim\\!\\textrm{B})[\/latex]<\/p>\n

 <\/p>\n

You may recognize the expression as one side of De Morgan\u2019s Law. \u00a0Therefore, there is an equivalence,<\/p>\n

[latex](\\sim\\!\\textrm{A})\\wedge(\\sim\\!\\textrm{B})= \\;\\sim\\!(\\textrm{A} \\vee \\textrm{B}) = \\overline{\\textrm{A} + \\textrm{B}}[\/latex]<\/p>\n

 <\/p>\n

Finally, the last expression corresponds to a circuit diagram with only two gates, an OR and a NOT.<\/p>\n

\"Diagram<\/a><\/p>\n

 <\/p>\n","protected":false},"author":21,"menu_order":24,"template":"","meta":{"_candela_citation":"","CANDELA_OUTCOMES_GUID":"","pb_show_title":"","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-1082","chapter","type-chapter","status-web-only","hentry"],"part":159,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1082","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":15,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1082\/revisions"}],"predecessor-version":[{"id":2391,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1082\/revisions\/2391"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/parts\/159"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1082\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/media?parent=1082"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapter-type?post=1082"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/contributor?post=1082"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/license?post=1082"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}