Lec03 Prop Induction Nosol

Propositional Logic:
Structural Induction
Alice Gao
Lecture 3
CS 245 Logic and Computation Fall 2019 Alice Gao 1 / 25

Outline
Learning goals
Propositional language
Structure of formulas
Inductively defined sets
Revisiting the learning goals

Learning goals
By the end of the lecture, you should be able to

▶ Prove properties of well-formed propositional formulas using
structural induction.
▶ Prove properties of a recursively defined concept using

Propositional language 𝐿𝑝
The propositional language 𝐿𝑝 consists of three classes of symbols:
▶ Propositional symbols: 𝑝, 𝑞, 𝑟, … .
▶ Connective symbols: ¬, ∧, ∨, →, ↔.
▶ Punctuation symbols: ( and ).

Well-formed propositional formulas
Definition (𝐹 𝑜𝑟𝑚(𝐿𝑝 ))
An expression of 𝐿𝑝 is a member of 𝐹 𝑜𝑟𝑚(𝐿𝑝 ) iff its being so
follows from (1) - (3):
1. 𝐴𝑡𝑜𝑚(𝐿𝑝 ) ⊆ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ).
2. If 𝐴 ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ), then (¬𝐴) ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ).
3. If 𝐴, 𝐵 ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ), then (𝐴 ∗ 𝐵) ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ).

Outline
Learning goals

Unique readability of well-formed formulas
Does every well-formed formula have a unique meaning? Yes.

Theorem: There is a unique way to construct each well-formed
formula.

Properties of well-formed formulas
We may want to prove other properties of well-formed formulas.

▶ Every well-formed formula has at least one propositional
variable.
▶ Every well-formed formula has an equal number of opening
and closing brackets.
▶ Every proper prefix of a well-formed formula has more opening
brackets than closing brackets.
▶ There is a unique way to construct every well-formed formula.

Why should you care?
Learning goals on structural induction:

Learning goals for future courses:
▶ Prove the space and time efficiency of recursive algorithms
using induction.

Properties of well-formed formulas
Theorem: For every well-formed propositional formula 𝜑, 𝑃 (𝜑) is

true.

Recursive structure in well-formed formulas
Definition (𝐹 𝑜𝑟𝑚(𝐿𝑝 ))
An expression of 𝐿𝑝 is a member of 𝐹 𝑜𝑟𝑚(𝐿𝑝 ) iff its being so
follows from (1) - (3):
1. 𝐴𝑡𝑜𝑚(𝐿𝑝 ) ⊆ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ). (Base case)
2. If 𝐴 ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ), then (¬𝐴) ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ). (Inductive case)
3. If 𝐴, 𝐵 ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ), then (𝐴 ∗ 𝐵) ∈ 𝐹 𝑜𝑟𝑚(𝐿𝑝 ). (Inductive
case)

A structural induction template for well-formed formulas
Theorem: For every well-formed formula 𝜑, 𝑃 (𝜑) holds.
Proof by structural induction:
Base case: 𝜑 is a propositional symbol 𝑞. Prove that 𝑃 (𝑞)
holds.
Induction step:
Case 1: 𝜑 is (¬𝑎), where 𝑎 is well-formed.
Induction hypothesis: Assume that 𝑃 (𝑎) holds.
We need to prove that 𝑃 ((¬𝑎)) holds.
Case 2: 𝜑 is (𝑎 ∗ 𝑏) where 𝑎 and 𝑏 are well-formed and ∗ is a
binary connective.
Induction hypothesis: Assume that 𝑃 (𝑎) and 𝑃 (𝑏) hold.
We need to prove that 𝑃 ((𝑎 ∗ 𝑏)) holds.
By the principle of structural induction, 𝑃 (𝜑) holds for every

well-formed formula 𝜑. QED

Review questions about the structural induction template
1. Why is the definition of a well-formed formula recursive?

