advertisement

Predicate Logic

67 %
33 %
advertisement
Information about Predicate Logic

Published on August 11, 2007

Author: giki67

Source: slideshare.net

Description

Predicate Logic is the Bases of all the Logic used in Formal Methods in Software Engineering
advertisement

Logic & Formal Methods Predicate Logic Instructor: Dr H. Farooq Ahmad Sarmad Sadik TA: Muhammad Afzal, Maqbool Reference: Discrete Mathematics with Examples by Simpson

Topics Universal quantification Existential quantification Satisfaction and validity The negation of quantifiers Free and bound variables Substitution Restriction Uniqueness Equational reasoning Natural deduction One point rule Page

Universal quantification

Existential quantification

Satisfaction and validity

The negation of quantifiers

Free and bound variables

Substitution

Restriction

Uniqueness

Equational reasoning

Natural deduction

One point rule

Pros and cons of propositional logic Propositional logic is declarative Propositional logic allows conjunction, disjunction, negated information Propositional logic is compositional : meaning of B 1,1  P 1,2 is derived from meaning of B 1,1 and of P 1,2 Meaning in propositional logic is context-independent (unlike natural language, where meaning depends on context) Propositional logic has very limited expressive power (unlike natural language)

Propositional logic is declarative

Propositional logic allows conjunction, disjunction, negated information

Propositional logic is compositional :

meaning of B 1,1  P 1,2 is derived from meaning of B 1,1 and of P 1,2

Meaning in propositional logic is context-independent (unlike natural language, where meaning depends on context)

Propositional logic has very limited expressive power (unlike natural language)

First-order logic Whereas propositional logic assumes the world contains facts , first-order logic (like natural language) assumes the world contains Objects: people, houses, numbers, colors, baseball games, wars, … Relations & functions: red, round, prime, brother of, bigger than, part of, comes between, father of, best friend, one more than, plus, …

Whereas propositional logic assumes the world contains facts ,

first-order logic (like natural language) assumes the world contains

Objects: people, houses, numbers, colors, baseball games, wars, …

Relations & functions: red, round, prime, brother of, bigger than, part of, comes between, father of, best friend, one more than, plus, …

Syntax of FOL: Basic elements Constants KingJohn, 2, NUS,... Functions Sqrt, LeftLegOf,... Variables x, y, a, b,... Connectives  ,  ,  ,  ,  Equality = Quantifiers  , 

Constants KingJohn, 2, NUS,...

Functions Sqrt, LeftLegOf,...

Variables x, y, a, b,...

Connectives  ,  ,  ,  , 

Equality =

Quantifiers  , 

Predicates A predicate is a proposition whose truth depends on the value of one or more variables. For example, “n is a perfect square” is a predicate whose truth depends on the value of n. A function like notation is used to denote a predicate supplied with specific variable values. P(n)=“n is a perfect square” P(4) is true and P(5) is false. Page

A predicate is a proposition whose truth depends on the value of one or more variables.

For example, “n is a perfect square” is a predicate whose truth depends on the value of n.

A function like notation is used to denote a predicate supplied with specific variable values. P(n)=“n is a perfect square”

P(4) is true and P(5) is false.

Universal Quantification Universal Quantification denoted as Universal Quantification allows us to capture statements of the form “for all” or “for every”. For example, “every natural number is greater than or equal to zero” can be written formally as Page

Universal Quantification denoted as

Universal Quantification allows us to capture statements of the form “for all” or “for every”.

For example, “every natural number is greater than or equal to zero” can be written formally as

Universal Quantification A quantified statement consists of three parts: the quantifier, the quantification, which describes the variables and the type of variable with which the statement is concerned and the predicate which is normally some statement about the quantified variables. Every predicate logic statement can be considered as follows Page

A quantified statement consists of three parts: the quantifier, the quantification, which describes the variables and the type of variable with which the statement is concerned and the predicate which is normally some statement about the quantified variables.

Every predicate logic statement can be considered as follows

Universal Quantification Page

Exercise Everybody likes Jaffa cakes All vegetarians don’t like Jaffa cakes Everybody either likes Jaffa cakes or is a vegetarian Either every body likes Jaffa cakes or everybody is a vegetarian Page

Everybody likes Jaffa cakes

All vegetarians don’t like Jaffa cakes

Everybody either likes Jaffa cakes or is a vegetarian

Either every body likes Jaffa cakes or everybody is a vegetarian

