First order logic(jae)

Readings : http://en.wikipedia.org/wiki/First-order_logic

Reading Questions

1.What does first-order logic additionally cover?

2.How is it different representing "Socrates is a philosopher" between propositional logic and first order logic?

3.Which kinds of quantifier are in first order logic?, Show me symbols and meaning

4.When does a deductive system be called sound?

5.When does a deductive system be called complete?

6.How different are they between logical symbols and non-logical symbols?

7.How is set of term in first order logic defined ?

8.How is formulas in first order logic defined?

9.What is a "first order sentence"?

First-order logic

First-order logic is a formal system used in mathematics, philosophy, linguistics, and computer science. While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification.

1) propositional logic

"Socrates is a philosopher": p

"Plato is a philosopher" : q

In propositional logic these are treated as two unrelated propositions,denoted by p and q.

2) first-order logic

"Socrates is a philosopher": Phil(s)

"Plato is a philosopher" : Phil(p)

In first-order logic we can represent these two propositions using predicate Phil.

Syntax

The syntax determines which collections of symbols are legal expressions in first-order logic.There are two key types of legal expressions.

1) terms

The set of terms is inductively define by following rules:

• 1. Variables. Any variable is a term.

  2. Functions. Any expression f(t₁,...,t_n) of n arguments (where each argument t_i is a term and f is a function symbol of valence n) is a term. In particular, symbols denoting individual constants are 0-ary function symbols, and are thus terms.

2) formulas

• 1. Predicate symbols. If P is an n-ary predicate symbol and t₁, ..., t_n are terms then P(t₁,...,t_n) is a formula.

  2. Equality. If the equality symbol is considered part of logic, and t₁ and t₂ are terms, then t₁ = t₂ is a formula.

  3. Negation. If φ is a formula, then

  4. φ is a formula.

  5. Binary connectives. If φ and ψ are formulas, then (φ

  6. ψ) is a formula. Similar rules apply to other binary logical connectives.

  7. Quantifiers. If φ is a formula and x is a variable, then

1. and are formulas.

Semantics

Deductive systems

A deductive system is used to demonstrate. These finite deductions themselves are often called derivations in proof theory.

A deductive system is sound if any formula that can be derived in the system is logically valid.

1) sound

A deductive system is sound if any formula that can be derived in the system is logically valid.

2) complete

A deductive system is complete if every logically valid formula is derivable.

Sequent calculus

where A₁, ..., A_n, B₁, ..., B_k are formulas and the turnstile symbol