First order predicate logic(fopl)

First order predicate logic(fopl)

1. FIRST ORDER PREDICATE LOGIC(FOPL) Submitted By: Surbhi Jha

2. OBJECTIVE INTODUCTION DIFFERENCE BETWEEN PROPOSITIONAL LOGIC & FIRST ORDER LOGIC PARTS OF FIRST ORDER LOGIC QUANTIFIERS What are Rules of Inference for? PROS & CONS OF FOPL REFERENCES

3. Introduction First-order logic —also known as  first-order predicate calculus  and  predicate logic —is a collection of  formal systems  used in  mathematics ,  philosophy ,  linguistics , and  computer science . First-order logic uses  quantified variables  over non-logical objects and allows the use of sentences that contain variables, so that rather than propositions such as  Socrates is a man  one can have expressions in the form "there exists X such that X is Socrates and X is a man" and  there exists  is a quantifier while  X  is a variable.

4. PL(Propositional Logic) It uses prepositions in which complete sentence is denoted by symbol. PL can’t represent individual entities. Eg : Meena is short It can’t express generalization, specialization or pattern. Eg : Triangles have 3 sides. Difference between propositional logic & first order logic FOL(First Order Logic) FOL was predicated which involve constants, variables, functions, relations. FOL can represent individual properties. Eg : short( Meena ). It can express generalization, specialization or pattern. Eg : No._ of_sides (triangle 3)

5. PARTS OF FIRST ORDER LOGIC There are two key parts of first-order logic. The  syntax  determines which collections of symbols are legal expressions in first-order logic, while the  semantics  determine the meanings behind these expressions.

6. Syntax of First-order Logic: Basic Elements Note: The equality predicate is always in the vocabulary. It is written in infix notation

7. Atomic sentence predicate ( term 1; : : : ; termn ) or term 1 = term 2 Term function ( term 1; : : : ; termn ) or constant or variable

8. Syntax of First-order Logic: Atomic Sentences Example

9. Syntax of First-order Logic: Complex Sentences Built from atomic sentences using connectives

10. Semantics A predicate logic expression gets a meaning through a configuration, i.e. the specification of 1. a non-empty domain, 2. an interpretation that gives for every constant an element of that domain, for every function symbol with arity n some concrete n- ary function on the domain, and for every predicate symbol with arity n some concrete n- ary relation on the domain, and 3. an assignment for the free variables in the expression.

11. Semantics of terms & FORMULAS

12. Semantics: Examples

13. Quantifiers The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and Existential Quantifier. Universal Quantifier Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol ∀. ∀ xP (x) is read as for every value of x, P(x) is true. Example  − "Man is mortal" can be transformed into the propositional form ∀ xP (x) where P(x) is the predicate which denotes x is mortal and the universe of discourse is all men.

14. Existential Quantifier Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol ∃. ∃ xP (x) is read as for some values of x, P(x) is true. Example  − "Some people are dishonest" can be transformed into the propositional form ∃ xP (x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse is some people. Nested Quantifiers If we use a quantifier that appears within the scope of another quantifier, it is called nested quantifier. Example ∀  a∃ bP ( x,y ) where  P( a,b ) denotes  a+b =0 ∀  a∀b∀cP ( a,b,c ) where P( a,b )P( a,b ) denotes a+( b+c )=( a+b )+c Note  − ∀ a∃bP ( x,y )≠∃ a∀bP ( x,y ) To deduce new statements from the statements whose truth that we already know,  Rules of Inference  are used.

15. What are Rules of Inference for? Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements. An argument is a sequence of statements. The last statement is the conclusion and all its preceding statements are called premises (or hypothesis). The symbol “∴∴”, (read therefore) is placed before the conclusion. A valid argument is one where the conclusion follows from the truth values of the premises. Rules of Inference provide the templates or guidelines for constructing valid arguments from the statements that we already have.

16. Table for rules of inference

17. Addition: If P is a premise, we can use Addiction rule to derive P∨ Q.

18. PROS & CONS OF FOPL PROS: Propositional logic is declarative: pieces of syntax correspond to facts Propositional logic allows partial / disjunctive / negated information (unlike most data structures and databases) 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) CONS: Propositional logic has very limited expressive power (unlike natural language) Example: Cannot say “pits cause breezes in adjacent squares” except by writing one sentence for each square

19. aPPLICATIONS Predicate logic is useful in its own right as a tool for presenting arguments rigorously & determining their validity. The original purpose of predicate logic was to provide a formal procedure for proving mathematical theorems. The main work done by predicate logic is as the framework for the formulation of theories.

20. REFERENCES https://en.wikipedia.org/wiki/Geographic_information_system https://www.youtube.com/watch?v=pcV2lL6yNZ8 https://www.tutorialspoint.com/discrete_mathematics/operators_and_postulates.htm