Solution Page

Universal Quantification Law 1 Example Page

Law 1

Example

Universal Quantification Law 2 Example Page

Law 2

Example

Existential quantification Existential quantifier denoted by As universal quantification is used to assert that a certain property holds of every element of a set, existential quantification is used to assert that such a property holds of some (or at least) elements of a set “ Some natural numbers are divisible by 3” may be written as Page

Existential quantifier denoted by

As universal quantification is used to assert that a certain property holds of every element of a set, existential quantification is used to assert that such a property holds of some (or at least) elements of a set

“ Some natural numbers are divisible by 3” may be written as

Exercise Some people like Jaffa cakes Some vegetarians don’t like Jaffa cakes Some people either like Jaffa cakes or are vegetarian Either some people like Jaffa cakes or some people are vegetarian Page

Some people like Jaffa cakes

Some vegetarians don’t like Jaffa cakes

Some people either like Jaffa cakes or are vegetarian

Either some people like Jaffa cakes or some people are vegetarian

Solution Page

Existential quantification Law 3 Example Page

Law 3

Example

Existential quantification Law 4 Example Page

Law 4

Example

Satisfaction and validity The predicate n>3 can be considered neither true nor false unless we know the value associated with n A predicate p is valid if and only if it is true for all possible values of the appropriate type. That is, if a predicate p is associated with a variable x of type X, then p is valid if, and only if, Example Page

The predicate n>3 can be considered neither true nor false unless we know the value associated with n

A predicate p is valid if and only if it is true for all possible values of the appropriate type. That is, if a predicate p is associated with a variable x of type X, then p is valid if, and only if,

Example

Satisfaction and validity A predicate p is satisfiable if and only if it is true for some values of the appropriate type. That is, if a predicate p is associated with a variable x of type X, then p is satisfiable if, and only if , Example Page

A predicate p is satisfiable if and only if it is true for some values of the appropriate type. That is, if a predicate p is associated with a variable x of type X, then p is satisfiable if, and only if ,

Example

Satisfaction and validity A predicate p is unsatisfiable if, and only if, it is false for all possible values of the appropriate type. If a predicate p is associated with a variable x of type X, then p is unsatisfiable if, and only if, Page

A predicate p is unsatisfiable if, and only if, it is false for all possible values of the appropriate type.

If a predicate p is associated with a variable x of type X, then p is unsatisfiable if, and only if,

Satisfaction and validity The analogies between valid, satisfiable and unsatisfiable predicates, and tautologies, contingencies and contradictions: valid predicates and tautologies are always true satisfiable predicates and contingencies are sometimes true and sometimes false unsatisfiable predicates and contradictions are never true Page

The analogies between valid, satisfiable and unsatisfiable predicates, and tautologies, contingencies and contradictions:

valid predicates and tautologies are always true

satisfiable predicates and contingencies are sometimes true and sometimes false

unsatisfiable predicates and contradictions are never true

The negation of quantifiers The statement “some body like Brian” may be expressed via predicate logic as To negate this expression, we may write as, which in natural language may be expressed as “nobody likes Brian” Page

The statement “some body like Brian” may be expressed via predicate logic as

To negate this expression, we may write as,

which in natural language may be expressed as “nobody likes Brian”

The negation of quantifiers Logically saying “nobody likes Brian” is equivalent to saying “everybody does not like Brian”. The negation of quantifiers behaves exactly in this fashion, just as in natural language, “nobody likes Brian” and “everybody does not like Brian” are equivalent so in predicate logic And are equivalent. Page

Logically saying “nobody likes Brian” is equivalent to saying “everybody does not like Brian”.

The negation of quantifiers behaves exactly in this fashion, just as in natural language, “nobody likes Brian” and “everybody does not like Brian” are equivalent so in predicate logic

And

are equivalent.

The negation of quantifiers Law 5 When negation is applied to a quantified expression it flips quantifiers as it moves inwards(i.e negation turns all universal quantifiers to existential quantifiers and vice versa, and negates all predicates) Page

Law 5

When negation is applied to a quantified expression it flips quantifiers as it moves inwards(i.e negation turns all universal quantifiers to existential quantifiers and vice versa, and negates all predicates)

The negation of quantifiers Consider the statement, The effect of negation of this expression can be determined as, Page

Consider the statement,

The effect of negation of this expression can be determined as,

