Mathematics for Computer Science

3.7. References 67

Problems for Section 3.3

Practice Problems

Problem 3.8.
Indicate whether each of the following propositional formulas is valid (V), satis-
fiable but not valid (S), or not satisfiable (N). For the satisfiable ones, indicate a
satisfying truth assignment.

MIMPLIESQ

MIMPLIES.PORQ/

MIMPLIESŒMAND.P IMPLIESM/ç

.PORQ/IMPLIESQ

.PORQ/IMPLIES.PANDQ/

.PORQ/IMPLIESŒMAND.P IMPLIESM/ç

.PXORQ/IMPLIESQ

.PXORQ/IMPLIES.PORQ/

.PXORQ/IMPLIESŒMAND.P IMPLIESM/ç

Problem 3.9.
Prove that the propositional formulas

PORQORR

and

.PAND NOT.Q//OR.QAND NOT.R//OR.RAND NOT.P//OR.PANDQANDR/:

are equivalent.

Problem 3.10.
Prove by truth table thatORdistributes overAND, namely,

POR.QANDR/ is equivalent to .PORQ/AND.PORR/ (3.26)