# 计算机代写 COMP9418: Advanced Topics in Statistical Machine Learning – cscodehelp代写

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