Introduction to Predicate Logic in Mathematics
undefined
ROLL NO –183115-21-0150
REGISTRATION NO –115-1111-0995-18
SMMESTER – 4 (YEAR -2020)
SECTION – B , COLLEGE ROLL NO -170
PREDICATE
LOGIC
DEPARTMENT OF MATHEMATICS
SURENDRANATH COLLEGE
(University of Calcutta)
NAME – PALASH GHATA
NAME – PALASH GHATA
I
I
N
N
T
T
R
R
O
O
D
D
U
U
C
C
T
T
I
I
O
O
N
N
:
:
“Logic will get you from A to B, Imagination will take you
everywhere “ - Einstein
This logic is devoted to a different kind of logic, called predicate logic.
The propositional logic is not so powerful enough to represent all
types of assertions that are used in computer science, or to express
certain types of relationships, such as equivalence, between
propositions.For example, the assertion “x>3”,where x is a variable ,is
not a proposition because we do not know whether is true or not
unless we know the value of x .Thus, the propositional logic can not
handle such sentences. The propositional logic also can not identify
the pattern involved in the following logical equivalences :
“ Not all integers are even “ is equivalent to “ Some integers are not
even “.
“Some birds don’t fly.” is equivalent to “Not all birds fly “.
Thus, we need stronger logic to deal with these and other problems .
One of such logic is predicate logic.
A predicate
is a statement that contains variables (predicate
variables),and they may be true or false depending on the value of
these variables.
Examples
:
p(x) = “x
²
is greater than x” is a predicate. It contains one
predicate variable x . If we choose x = 1 , p(1) is “1 is greater than 1”
,which is a proposition ( always false).
D
D
E
E
F
F
I
I
N
N
I
I
T
T
I
I
O
O
N
N
:
:
P
R
E
D
I
C
A
T
E
I
N
S
T
A
N
T
I
A
T
E
D
/
D
O
M
A
I
N
:
Definition
:
The domain
of predicate variable is the collection of all
possible values that the variable may take .
Examples
:
Consider the predicate p(x,y) = “x>y” ,in two predicate
variables.We have
Z
(the set of integers) as domain for both of them .
●
Take x= 4,y= 3 then p(4,3)=“4>3”,which is a proposition taking the
value true.
●
Take x=1,y=2 then p(1,2)=“1>2”,which is a proposition taking the
value false.
●
Note that in general p(x,y) not equal to p(y,x)!
Q
Q
U
U
A
A
N
N
T
T
I
I
F
F
I
I
C
C
A
A
T
T
I
I
O
O
N
N
:
:
In predicate logic, predicates are used alongside quantifiers to express the
extent to which a predicate is true over a range of elements. Using
quantifiers to create such proposition is called quantification.
●Statements like
- Some
birds are angry.
- On the internet,
no one
who you are.
-
The square of
any
real number is nonnegative .
We now introduce two quantifiers
i)The
universal quantifiers ,
ii)The
existential quantifiers .
U
N
I
V
E
R
S
A
L
&
E
X
I
S
T
E
N
T
I
A
L
Q
U
A
N
T
I
F
I
C
A
T
I
O
N
:
Universal quantification
:
A
universal quantification
is a quantifier
(something that tells the amount or quantity) meaning “given any” or
“ for all”.
(
v
universal quantification)
Example
:
Here is a formal way to say that for all values that a predicate
variable X can take in a domain D ,the predicate is true
V
x
€ D
p(x) ( is true)
For example
,
for all x belonging to D.
V
x
€
R
, x
²
>
0
for all x belonging to
the real
numbers.
Existential quantification
:
An
existential quantification
is a quantifire
(something that tells the amount or quantity) meaning “there exists”,
“there is at least one” or “ for some”. (
]
existential quantification) .
Example
:
Here is a form way to say that for some values that a
predicate variable X can take in a domain D, the predicate is true.
]
x
€ D
,p(x)(is true)
for some x belonging to D .
For example, for D={birds}, p(x) = “x is angry”,]
x
€ D
p(x) ( is true).
some birds are angry
NESTED QUANTIFICATION
NESTED QUANTIFICATION
:
:
Definition
:
Two quantifiers are
nested
if one is within the scope of the other .
V
x
]
y ( x+y=0)
→p(x,y)
↓
Q(x)
V
x Q (x) , Q (x) is
]
y p( x,y)
p(x,y) is (x+y = 0) .
Examples
:
Translate the following statement into english.
V
x
V
y ((x>0)
^
(y<0)→( x y < 0)).
Domain : real numbers
Solution : For every real numbers x and y. If x is positive and y is negative then xy is
negative.
The product of a positive real number and a negative real number is always a
negative real number.
N
E
G
A
T
I
O
N
O
F
Q
U
A
N
T
I
F
I
C
A
T
I
O
N
:
“All students of B.sc Mathematics have taken the course of Mathematical
Logic”.
Let, x€D U ● D : D = {All students of B.sc Mathematics}and the predicate beP: have taken the course of Mathematical Logic.
This can be written as (
v
x € D) (p(x)) .
The negation of the above statement is (
]
x) (
7
p(x))
On there exists a student of B.sc Mathematics who has not taken the course
of Mathematical Logic.
Let us consider another statement,
“ There is a student of B.sc Mathematics who has taken the course of
Mathematical Logic”.
OR (
]
x) (p(x)).
The negation is (
v
x) (
7
p(x)).
I.e All students of B.sc Mathematics have not taken the course of
Mathematical Logic.
C
C
O
O
N
N
D
D
I
I
T
T
I
I
O
O
N
N
A
A
L
L
Q
Q
U
U
A
A
N
N
T
T
I
I
F
F
I
I
C
C
A
A
T
T
I
I
O
O
N
N
:
In logic,
a conditional quantification
is a kind of
Lindstrom qunantifier
(or
generalized quantifire) QA that, relative to a classical model A, satisfies
some or all of the following Conditions.
● For all real number x, if x>1 then x
²
>1.
-I.e,any real number greater than 1 has a square larger than 1.
-
In symbolic form
-
Let p(x) denote “ x>1”, - Let Q(x) denote “x
²
>1”
-
Let
R
denote the domain,the collection of all real numbers.
●
V
x (p(x)→Q(x)).
●
Given a conditional quantification – such as
V
x € A (p(x)→Q(x)).
●Then we define -contrapositive
V
x € A ,
7
Q(x) →
7
p(x).
- converse
V
x € A, Q (x)→ p(x).
- inverse
V
x € A, p(x)→
7
Q(x).
Note: A conditional proposition is logically equivalent to its contrapositive.
FIRST-ORDER LOGIC
FIRST-ORDER LOGIC
:
First order logical is symbolized reasoning in which each sentence,or
statement,is broken down into a subject and a predicate
.
●A first order language
£
contains the following symbols.
1.
The propositional connectives 7 and => , and the universal
quantifier symbol
v
2. Punctuation marks : “( “ ,” )” , “ ,”
3. Countably many individual variables : X1 , X2 , …. …. ..
4. A finite or enumerable, possibly empty, set of function letters.
5. A finite or enumerable, possibly empty, set of indivisual constants.
6. A nonempty set of predicate letters.
APPLICATIONS
APPLICATIONS
:
:
The predicate logic is a part of artificial intelligence which is
applicable in the field of robotics, medicine and it is used in
intelligence database in order to solve some complex problems.
Predicate logic is used for providing system safety,it is used in ssh to
provide security to the system.Predicate logic is used for representing
knowledge by the comparative study of knowledge representation
schemes and application in the filed of medicine based on predicate
logic theory.
A
A
C
C
K
K
N
N
O
O
W
W
L
L
E
E
D
D
G
G
E
E
M
M
E
E
N
N
T
T
:
:
I would like to give special thanks of gratitude to my teacher Mrs.
Soma Chatterjee for her guidance in making this presentation to the
point and presentable.
Also I would to like to give my thanks of gratitude to our HOD Mr.
Nitai Roy for making me a part of this beautiful project,which also
helped me doing research a lot and I came to know so many new
things.
Predicate logic is a powerful tool used in mathematics to express complex relationships and assertions that cannot be adequately represented by propositional logic. It allows for the quantification of statements over a range of elements using predicates and quantifiers like universal and existential. By defining predicates, domains, and quantification, predicate logic enhances our ability to reason and derive conclusions in a structured manner.
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
DEPARTMENT OF MATHEMATICS SURENDRANATH COLLEGE (University of Calcutta) NAME PALASH GHATA PREDICATE LOGIC ROLL NO 183115-21-0150 REGISTRATION NO 115-1111-0995-18 SMMESTER 4 (YEAR -2020) SECTION B , COLLEGE ROLL NO -170
INTRODUCTION INTRODUCTION : : Logic will get you from A to B, Imagination will take you everywhere - Einstein This logic is devoted to a different kind of logic, called predicate logic. The propositional logic is not so powerful enough to represent all types of assertions that are used in computer science, or to express certain types of relationships, such as equivalence, between propositions.For example, the assertion x>3 ,where x is a variable ,is not a proposition because we do not know whether is true or not unless we know the value of x .Thus, the propositional logic can not handle such sentences. The propositional logic also can not identify the pattern involved in the following logical equivalences : Not all integers are even is equivalent to Some integers are not even . Some birds don t fly. is equivalent to Not all birds fly . Thus, we need stronger logic to deal with these and other problems . One of such logic is predicate logic.
DEFINITION DEFINITION : : A predicateis a statement that contains variables (predicate variables),and they may be true or false depending on the value of these variables. Examples : p(x) = x is greater than x is a predicate. It contains one predicate variable x . If we choose x = 1 , p(1) is 1 is greater than 1 ,which is a proposition ( always false).
PREDICATE INSTANTIATED / DOMAIN : PREDICATE INSTANTIATED / DOMAIN : Definition:The domainof predicate variable is the collection of all possible values that the variable may take . Examples: Consider the predicate p(x,y) = x>y ,in two predicate variables.We have Z (the set of integers) as domain for both of them . Take x= 4,y= 3 then p(4,3)= 4>3 ,which is a proposition taking the value true. Take x=1,y=2 then p(1,2)= 1>2 ,which is a proposition taking the value false. Note that in general p(x,y) not equal to p(y,x)!
QUANTIFICATION QUANTIFICATION : : In predicate logic, predicates are used alongside quantifiers to express the extent to which a predicate is true over a range of elements. Using quantifiers to create such proposition is called quantification. Statements like - Some birds are angry. - On the internet, no one who you are. -The square of any real number is nonnegative . We now introduce two quantifiers i)The universal quantifiers , ii)The existential quantifiers .
UNIVERSAL & EXISTENTIAL QUANTIFICATION: UNIVERSAL & EXISTENTIAL QUANTIFICATION: Universal quantification : A universal quantificationis a quantifier (something that tells the amount or quantity) meaning given any or for all . ( v universal quantification) Example : Here is a formal way to say that for all values that a predicate variable X can take in a domain D ,the predicate is true Vx D p(x) ( is true) For example, for all x belonging to D. V x R for all x belonging to the real numbers. , x > 0
Existential quantification : An existential quantificationis a quantifire (something that tells the amount or quantity) meaning there exists , there is at least one or for some . ( ] existential quantification) . Example : Here is a form way to say that for some values that a predicate variable X can take in a domain D, the predicate is true. ] x D ,p(x)(is true) for some x belonging to D . For example, for D={birds}, p(x) = x is angry , ] x D p(x) ( is true). some birds are angry
NESTED QUANTIFICATION : Definition: Two quantifiers arenestedif one is within the scope of the other . V x ] y ( x+y=0) p(x,y) Q(x) Vx Q (x) , Q (x) is ] y p( x,y) p(x,y) is (x+y = 0) . Examples : Translate the following statement into english. V x V y ((x>0) ^(y<0) ( x y < 0)). Domain : real numbers Solution : For every real numbers x and y. If x is positive and y is negative then xy is negative. The product of a positive real number and a negative real number is always a negative real number.
NEGATION OF QUANTIFICATION NEGATION OF QUANTIFICATION : : All students of B.sc Mathematics have taken the course of Mathematical Logic . Let, x D U D : D = {All students of B.sc Mathematics}and the predicate be P: have taken the course of Mathematical Logic. This can be written as ( v x D) (p(x)) . The negation of the above statement is ( ] x) ( 7p(x)) On there exists a student of B.sc Mathematics who has not taken the course of Mathematical Logic. Let us consider another statement, There is a student of B.sc Mathematics who has taken the course of Mathematical Logic . OR ( ] x) (p(x)). The negation is (v x) (7 p(x)). I.e All students of B.sc Mathematics have not taken the course of Mathematical Logic.
CONDITIONAL QUANTIFICATION : : In logic,a conditional quantificationis a kind of Lindstrom qunantifier(or generalized quantifire) QA that, relative to a classical model A, satisfies some or all of the following Conditions. For all real number x, if x>1 then x >1. -I.e,any real number greater than 1 has a square larger than 1. - In symbolic form - Let p(x) denote x>1 , - Let Q(x) denote x >1 - Let R denote the domain,the collection of all real numbers. V x (p(x) Q(x)). Given a conditional quantification such as V x A (p(x) Q(x)). Then we define -contrapositive V x A , 7 Q(x) 7 p(x). - converse V x A, Q (x) p(x). - inverse V x A, p(x) 7 Q(x). Note: A conditional proposition is logically equivalent to its contrapositive.
FIRST-ORDER LOGIC : First order logical is symbolized reasoning in which each sentence,or statement,is broken down into a subject and a predicate . A first order language contains the following symbols. 1. The propositional connectives 7 and => , and the universal quantifier symbol v 2. Punctuation marks : ( , ) , , 3. Countably many individual variables : X1 , X2 , . . .. 4. A finite or enumerable, possibly empty, set of function letters. 5. A finite or enumerable, possibly empty, set of indivisual constants. 6. A nonempty set of predicate letters.
APPLICATIONS : The predicate logic is a part of artificial intelligence which is applicable in the field of robotics, medicine and it is used in intelligence database in order to solve some complex problems. Predicate logic is used for providing system safety,it is used in ssh to provide security to the system.Predicate logic is used for representing knowledge by the comparative study of knowledge representation schemes and application in the filed of medicine based on predicate logic theory.
ACKNOWLEDGEMENT ACKNOWLEDGEMENT : : I would like to give special thanks of gratitude to my teacher Mrs. Soma Chatterjee for her guidance in making this presentation to the point and presentable. Also I would to like to give my thanks of gratitude to our HOD Mr. Nitai Roy for making me a part of this beautiful project,which also helped me doing research a lot and I came to know so many new things.