2. To prove a property of well-formed formulas using structural
induction, how many base cases and inductive cases are there
in the proof?
3. In the base case, how do we prove the theorem? Does the
proof rely on any additional assumption about the formula?
4. In an inductive case, how do we prove the theorem? Does the
proof rely on any additional assumption about the formula?

Structural induction problems
Problem 1: Every well-formed formula has at least one

propositional variable.
Problem 2: Every well-formed formula has an equal number of

opening and closing brackets.
Problem 3: Every proper prefix of a well-formed formula has more

opening brackets than closing brackets.

Outline
Learning goals

Structural induction for other problems
Structural induction is an important concept and it does not only

apply to well-formed propositional formulas.
Let’s look at some structural induction examples.

Ways of defining a set
▶ List all the elements in the set. Example: 𝐴 = {1, 2, 3, 4}.

▶ Characterize the set by some property of all the elements in
the set. Example: the set of even integers.
▶ Define a set inductively.

An inductively definition of a set consists of three components:

▶ A domain set 𝑋
▶ A core set 𝐶
▶ A set of operations 𝑃

Closed and minimal set
A set Y is closed under a set of operations P iff applying any

operation in P to elements in Y will always give us back an
element in Y.
A set Y is a minimal set with respect to a property R if

▶ Y has property R, and
▶ For every set Z that has property R, 𝑌 ⊆ 𝑍.

Defining a set inductively
Given a domain set 𝑋, a core set 𝐶 and a set of operations 𝑃 ,

𝐼(𝑋, 𝐶, 𝑃 ) is the minimal subset of 𝑋 that
▶ contains 𝐶, and
▶ is closed under 𝑃 .

Example 1: Inductively defined sets
Consider the domain set, the core set, and the set of operations
defined below.
▶ The domain set X = ℝ (the set of real numbers)
▶ The core set C = {0}.
▶ The set of operations P = {𝑓(𝑥) = 𝑥 + 1}
CQ: What set does this define?
(A) The set of natural numbers {0, 1, 2, ...}.
(B) The set of even natural numbers {0, 2, ...}.
(C) The set of integers {..., −2, −1, 0, 1, 2, ...}.
(D) The set of even integers {..., −2, 0, 2, ...}.
(E) The set of real numbers.

Example 2: Inductively defined sets
Consider the domain set, the core set, and the set of operations
defined below.
▶ The domain set X = ℝ (the set of real numbers)
▶ The core set C = {0, 2}.
▶ The set of operations P =
{𝑓1(𝑥, 𝑦) = 𝑥 + 𝑦, 𝑓2(𝑥, 𝑦) = 𝑥 − 𝑦}
CQ: What set does this define?
(A) The set of natural numbers {0, 1, 2, ...}.
(B) The set of even natural numbers {0, 2, ...}.
(C) The set of integers {..., −2, −1, 0, 1, 2, ...}.
(D) The set of even integers {..., −2, 0, 2, ...}.
(E) The set of real numbers.

Well-formed propositional formulas
Define the set of well-formed propositional formulas inductively.

▶ 𝑋 = the set of finite sequences of symbols in 𝐿𝑝 .
▶ 𝐶 = the set of propositional variables.
▶ 𝑃 = {𝑓1 (𝑥) = (¬𝑥), 𝑓2 (𝑥, 𝑦) = (𝑥 ∗ 𝑦)}
where ∗ is one of ∧, ∨, →, ↔.

Structural induction on 𝐼(𝑋, 𝐶, 𝑃 )
Claim: Every element of the set 𝐼(𝑋, 𝐶, 𝑃 ) has the property 𝑅.

Proof:
▶ Base case: Prove that 𝑅 holds for every element in the core
set 𝐶.
▶ Inductive case: Prove that for every operation 𝑓 ∈ 𝑃 of arity
𝑘 and any 𝑦1 , ..., 𝑦𝑘 ∈ 𝐼(𝑋, 𝐶, 𝑃 ) such that 𝑅(𝑦1 ), ..., 𝑅(𝑦𝑘 ),
𝑅(𝑓(𝑦1 , ..., 𝑦𝑘 )) holds.

