ECS 20 Discrete Math: Discussion 3, Mon 10/14/2013
To express a Boolean expression in CNF from a truth table, for example
𝐴𝐵𝑋 000 011 100 111
Write an equation in terms of what 𝑋 cannot be using the 0-rows. In this example 𝑋 cannot be 𝐴̅𝐵̅ and it cannot be 𝐴𝐵̅:
̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅ 𝑋 = ( 𝐴 ̅ 𝐵̅ ) ( 𝐴 𝐵̅ )
̅̅̅̅ ̅ ̅
Use De Morgan’s Law 𝐴𝐵 = 𝐴 ∨ 𝐵 on each clause to achieve OR relations:
Write a CNF formula for X and Y.
𝐴𝐵𝐶𝑋𝑌 00000 00101 01010 01110 10010 10101 11001 11111
𝑋 = (𝐴 ∨ 𝐵)(𝐴̅ ∨ 𝐵)
̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅
𝑋 = (𝐴𝐵𝐶) (𝐴𝐵𝐶) (𝐴𝐵𝐶) (𝐴𝐵𝐶)
̅̅ ̅̅̅
𝑋 = (𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)
̅ ̅̅̅
𝑌 = (𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)(𝐴 ∨ 𝐵 ∨ 𝐶)
Complete the following table, answering T or F given the universe of discourse indicated. N denotes all positive integers. (Z on PS3 denotes all integers.)
RN
TT FF FF TF TF FT F T
∃𝑥∃𝑦(𝑥+𝑦=10) ∀𝑥∀𝑦(𝑥+𝑦=10) ∃𝑥∀𝑦(𝑥+𝑦=10) ∀𝑥∃𝑦(𝑥+𝑦=10) ∀𝑥∃𝑦(𝑥 + 𝑦 < 0) ∃𝑥∀𝑦(𝑥 + 𝑦 ≥ 0) ∀𝑥(𝑥<5→∀𝑦(𝑦<𝑥→𝑦<4))
Write each of the following sentences into formulas of quantification logic, introducing predicates as needed.
a) There is someone in this discussion who did not have breakfast.
Let the universe of discourse be people. D(x) be in this discussion. B(x) had breakfast.
∃𝑥(𝐷(𝑥) ∧ ¬𝐵(𝑥))
b) Every ECS 20 student likes programming, but some ECS 20 students don’t like math.
Let the universe of discourse be ECS 20 students. P(x) likes programming. M(x) likes math.
∀𝑥 𝑃(𝑥) ∧ ∃𝑦 ¬𝑀(𝑦))
Negate each of the following statements. Recall that
¬∀𝑥 𝑝(𝑥) ≡ ∃𝑥 ¬𝑝(𝑥) and ¬∃𝑥 𝑝(𝑥) ≡ ∀𝑥 ¬𝑝(𝑥)
a) ∃𝑥∀𝑦 𝑝(𝑥, 𝑦) negates to ∀𝑥∃𝑦¬𝑝(𝑥, 𝑦)
b) ∀𝑥∀𝑦 𝑝(𝑥, 𝑦) negates to ∃𝑥∃𝑦¬𝑝(𝑥, 𝑦)
c) ∃𝑥∃𝑦∀𝑧 𝑝(𝑥, 𝑦, 𝑧) negates to ∀𝑥∀𝑦∃𝑧¬𝑝(𝑥, 𝑦, 𝑧)
d) ∀𝑥∃𝑦 (𝑝(𝑥, 𝑦) ∧ ¬𝑞(𝑥, 𝑦)) negates to ∃𝑥∀𝑦¬(𝑝(𝑥, 𝑦) ∧ ¬𝑞(𝑥, 𝑦)) Apply De Morgan’s Law: ∃𝑥∀𝑦(¬𝑝(𝑥, 𝑦) ∨ 𝑞(𝑥, 𝑦))
e) (∃𝑥 > 10)(∃𝑦) (𝑥 + 𝑦 = 𝑝(𝑥, 𝑦)) negates to (∀𝑥 > 10)(∀𝑦)¬(𝑥 + 𝑦 = 𝑝(𝑥, 𝑦)) Apply negation: (∀𝑥 > 10)(∀𝑦)(𝑥 + 𝑦 ≠ 𝑝(𝑥, 𝑦))
f) ∃𝑥∃𝑦 (𝑝(𝑥) ↔ 𝑝(𝑦)) negates and expands to ∀𝑥∀𝑦 ¬[(𝑝(𝑥) → 𝑝(𝑦)) ∧ (𝑝(𝑦) → 𝑝(𝑥))]
𝑝(𝑥) → 𝑝(𝑦) ≡ ¬𝑝(𝑥) ∨ 𝑝(𝑦): ∀𝑥∀𝑦 ¬[(¬𝑝(𝑥) ∨ 𝑝(𝑦)) ∧ (¬𝑝(𝑦) ∨ 𝑝(𝑥))] Apply De Morgan’s Law: ∀𝑥∀𝑦 [¬(¬𝑝(𝑥) ∨ 𝑝(𝑦)) ∨ ¬(¬𝑝(𝑦) ∨ 𝑝(𝑥))] Apply De Morgan’s Law: ∀𝑥∀𝑦 [(𝑝(𝑥) ∧ ¬𝑝(𝑦)) ∨ (𝑝(𝑦) ∧ ¬𝑝(𝑥))]
NAND (↑) is logically complete.
𝐴 ↑ 𝐵 = ¬(𝐴 ∧ 𝐵). The truth table for ↑:
𝐴𝐵𝐴∧𝐵𝐴↑𝐵 0001 0101 1001 1110
Recall that {∧, ∨, ¬} is logically complete.
To represent ¬ with ↑, consider the fact that a literal is equivalent to it ANDing itself, i.e.
𝐴 = 𝐴 ∧ 𝐴:
by definition of ↑; ¬ is achieved. Now consider representing ∧ with ↑ :
¬𝐴 = ¬(𝐴 ∧ 𝐴) =𝐴↑𝐴
𝐴 ∧ 𝐵 = ¬¬(𝐴 ∧ 𝐵) = ¬(𝐴 ↑ 𝐵)
= (𝐴 ↑ 𝐵) ↑ (𝐴 ↑ 𝐵)
so ∧ is achieved.
Finally consider representing ∨ with ↑, starting with De Morgan’s Law:
𝐴 ∨ 𝐵 = ¬(¬𝐴 ∧ ¬𝐵) = ¬[(𝐴 ↑ 𝐴) ∧ (𝐵 ↑ 𝐵)] = (𝐴 ↑ 𝐴) ↑ (𝐵 ↑ 𝐵)
by definition of ↑. So ∨ is achieved. Hence {↑} is logically complete.
For what the NAND gate looks like, and for the equivalent NAND circuits of NOT, AND, and OR circuits, visit http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html#c4