CC-BY
Fabian M. Suchanek
Propositional Logic
Running Example
2
“Hermione married Ron” -> why???
married
loves
A
propositional formula
over a set of atoms Ａ is any of the following
•
（α ∧ β）
•
（α ∨ β）
•
（α ⇒ β）
•
¬ α
•
（α ⇔ β）
•
any element of Ａ
•
ｔｒｕｅ
•
ｆａｌｓｅ
... where α and β are propositional formulae.
Example: Ａ ={smart, heroic, childish, dumb}
（ｓｍａｒｔ ∧ ｈｅｒｏｉｃ） ∨ （ｄｕｍｂ ∧ ｃｈｉｌｄｉｓｈ）
Def: Propositional Logic
3
(called
conjunction
)
(called
disjunction
)
(called
implication
)
(called
negation
)
(called
equivalence
)
(We usually omit outer brackets.)
NAND>53
A
propositional formula
over a set of atoms Ａ is either
•
an element of Ａ
•
or a formula of the form
This is NAND.
It is “true” if at least one of the arguments is “false”.
Also known as the “Sheffer Stroke”, and written as “|”
We define:
α ⇒ β ：＝ ¬ α ∨ β
α ⇔ β ：＝ （α ⇒ β） ∧ （β ⇒ α）
ｔｒｕｅ ：＝ ａ ∨ ¬ ａ for any ａ ∈ Ａ
ｆａｌｓｅ ：＝ ¬ ｔｒｕｅ
(We usually omit outer brackets.)
α ∨β ：＝ ¬（¬ α ∧ ¬β）
Digression: Alternative definition
4
Example:
KB={smart, rich}
A (propositional)
knowledge base (KB)
over a set of atoms Ａ is a subset Ｋ ⊆ Ａ .
An
interpretation/valuation/denotation/possible world
for a set of atoms A is a function φ：Ａ → ｛１，０｝ .
Often, the interpretation is given as a KB, with φ（ａ）＝１， ｉｆ ａ ∈ ＫＢ， ０ ｅｌｓｅ .
(Here, we first talk about only one candidate for Hermione. We will later generalize the definition to the previously known definition of a KB.)
(In most of the following, we will see a KB and an interpretation as the same.)
Def: Prop. Knowledge Base, Interpretation
5
Def: Prop. Knowledge Base, Interpretation
6
In the example:
φ（ｓｍａｒｔ）＝１
φ（ｒｉｃｈ）＝１
φ（ｈａｎｄｓｏｍｅ）＝０
An
interpretation/valuation/denotation/possible world
for a set of atoms A is a function φ：Ａ → ｛１，０｝ .
(Here, we first talk about only one candidate for Hermione. We will later generalize the definition to the previously known definition of a KB.)
Often, the interpretation is given as a KB, with φ（ａ）＝１， ｉｆ ａ ∈ ＫＢ， ０ ｅｌｓｅ .
(In most of the following, we will see a KB and an interpretation as the same.)
Example:
KB={smart, rich}
A (propositional)
knowledge base (KB)
over a set of atoms Ａ is a subset Ｋ ⊆ Ａ .
We extend the interpretation to propositional
formulae by defining
φ（ｔｒｕｅ） ＝ １
φ（ｆａｌｓｅ） ＝ ０
φ（α ∧ β） ＝
φ（α ∨β） ＝
φ（¬ α） ＝
φ（α ⇒ β） ＝
Extending Interpretations
7
φ（ｔｒｕｅ） ＝ １
φ（ｆａｌｓｅ） ＝ ０
φ（α ∧ β） ＝ φ（α） × φ（β）
φ（α ∨β） ＝ １－（１－φ（α）） × （１－φ（β））
φ（¬ α） ＝ １ － φ（α）
φ（α ⇒ β） ＝ １－（φ（α）× （１－φ（β）））
We extend the interpretation to propositional
formulae by defining
Extending Interpretations
8
Example:
KB={smart, rich}
φ（α ⇒ β） ＝ １－（φ（α）× （１－φ（β）））
φ（ｆａｌｓｅ） ＝ ０
φ（α ∧ β） ＝ φ（α） × φ（β）
φ（¬ α） ＝ １ － φ（α）
φ（ｔｒｕｅ） ＝ １
φ（α ∨β） ＝ １－（１－φ（α）） × （１－φ（β））
We extend the interpretation to propositional
formulae by defining
Extending Interpretations
9
φ（ｒｉｃｈ ∧ ｓｍａｒｔ）＝ ?
φ（ｒｉｃｈ ∨ ｓｍａｒｔ）＝ ?
φ（ｓｍａｒｔ ⇒ ｈａｎｄｓｏｍｅ）＝ ?
φ（ｒｉｃｈ ∧ ｓｍａｒｔ）＝１
φ（ｒｉｃｈ ∨ ｓｍａｒｔ）＝１
φ（ｓｍａｒｔ ⇒ ｈａｎｄｓｏｍｅ）＝０
φ（α ⇒ β） ＝ １－（φ（α）× （１－φ（β）））
φ（ｆａｌｓｅ） ＝ ０
φ（α ∧ β） ＝ φ（α） × φ（β）
φ（¬ α） ＝ １ － φ（α）
φ（ｔｒｕｅ） ＝ １
φ（α ∨β） ＝ １－（１－φ（α）） × （１－φ（β））
We extend the interpretation to propositional
formulae by defining
Extending Interpretations
10
Example:
KB={smart, rich}
Example:
KB={smart, rich}
We say: The formula is true/satisfied in the KB.
φ（α ⇒ β） ＝ １－（φ（α）× （１－φ（β）））
φ（ｆａｌｓｅ） ＝ ０
φ（α ∧ β） ＝ φ（α） × φ（β）
φ（¬ α） ＝ １ － φ（α）
φ（ｔｒｕｅ） ＝ １
φ（α ∨β） ＝ １－（１－φ（α）） × （１－φ（β））
We extend the interpretation to propositional
formulae by defining
Extending Interpretations
11
φ（ｒｉｃｈ ∧ ｓｍａｒｔ）＝１
φ（ｒｉｃｈ ∨ ｓｍａｒｔ）＝１
φ（ｓｍａｒｔ ⇒ ｈａｎｄｓｏｍｅ）＝０
NAND>61
eqv>62
The usual truth tables follow from this.
We extend the interpretation to propositional formulae by defining
Digression: Interpretations and NAND
12
A formula α is a
tautology
, if for all φ , φ（α）＝１ .
We write ⊧ α .
Examples:
Two formulas α and β are
equivalent
, if ⊧ α ⇔ β .
⊧ ｒｉｃｈ ∨ ¬ ｒｉｃｈ
⊧ ｓｍａｒｔ ∧ ｒｉｃｈ ⇒ ｒｉｃｈ
Def: Tautology, Equivalence
13
Examples:
⊧ ｒｉｃｈ ∨ ｓｍａｒｔ ⇔ ｓｍａｒｔ ∨ ｒｉｃｈ
⊧ ¬ ¬ ｓｍａｒｔ ⇔ ｓｍａｒｔ
An implication α ⇒ β is equivalent to ¬ α ∨ β .
¬ ｓｍａｒｔ ∨ ｒｉｃｈ
Example:
KB={smart, rich}
ｓｍａｒｔ ⇒ ｒｉｃｈ
There is only one case where an implication α ⇒ β is false: if α is true and β is false.
Implications
14
φ（ｓｍａｒｔ ⇒ ｈａｎｄｓｏｍｅ）＝ ?
φ（ｈａｎｄｓｏｍｅ ⇒ ｒｉｃｈ）＝ ?
φ（ｈａｎｄｓｏｍｅ ∧ ｓｍａｒｔ ⇒ ｈｅｒｏ）＝ ?
Implications
15
φ（ｓｍａｒｔ ⇒ ｈａｎｄｓｏｍｅ）＝０
φ（ｈａｎｄｓｏｍｅ ⇒ ｒｉｃｈ）＝１
φ（ｈａｎｄｓｏｍｅ ∧ ｓｍａｒｔ ⇒ ｈｅｒｏ）＝１
details>69
An implication α ⇒ β is equivalent to ¬ α ∨ β .
¬ ｓｍａｒｔ ∨ ｒｉｃｈ
Example:
KB={smart, rich}
ｓｍａｒｔ ⇒ ｒｉｃｈ
There is only one case where an implication α ⇒ β is false: if α is true and β is false.
Example:
The
law of contraposition
says that an implication can be “turned around”:
ｓｍａｒｔ ⇒ ｒｉｃｈ
¬ ｒｉｃｈ ⇒ ¬ ｓｍａｒｔ
Implications
16
details>69
Here are some well-known tautological equivalences:
• Identity
• Domination
• Idempotence
• Double negation
• Commutation
• Associativity
• Distribution
• De Morgan
• Absorption
• Negation
ｐ ∧ ｔｒｕｅ ⇔ ｐ， ｐ ∨ ｆａｌｓｅ ⇔ ｐ
ｐ ∧ ｆａｌｓｅ⇔ ｆａｌｓｅ， ｐ ∨ ｔｒｕｅ ⇔ ｔｒｕｅ
ｐ ∧ ｐ ⇔ ｐ， ｐ ∨ ｐ ⇔ ｐ
¬ ¬ ｐ ⇔ ｐ
（ｐ ∧ ｑ） ∧ ｒ ⇔ ｐ ∧ （ｑ ∧ ｒ）
（ｐ ∨ ｑ） ∨ ｒ ⇔ ｐ ∨ （ｑ ∨ ｒ）
ｐ ∨ ｑ ⇔ ｑ ∨ ｐ， ｐ ∧ ｑ ⇔ ｑ ∧ ｐ
ｐ∨ （ｑ ∧ ｒ） ⇔ （ｐ ∨ ｑ）∧ （ｐ ∨ ｒ）
ｐ∧ （ｑ ∨ ｒ） ⇔ （ｐ ∧ ｑ）∨ （ｐ ∧ ｒ）
¬ （ｐ ∧ ｑ） ⇔ ¬ ｐ ∨ ¬ ｑ
¬ （ｐ ∨ ｑ） ⇔ ¬ ｐ ∧ ¬ ｑ
ｐ ∨ （ｐ ∧ ｑ） ⇔ ｐ
ｐ ∧ （ｐ ∨ ｑ） ⇔ ｐ
ｐ ∨ ¬ ｐ ⇔ ｔｒｕｅ， ｐ∧ ¬ ｐ ⇔ ｆａｌｓｅ
Equivalences
17
details>69
A formula in
conjunctive normal form
(CNF) is a conjunction of disjunctions
of possibly negated atoms.
Examples:
Every formula can be transformed into an equivalent CNF.
（ａ ∨ ｂ ∨ ¬ ｃ） ∧ （¬ ｂ ∨ ｃ ∨ ｄ ∨ ¬ ｅ）
ｂ ∧ （¬ ａ ∨ ｂ） ∧ （¬ ｂ ∨ ¬ ｅ） ∧ ｆ ∧ （ｆ ∨ ｅ）
Def: Conjunctive normal form
18
Examples:
(This may entail an exponential blowup)
details>69
α
entails
β (written α ⊧ β ), if ⊧ α ⇒ β .
Examples:
ａ ∧ ｂ ⊧ ａ
ａ ∧ ¬ ａ ⊧ ｂ
ａ ∨ ｂ ⊧ ｂ ∨ ａ
If we want to find entailments in a naive way, we have to try out exponentially many
interpretations. Therefore, we usually resort to calculi (next slide).
Def: Entailment
19
details>69
An
inference rule
is a function ｐ： Γ × Γ → Γ
where Γ is the set of formulas over a set of atoms.
We write
if
or if there are ｉ , ｊ , s.t.
and
.
Calculi and Proof Systems
20
Example: Modus Ponens inference rule
Example of a deduction with Modus Ponens:
ａ， ａ ⇒ ｂ， ｂ ⇒ ｃ ⊦ ｂ
and hence
ａ， ａ ⇒ ｂ， ｂ ⇒ ｃ ⊦ ｃ
An
inference rule
is a function ｐ： Γ × Γ → Γ
where Γ is the set of formulas over a set of atoms.
We write
if
or if there are ｉ , ｊ , s.t.
and
.
Calculi and Proof Systems
21
Examples:
• Modus Ponens + appropriate axioms
• Natural deduction
• Resolution
A
proof system / calculus
is a set of inference rules.
A calculus is
• complete, if α ⊧ β implies α ⊦ β
• correct, ifα ⊦ β implies α ⊧ β
We broaden our definition of an
atom
: An atom over a set Ｒ of relation names,
and a set Ｃ of constants is a string of the form
with
for ｉ＝１，．．．，ｎ .
Examples:
loves(Ron, Hermione)
smart(Hermione)
dumb(Ron)
The definition of a KB and an interpretation is broadened
accordingly, i.e., given the KB on the left,
φ（ｌｏｖｅｓ（Ｒｏｎ，Ｈｅｒｍｉｏｎｅ））＝１
Def: Atom
22
(We will implicitly take R as the set of lowercase words and C as the set of initial-capitalized words)
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｐｒｉｓｃｉｌｌａ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｐｒｉｓｃｉｌｌａ，Ｅｌｖｉｓ）
ｈａｓＳｐｏｕｓｅ（ｃａｔ，ｄｏｇ） ⇒ ｈａｓＳｐｏｕｓｅ（ｄｏｇ，ｃａｔ）
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｅｌｖｉｓ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｅｌｖｉｓ）
ｈａｓＳｐｏｕｓｅ（Ｈｅｒｍｉｏｎｅ，Ｒｏｎ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｒｏｎ，Ｈｅｒｍｉｏｎｅ）
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｐｒｉｓｃｉｌｌａ） ∨ ｌｏｖｅｓ（Ｐｒｉｓｃｉｌｌａ，Ｅｌｖｉｓ）
Given this KB, which of the following formulas are true?
23
Example: A KB of atoms
hasSpouse
hasSpouse
hasSpouse
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｐｒｉｓｃｉｌｌａ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｐｒｉｓｃｉｌｌａ，Ｅｌｖｉｓ）
ｈａｓＳｐｏｕｓｅ（ｃａｔ，ｄｏｇ） ⇒ ｈａｓＳｐｏｕｓｅ（ｄｏｇ，ｃａｔ）
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｅｌｖｉｓ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｅｌｖｉｓ）
24
Example: A KB of atoms
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ，Ｐｒｉｓｃｉｌｌａ） ∨ ｌｏｖｅｓ（Ｐｒｉｓｃｉｌｌａ，Ｅｌｖｉｓ）
Given this KB, which of the following formulas are true?
hasSpouse
hasSpouse
hasSpouse
ｈａｓＳｐｏｕｓｅ（Ｈｅｒｍｉｏｎｅ，Ｒｏｎ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｒｏｎ，Ｈｅｒｍｉｏｎｅ）
ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ⇒ ｌｉｋｅｓ（Ｈａｒｒｙ，Ｒｏｎ）
ｌｉｋｅｓ（Ｈａｒｒｙ， Ｒｏｎ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｈａｒｒｙ，Ｈｅｒｍｉｏｎｅ）
¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｈａｒｒｙ） ⇒ ｅｎｖｉｅｓ（Ｈａｒｒｙ，Ｒｏｎ）
¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｈａｒｒｙ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ）
ｌｉｋｅｓ（Ｈｅｒｍ．， Ｒｏｎ）∧ ¬ ｅｎｖｉｅｓ（Ｈａｒｒｙ，Ｒｏｎ）⇒ ｆｆｅ（Ｈａｒｒｙ，Ｒｏｎ）
25
likes
envies
likes
Example: A KB of atoms
Given this KB, which of the following formulas are true?
>universal
A
literal
is a possibly negated atom that may contain variables from a set Ｖ of variables.
Examples:
¬ loves(x, y)
smart(z)
¬ smart(Ron)
adores(x, x)
Def: Literal / Quantified Formula
26
(We will implicitly take V as the set of single letters)
A
universally quantified formula
is a formula built over literals instead of atoms.
Example:
(sometimes written as ∀ ｘ， ｙ， ｚ， ．．． . This is the fragment of FOL without existential quantifiers and function symbols)
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｘ）
A
binding
is a function from variables to constants.
｛ ｘ → Ｒｏｎ， ｙ → Ｅｌｖｉｓ ｝
An
instantiation
(ground instance) of a formula by a binding is the
formula obtained by substituting all variables by the constants given by
the binding.
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， Ｒｏｎ）
For a formula α and an interpretation φ , we define φ（α）＝１ iff φ（α＇）＝１
for all possible instantiations α＇ of α . We say that the formula is
true
under φ .
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｘ）
Def: Bindings
27
Example:
Example:
ｈａｓＳｐｏｕｓｅ（ｘ， ｙ） ⇒ ｈａｓＳｐｏｕｓｅ（ｙ， ｘ）
ｈａｓＳｐｏｕｓｅ（Ｅｌｖｉｓ， ｙ） ⇒ ｈａｓＳｐｏｕｓｅ（ｙ， Ｅｌｖｉｓ）
ｈａｓＳｐｏｕｓｅ（ｘ， Ｒｏｎ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｒｏｎ， ｘ）
Example: Universally quantified formulas
28
hasSpouse
hasSpouse
hasSpouse
Which formulas are true?
>clauses
A
rule
is a clause with exactly one positive literal.
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ∨ ¬ ｓｍａｒｔ（ｘ） ∨ ¬ ｃｕｔｅ（ｘ）
We usually write them as the equivalent implication:
ｓｍａｒｔ（ｘ） ∧ ｃｕｔｅ（ｘ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ← ｓｍａｒｔ（ｘ） ∧ ｃｕｔｅ（ｘ）
... or sometimes in the following form:
A
clause
is a disjunction of literals. We often write the clause as a set.
ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ∨ ｓｍａｒｔ（ｘ） ∨ ¬ ｃｕｔｅ（ｘ）
｛ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）， ｓｍａｒｔ（ｘ）， ¬ ｃｕｔｅ（ｘ） ｝
Def: Clause & Rule
29
Head
Body
Propositional logic is a formalism to express statements and their logical connections.
Summary: Propositional Logic
30
“If you’re smart then you’re rich”: ｓｍａｒｔ ⇒ ｒｉｃｈ
A calculus is a system to deduce new statements from given formulas.
Propositional logic can be broadened to atoms with arguments.