Propositional logic

(1)

Propositional logic

(2)

Propositional logic

Vocabulary Propositional letters: Σ = {p, q, r, …}

(aka Boolean variables)

Boolean connectives: ∨, ∧, ¬, →,

(3)

Propositional logic

Syntax φ : p | q | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ

(4)

Propositional logic

Semantics Requires a model M : Σ → {true, false}

Describes when φ holds on M (M ⊨ φ)

(5)

Propositional logic

Semantics Requires a model M : Σ → {true, false}

Describes when φ holds on M (M ⊨ φ) iff

M ⊨ p M(p) = true

iff

M ⊨ φ1 ∨ φ2 M ⊨ φ1 or M ⊨ φ2

iff

M ⊨ φ1 ∧ φ2 M ⊨ φ1 and M ⊨ φ2

iff

M ⊨ ¬φ M ⊭ φ

iff

M ⊨ φ1 → φ2 M ⊭ φ1 or M ⊨ φ2

…

(6)

Logical equivalences

iff

φ tautology for every model M, M ⊨ φ

iff

φ contradiction for every model M, M ⊭ φ

iff

φ1 consequence of φ2 for every model M, M ⊨ φ1 implies M ⊨ φ2

iff

φ1 equivalent to φ2 for every model M, M ⊨ φ1 iff M ⊨ φ2

(7)

Logical equivalences

Example φ1 → φ2 is equivalent to its contrapositive (¬φ2 → ¬φ1) but not to its converse (φ2 → φ1)

iff

φ tautology for every model M, M ⊨ φ

iff

φ contradiction for every model M, M ⊭ φ

iff

φ1 consequence of φ2 for every model M, M ⊨ φ1 implies M ⊨ φ2

iff

φ1 equivalent to φ2 for every model M, M ⊨ φ1 iff M ⊨ φ2

(8)

Algorithms

Model-check(φ,M) if φ = p then

return M(p)

else if φ = φ1 ∨ φ2 then

return Model-check(φ1,M) OR Model-check(φ2,M)

else if φ = φ1 ∧ φ2 then

return Model-check(φ1,M) AND Model-check(φ2,M)

else …

(9)

Algorithms

Complexity: P-complete

Model-check(φ,M) if φ = p then

return M(p)

else if φ = φ1 ∨ φ2 then

return Model-check(φ1,M) OR Model-check(φ2,M)

else if φ = φ1 ∧ φ2 then

return Model-check(φ1,M) AND Model-check(φ2,M)

else …

(10)

Algorithms

Satisfiable(φ)

let p1, p2, … = prop. letters in φ for M(p1) ∈ {true, false} do

for M(p2) ∈ {true, false} do

…

if Model-check(φ,M) then return true

return false

(11)

Algorithms

Satisfiable(φ)

let p1, p2, … = prop. letters in φ for M(p1) ∈ {true, false} do

for M(p2) ∈ {true, false} do

…

if Model-check(φ,M) then return true

return false

Complexity: in EXP (actually, NP-complete …)

(12)

Economy of syntax and normal forms

Lemma ∧, →, can be defined using ∨, ¬

Namely:

is equivalent to

φ1 ∧ φ2 ¬(¬φ1 ∨ ¬φ2)

is equivalent to

φ1 → φ2 ¬φ1 ∨ φ2

is equivalent to

φ1 φ2 ¬(¬(¬φ1 ∨ φ2) ∨ ¬(¬φ2 ∨ φ1))

(13)

Economy of syntax and normal forms

NNF (Negation Normal Form) φ : φ ∨ φ | φ ∧ φ | α α : p | ¬p

(14)

Economy of syntax and normal forms

Lemma Given φ ( -free), one can compute in polynomial time an equivalent formula φ* in NNF

(15)

Economy of syntax and normal forms

Proof Redefine → and push negations inside:

φ1 → φ2 ⇝ ¬φ1 ⋁ φ2

¬(φ1 ⋀ φ2) ⇝ ¬φ1 ⋁ ¬φ2

¬(φ1 ⋁ φ2) ⇝ ¬φ1 ⋀ ¬φ2

(16)

Economy of syntax and normal forms

(17)

Economy of syntax and normal forms

CNF (Conjunctive Normal Form) φ : φ ∧ φ | α

α : α ∨ α | p | ¬p

(18)

Economy of syntax and normal forms

α : α ∨ α | p | ¬p

Lemma Given φ, one can compute in polynomial time an equi-satisfiable formula φ* in CNF

(19)

Economy of syntax and normal forms

α : α ∨ α | p | ¬p

Corollary CNF-Sat is still NP-complete

(20)

Economy of syntax and normal forms

α : α ∨ α | p | ¬p DNF (Disjunctive Normal Form) φ : φ ∨ φ | α

α : α ∧ α | p | ¬p

(21)

Back to algorithms — Tableaux for satisfiability

