Just enable partialSubmit for the Checkbox and integrate a ValueChangeListener like
Code:
public void checkboxChanged(ValueChangeEvent event) {
Boolean val = (Boolean)event.getNewValue();
if(!val) {
facesMessages.add("Value not Valid.");
}
}
May this helps you.
Greetz
Florian Hell