Thread: Minimize the function in the basis of CNF in two ways

1. Minimize the function in the basis of CNF in two ways

Hi Guys!
I have a small question. The day before yesterday got the job on Discrete Mathematics:
1. Minimize the function in the basis of CNF in two ways;
2. Show the minimum function in the bases and Schaeffer Pierce;
The function itself: 1019
I cannot understand how to do the first task (What are two ways to minimize? How to do it?).
Thanks!

2. Re: Minimize the function in the basis of CNF in two ways

We need to clarify some definitions. What does it mean to minimize a function "in the basis of CNF": to give the shortest formula using the connectives from CNF, or to give the shortest CNF? What does it mean to show the minimum function "in the bases"? What is "Schaeffer Pierce"? Do you mean to express the function using Sheffer stroke and Peirce arrow?

A usual way to minimize functions is using a Karnaugh map. Apparently, Quine–McCluskey algorithm is functionally identical to Karnaugh mapping (Wikipedia). Another possibility is that there are two shortest CNFs (or DNFs) with the same number of connectives (or literals). Finally, maybe the two ways refers to the way you show the equivalence of the original and the minimum function: using truth tables and the laws of Boolean algebra.

3. Re: Minimize the function in the basis of CNF in two ways

Originally Posted by emakarov
We need to clarify some definitions. What does it mean to minimize a function "in the basis of CNF": to give the shortest formula using the connectives from CNF, or to give the shortest CNF? What does it mean to show the minimum function "in the bases"? What is "Schaeffer Pierce"? Do you mean to express the function using Sheffer stroke and Peirce arrow?

A usual way to minimize functions is using a Karnaugh map. Apparently, Quine–McCluskey algorithm is functionally identical to Karnaugh mapping (Wikipedia). Another possibility is that there are two shortest CNFs (or DNFs) with the same number of connectives (or literals). Finally, maybe the two ways refers to the way you show the equivalence of the original and the minimum function: using truth tables and the laws of Boolean algebra.
Sorry for the incorrect question!

To give the shortest CNF, then submit these minimal functions using Sheffer stroke and Peirce arrow.
I am very confused by this function 1019.
Thanks!

4. Re: Minimize the function in the basis of CNF in two ways

Originally Posted by TheOneTwo
I am very confused by this function 1019.Thanks!
My guess is that 1019 has to be written in binary to get the column of values in a truth table with 4 inputs, as described here in Wikipedia. After that, you need to construct a Karnaugh map and use it to build a CNF.

5. Re: Minimize the function in the basis of CNF in two ways

Hi!
I've done this:

1019 = 509•2 + 1
509 = 254•2 + 1
254 = 127•2 + 0
127 = 63•2 + 1
63 = 31•2 + 1
31 = 15•2 + 1
15 = 7•2 + 1
7 = 3•2 + 1
3 = 1•2 + 1
We obtain: 1111111011

The function receives one 0, is this normal?
How do I use this to construct the truth table?

Thanks!