Motto Instead of guessing pieces of a model (for M(p) ∈ {true, false} …) guess pieces of the formula to be satisfied (^{α¹^{, α}²^{, …}})

(22)

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p { (p ∨ ¬q) ∧ ¬p }{ (p ∨ ¬q) ∧ ¬p }

(23)

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p { (p ∨ ¬q) ∧ ¬p }

{ (p ∨ ¬q) ∧ ¬p }

(24)

{ p ∨ ¬q , ¬p }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p

{ (p ∨ ¬q) ∧ ¬p }

(25)

{ p , ¬p }{ ¬q , ¬p } { p ∨ ¬q , ¬p }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p

{ (p ∨ ¬q) ∧ ¬p }

(26)

{ p , ¬p } { ¬q , ¬p }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p { (p ∨ ¬q) ∧ ¬p }

{ p ∨ ¬q , ¬p }

(27)

{ p , ¬p } { ¬q , ¬p }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p { (p ∨ ¬q) ∧ ¬p }

{ p ∨ ¬q , ¬p }

{ p , ¬p } { ¬q , ¬p }

(28)

{ p , ¬p } { ¬q , ¬p }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ ¬p { (p ∨ ¬q) ∧ ¬p }

{ p ∨ ¬q , ¬p }

{ p , ¬p } { ¬q , ¬p }

(29)

{ (p ∨ ¬q) ∧ (¬p ∧ q) }

Back to algorithms — Tableaux for satisfiability

Example φ = (p ∨ ¬q) ∧ (¬p ∧ q) { (p ∨ ¬q) ∧ (¬p ∧ q) }

(30)

Back to algorithms — Tableaux for satisfiability

{ (p ∨ ¬q) ∧ (¬p ∧ q) }

(31)

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

(32)

{ p , ¬p ∧ q }{ ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

(33)

{ p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

(34)

{ p , ¬p ∧ q } { ¬q , ¬p ∧ q } { p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

(35)

{ p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

{ p , ¬p ∧ q } { ¬q , ¬p ∧ q }

(36)

{ p , ¬p , q } { ¬q , ¬p , q } { p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

(37)

{ p , ¬p , q } { ¬q , ¬p , q } { p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

{ p , ¬p , q } { ¬q , ¬p , q }

Note: different choices give different tableaux!

(38)

{ p , ¬p , q } { ¬q , ¬p , q } { p , ¬p ∧ q } { ¬q , ¬p ∧ q }

Back to algorithms — Tableaux for satisfiability

{ p ∨ ¬q , ¬p ∧ q }

{ p , ¬p , q } { ¬q , ¬p , q }

(39)

Back to algorithms — Tableaux for satisfiability

Tableaux construction:

1. assume φ is in Negation Normal Form (not necessary, but simplifies cases) 2. start with singleton tree { φ }

3. choose unblocked leaf F = { α1, α2, … } and subformula α ∈ F 4. expand tree under leaf F by adding

• one child F1 = (F \ α) ∪ { β, γ } if α = β ∧ γ

• two children F1 = (F \ α) ∪ { β } and F2 = (F \ α) ∪ { γ } if α = β ∨ γ 5. new leaves that contain both p and ¬p are declared blocked

6. stop with success as soon as there is an unblocked leaf with only literals

(40)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Consider an electronic device whose internal state can be encoded by k bits

• initial state is described by a propositional formula φinit(p̅)

Application example — a simple transition system

(41)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

φinit(p̅)

Application example — a simple transition system

(42)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

φinit(p̅) φgoal(p̅)

Application example — a simple transition system

• desired final state is described by another propositional formula φgoal(p̅)

(43)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

• discrete transitions between states also described by a formula φtrans(p̅,p̅’)

φtrans(p̅,p̅’)

(44)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

φtrans(p̅,p̅’)

(45)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

φtrans(p̅,p̅’)

(46)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

φtrans(p̅,p̅’)

(47)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

Problem does the device admit a run from initial state to desired final state ? φtrans(p̅,p̅’)

(48)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

Note sufficient to consider runs of at most n = 2^k transitions

Problem does the device admit a run from initial state to desired final state ? φtrans(p̅,p̅’)

(49)

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

{

k bits

Application example — a simple transition system

Note sufficient to consider runs of at most n = 2^k transitions

Problem does the device admit a run from initial state to desired final state ?

φreach = φinit[p̅1] ∧ φgoal[p̅n] ∧

⋀

^i=2,...,n φtrans[p̅i-1,p̅i] Test satisfiability of

φtrans(p̅,p̅’)

(50)

Things to remember

(51)

Things to remember

• Propositional logic is very simple, yet useful

• Algorithms (model-checking and satisfiability) are conceptually simple

but they can be presented and implemented in different ways (e.g. tableaux)

• There are efficiently computable normal forms (NNF, CNF)