The average size of a minimum defining set

Let \( \varphi \) be a formula in propositional logic with variables \( \mathcal{X}=\{x_1,...,x_n\} \). Let's use the following as the running example: \[ \varphi(x,y,z)=(x\to y)\wedge z. \]

This formula encapsulates facts about the states of the world. For example, ``if it snowed yesterday and no one cleared the snow from the sidewalk before night, in the morning the sidewalk will be icy''. This statement describes multiple possible states of the world: maybe it snowed yeseterday, maybe it didn't. In other words, this statement is a formula with multiple satisfying assignments: functions \( v:\mathcal{X}\to\{0,1\} \).

Let's say we both know \( \varphi \), but only I know the true state of the world, or the true satisfying assignment \( V \), which is \( V=(1,1,1) \), and I want you to learn the assignment too. The simplest method of communication I can use is sending you tuples \( (i,V(x_i)) \), one by one, until you know \( V \), and you reply with a bit indicating whether you know \( V \) or not. Our goal is to for you to learn \( V \), and for me to send the smallest number of messages.

If you don't do anything on your end besides receiving my messages and constructing \( V \) naively, I don't have a lot of choice -- I'll need to tell you the entirety of \( V \), namely send you \( n \) messages.

But what if you do something smarter?

\(\min(\log m,n)\).