Consider the following definition of monotone propositional formulas (these are

Question

Consider the following definition of monotone propositional formulas (these are basically formulas with only ANDs and ORs)

• A variable is a monotone formula

• If f1 and f2 are monotone formulas then (f1) ? (f2) is a monotone formula

• If f1 and f2 are monotone formulas then (f1) ? (f2) is a monotone formula

Suppose two models m1 and m2 are such that every variable that is true in m1 is also true in m2. Suppose f is a monotone formula. Prove, using structural induction, that if f(m1) is true, then so is f(m2). Also Prove that there exist boolean functions that cannot be represented by monotone formulas.

Explanation / Answer

Solution:

Base case:

If m1 is true then m2 is also true

now

Inductive case:

then f(m1) v f(m2)=> true v true is true

and f(m1) ^ f(m2)=> true ^ true is also true

If the boolean function contains negation, for example

the expression is

m1' + m2

then it cannot be represented by the monotone formula.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects