ISI2017-PCB-CS-7-a

Question

Show that $\{1,A \bar{B}\}$ is functionality complete, i.e., any Boolean function with variables $A$ and $B$ can be expressed using these two primitives.

Comments

Detailed Video Solution: https://www.youtube.com/watch?v=XmmkE4yRk5c&t=3795s

 

Functional Completeness Complete Playlist: Functional Completeness Complete Playlist

Answer 1

We have $1$ and $AB'$.

$F(A,B) = AB'$

$F(1,B) = 1.B' = B.$

$F(A,B') = A.(B')' = AB$

We can $ [*,’]$ so its functionally complete.

Answer 2

Detailed Video Solution: https://www.youtube.com/watch?v=XmmkE4yRk5c&t=3795s 

$S = \{ 1, f(A,B) = A \bar{B} \}$ is functionally complete.

---

Proof 1: By creating $\{NOT, AND \}$ from $S:$

Creating "NOT": $f(1,B) =  \bar{B} $ ; So we can create "NOT" operation using $S.$

Creating "AND": $f( A, f(1,B) ) = AB$ ; So we can create "AND" operation using $S.$

Since we create $\{NOT, AND \}$ from $S$, So, $S$ is functionally complete.

---

Proof 2: Using Post's functional completeness theorem:

$S = \{ 1, A \bar{B} \}$

1. "$1$" is Not 0-preserving. 

2. $A \bar{B} $ is Not 1-preserving. 

3. $A \bar{B} $ is Not Self-Dual. "$1$" is also Not Self-Dual.  

4. $A \bar{B} $ is Not Linear.

5. $A \bar{B} $ is Not Monotonic.

So, by Post's theorem, $S$ is Functionally Complete. 

Detailed Video Solution: https://www.youtube.com/watch?v=XmmkE4yRk5c&t=3795s 

---

Functional Completeness Complete Playlist: Functional Completeness Complete Playlist