COMP9418: Advanced Topics in Statistical Machine Learning
Propositional Logic
Instructor: University of Wales
Introduction
§ This lecture provides an introduction to propositional logic § Syntax and semantics of propositional logic
§ Monotonicity of propositional logic
§ This topic will provide a basis to review probability calculus § As an extension of logic concepts
§ Allow to reason in the presence of uncertainty
2
Syntax of Propositional Sentences
§ Consider an alarm for detecting burglaries § It can also be triggered by an earthquake
§ An event of a burglary or earthquake can be expressed by the following sentence
§ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 and 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 are propositional variables § ∨ is a logical disjunction (or)
§ Propositional logic can be used to express more complex statements
§ ⇒ is the logical implication
§ It means that a burglary or an earthquake is guaranteed to trigger
the alarm
§ Consider also this sentence
§ ¬ is a logical negation (not) and ∧ is the logical conjunction (and)
§ It means that if there is no burglary and no earthquake, the alarm will not trigger
3
Syntax of Propositional Sentences
§ Consider an alarm for detecting burglaries § It can also be triggered by an earthquake
§ An event of a burglary or earthquake can be expressed by the following sentence
§ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 and 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 are propositional variables § ∨ is a logical disjunction (or)
§ Propositional logic can be used to express more complex statements
§ ⇒ is the logical implication
§ It means that a burglary or an earthquake is guaranteed to trigger
the alarm
§ Consider also this sentence
§ ¬ is a logical negation (not) and ∧ is the logical conjunction (and)
§ It means that if there is no burglary and no earthquake, the alarm will not trigger
𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∨ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒
𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∨ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ⟹ 𝐴𝑙𝑎𝑟𝑚
¬𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∧ ¬𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ⟹ ¬𝐴𝑙𝑎𝑟𝑚
4
Syntax of Propositional Sentences
§ Propositional sentences are formed using a set of propositional variables
§ These variables are also called Boolean variables or binary variables
§ Assume one of two possible values, typically indicated by 𝑡𝑟𝑢𝑒 and 𝑓𝑎𝑙𝑠𝑒
§ The simplest sentence has the form 𝑃!
§ It is an atomic sentence
§ It means that the variable 𝑃! has the value 𝑡𝑟𝑢𝑒
§ More generally, propositional sentences are formed as follows
§ Every propositional variable 𝑃! is a sentence
§ If𝛼and𝛽aresentences,then¬𝛼,𝛼∧𝛽,and𝛼∨𝛽arealso sentences
𝑃”, … , 𝑃#
5
Syntax of Propositional Sentences
§ The symbols ¬, ∧ and ∨ are logical connectives § They stand for negation, conjunction and disjunction
§ Other connectives can also be introduced § Such as implication (⟹) and equivalence (⟺)
§ But these can be defined in terms of the three primitive connectives
§ A propositional knowledge base is a set of propositional sentences 𝛼<, 𝛼=, ... , 𝛼>
§ Interpreted as a conjunction 𝛼! ∧ 𝛼” ∧ ⋯ ∧ 𝛼#
𝛼 ⟹ 𝛽 ≡ ¬𝛼 ∨ 𝛽
𝛼⟺𝛽≡ 𝛼⟹𝛽 ∧(𝛽⟹𝛼)
6
Syntax of Propositional Sentences
§ Consider this digital circuit with two inputs and one output
§ Let’s write a propositional knowledge base that captures the behavior of this circuit
§ We need to choose a set of propositional variables § Common choice is one variable to each wire
7
Syntax of Propositional Sentences
§ Consider this digital circuit with two inputs and one output
§ Let’s write a propositional knowledge base that captures the behavior of this circuit
§ We need to choose a set of propositional variables
§ Common choice is one variable to each wire
§ The idea is that when the variable is true, the
corresponding wire is high 𝐴 § Also, a when a variable is false, the wire is low
AB
XY C
§ This leads to the following knowledge base
Δ =
⟹ ¬𝑋 ¬𝐴 ⟹𝑋 𝐴∧𝐵 ⟹𝑌
¬𝐴∧𝐵 ⟹¬𝑌 𝑋∨𝑌 ⟹𝐶 ¬𝑋∨𝑌 ⟹¬𝐶
8
Semantics of Propositional Sentences
§ Propositional logic provides a framework for defining
§ Properties of sentences such as consistency and validity
§ Relationships among them, such as implication,
equivalence and mutual exclusiveness
§ For instance, this sentence § Logically implies
§ These properties and relationships are easy to figure out for simple sentences
§ 𝐴 ∧ ¬𝐴 is inconsistent (will never hold) § 𝐴 ∨ ¬𝐴 is valid (always hold)
§ 𝐴 and (𝐴 ⟹ 𝐵) implies 𝐵
§ 𝐴 ∨ 𝐵 is equivalent to 𝐵 ∨ 𝐴
𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∨ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ⟹ 𝐴𝑙𝑎𝑟𝑚 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ⟹ 𝐴𝑙𝑎𝑟𝑚
𝐴𝑙𝑎𝑟𝑚 ∧ ¬𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ⟹ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒
9
Semantics of Propositional Sentences
§ Yet it may not be obvious that 𝐴 ⟹ 𝐵 and ¬𝐵 ⟹ ¬𝐴 are equivalent
§Orthat 𝐴⟹𝐵 ∧(𝐴⟹¬𝐵)implies¬𝐴
§ For this reason, we need formal definitions of logical properties and relationships
§ These notions are relatively easy ones the notion of world is defined
10
Worlds, Models and Events
world
Earthquake
Burglary
Alarm
𝑤!
true
true
true
𝑤”
true
true
false
𝑤#
true
false
true
𝑤$
true
false
false
𝑤%
false
true
true
𝑤&
false
true
false
𝑤’
false
false
true
𝑤(
false
false
false
§ A world is a state in which the value of each variable is known
§ In the Burglary example, we have three variables and eight worlds
§ A world 𝑤 is a function that maps each propositional variable 𝑃C into a value 𝑤 𝑃C ∈ {𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑠𝑒}
§ A world is also called a truth assignment, variable assignment or variable instantiation
§ Worlds allow to decide the truth of sentences without ambiguity
§ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 is true at world 𝑤!
§ ¬𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 is true at world 𝑤$
§ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∨ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 is true at world 𝑤%
11
Worlds, Models and Events
§ We use the notation 𝑤 ⊨ 𝛼 to mean that the sentence 𝛼 is true at world 𝑤
§ Also, world 𝑤 satisfies (or entails) sentence 𝛼
§ A set of worlds that satisfy a sentence 𝛼 is called the models of 𝛼
§ Every sentence 𝛼 can be viewed as representing a set of worlds 𝑀𝑜𝑑𝑠(𝛼), which is called the event denoted by 𝛼
§ We use the terms “sentence” and “events” interchangeably § We can prove the following properties
§ 𝑀𝑜𝑑𝑠(𝛼 ∧ 𝛽) = 𝑀𝑜𝑑𝑠(𝛼) ∩ 𝑀𝑜𝑑𝑠(𝛽) §𝑀𝑜𝑑𝑠 𝛼∨𝛽 = 𝑀𝑜𝑑𝑠 𝛼 ∪𝑀𝑜𝑑𝑠(𝛽)
§ 𝑀𝑜𝑑𝑠(¬𝛼) = 𝑀𝑜𝑑𝑠 𝛼
𝑀𝑜𝑑𝑠(𝛼)≝{𝑤∶ 𝑤⊨𝛼}
12
Worlds, Models and Events
world
Earthquake
Burglary
Alarm
𝑤!
true
true
true
𝑤”
true
true
false
𝑤#
true
false
true
𝑤$
true
false
false
𝑤%
false
true
true
𝑤&
false
true
false
𝑤’
false
false
true
𝑤(
false
false
false
§ Some example sentences and their truth at worlds § 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 is true at worlds 𝑤”, … , 𝑤$
𝑀𝑜𝑑𝑠(𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒) = {𝑤!,…,𝑤”}
§ ¬𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 is true at worlds 𝑤%, … , 𝑤& 𝑀𝑜𝑑𝑠(¬𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒) = 𝑀𝑜𝑑𝑠(𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒)
§ ¬𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 is true at worlds 𝑤’, 𝑤$, 𝑤(, 𝑤& § 𝐴𝑙𝑎𝑟𝑚 is true at worlds 𝑤”, 𝑤’, 𝑤%, 𝑤(
§ ¬(𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∨ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦) is true at worlds 𝑤(, 𝑤& 𝑀𝑜𝑑𝑠(¬(𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∨ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦)) = 𝑀𝑜𝑑𝑠 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∪ 𝑀𝑜𝑑𝑠(𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦)
§¬𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒∨𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∨𝐴𝑙𝑎𝑟𝑚istrueatworlds 𝑤”, 𝑤’, 𝑤%, 𝑤(, 𝑤&
§ 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∨ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ⟹ 𝐴𝑙𝑎𝑟𝑚 is true at worlds 𝑤”, 𝑤’, 𝑤%, 𝑤(, 𝑤&
§ ¬𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ∧ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 is not true at any world
13
Logical Properties
§ We say that a sentence 𝛼 is consistent if and only if there is at least one world 𝑤 at which 𝛼 is true
§ Otherwise, the sentence 𝛼 is inconsistent
§ We also use the terms satisfiable/unsatisfiable
§ The symbol 𝑓𝑎𝑙𝑠𝑒 is used to denote a sentence that is unsatisfiable
§ A sentence 𝛼 is valid if and only if it is true at every world
§Ifasentence𝛼isnotvalid,wecanidentifyaworld𝑤at which 𝛼 is false
§ The symbol 𝑡𝑟𝑢𝑒 is used to denote a sentence that is valid. We also write ⊨ 𝛼
𝑀𝑜𝑑𝑠𝛼 ≠∅ 𝑀𝑜𝑑𝑠𝛼 =∅
𝑀𝑜𝑑𝑠𝛼 =Ω 𝑀𝑜𝑑𝑠 𝛼 ≠Ω
14
Logical Relationships
§ Logical properties apply to single sentences. Logical relationships apply to two or more sentences
§ Sentences 𝛼 and 𝛽 are equivalent iff they are true at the same set of worlds
§ Sentences 𝛼 and 𝛽 are mutually exclusive iff they are never true at the same world
§ Sentences 𝛼 and 𝛽 are exhaustive iff each world satisfies at least one of the sentences
§ Sentence 𝛼 implies sentence 𝛽 iff 𝛽 is true whenever 𝛼 is true
𝑀𝑜𝑑𝑠 𝛼 = 𝑀𝑜𝑑𝑠(𝛽)
𝑀𝑜𝑑𝑠𝛼 ∩𝑀𝑜𝑑𝑠(𝛽)=∅
𝑀𝑜𝑑𝑠𝛼 ∪𝑀𝑜𝑑𝑠(𝛽)=Ω 𝑀𝑜𝑑𝑠 𝛼 ⊆ Mods(𝛽)
§ Symbol ⊨ is also used to indicate implication
between sentences 𝛼⊨𝛽
§ 𝛼 implies or entails 𝛽
15
Equivalences
§ These equivalences are useful when working with propositional logic
§ They are defined for schemas, which are templates
§ For instance 𝛼 ⟹ 𝛽 is a schema for ¬𝐴 ⟹ (𝐵 ∨ ¬𝐶)
Schema
¬𝑡𝑟𝑢𝑒
¬𝑓𝑎𝑙𝑠𝑒
𝑓𝑎𝑙𝑠𝑒 ∧ 𝛽
𝛼 ∧ 𝑡𝑟𝑢𝑒
𝑓𝑎𝑙𝑠𝑒 ∨ 𝛽
𝛼 ∨ 𝑡𝑟𝑢𝑒
¬¬𝛼
¬(𝛼 ∧ 𝛽)
¬(𝛼 ∨ 𝛽)
𝛼 ∨ (𝛽 ∧ 𝛾)
Equivalent Schema
𝑓𝑎𝑙𝑠𝑒
𝑡𝑟𝑢𝑒
𝑓𝑎𝑙𝑠𝑒
𝛼
𝛽
𝑡𝑟𝑢𝑒
𝛼
¬𝛼 ∨ ¬𝛽
¬𝛼 ∧ ¬𝛽
𝛼∨𝛽 ∧(𝛼∨𝛾)
Name
Double negation
de Morgan
de Morgan
𝛼 ∧ (𝛽 ∨ 𝛾)
𝛼⟹𝛽
𝛼⟹𝛽
𝛼⟺𝛽
𝛼∧𝛽 ∨(𝛼∧𝛾)
¬𝛽 ⟹ ¬𝛼
¬𝛼 ∨ 𝛽
𝛼⟹𝛽 ∧(𝛽⟹𝛼)
distribution
distribution
contraposition
definition of ⟹
definition of ⟺
16
Reductions
§ We can also state several reductions between logical properties and relationships
§ This table shows how the relationships of implication, equivalence, mutual exclusiveness and exhaustiveness can be defined in terms of satisfiability and validity
Relationship
Property
𝛼 implies 𝛽
𝛼 ∧ ¬𝛽 is unsatisfiable
𝛼 implies 𝛽
𝛼 ⟹ 𝛽 is valid
𝛼 and 𝛽 are equivalent
𝛼 ⟺ 𝛽 is valid
𝛼 and 𝛽 are mutually exclusive
𝛼 ∧ 𝛽 is unsatisfiable
𝛼 and 𝛽 are exhaustive
𝛼 ∨ 𝛽 is valid
17
Monotonicity
§ Consider the earthquake-burglary-alarm example
§ Suppose we introduce the sentence
𝛼: 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∨ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ⟹ 𝐴𝑙𝑎𝑟𝑚
§ 𝛼 makes some of the worlds impossible § Changing our state of belief
§ 𝑀𝑜𝑑𝑠 𝛼 = {𝑤!,𝑤$,𝑤&,𝑤’,𝑤(}
world
Earthquake
Burglary
Alarm
𝛼
𝒘𝟏
true
true
true
true
𝑤”
true
true
false
false
𝒘𝟑
true
false
true
true
𝑤$
true
false
false
false
𝒘𝟓
false
true
true
true
𝑤&
false
true
false
false
𝒘𝟕
false
false
true
true
𝒘𝟖
false
false
false
true
18
Monotonicity
§ Suppose we learn
§ 𝛽: 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ⟹ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦
§ 𝑀𝑜𝑑𝑠 𝛽 = {𝑤!,𝑤”,𝑤&,𝑤),𝑤’,𝑤(}
§ Our state of belief rules out 𝑤F §𝑀𝑜𝑑𝑠 𝛼∧𝛽 =𝑀𝑜𝑑𝑠 𝛼 ∩𝑀𝑜𝑑𝑠(𝛽)
𝛼Δ
world
Earthquake
Burglary
Alarm
𝛼
𝛽
𝒘𝟏
true
true
true
true
true
𝑤”
true
true
false
false
true
𝑤#
true
false
true
true
false
𝑤$
true
false
false
false
false
𝒘𝟓
false
true
true
true
true
𝑤&
false
true
false
false
true
𝒘𝟕
false
false
true
true
true
𝒘𝟖
false
false
false
true
true
19
Monotonicity
§ Suppose we learn
§ 𝛽: 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ⟹ 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦
§ 𝑀𝑜𝑑𝑠 𝛽 = {𝑤!,𝑤”,𝑤&,𝑤),𝑤’,𝑤(}
§ Our state of belief rules out 𝑤F §𝑀𝑜𝑑𝑠 𝛼∧𝛽 =𝑀𝑜𝑑𝑠 𝛼 ∩𝑀𝑜𝑑𝑠(𝛽)
world
Earthquake
Burglary
Alarm
𝛼
𝛽
𝒘𝟏
true
true
true
true
true
𝑤”
true
true
false
false
true
𝑤#
true
false
true
true
false
𝑤$
true
false
false
false
false
𝒘𝟓
false
true
true
true
true
𝑤&
false
true
false
false
true
𝒘𝟕
false
false
true
true
true
𝒘𝟖
false
false
false
true
true
𝛼
𝛽
Δ=𝛼∧𝛽
20
Monotonicity
𝛼
Δ⊨𝛼 Δ
𝛾 𝛼
Δ
𝛼⊨𝛾 Δ⊨𝛾
𝛼
Δ
𝛾
𝛽
Δ⊨𝛼∧𝛽 Δ⊨𝛾
21
Multivalued Variables
world
Earthquake
Burglary
Alarm
𝑤!
true
true
high
𝑤”
true
true
low
𝑤#
true
true
off
𝑤$
true
false
high
𝑤%
true
false
low
𝑤&
true
false
off
𝑤’
false
true
high
𝑤(
false
true
low
𝑤.
false
true
off
𝑤!/
false
false
high
𝑤!!
false
false
low
𝑤!”
false
false
off
§ Propositional variables are binary
§ As they assume the values 𝑡𝑟𝑢𝑒 or 𝑓𝑎𝑙𝑠𝑒
§ These values are implicit in the syntax as we use 𝑋 to mean 𝑋 = 𝑡𝑟𝑢𝑒 and ¬𝑋 to mean 𝑋 = 𝑓𝑎𝑙𝑠𝑒
§ We can generalise propositional logic to allow multivalued variables
§ For instance, an alarm that triggers high or low
§ We will need to explicate the values assigned 𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 ⟹ 𝐴𝑙𝑎𝑟𝑚 = h𝑖𝑔h
𝐵𝑢𝑟𝑔𝑙𝑎𝑟𝑦 = 𝑡𝑟𝑢𝑒 ⟹ 𝐴𝑙𝑎𝑟𝑚 = h𝑖𝑔h
22
Multivalued Variables
world
Earthquake
Burglary
Alarm
𝑤!
true
true
high
𝑤”
true
true
low
𝑤#
true
true
off
𝑤$
true
false
high
𝑤%
true
false
low
𝑤&
true
false
off
𝑤’
false
true
high
𝑤(
false
true
low
𝑤.
false
true
off
𝑤!/
false
false
high
𝑤!!
false
false
low
𝑤!”
false
false
off
§ Sentences in the generalized logic respect the following rules
§ Every propositional variable is a sentence
§ 𝑉 = 𝑣 is a sentence, where 𝑉 is a variable and 𝑣 is one of its
values
§ If 𝛼 and 𝛽 are sentences, them ¬𝛼, 𝛼 ∧ 𝛽, and 𝛼 ∨ 𝛽 are also sentences
§ The semantics of generalized logic is similar to the standard logic
§ For example, the sentence 𝐸𝑎𝑟𝑡h𝑞𝑢𝑎𝑘𝑒 ∧ 𝐴𝑙𝑎𝑟𝑚 = 𝑜𝑓𝑓
rules out all worlds but 𝑤$ and 𝑤)
23
Variable Instantiation
§ An instantiation of variables is a propositional sentence if the form
§ For variables 𝐴, 𝐵 and 𝐶 and values 𝑎, 𝑏 and 𝑐
§ We simplify the notation by
§ Use simply 𝑎 instead of 𝐴 = 𝑎
§ Replace the operator ∧ by a comma
§ A trivial instantiation is an instantiation to an empty set of variables
§ We will denote variables by upper-case letters (𝐴) § Values by lower-case letter (𝑎)
§ Cardinalities (number of values) by |𝐴|
𝐴=𝑎 ∧ 𝐵=𝑏 ∧(𝐶=𝑐) 𝑎,𝑏,𝑐
⊺
24
Variable Instantiation
§ Sets of variables will be denoted by bold-face upper- caseletters(𝑨)
§ Their instantiations by bold-face lower-case (𝒂) § Number of instantiations by 𝑨#
§ For a Boolean variable 𝐴 § 𝑎 denotes 𝐴 = 𝑡𝑟𝑢𝑒
§ 𝑎_ denotes 𝐴 = 𝑓𝑎𝑙𝑠𝑒
§ We also use 𝒙~𝒚 to denote 𝒙 and 𝒚 are compatible instantiations
§ They agree on the value of all common variables
𝐴 = {𝑎!, 𝑎”, 𝑎$} 𝐵= 𝑏!,𝑏”
𝐶 = {𝑐!,𝑐”}
𝑫 = {𝐴,𝐵,𝐶} 𝑫# = 12
𝑎,𝑏,𝑐̅ ~{𝑏,𝑐̅,𝑑̅}
{𝑎, 𝑏, 𝑐̅} and 𝑏, 𝑐, 𝑑̅ are
not compatible since they disagree on 𝐶
25
Conclusion
§ Logic is a reasoning framework widely used in AI
§ Logic limitations include the monotonicity property and lack of support
to uncertain events
§ This framework has been extended overcome this limitations, such as fuzzy logic and other ad-hoc methods (certainty factors and pseudoprobabilities)
§ This the next lecture, we will extend this framework to handle uncertainly through probabilistic reasoning
§ Tasks
§ Read Chapter 2, but Section 2.7 from the textbook (Darwiche)
26