By the end of the lecture, you should be able to


Lec03 Prop Induction Nosol

Uploaded by

Copyright:

Available Formats

Lec03 Prop Induction Nosol

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec03 Prop Induction Nosol

Uploaded by

Copyright:

Available Formats

Propositional Logic:

CS 245 Logic and Computation Fall 2019 Alice Gao 1 / 25

Inductively defined sets

Revisiting the learning goals

CS 245 Logic and Computation Fall 2019 Alice Gao 2 / 25

By the end of the lecture, you should be able to

CS 245 Logic and Computation Fall 2019 Alice Gao 3 / 25

The propositional language 𝐿𝑝 consists of three classes of symbols:

CS 245 Logic and Computation Fall 2019 Alice Gao 4 / 25

CS 245 Logic and Computation Fall 2019 Alice Gao 5 / 25

Inductively defined sets

Revisiting the learning goals

CS 245 Logic and Computation Fall 2019 Alice Gao 6 / 25

Does every well-formed formula have a unique meaning? Yes.

CS 245 Logic and Computation Fall 2019 Alice Gao 7 / 25

We may want to prove other properties of well-formed formulas.

CS 245 Logic and Computation Fall 2019 Alice Gao 8 / 25

Learning goals on structural induction:

CS 245 Logic and Computation Fall 2019 Alice Gao 9 / 25

Theorem: For every well-formed propositional formula 𝜑, 𝑃 (𝜑) is

CS 245 Logic and Computation Fall 2019 Alice Gao 10 / 25

CS 245 Logic and Computation Fall 2019 Alice Gao 11 / 25

By the principle of structural induction, 𝑃 (𝜑) holds for every

CS 245 Logic and Computation Fall 2019 Alice Gao 12 / 25

1. Why is the definition of a well-formed formula recursive?

CS 245 Logic and Computation Fall 2019 Alice Gao 13 / 25

Problem 1: Every well-formed formula has at least one

Problem 2: Every well-formed formula has an equal number of

Problem 3: Every proper prefix of a well-formed formula has more

CS 245 Logic and Computation Fall 2019 Alice Gao 14 / 25

Inductively defined sets

Revisiting the learning goals

CS 245 Logic and Computation Fall 2019 Alice Gao 15 / 25

Structural induction is an important concept and it does not only

Let’s look at some structural induction examples.

CS 245 Logic and Computation Fall 2019 Alice Gao 16 / 25

▶ List all the elements in the set. Example: 𝐴 = {1, 2, 3, 4}.

CS 245 Logic and Computation Fall 2019 Alice Gao 17 / 25

An inductively definition of a set consists of three components:

CS 245 Logic and Computation Fall 2019 Alice Gao 18 / 25

A set Y is closed under a set of operations P iff applying any

A set Y is a minimal set with respect to a property R if

CS 245 Logic and Computation Fall 2019 Alice Gao 19 / 25

Given a domain set 𝑋, a core set 𝐶 and a set of operations 𝑃 ,

CS 245 Logic and Computation Fall 2019 Alice Gao 20 / 25

CS 245 Logic and Computation Fall 2019 Alice Gao 21 / 25

CS 245 Logic and Computation Fall 2019 Alice Gao 22 / 25

Define the set of well-formed propositional formulas inductively.

CS 245 Logic and Computation Fall 2019 Alice Gao 23 / 25

Claim: Every element of the set 𝐼(𝑋, 𝐶, 𝑃 ) has the property 𝑅.

CS 245 Logic and Computation Fall 2019 Alice Gao 24 / 25

By the end of the lecture, you should be able to

CS 245 Logic and Computation Fall 2019 Alice Gao 25 / 25

You might also like