3

A, a proposition in Propositional calculus is called "Monotonic" if when there is an assigning M s.t $$M\models{A}$$ any other assigning $M'$ that similar to $M$ on the True values but may change False values to True maintains $$M'\models{A}$$ Prove: A is logically equivalent to a proposition that built out of the connectives $\{\lor, \land\}$ if and only if A is Monotonic, not a contradiction and not a tautology.

I was able to prove one direction (with induction on the structure of A) but i'm having difficulties to prove the other direction (assuming A is monotonic...).

Thank you for helping!

dave
  • 705
  • 4
  • 16

1 Answers1

2

Let $V$ be the set of variables in the formula $A$, and consider the set $\Gamma$ of all of its subsets $X\subseteq V$ which makes $A$ valid w.r.t. the assigning $M_X:=\big\{(x\mapsto$"true"$)$ iff $x\in X\big\}$: $$\Gamma\ :=\ \{X\subseteq V\ \mid\ M_X\models A\}$$

(Alternatively, you can keep only the minimal nonempty elements of $\Gamma$, w.r.t. inclusion.)

Then let $B:=\displaystyle\bigvee_{X\in\Gamma}\left(\bigwedge_{x\in X}x\right)$, and verify that $A\Leftrightarrow B$, using the condition on $A$ for $(M\models B)\Rightarrow (M\models A)$.

Berci
  • 90,745
  • cool thanks alot – dave May 24 '14 at 22:57
  • 1
    You're welcome. – Berci May 24 '14 at 22:58
  • Do you have an advice how could i figure it out myself? thinking about that direction.... – dave May 24 '14 at 23:14
  • 2
    Since each formula is equivalent to its disjunctive normal form, we can assume that $A$ is already in disj.normal form, i.e. it is a disjunction of 'clauses'. Now negation should not be included, so each clause is of the form $\land_{x\in X}x$ for a set $X$ of plain (not negated) variables. Then collect, which clauses could be included in $A$... – Berci May 24 '14 at 23:32