Exercise Everyone likes everyone Everyone likes someone Someone likes everyone Someone likes someone Page

Everyone likes everyone

Everyone likes someone

Someone likes everyone

Someone likes someone

Free and bound variables Consider two predicates n>5…..Eq. 1 In equation 2, the variable n is bound, it is existentially quantified variable. In equation 1, n is free as its value may not be determined or restricted Page

Consider two predicates

n>5…..Eq. 1

In equation 2, the variable n is bound, it is existentially quantified variable.

In equation 1, n is free as its value may not be determined or restricted

Free and bound variables Example In this statement, y and x are two variables. y is universally quantified and it is bound, while x is free variable. In statement, The occurrence of x in the declaration is binding, any occurrences of x in p are bound, and any occurrences of any variables other than x are free Page

Example

In this statement, y and x are two variables. y is universally quantified and it is bound, while x is free variable.

In statement,

The occurrence of x in the declaration is binding, any occurrences of x in p are bound, and any occurrences of any variables other than x are free

Free and bound variables Example Exercise, Determine the scope of the universal and existential quantifiers of the following predicate, The distinction between predicates and propositions can be stated as predicates are logical statements which can contain free variables while propositions are logical statements which contain no such holes Page

Example

Exercise, Determine the scope of the universal and existential quantifiers of the following predicate,

The distinction between predicates and propositions can be stated as predicates are logical statements which can contain free variables while propositions are logical statements which contain no such holes

Substitution Consider statement, we may replace the name n with any term t, provided that t is of the same type as n. This process is called substitution: the expression p[t/n] denotes the fact that the term t is being substituted for the variable name n in the predicate p. Example, we may denote the substitution of 3 for n in the predicate n>5 by Page

Consider statement,

we may replace the name n with any term t, provided that t is of the same type as n. This process is called substitution: the expression p[t/n] denotes the fact that the term t is being substituted for the variable name n in the predicate p.

Example, we may denote the substitution of 3 for n in the predicate n>5 by

Substitution Also, we may denote the substitution of 3+4 for n in n>5 by n>5[3+4/n] Substitution is only for free variables Page

Also, we may denote the substitution of 3+4 for n in n>5 by

n>5[3+4/n]

Substitution is only for free variables

Substitution More than one substitution in case of more than one free variable Consider predicate, Here x and y are both free variables. We may substitute nigel for x as follows, Now substituting ken for y, Page

More than one substitution in case of more than one free variable

Consider predicate,

Here x and y are both free variables. We may substitute nigel for x as follows,

Now substituting ken for y,

Substitution Similarly, in one step, overall substitution may be denoted as, These two substitutions take place sequentially, first nigel is substituted for x, then ken is substituted for y. However, for simultaneous substitutions, Page

Similarly, in one step, overall substitution may be denoted as,

These two substitutions take place sequentially, first nigel is substituted for x, then ken is substituted for y. However, for simultaneous substitutions,

Substitution To illustrate the difference between sequential and simultaneous substitution, consider the example, In former there is only one occurrence of y and in latter there are two occurrences of y Page

To illustrate the difference between sequential and simultaneous substitution, consider the example,

In former there is only one occurrence of y and in latter there are two occurrences of y

Restriction Filters role in predicate logic Considering an example, all natural numbers which are prime numbers and are greater than 2 are odd, may be written as, Using a filter, statement may be written as, Form of restricted predicates as, Page

Filters role in predicate logic

Considering an example, all natural numbers which are prime numbers and are greater than 2 are odd, may be written as,

Using a filter, statement may be written as,

Form of restricted predicates as,

Restriction Restriction can also be used in existential quantification, “there has been a female British Prime Minister”, may be written as Page

Restriction can also be used in existential quantification, “there has been a female British Prime Minister”, may be written as

Restriction Law 6 Law 7 Page

Law 6

Law 7

Exercise Represent the following statement in the form, Everyone who likes cheese likes spam There is a person who likes cheese that likes spam Everyone who likes cheese also likes spam and likes bananas Page

Represent the following statement in the form,

Everyone who likes cheese likes spam

There is a person who likes cheese that likes spam

Everyone who likes cheese also likes spam and likes bananas

Solution Page

Uniqueness Existential quantifier, allows us to represent statements such as “there is at least one x, such that…”. In order to be more specific, consider, “there is exactly one x, such that…” Consider an example statement, it is the case that the predicate x+1=1 is true for exactly one natural number:0 Page

Existential quantifier, allows us to represent statements such as “there is at least one x, such that…”.

In order to be more specific, consider, “there is exactly one x, such that…”

Consider an example statement,

it is the case that the predicate x+1=1 is true for exactly one natural number:0

The operator which allow us to state that “ there is exactly one natural number, x, is denoted as As an example, Uniqueness Page

The operator which allow us to state that “ there is exactly one natural number, x, is denoted as

As an example,

Uniqueness Assuming the statement It is sometimes useful to pinpoint exactly which element of X for which predicate p holds. Also, it is convenient to perform some operation on this value. The µ operator allows us to do exactly this, the statement ( µ x:X | p) is read as “ the unique x from set X such that p holds of x ” Example, ( µ x:N | x+1=1) where µ is associated with value 0 Page

Assuming the statement

It is sometimes useful to pinpoint exactly which element of X for which predicate p holds. Also, it is convenient to perform some operation on this value.

The µ operator allows us to do exactly this, the statement ( µ x:X | p) is read as “ the unique x from set X such that p holds of x ”

Example, ( µ x:N | x+1=1) where µ is associated with value 0

Uniqueness When a unique element of the relevant type does possess the relevant property, then we are free to construct statements as given previously On the other hand, µ expressions that are not associated with a unique element generate an undefined value. As an example, the µ expressions ( µ n:N | n is even) and ( µ c:Country | population (c) > 10,000,000) are both undefined Page

When a unique element of the relevant type does possess the relevant property, then we are free to construct statements as given previously

On the other hand, µ expressions that are not associated with a unique element generate an undefined value.

As an example, the µ expressions

( µ n:N | n is even)

and

( µ c:Country | population (c) > 10,000,000)

are both undefined

Uniqueness We can incorporate terms into set comprehensions, so we can apply terms in µ expressions. Expressions of the form, return the result of applying the term t to the unique element of the set X which satisfies the predicate p gives the value Washington Page

We can incorporate terms into set comprehensions, so we can apply terms in µ expressions. Expressions of the form,

return the result of applying the term t to the unique element of the set X which satisfies the predicate p

gives the value Washington

Uniqueness If there is no unique element which possesses the relevant property, then the result is undefined and are both undefined. Page

If there is no unique element which possesses the relevant property, then the result is undefined

and

are both undefined.

Exercise Write the following in terms of µ expressions The tallest mountain in the world The height of the tallest mountain The oldest person in the world The nationality of the oldest person in the world The smallest natural number Page

Write the following in terms of µ expressions

The tallest mountain in the world

The height of the tallest mountain

The oldest person in the world

The nationality of the oldest person in the world

The smallest natural number

Solution Page

Equational Reasoning Two methods of reasoning Equational reasoning Natural deduction Also, Page

Two methods of reasoning

Equational reasoning

Natural deduction

Also,

Equational Reasoning Law 8 If a predicate holds for all elements of a set, then it holds for some of them Law 9 If a predicate holds for exactly one element of a set, then it holds for at least one of them Page

Law 8

If a predicate holds for all elements of a set, then it holds for some of them

Law 9

If a predicate holds for exactly one element of a set, then it holds for at least one of them

Equational Reasoning Law 10 If p holds for all elements of X and t is a term of type X, then p holds for t Example, The predicate holds for all natural numbers. The term 3+4 is of type N and as such, holds. Page

Law 10

If p holds for all elements of X and t is a term of type X, then p holds for t

Example,

The predicate

holds for all natural numbers. The term 3+4 is of type N and as such,

holds.

Equational Reasoning Law 11 This law states that if t is a term of type X and p holds of t, then we can conclude that p holds for some elements of X Example The proposition 7 ε N is true and furthermore 7 is prime. As such, Page

Law 11

This law states that if t is a term of type X and p holds of t, then we can conclude that p holds for some elements of X

Example

The proposition 7 ε N is true and furthermore 7 is prime. As such,

Equational Reasoning The quantification of any variables with regards to propositions which are always true or always has absolutely no effect. This notion is captured by following laws, Law 12 Law 13 Law 14 Law 15 Page

The quantification of any variables with regards to propositions which are always true or always has absolutely no effect. This notion is captured by following laws,

Law 12

Law 13

Law 14

Law 15

Equational Reasoning The predicate is concerned with three variables: x, y and z. x is bound and y and z are free. As x does not appear in the predicate y=z, we are free to assume that the existential quantification of x has no effect on the truth or falsity of that predicate. We conclude that following equivalence holds. Page

