Discrete Structures Lecture 5


 Delphia York
 3 years ago
 Views:
Transcription
1 Introduction EXAMPLE 1 Express xx yy(xx + yy = 0) without the existential quantifier. Solution: xx yy(xx + yy = 0) is the same as xxxx(xx) where QQ(xx) is yyyy(xx, yy) and PP(xx, yy) = xx + yy = 0 EXAMPLE 2 Translate xx yy((xx > 0) (yy < 0) xxxx < 0)) into English. The Order of Quantifiers Solution: This statement says that for every real number x and for every real number y, if xx > 0 and yy < 0, then xxxx < 0. That is, this statement says that for real numbers x and y, if x is positive and y is negative, then xy is negative. The can be stated more succinctly as The product of a positive real number and a negative real number is always a negative real number. EXAMPLE 3 Let PP(xx, yy) be the statement xx + yy = yy + xx. " What are the truth values of the quantifications xx yyyy(xx, yy) and yy xxxx(xx, yy) where the domain for all variables consists of all real numbers. Solution: The quantification xx yyyy(xx, yy) denotes the proposition For all real numbers x, for all real numbers y, xx + yy = yy + xx. Because PP(xx, yy) is true for all real numbers x and y (it is the commutative law for addition which is an axiom for the real numbers), the proposition xx yyyy(xx, yy) is true. Note that the statement yy xxxx(xx, yy) says For all real numbers y, for all real numbers x, xx + yy = yy + xx. This has the same meaning as the statement For all real numbers x, for all real numbers y, xx + yy = yy + xx. That is, xx yyyy(xx, yy) and yy xxxx(xx, yy) have the same meaning, and both are true. This illustrates the principle that the order of nested universal quantifiers in a statement without other quantifiers can be changed without changing the meaning of the quantified statement. 1
2 EXAMPLE 4 Let QQ(xx, yy) denote xx + yy = 0. What are the truth values of the quantifications yy xxxx(xx, yy), where the domain for all variables consists of all real numbers. Solution: The quantification yy xxxx(xx, yy) denotes the proposition There is a real number y such that for every real number x, QQ(xx, yy). No matter what value of y is chosen, there is only one value of x for which xx + yy = 0. Because there is no real number y such that xx + yy = 0 for all real numbers x, the statement yy xxxx(xx, yy) is false. The quantification denotes the proposition xx yyyy(xx, yy) For every real number x there is a real number y such that QQ(xx, yy). Given a real number x, there is a real number y such that xx + yy = 0; namely, yy = xx. Hence, the statement xx yyyy(xx, yy) is true. Example 4 illustrates that the order in which quantifiers appear makes a difference. The statements yy xxxx(xx, yy) and xx yyyy(xx, yy) are not logically equivalent. The statement yy xxxx(xx, yy) is true if and only if there is a y that makes PP(xx, yy) true for every x. So, for this statement to be true, there must be a particular value of y for which PP(xx, yy) is true regardless of the choice of x. On the other hand, xx yyyy(xx, yy) is true if and only if for every value of x there is a value of y for which PP(xx, yy) is true. So, for this statement to be true, no matter which x you choose, there must be a value of y (possibly depending of the x you choose) for which PP(xx, yy) is true. In other words, in the second case, y can depend on x, whereas in the first case y is a constant independent of x. From these observations it follows that if yy xxxx(xx, yy) is true, then xx yyyy(xx, yy) must also be true. However, if xx yyyy(xx, yy) is true, it is not necessary for yy xxxx(xx, yy) to be true. 2
3 TABLE 1 Quantifications of Two Variables. Statement When True? When False? xx yyyy(xx, yy) PP(xx, yy) is true for every pair x, y. There is a pair x, y for which PP(xx, yy) is yy xxxx(xx, yy) false. xx yyyy(xx, yy) For every xx there is a yy for which PP(xx, yy) is true. There is an x such that PP(xx, yy) is false for every y. xx yyyy(xx, yy) There is an x for which PP(xx, yy) is For every x there is a y for which PP(xx, yy) xx yyyy(xx, yy) yy xxxx(xx, yy) true for every y. There is a pair xx, yy for which PP(xx, yy) is true. is false. PP(xx, yy) is false for every pair xx, yy. EXAMPLE 5 Let QQ(xx, yy, zz) be the statement xx + yy = zz. What are the truth values of the statements xx yy zzzz(xx, yy, zz) and zz xx yyyy(xx, yy, zz), where the domain of all variables consists of all real numbers? Solution: Suppose that xx and yy are assigned values. Then, there exists a real number zz such that xx + yy = zz. Consequently, the quantification xx yy zzzz(xx, yy, zz) which is the statement For all real numbers x and for all real numbers y there is a real number z such that xx + yy = zz. " is true. The order of the quantification is important, because the quantification zz xx yyyy(xx, yy, zz) which is the statement There is a real number z such that for all real numbers x and for all real numbers y it is true that xx + yy = zz. is false, because there is no value of z that satisfies the equation xx + yy = zz for all values of x and y. 3
4 Translating Mathematical Statements into Statements Involving Nested Quantifiers EXAMPLE 6 Translate the statement The sum of two positive integers is always positive into a logical expression. Solution: 1. To translate this statement into a logical expression, we first rewrite it so that the implied quantifiers and a domain are shown. For every two integers, if these integers are both positive, then the sum of these integers is positive. 2. Next, we introduce the variables x and y to obtain For all positive integers x and y, xx + yy is positive. 3. We can express the foregoing as xx yy((xx > 0) (yy > 0) (xx + yy > 0)) where the domain for both variables consists of all integers. 4. Note that we could also translate this using the positive integers as the domain. Then the statement The sum of two positive integers is always positive becomes For every two positive integers, the sum of these integers is positive. We can express this as xx yy(xx + yy > 0). 4
5 Translating from Nested Quantifiers into English EXAMPLE 9 Translate the statement xx(cc(xx) yyyy(yy) FF(xx, yy))) into English, where CC(xx) is the x has a computer, FF(xx, yy) is x and y are friends, and the domain for both x and y consists of all students in your school. Solution: The statement says that for every student x in your school, x has a computer or there is a student y such that y has a computer and x and y are friends. In other words, every student in your school has a computer or has a friend who has a computer. Translating English Sentences into Logical Expressions EXAMPLE 11 Express the statement If a person is female and is a parent, then this person is someone s mother as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives. Solution: 1. FF(xx) x is female. 2. PP(xx) x is a parent. 3. MM(xx, yy) x is the mother of y. xx( FF(xx) PP(xx) yyyy(xx, yy)) or xx yy( FF(xx) PP(xx) MM(xx, yy)) EXAMPLE 13 Use quantifiers to express the statement There is a woman who has taken a flight on every airline in the world. Solution: Let PP(ww, ff) be w has taken f and QQ(ff, aa) be f is a flight on a. We can express the statement as ww aa ff(pp(ww, ff) QQ(ff, aa)), where the domains of discourse for w, f, and a consist of all the women in the world, all airplane flights, and all airlines respectively. 5
6 Negating Nested Quantifiers TABLE 2 De Morgan s Laws for Quantifiers (from section 1.3) Negation Equivalent Statement When Is Negation True? When False? xxxx(xx) xx PP(xx) For every x, PP(xx) is false There is an xx, for which PP(xx) is true. xxxx(xx) xx PP(xx) There is an xx, for which PP(xx) is false. PP(xx) is true for every x. EXAMPLE 14 Express the negation of the statement xx yy(xxxx = 1) so that no negation precedes a quantifier. Solution: By successively applying De Morgan s laws for quantifiers in Table 2 of Section 1.3, we can move the negation in xx xx(xxxx = 1) inside all the quantifiers. We find that xx yy(xxxx = 1) is equivalent to xx yy(xxxx = 1), which is equivalent to xx yy (xxxx = 1). Because (xxxx = 1) can be expressed more simply as xxxx 1, we conclude that our negated statement can be expressed as xx yy(xxxx 1) EXAMPLE 15 Use quantifiers to express the statement that There does not exist a woman who has taken a flight on every airline in the world. Solution: This statement is the negation of the statement There is a woman who has taken a flight on every airline in the world. from Example 13. By Example 13, our statement can be expressed as ww aa ff PP(ww, ff) QQ(ff, aa), where PP(ww, ff) be w has taken f and QQ(ff, aa) be f is a flight on a. By successively applying De Morgan s laws for quantifiers in Table 2 of Section 1.3 to move the negation inside successive quantifiers and by applying De Morgan s low for negating a conjunction in the last step, we find that our statement is equivalent to each of the sequence of statements: Statement Justification ww aa ff PP(ww, ff) QQ(ff, aa) Original statement ww aa ff PP(ww, ff) QQ(ff, aa) Table 2 Section 1.3 xxxx(xx) xx PP(xx) ww aa ff PP(ww, ff) QQ(ff, aa) Table 2 Section 1.3 xxxx(xx) xx PP(xx) ww aa ff PP(ww, ff) QQ(ff, aa) Table 2 Section 1.3 xxxx(xx) xx PP(xx) ww aa ff PP(ww, ff) QQ(ff, aa) Table 2 Section 1.2 (pp qq) pp qq This last statement states For every woman there is an airline such that for all flights, this woman has not taken that flight or that flight is not on this airline. 6
Discrete Structures Lecture Predicates and Quantifiers
Introduction In this section we will introduce a more powerful type of logic called predicate logic. Predicates Consider the statement: xx > 3. The statement has two parts: 1. the variable, xx and 2. the
More informationSection Summary. Section 1.5 9/9/2014
Section 1.5 Section Summary Nested Quantifiers Order of Quantifiers Translating from Nested Quantifiers into English Translating Mathematical Statements into Statements involving Nested Quantifiers Translated
More informationDiscrete Mathematics and Its Applications
Discrete Mathematics and Its Applications Lecture 1: The Foundations: Logic and Proofs (1.31.5) MING GAO DASE @ ECNU (for course related communications) mgao@dase.ecnu.edu.cn Sep. 19, 2017 Outline 1 Logical
More informationThinking of Nested Quantification
Section 1.5 Section Summary Nested Quantifiers Order of Quantifiers Translating from Nested Quantifiers into English Translating Mathematical Statements into Statements involving Nested Quantifiers. Translating
More informationLecture 3. Logic Predicates and Quantified Statements Statements with Multiple Quantifiers. Introduction to Proofs. Reading (Epp s textbook)
Lecture 3 Logic Predicates and Quantified Statements Statements with Multiple Quantifiers Reading (Epp s textbook) 3.13.3 Introduction to Proofs Reading (Epp s textbook) 4.14.2 1 Propositional Functions
More informationRecall that the expression x > 3 is not a proposition. Why?
Predicates and Quantifiers Predicates and Quantifiers 1 Recall that the expression x > 3 is not a proposition. Why? Notation: We will use the propositional function notation to denote the expression "
More informationLogical equivalences 12/8/2015. S T: Two statements S and T involving predicates and quantifiers are logically equivalent
1/8/015 Logical equivalences CSE03 Discrete Computational Structures Lecture 3 1 S T: Two statements S and T involving predicates and quantifiers are logically equivalent If and only if they have the same
More informationLogical Operators. Conjunction Disjunction Negation Exclusive Or Implication Biconditional
Logical Operators Conjunction Disjunction Negation Exclusive Or Implication Biconditional 1 Statement meaning p q p implies q if p, then q if p, q when p, q whenever p, q q if p q when p q whenever p p
More informationLogic and Proofs. (A brief summary)
Logic and Proofs (A brief summary) Why Study Logic: To learn to prove claims/statements rigorously To be able to judge better the soundness and consistency of (others ) arguments To gain the foundations
More informationDiscrete Mathematics Recitation Course 張玟翔
Discrete Mathematics Recitation Course 1 2013.03.07 張玟翔 Acknowledge 鄭安哲 TA 2012 About Myself English Name : Zak Chinese Name : 張玟翔 Mail:o0000032@yahoo.com.tw Lab: ED612 11 Propositional Logic 11 Ex.2
More informationPropositional Logic Not Enough
Section 1.4 Propositional Logic Not Enough If we have: All men are mortal. Socrates is a man. Does it follow that Socrates is mortal? Can t be represented in propositional logic. Need a language that talks
More informationSection Summary. Predicate logic Quantifiers. Negating Quantifiers. Translating English to Logic. Universal Quantifier Existential Quantifier
Section 1.4 Section Summary Predicate logic Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan s Laws for Quantifiers Translating English to Logic Propositional Logic
More informationCSI30. Chapter 1. The Foundations: Logic and Proofs Nested Quantifiers
Chapter 1. The Foundations: Logic and Proofs 1.91.10 Nested Quantifiers 1 Two quantifiers are nested if one is within the scope of the other. Recall one of the examples from the previous class: x ( P(x)
More informationIntroduction to Sets and Logic (MATH 1190)
Introduction to Sets Logic () Instructor: Email: shenlili@yorku.ca Department of Mathematics Statistics York University Sept 18, 2014 Outline 1 2 Tautologies Definition A tautology is a compound proposition
More informationMat 243 Exam 1 Review
OBJECTIVES (Review problems: on next page) 1.1 Distinguish between propositions and nonpropositions. Know the truth tables (i.e., the definitions) of the logical operators,,,, and Write truth tables for
More informationPredicates and Quantifiers. Nested Quantifiers Discrete Mathematic. Chapter 1: Logic and Proof
Discrete Mathematic Chapter 1: Logic and Proof 1.3 Predicates and Quantifiers 1.4 Nested Quantifiers Dr Patrick Chan School of Computer Science and Engineering South China University of Technology http://125.216.243.100/dm/
More information! Predicates! Variables! Quantifiers. ! Universal Quantifier! Existential Quantifier. ! Negating Quantifiers. ! De Morgan s Laws for Quantifiers
Sec$on Summary (K. Rosen notes for Ch. 1.4, 1.5 corrected and extended by A.Borgida)! Predicates! Variables! Quantifiers! Universal Quantifier! Existential Quantifier! Negating Quantifiers! De Morgan s
More information2/2/2018. CS 103 Discrete Structures. Chapter 1. Propositional Logic. Chapter 1.1. Propositional Logic
CS 103 Discrete Structures Chapter 1 Propositional Logic Chapter 1.1 Propositional Logic 1 1.1 Propositional Logic Definition: A proposition :is a declarative sentence (that is, a sentence that declares
More informationPredicate Logic. CSE 191, Class Note 02: Predicate Logic Computer Sci & Eng Dept SUNY Buffalo
Predicate Logic CSE 191, Class Note 02: Predicate Logic Computer Sci & Eng Dept SUNY Buffalo c Xin He (University at Buffalo) CSE 191 Discrete Structures 1 / 22 Outline 1 From Proposition to Predicate
More informationVariable Names. Some Ques(ons about Quan(fiers (but answers are not proven just stated here!) x ( z Q(z) y P(x,y) )
FOL Con(nued Review Variable Names Note that just because variables have different names it does not mean they have different values e.g. over the domain of positive integers x. y. (x+y=2) is True, (exctly
More informationLecture Predicates and Quantifiers 1.5 Nested Quantifiers
Lecture 4 1.4 Predicates and Quantifiers 1.5 Nested Quantifiers Predicates The statement "x is greater than 3" has two parts. The first part, "x", is the subject of the statement. The second part, "is
More informationToday s Lecture. ICS 6B Boolean Algebra & Logic. Predicates. Chapter 1: Section 1.3. Propositions. For Example. Socrates is Mortal
ICS 6B Boolean Algebra & Logic Today s Lecture Chapter 1 Sections 1.3 & 1.4 Predicates & Quantifiers 1.3 Nested Quantifiers 1.4 Lecture Notes for Summer Quarter, 2008 Michele Rousseau Set 2 Ch. 1.3, 1.4
More informationIntroduction to Decision Sciences Lecture 2
Introduction to Decision Sciences Lecture 2 Andrew Nobel August 24, 2017 Compound Proposition A compound proposition is a combination of propositions using the basic operations. For example (p q) ( p)
More informationCS 220: Discrete Structures and their Applications. Predicate Logic Section in zybooks
CS 220: Discrete Structures and their Applications Predicate Logic Section 1.61.10 in zybooks From propositional to predicate logic Let s consider the statement x is an odd number Its truth value depends
More informationPredicate Calculus lecture 1
Predicate Calculus lecture 1 Section 1.3 Limitation of Propositional Logic Consider the following reasoning All cats have tails Gouchi is a cat Therefore, Gouchi has tail. MSU/CSE 260 Fall 2009 1 MSU/CSE
More informationProposi'onal Logic Not Enough
Section 1.4 Proposi'onal Logic Not Enough If we have: All men are mortal. Socrates is a man. Socrates is mortal Compare to: If it is snowing, then I will study discrete math. It is snowing. I will study
More informationSection Summary. Predicate logic Quantifiers. Negating Quantifiers. Translating English to Logic. Universal Quantifier Existential Quantifier
Section 1.4 Section Summary Predicate logic Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan s Laws for Quantifiers Translating English to Logic Propositional Logic
More informationMath.3336: Discrete Mathematics. Nested Quantifiers
Math.3336: Discrete Mathematics Nested Quantifiers Instructor: Dr. Blerina Xhabli Department of Mathematics, University of Houston https://www.math.uh.edu/ blerina Email: blerina@math.uh.edu Fall 2018
More informationChapter 2: The Logic of Quantified Statements. January 22, 2010
Chapter 2: The Logic of Quantified Statements January 22, 2010 Outline 1 2.1 Introduction to Predicates and Quantified Statements I 2 2.2  Introduction to Predicates and Quantified Statements II 3 2.3
More informationLogic and Proof. Aiichiro Nakano
Logic and Proof Aiichiro Nakano Collaboratory for Advanced Computing & Simulations Department of Computer Science Department of Physics & Astronomy Department of Chemical Engineering & Materials Science
More informationPredicate in English. Predicates and Quantifiers. Predicate in Logic. Propositional Functions: Prelude. Propositional Function
Predicates and Quantifiers Chuck Cusack Predicate in English In English, a sentence has 2 parts: the subject and the predicate. The predicate is the part of the sentence that states something about the
More informationDiscrete Structures for Computer Science
Discrete Structures for Computer Science William Garrison bill@cs.pitt.edu 6311 Sennott Square Lecture #4: Predicates and Quantifiers Based on materials developed by Dr. Adam Lee Topics n Predicates n
More informationSection Summary. Predicates Variables Quantifiers. Negating Quantifiers. Translating English to Logic Logic Programming (optional)
Predicate Logic 1 Section Summary Predicates Variables Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan s Laws for Quantifiers Translating English to Logic Logic Programming
More informationLecture 4. Predicate logic
Lecture 4 Predicate logic Instructor: Kangil Kim (CSE) Email: kikim01@konkuk.ac.kr Tel. : 024503493 Room : New Milenium Bldg. 1103 Lab : New Engineering Bldg. 1202 All slides are based on CS441 Discrete
More informationICS141: Discrete Mathematics for Computer Science I
ICS141: Discrete Mathematics for Computer Science I Dept. Information & Computer Sci., Originals slides by Dr. Baek and Dr. Still, adapted by J. Stelovsky Based on slides Dr. M. P. Frank and Dr. J.L. Gross
More informationReview. Propositional Logic. Propositions atomic and compound. Operators: negation, and, or, xor, implies, biconditional.
Review Propositional Logic Propositions atomic and compound Operators: negation, and, or, xor, implies, biconditional Truth tables A closer look at implies Translating from/ to English Converse, inverse,
More information3/29/2017. Logic. Propositions and logical operations. Main concepts: propositions truth values propositional variables logical operations
Logic Propositions and logical operations Main concepts: propositions truth values propositional variables logical operations 1 Propositions and logical operations A proposition is the most basic element
More informationNested Quantifiers. Predicates and. Quantifiers. Agenda. Limitation of Propositional Logic. Try to represent them using propositional.
Disc rete M athema tic Chapter 1: Logic and Proof 1.3 Predicates and Quantifiers 1.4 Nested Quantifiers Dr Patrick Chan School of Computer Science and Engineering South China Univers ity of Technology
More informationPredicate Logic Thursday, January 17, 2013 Chittu Tripathy Lecture 04
Predicate Logic Today s Menu Predicate Logic Quantifiers: Universal and Existential Nesting of Quantifiers Applications Limitations of Propositional Logic Suppose we have: All human beings are mortal.
More informationECOM Discrete Mathematics
ECOM 2311 Discrete Mathematics Chapter # 1 : The Foundations: Logic and Proofs Fall, 2013/2014 ECOM 2311 Discrete Mathematics  Ch.1 Dr. Musbah Shaat 1 / 85 Outline 1 Propositional Logic 2 Propositional
More information1 Predicates and Quantifiers
1 Predicates and Quantifiers We have seen how to represent properties of objects. For example, B(x) may represent that x is a student at Bryn Mawr College. Here B stands for is a student at Bryn Mawr College
More information1.3 Predicates and Quantifiers
1.3 Predicates and Quantifiers INTRODUCTION Statements x>3, x=y+3 and x + y=z are not propositions, if the variables are not specified. In this section we discuss the ways of producing propositions from
More informationPredicates, Quantifiers and Nested Quantifiers
Predicates, Quantifiers and Nested Quantifiers Predicates Recall the example of a nonproposition in our first presentation: 2x=1. Let us call this expression P(x). P(x) is not a proposition because x
More informationPredicate Logic & Quantification
Predicate Logic & Quantification Things you should do Homework 1 due today at 3pm Via gradescope. Directions posted on the website. Group homework 1 posted, due Tuesday. Groups of 13. We suggest 3. In
More informationChapter 1, Part II: Predicate Logic
Chapter 1, Part II: Predicate Logic With Question/Answer Animations Copyright McGrawHill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGrawHill
More information1.1 Language and Logic
c Oksana Shatalov, Fall 2017 1 1.1 Language and Logic Mathematical Statements DEFINITION 1. A proposition is any declarative sentence (i.e. it has both a subject and a verb) that is either true or false,
More informationPredicate Calculus  Syntax
Predicate Calculus  Syntax Lila Kari University of Waterloo Predicate Calculus  Syntax CS245, Logic and Computation 1 / 26 The language L pred of Predicate Calculus  Syntax L pred, the formal language
More informationTHE LOGIC OF QUANTIFIED STATEMENTS. Predicates and Quantified Statements I. Predicates and Quantified Statements I CHAPTER 3 SECTION 3.
CHAPTER 3 THE LOGIC OF QUANTIFIED STATEMENTS SECTION 3.1 Predicates and Quantified Statements I Copyright Cengage Learning. All rights reserved. Copyright Cengage Learning. All rights reserved. Predicates
More information1.1 Language and Logic
c Oksana Shatalov, Spring 2018 1 1.1 Language and Logic Mathematical Statements DEFINITION 1. A proposition is any declarative sentence (i.e. it has both a subject and a verb) that is either true or false,
More informationMAT 243 Test 1 SOLUTIONS, FORM A
t MAT 243 Test 1 SOLUTIONS, FORM A 1. [10 points] Rewrite the statement below in positive form (i.e., so that all negation symbols immediately precede a predicate). ( x IR)( y IR)((T (x, y) Q(x, y)) R(x,
More informationIntroduction to firstorder logic:
Introduction to firstorder logic: Firstorder structures and languages. Terms and formulae in firstorder logic. Interpretations, truth, validity, and satisfaction. Valentin Goranko DTU Informatics September
More informationDiscrete Mathematical Structures. Chapter 1 The Foundation: Logic
Discrete Mathematical Structures Chapter 1 he oundation: Logic 1 Lecture Overview 1.1 Propositional Logic 1.2 Propositional Equivalences 1.3 Quantifiers l l l l l Statement Logical Connectives Conjunction
More informationP A L A C E P IE R, S T. L E O N A R D S. R a n n o w, q u a r r y. W WALTER CR O TC H, Esq., Local Chairman. E. CO O PER EVANS, Esq.,.
? ( # [ ( 8? [ > 3 Q [ ««> » 9 Q { «33 Q> 8 \ \ 3 3 3> Q»«9 Q ««« 3 8 3 8 X \ [ 3 ( ( Z ( Z 3( 9 9 > < < > >? 8 98 ««3 ( 98 < # # Q 3 98? 98 > > 3 8 9 9 ««««> 3 «>
More informationCSC Discrete Math I, Spring Propositional Logic
CSC 125  Discrete Math I, Spring 2017 Propositional Logic Propositions A proposition is a declarative sentence that is either true or false Propositional Variables A propositional variable (p, q, r, s,...)
More informationLogic. Logic is a discipline that studies the principles and methods used in correct reasoning. It includes:
Logic Logic is a discipline that studies the principles and methods used in correct reasoning It includes: A formal language for expressing statements. An inference mechanism (a collection of rules) to
More informationsoftware design & management Gachon University Chulyun Kim
Gachon University Chulyun Kim 2 Outline Propositional Logic Propositional Equivalences Predicates and Quantifiers Nested Quantifiers Rules of Inference Introduction to Proofs 3 1.1 Propositional Logic
More informationTHE LOGIC OF QUANTIFIED STATEMENTS
CHAPTER 3 THE LOGIC OF QUANTIFIED STATEMENTS Copyright Cengage Learning. All rights reserved. SECTION 3.2 Predicates and Quantified Statements II Copyright Cengage Learning. All rights reserved. Negations
More informationPredicate Logic. Predicates. Math 173 February 9, 2010
Math 173 February 9, 2010 Predicate Logic We have now seen two ways to translate English sentences into mathematical symbols. We can capture the logical form of a sentence using propositional logic: variables
More informationCS Module 1. Ben Harsha Apr 12, 2017
CS 50010 Module 1 Ben Harsha Apr 12, 2017 Course details Course is split into 2 modules Module 1 (this one): Covers basic data structures and algorithms, along with math review. Module 2: Probability,
More informationEECS 1028 M: Discrete Mathematics for Engineers
EECS 1028 M: Discrete Mathematics for Engineers Suprakash Datta Office: LAS 3043 Course page: http://www.eecs.yorku.ca/course/1028 Also on Moodle S. Datta (York Univ.) EECS 1028 W 18 1 / 26 Why Study Logic?
More informationMath 10850, fall 2017, University of Notre Dame
Math 10850, fall 2017, University of Notre Dame Notes on first exam September 22, 2017 The key facts The first midterm will be on Thursday, September 28, 6.15pm7.45pm in HayesHealy 127. What you need
More informationDISCRETE MATHEMATICS BA202
TOPIC 1 BASIC LOGIC This topic deals with propositional logic, logical connectives and truth tables and validity. Predicate logic, universal and existential quantification are discussed 1.1 PROPOSITION
More informationSection 2.3: Statements Containing Multiple Quantifiers
Section 2.3: Statements Containing Multiple Quantifiers In this section, we consider statements such as there is a person in this company who is in charge of all the paperwork where more than one quantifier
More informationChapter 2: The Logic of Quantified Statements
Chapter 2: The Logic of Quantified Statements Topics include 2.1, 2.2 Predicates and Quantified Statements, 2.3 Statements with Multiple Quantifiers, and 2.4 Arguments with Quantified Statements. cs1231y
More informationComputer Science 280 Spring 2002 Homework 2 Solutions by Omar Nayeem
Computer Science 280 Spring 2002 Homework 2 Solutions by Omar Nayeem Part A 1. (a) Some dog does not have his day. (b) Some action has no equal and opposite reaction. (c) Some golfer will never be eated
More informationPredicates and Quantifiers. CS 231 Dianna Xu
Predicates and Quantifiers CS 231 Dianna Xu 1 Predicates Consider P(x) = x < 5 P(x) has no truth values (x is not given a value) P(1) is true 1< 5 is true P(10) is false 10 < 5 is false Thus, P(x) will
More informationLogic Overview, I. and T T T T F F F T F F F F
Logic Overview, I DEFINITIONS A statement (proposition) is a declarative sentence that can be assigned a truth value T or F, but not both. Statements are denoted by letters p, q, r, s,... The 5 basic logical
More informationTransparencies to accompany Rosen, Discrete Mathematics and Its Applications Section 1.3. Section 1.3 Predicates and Quantifiers
Section 1.3 Predicates and Quantifiers A generalization of propositions  propositional functions or predicates.: propositions which contain variables Predicates become propositions once every variable
More informationChapter 1 Elementary Logic
20172018 Chapter 1 Elementary Logic The study of logic is the study of the principles and methods used in distinguishing valid arguments from those that are not valid. The aim of this chapter is to help
More informationTHE LOGIC OF QUANTIFIED STATEMENTS. Statements with Multiple Quantifiers. Statements with Multiple Quantifiers CHAPTER 3 SECTION 3.
CHAPTER 3 THE LOGIC OF QUANTIFIED STATEMENTS SECTION 3.3 Statements with Multiple Quantifiers Copyright Cengage Learning. All rights reserved. Copyright Cengage Learning. All rights reserved. When a statement
More information1 The Foundation: Logic and Proofs
1 The Foundation: Logic and Proofs 1.1 Propositional Logic Propositions( 명제 ) a declarative sentence that is either true or false, but not both nor neither letters denoting propositions p, q, r, s, T:
More informationDiscrete Mathematics and Probability Theory Spring 2014 Anant Sahai Note 1
EECS 70 Discrete Mathematics and Probability Theory Spring 2014 Anant Sahai Note 1 Getting Started In order to be fluent in mathematical statements, you need to understand the basic framework of the language
More informationDiscrete Mathematics. Instructor: Sourav Chakraborty. Lecture 4: Propositional Logic and Predicate Lo
gic Instructor: Sourav Chakraborty Propositional logic and Predicate Logic Propositional logic and Predicate Logic Every statement (or proposition) is either TRUE or FALSE. Propositional logic and Predicate
More informationLogic. Definition [1] A logic is a formal language that comes with rules for deducing the truth of one proposition from the truth of another.
Math 0413 Appendix A.0 Logic Definition [1] A logic is a formal language that comes with rules for deducing the truth of one proposition from the truth of another. This type of logic is called propositional.
More informationSection 2.1: Introduction to the Logic of Quantified Statements
Section 2.1: Introduction to the Logic of Quantified Statements In the previous chapter, we studied a branch of logic called propositional logic or propositional calculus. Loosely speaking, propositional
More informationAnnouncements CompSci 102 Discrete Math for Computer Science
Announcements CompSci 102 Discrete Math for Computer Science Read for next time Chap. 1.41.6 Recitation 1 is tomorrow Homework will be posted by Friday January 19, 2012 Today more logic Prof. Rodger Most
More informationTwo Posts to Fill On School Board
Y Y 9 86 4 4 qz 86 x : ( ) z 7 854 Y x 4 z z x x 4 87 88 Y 5 x q x 8 Y 8 x x : 6 ; : 5 x ; 4 ( z ; ( ) ) x ; z 94 ; x 3 3 3 5 94 ; ; ; ; 3 x : 5 89 q ; ; x ; x ; ; x : ; ; ; ; ; ; 87 47% : () : / : 83
More informationP.3 Division of Polynomials
00 section P3 P.3 Division of Polynomials In this section we will discuss dividing polynomials. The result of division of polynomials is not always a polynomial. For example, xx + 1 divided by xx becomes
More information1 The Foundation: Logic and Proofs
1 The Foundation: Logic and Proofs 1.1 Propositional Logic Propositions( ) a declarative sentence that is either true or false, but not both nor neither letters denoting propostions p, q, r, s, T: true
More informationMathematical Reasoning. The Foundation of Algorithmics
Mathematical Reasoning The Foundation of Algorithmics The Nature of Truth In mathematics, we deal with statements that are True or False This is known as The Law of the Excluded Middle Despite the fact
More informationLesson 24: Using the Quadratic Formula,
, b ± b 4ac x = a Opening Exercise 1. Examine the two equation below and discuss what is the most efficient way to solve each one. A. 4xx + 5xx + 3 = xx 3xx B. cc 14 = 5cc. Solve each equation with the
More informationP.2 Multiplication of Polynomials
1 P.2 Multiplication of Polynomials aa + bb aa + bb As shown in the previous section, addition and subtraction of polynomials results in another polynomial. This means that the set of polynomials is closed
More informationDepartment of Computer Science & Software Engineering Comp232 Mathematics for Computer Science
Department of Computer Science & Software Engineering Comp232 Mathematics for Computer Science Fall 2018 Assignment 1. Solutions 1. For each of the following statements use a truth table to determine whether
More informationReasoning. Inference. Knowledge Representation 4/6/2018. User
Reasoning Robotics Firstorder logic Chapter 8Russel Representation and Reasoning In order to determine appropriate actions to take, an intelligent system needs to represent information about the world
More informationProving logical equivalencies (1.3)
EECS 203 Spring 2016 Lecture 2 Page 1 of 6 Proving logical equivalencies (1.3) One thing we d like to do is prove that two logical statements are the same, or prove that they aren t. Vocabulary time In
More informationITS336 Lecture 6 FirstOrder Logic
ITS6 Lecture 6 FirstOrder Logic 6.1 Syntax for FOL Basic Elements of FOL Constant Symbols A constant is an specific object such as a person name Tom, a particular apple etc. Variable Symbols A countably
More informationBefore you get started, make sure you ve read Chapter 1, which sets the tone for the work we will begin doing here.
Chapter 2 Mathematics and Logic Before you get started, make sure you ve read Chapter 1, which sets the tone for the work we will begin doing here. 2.1 A Taste of Number Theory In this section, we will
More informationRosen, Discrete Mathematics and Its Applications, 6th edition Extra Examples
Rosen, Discrete Mathematics and Its Applications, 6th edition Extra Examples Section 1.4 Nested Quantifiers Page references correspond to locations of Extra Examples icons in the textbook. #1. Write the
More informationPropositional Functions. Quantifiers. Assignment of values. Existential Quantification of P(x) Universal Quantification of P(x)
Propositional Functions Rosen (6 th Ed.) 1.3, 1.4 Propositional functions (or predicates) are propositions that contain variables. Ex: P(x) denote x > 3 P(x) has no truth value until the variable x is
More informationSection A (not in the text) Which of the following are statements? Explain. 3. The President of the United States in 2089 will be a woman.
Math 299 Homework Assignment, Chapter 2 Section 2.1 2.A (not in the text) Which of the following are statements? Explain. 1. Let x be a positive integer. Then x is rational. 2. Mathematics is fun. 3. The
More informationCSE 20. Final Review. CSE 20: Final Review
CSE 20 Final Review Final Review Representation of integers in base b Logic Proof systems: Direct Proof Proof by contradiction Contraposetive Sets Theory Functions Induction Final Review Representation
More informationSolutions to Exercises (Sections )
s to Exercises (Sections 1.11.10) Section 1.1 Exercise 1.1.1: Identifying propositions (a) Have a nice day. : Command, not a proposition. (b) The soup is cold. : Proposition. Negation: The soup is not
More informationConjunction: p q is true if both p, q are true, and false if at least one of p, q is false. The truth table for conjunction is as follows.
Chapter 1 Logic 1.1 Introduction and Definitions Definitions. A sentence (statement, proposition) is an utterance (that is, a string of characters) which is either true (T) or false (F). A predicate is
More informationAnnouncements. CS311H: Discrete Mathematics. Introduction to FirstOrder Logic. A Motivating Example. Why FirstOrder Logic?
Announcements CS311H: Discrete Mathematics Introduction to FirstOrder Logic Instructor: Işıl Dillig Homework due at the beginning of next lecture Please bring a hard copy of solutions to class! Instructor:
More informationCS 1571 Introduction to AI Lecture 14. Firstorder logic. CS 1571 Intro to AI. Midterm
CS 1571 Introduction to AI Lecture 14 Firstorder logic Milos Hauskrecht milos@cs.pitt.edu 5329 Sennott Square Midterm The midterm for the course will be held on October 28, 2014 In class exam Closed book
More informationPredicate logic. G. Carl Evans. Summer University of Illinois. Propositional Logic Review Predicate logic Predicate Logic Examples
G. Carl Evans University of Illinois Summer 2013 Propositional logic Propositional Logic Review AND, OR, T/F, implies, etc Equivalence and truth tables Manipulating propositions Implication Propositional
More informationIntroduction. Predicates and Quantifiers. Discrete Mathematics Andrei Bulatov
Introduction Predicates and Quantifiers Discrete Mathematics Andrei Bulatov Discrete Mathematics Predicates and Quantifiers 72 What Propositional Logic Cannot Do We saw that some declarative sentences
More informationLOWELL WEEKLY JOURNAL. ^Jberxy and (Jmott Oao M d Ccmsparftble. %m >ai ruv GEEAT INDUSTRIES
? (») /»» 9 F ( ) / ) /»F»»»»»# F??»»» Q ( ( »»» < 3»» /» > > } > Q ( Q > Z F 5
More informationA statement is a sentence that is definitely either true or false but not both.
5 Logic In this part of the course we consider logic. Logic is used in many places in computer science including digital circuit design, relational databases, automata theory and computability, and artificial
More informationLecture 3 : Predicates and Sets DRAFT
CS/Math 240: Introduction to Discrete Mathematics 1/25/2010 Lecture 3 : Predicates and Sets Instructor: Dieter van Melkebeek Scribe: Dalibor Zelený DRAFT Last time we discussed propositions, which are
More information