Understanding Predicate Logic and Quantifiers
Predicate logic extends propositional logic by allowing statements to be assigned specific values. The limitations of propositional logic are overcome through predicate logic, where statements like "?. is greater than 3" have subject and predicate parts denoted as ?(?). Furthermore, predicates can become propositions when values are assigned, or through quantification using universal and existential quantifiers.
Uploaded on Nov 28, 2024 | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The limitation of propositional logic ? > 3 Is not a proposition Because we can not tell whether it is true or false unless we know the value of ?.
Predicate Logic The statement ? is greater than 3 has two parts: Subject : ? is the subject of the statement Predicate : is greater than 3 We denote the statement ? is greater than 3 by ?(?), where ? is the predicate is greater than 3 and ? is the variable. The statement ?(?) is also called the value of propositional function ? at ?.
More on Predicate Logic A predicate becomes a proposition when specific values are assigned to the variables. ? ?1,?2,?3, ,?? is called a predicate of ? variables or ? arguments Examples: ??? ??(?) ???? ??(?,?) : binary predicate ???(?,?,?) ?(?,?,?,?) : unary predicate : ternary predicate : ?-ary predicate
Example of Predicate Logic Odd(?)= ? ?? ?? ??? ?????? Odd(2) is false Odd(3) is true Capital ?,? = "? ?? ? ? ??????? ?? ?" Capital ????????,??????? ???? is true Capital ????,???? ???? is false
Quantifier A predicate becomes a proposition when we assign it fixed values. However, another way to make a predicate into a proposition is to quantify it. Such quantification can be done with two quantifiers: the universal quantifier and the existential quantifier
Universal Quantifier ?(?) is true for all values of ? in the universe of discourse ??(?) which can be read : for all ? For every ? for any for arbitrary for each
Universal Quantifier Example Let ? ? : ? must take a discrete mathematics course ?(?): ? is a computer science student Express the statement: Every computer science student must take a discrete mathematics course . ?(?(?) ?(?)) Everybody must take a discrete mathematics course or be a computer science student ?(?(?) ?(?))
Universal Quantifier Example 2 Express the statement for every ? and for every ?, ? + ? > 10
Existential Quantifier The existential quantification of a predicate ?(?) is the proposition There exists an ? in the universe of discourse such that ?(?) is true. ??(?) which can be read there exists an ? for some for at least one
More on Existential Quantifier !??(?) which can be read there exists a unique there is one and only one
Quantifier - Example Let ?(?): ? is a non-negative integer ?(?): ? is even ?(?): ? is odd ?(?): ? is prime Translate into logical notation. ?? ? ?(? ? ? ? ) 1. There exists an even integer. 2. Every integer is even or odd. 3. All prime integers are non-negative. ?(? ? ? ? ) ?(? ? ? ? ) 4. Not all primes are odd.
Quantifier - Example 2 Let ?(?): ? is a lion ?(?): ? is fierce ?(?): ? drinks coffee Translate into logical notation. 1. all lions are fierce 2. some lions do not drink coffee 3. some fierce creatures do not drink coffee ?(? ? ? ? ) ?(? ? ? ? ) ?(? ? ? ? )
Negating Quantified Statements DeMorgan s laws for quantifiers: ?? ? ? ? ? ( ?,? ? ? ? ) ?(?(?) ? ? ) ( ?,? ? ? ? ) ?(?(?) ? ? )
Statement Equivalent Statement Negation of Statement All A are B There are no A that are not B Some A are not B Some A are not B Not all A are B All A are B Some A are B There exists at least one A that is a B All A are not B No A are B No A are B Some A are B
Quantifier - Example 3 All dogs are animals. Some kids do not like video games. Some video games are nonviolent. No math courses are difficult
Definition A sentence A entails another sentence B if, whenever A is true, B must also be true A|=B
Entailment in Propositional Logic: Examples A,A ? | = ? {?}| = ? ? {?,?} | = ? ? {?} | ? ? {A A} | A A B A B T F T T ? ? A A T F F F A B T T F F 1 2 3 4 T F T F T T T F T T T T
Another Example Which one of the following statement is entailment? 1. {? ?}| = ? 2. {? ?}| = ? 3. { ?,? ?}| = ? 4. {?}| = ? ? 5. {?}| = ? ?