The predicate is concerned with three variables: x, y and z.

x is bound and y and z are free. As x does not appear in the predicate y=z, we are free to assume that the existential quantification of x has no effect on the truth or falsity of that predicate.

We conclude that following equivalence holds.

Equational Reasoning Law 16 It states that as x does not appear free in q, the following holds Example, Page

Law 16

It states that as x does not appear free in q, the following holds

Example,

Equational Reasoning Law 17 It states that as x does not appear free in q, the following holds, Example Page

Law 17

It states that as x does not appear free in q, the following holds,

Example

Equational Reasoning Law 18 It states as x does not appear free in q, the following holds Example Page

Law 18

It states as x does not appear free in q, the following holds

Example

Equational Reasoning Law 19 It states as x does not appear free in q, the following holds Example Page

Law 19

It states as x does not appear free in q, the following holds

Example

Equational Reasoning Example: A theorem in predicate logic Proof: Page

Example: A theorem in predicate logic

Proof:

Equational Reasoning Example Theorem Page

Example Theorem

Exercise Page

Solution Page

Natural deduction Natural deduction can also be extended to predicate logic Natural deduction rules for universal quantification Rule1 states that if p holds for all values of X, then provided that t is of type X- p holds for t Page

Natural deduction can also be extended to predicate logic

Natural deduction rules for universal quantification

Rule1 states that if p holds for all values of X, then provided that t is of type X- p holds for t

Natural deduction Example: All natural numbers which are prime and greater than 2 are odd. 7 is prime and greater than 2 and we may conclude that it is odd. Page

Example:

All natural numbers which are prime and greater than 2 are odd. 7 is prime and greater than 2 and we may conclude that it is odd.

Natural deduction Rules for existential quantification If x ε X such that p holds for x, then if we are able to define further predicate, q in which x does not appear free, then we may conclude q Page

Rules for existential quantification

If x ε X such that p holds for x, then if we are able to define further predicate, q in which x does not appear free, then we may conclude q

Natural deduction Intro rule If p is true for any term t of set X, then we conclude that, holds Page

Intro rule

If p is true for any term t of set X, then we conclude that, holds

Natural deduction Example Page

Example

The one-point rule It states that p is a person that likes Emily, but also that the name of person is Rick We can conclude that rick ε Person and rick likes emily are both true Law 20 Page

It states that p is a person that likes Emily, but also that the name of person is Rick

We can conclude that rick ε Person and rick likes emily are both true

Law 20

The one-point rule Example Page

Example

References Discrete Mathematics with Examples by Simpson Page

Discrete Mathematics with Examples by Simpson

Thank you! Page

Add a comment

Related pages

Predicate logic - Wikipedia, the free encyclopedia

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic, or ...
Read more

Predicate Logic, Inc.

PREDICATE LOGIC, ® INC., is an ISO 9001 certified, Woman-Owned and employee owned small business, high technology communications and engineering services ...
Read more

First-order logic - Wikipedia, the free encyclopedia

Introduction. While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification.
Read more

Introduction to Predicate Logic - Department Of Computer ...

Introduction to Predicate Logic. The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and ...
Read more

Predicate Logic - The Stanford University InfoLab

734 PREDICATE LOGIC “Interpretations” for expressions of predicate logic are possible meanings for the predicates and variables (Section 14.5).
Read more

Predicate Logic - University of Texas at Austin

Predicate Logic Example: All men are mortal. Socrates is a man. ···Socrates is mortal. Note: We need logic laws that work for statements involving quan-
Read more

dict.cc | predicate logic | Wörterbuch Englisch-Deutsch

Übersetzung für predicate logic im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Peter Suber, "Predicate Logic Terms and Symbols"

Predicate Logic Terms and Symbols Peter Suber, Philosophy Department, Earlham College. In logic, as in grammar, a subject is what we make an assertion ...
Read more

predicate logic - Englisch ⇔ Deutsch Wörterbuch - leo.org

Das Sprachangebot für Englisch-Deutsch: Wörterbuch mit Übersetzungen, Flexionstabellen und Audio, interaktivem Forum und Trainer für flexibles Lernen.
Read more

Predicate Logic - Careers

As a small, dynamic, employee owned company, Predicate Logic offers unlimited opportunities for professional growth, involvement and leadership.
Read more