Mathematics for Computer Science

11.11. References 441

(b)The staff’s records show that each student is a member of at most 4 groups,
and all the groups have 4 or more members. That’s enough to guarantee there is a
proper delegate selection. Explain.

Problem 11.14.
LetbRbe the “implies” binary relation on propositional formulas defined by the rule
that
FbR G iff Œ.FIMPLIESG/is a valid formulaç: (11.4)

For example,.PANDQ/R Pb , because the formula.P ANDQ/IMPLIESP is
valid. Also, it is not true that.PORQ/bR Psince.PORQ/IMPLIESP is not
valid.

(a)LetAandBbe the sets of formulas listed below. Explain whybRis not a weak
partial order on the setA[B.

(b)Fill in theRbarrows fromAtoB.

A arrows B

Q

PXORQ

PORQ

PANDQ

PORQOR.PANDQ/

NOT.PANDQ/

P

(c)The diagram in part (b) defines a bipartite graphGwithL.G/DA,R.G/D
Band an edge betweenFandGiffFR Gb. Exhibit a subsetSofAsuch that both
SandASare nonempty, and the set N.S/of neighbors ofSis the same size as
S, that is,jN.S/jDjSj.

(d)LetGbe an arbitrary, finite, bipartite graph. For any subsetSL.G/, let
SWWDL.G/S, and likewise for anyMR.G/, letMWWDR.G/M. Suppose