Chapter 3 Logical Formulas68
Class Problems
Problem 3.11. (a)Verify by truth table that
.P IMPLIES Q/ OR.Q IMPLIES P/is valid.
(b)LetPandQbe propositional formulas. Describe a single formula,R, using
onlyAND’s,OR’s,NOT’s, and copies ofPandQ, such thatRis valid iffPandQ
are equivalent.
(c)A propositional formula issatisfiableiff there is an assignment of truth values
to its variables—anenvironment—which makes it true. Explain why
Pis valid iff NOT.P/isnotsatisfiable.(d)A set of propositional formulasP 1 ;:::;Pkisconsistentiff there is an envi-
ronment in which they are all true. Write a formula,S, so that the setP 1 ;:::;Pk
isnotconsistent iffSis valid.
Problem 3.12.
This problem^3 examines whether the following specifications aresatisfiable:
- If the file system is not locked, then
(a) new messages will be queued.
(b) new messages will be sent to the messages buffer.
(c) the system is functioning normally, and conversely, if the system is
functioning normally, then the file system is not locked.- If new messages are not queued, then they will be sent to the messages buffer.
- New messages will not be sent to the message buffer.
(a)Begin by translating the five specifications into propositional formulas using
four propositional variables:
LWWDfile system locked;
QWWDnew messages are queued;
BWWDnew messages are sent to the message buffer;
NWWDsystem functioning normally:(^3) Revised from Rosen, 5th edition, Exercise 1.1.36