Hand-in @ lecture #3
1.1.50
Are these system specifications consistent?
Whenever the system software is being upgraded, users cannot access the file system. If users can access the file system, then they can save new files. If users cannot save new files, then the system software is not being upgraded.
Let \(p\), \(q\) and \(r\) denote the system software is being upgraded
, users can access the file system
and users can save new files
, respectively.
Then the propositions can be expressed in logic as \((p \rightarrow \lnot q) \land (q \rightarrow r) \land (\lnot r \rightarrow \lnot p)\).
The truth table for the propositions is shown below.
| \(p\) | \(q\) | \(r\) | \(\lnot p\) | \(\lnot q\) | \(\lnot r\) | \(p \rightarrow \lnot q\) | \(q \rightarrow r\) | \(\lnot r \rightarrow \lnot p\) | \((p \rightarrow \lnot q) \land (q \rightarrow r) \land (\lnot r \rightarrow \lnot p)\) |
|---|---|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F | T | T | F |
| T | T | F | F | F | T | F | F | F | F |
| T | F | T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T | F | F |
| F | T | T | T | F | F | T | T | T | T |
| F | T | F | T | F | T | T | F | T | F |
| F | F | T | T | T | F | T | T | T | T |
| F | F | F | T | T | T | T | T | T | T |
Since \((p \rightarrow \lnot q) \land (q \rightarrow r) \land (\lnot r \rightarrow \lnot p)\) have both true and false values, those system specifications are consistent.
1.2.6
Use a truth table to verify the first De Morgan law \(\lnot (p \land q) \equiv \lnot p \lor \lnot q\).
The truth table for De Morgan’s first law is shown below.
| \(p\) | \(q\) | \(\lnot p\) | \(\lnot q\) | \(p \land q\) | \(\lnot (p \land q)\) | \(\lnot p \lor \lnot q\) | |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F | |
| T | F | F | T | F | T | T | |
| F | T | T | F | F | T | T | |
| F | F | T | T | F | T | T |
The last two columns have same values in above truth table, as prescribed by De Morgan’s first law.
1.2.14
Determine whether \(( \lnot p \land (p \rightarrow q)) \rightarrow \lnot q\) is a tautology.
The subexpression \(\lnot p \land (p \rightarrow q)\) is a conditional statement without the condition, i.e. \(\lnot p \land (p \rightarrow q) \equiv q\).
The expression can therefore be simplified as \(q \rightarrow \lnot q\).
Since a conditional statement with a true condition cannot be false, \(q \rightarrow \lnot q\) is a contradiction, i.e. not a tautology.