6. Predicate Logic

Sept. 28th, 2016

Reference on this topic origin from UTexas CS301k Logic.

6.1. Propositional Logic

• Reference

• Zeroth-order logic

• True or false

• Example:

  Premise 1: If it's raining then it's cloudy.
  Premise 2: It's raining.
  Conclusion: It's cloudy.
  

Logic operations (connectives)

• \(\neg\) denotes not
• \(\vee\) denotes or
• \(\wedge\) denotes and
• \(\rightarrow\) For propositions \(P\) and \(Q\), the implication or conditional statement \(P\rightarrow Q\) is false when \(P\) is true and \(Q\) is false, and is true otherwise. \(P\) is called the premise or hypothesis, and \(Q\) is called the conclusion.
• \(\leftrightarrow\) The biconditional of statements \(P\) and \(Q\), denoted \(P \leftrightarrow Q\), is read “\(P\) if and only if \(Q\)” (or “\(P\) is necessary and sufficient for \(Q\)”), and is true if \(P\) and \(Q\) have the same truth values, and false otherwise.

Logic equivalent and identities

• Logically equivalent: \(R\equiv S\).
• Important identities:

\[\begin{split}P \rightarrow Q&\equiv \neg P \vee Q &\text{(implication)}\\ P \vee (Q \wedge R) &\equiv (P \vee Q) \wedge (P \vee R) &\text{(distributivity)}\\ P \wedge (Q \vee R) &\equiv (P \wedge Q) \vee (P \wedge R) &\text{} \\ \neg(P \vee Q) &\equiv \neg P \wedge \neg Q &\text{(DeMorgan's law)}\\ \neg (P \wedge Q) &\equiv \neg P \vee \neg Q &\text{} \\ P \vee (P \wedge Q) &\equiv P &\text{(absorption)} \\ P \wedge (P \vee Q) &\equiv P &\text{}\end{split}\]

Normal form

• Disjuctive normal form (DNF): OR of ANDs
• Conjuctive normal form (DNF): AND of ORs
• Conversion of disjuctive and conjuctive normal form.

6.2. Defination of Predicate Logic

• Reference (link failure)
• First-order logic
• A predicate is a property that a variable or a finite collection of variables can have.
• A predicate becomes a proposition when specific values are assigned to the variables.
• \(P(x_1, x_2, ..., x_n)\) is called a predicate of n variables or n arguments.
• Domain and truth set

Quantifier

• Universal quantifier \(\forall\), existential quantifier \(\exists\)
• Quantifier truns a predicate into a proposition.

• The scope: if a quantifier is the part of a statement in which variables are bound by the quantifier.

  • Eg: \(R \vee \exists(P(x) \vee Q(x))\), scope of \(\exists\) is \(P(x) \vee Q(x)\)

• Distribution equation

6.3. Prenex Normal Form

• Reference
• Defination: A formula is in prenex normal form if it is of the form

\[Q_1x_1 Q_2x_2 \dots Q_nx_nB\]

where \(Q_i(i = 1, \dots, n)\) is \(\forall\) or \(\exists\) and the formula \(B\) is quantifier free.

• Any expression can be converted into prenex normal form. (How to!!!!)

  1. Eliminate all occurrences of → and ↔ from the formula in question

     • \(A \rightarrow B \equiv \neg A \vee B\)
     • \(A \leftrightarrow B \equiv (A \wedge B) \vee (\neg A \wedge \neg B)\)

  2. Move all negations inward such that, in the end, negations only appear as part of literals

     • De Morgan’s Laws

  3. Standardize the variables apart (when necessary)

     

  4. The prenex normal form can now be obtained by moving all quantifiers to the front of the formula

     

• Example:

  

6.4. Resolution Principle

• Reference
• First occurred in 1965, published by Alan Robinson.
• Refutation-complete: if you write any set of sentences in first order logic which are unsatisfiable (i.e., taken together they are false, in that they have no models), then the resolution method will eventually derive the False symbol, indicating that the sentences somehow contradict each other.

Clausal form

• A literal is either an atomic sentence or a negation of an atomic sentence.
• A clausal sentence is either a literal or a `disjunction <https://en.wikipedia.org/wiki/Logical_disjunction>`_(connected by OR operation) of literals.

• A clause is the set of literals in a clausal sentence.

  • Empty set {} is also a clause. It is equivalent to an empty disjunction and is unsatisfiable (cannot be true).

• An arbitrary set of Propositional Logic sentences can be deducted to an equivalent set of clauses.

Rule of inference (Resolution principle)

• Intuition

  • \({p, q}\): p is true or q is true.
  • \({\neg q, r}\): q is false or r is true.
  • q is either true or false: either p is true or r is true.
  • \({p, r}\)

• Principle:

• Resolution is not generatively complete, i.e. it is not possible to find resolution derivations for all clauses that are logically entailed by a set of premise clauses.
• (Herbrand’s Theorem) If a set \(\Delta\) of clauses is unsatisfiable, then there is guaranteed to be a resolution derivation of the empty clause from \(\Delta\).