ECS 20 Discrete Math: Discussion 2 Answers
1. State the order of precedence for the logical operators ∧, ∨, ¬, and →.
¬>∧>∨>→
2. Write down a truth table for the formula = ¬ ∧ (¬ → )
¬ ¬→ 00100 01111 10010 11010
Is ¬ ∧ (¬ → ) logically equivalent to ¬ → ? No.
Re-write ¬ ∧ (¬ → ) using the least number of logical operators. ¬ ∧
3. State DeMorgan’s Law. ¬( ∧ ) = ¬ ∨ ¬
4. Translate the following sentences into a formula of sentential logic: “A country must shut down the government if it has a political deadlock and its head of state does not negotiate. An exception is made for European and Communist countries.”
Use HasPoliticalDeadlock, HeadOfStateNegotiates, European, Communist, ShutDownGovt in your answer.
HasPoliticalDeadlock ∧ ¬HeadOfStateNegotiates ∧ ¬European ∧ ¬Communist → ShutDownGovt
ECS 20 Discrete Math: Discussion 2 Problem Set 2 notes
1. Cut and shuffle in your proposed number of moves to see if you can indeed
reach .
2. Treatifsthenpelseqlikecode.Itisthesameasifs?p:qor
if (s) {
output = p;
} else {
output = q;
}
3. A mux (multiplexor) is a common device in circuit design that selects one signal to output from multiple inputs.
4. You need not define variables for the various conditions. Use words or phrases like in #4 of the mock quiz for the various conditions to formulate the answer.
5. You may define variables, for example , to mean that A is guilty (copied). A student cannot be both guilty and innocent, though there may not be enough information to show either way. A student can only be completely truthful or completely lying.
6. Recall that {∧, ∨, ¬} is logically complete.
7. A party function returns 1 when the input contains an odd number of ones. Note: an earlier version of this assignment contained a non-essential typo for the parity function formula.