Алгоритм построения с.Д.Н.Ф. При помощи равносильных преобразований.

1. Заменить все элементарные булевы функции формулами в базисе {, , }.

2. Применяя правила де Моргана, перейти в полученной формуле от отрицаний над функциями к отрицаниям над переменными.

3. Применить законы дистрибутивности.

4. Сократить полученную д.н.ф., используя законы склеивания, поглощения и идемпотентности.

5. Если элементарная конъюнкция не содержит x_i, умножить ее на и применить законы дистрибутивности и идемпотентности.

Алгоритм построения с.К.Н.Ф. По таблице значений функции.

1. Выбрать строку, в которой функция равна 0.

2. Построить элементарную дизъюнкцию, включая в нее с отрицанием те переменные, которые в этой строке равны 1.

3. Перейти к следующей строке таблицы, на которой функция равна 0.

4. После перебора всех строк составить с.к.н.ф. из полученных дизъюнкций.

Алгоритм построения с.К.Н.Ф. При помощи равносильных преобразований.

1. Заменить все элементарные булевы функции формулами в базисе {, , }.

2. Применяя правила де Моргана, перейти в полученной формуле от отрицаний над функциями к отрицаниям над переменными.

3. Применить законы дистрибутивности.

4. Сократить полученную к.н.ф., используя законы склеивания, поглощения и идемпотентности.

5. Если элементарная дизъюнкция не содержит x_i, то добавиь и применить законы дистрибутивности и идемпотентности.

Задачи

11. Представить в виде совершенной д.н.ф. функцию:

1. ;

2. _f=(0110110010000010);

1. ;

2. _f=(1001010101000001);

1. ;

2. _f=(1101100100000100);

1. 

2. _f=(0100100011000010);

1. ;

2. _f=(1000011100110001);

1. ;

2. _f=(1100100010010011);

1. ;

2. _f=(1011001000001001);

1. ;

2. _f=(0010101010000010);

1. ;

2. _f=(0101010100000100);

1. ;

2. _f=(1010101000001000).

12. Представить в виде совершенной к.н.ф. функцию:

1. _f=(0101111101110011);

2. ;

1. _f=(0110111011100101);

2. ;

1. _f=(1101101100001001);

2. ;

1. _f=(0110100101111011);

2. ;

1. _f=(1101001011110110);

2. ;

1. _f=(1010010111101101);

2. ;

1. _f=(0100101111011011);

2. ;

1. _f=(1001011110110110);

2. ;

1. _f=(0010111101101101);

2. ;

1. _f=(0101111011011010);

2. .

13. С помощью эквивалентных преобразований построить д.н.ф. функции:

    1. ;

    2. ;

    3. ;

    4. ;

    5. ;

    6. ;

    7. ;

    8. ;

    9. ;

    10. .

14. С помощью эквивалентных преобразований построить к.н.ф. функции:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. .

15. Построить из заданной д.н.ф. функции ее с.д.н.ф.:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. .

16. Построить из заданной к.н.ф. функции ее с.к.н.ф.:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. .

17. Перейти от к.н.ф. функции к ее д.н.ф.:

    1. ;

    2. ;

    3. ;

    4. ;

    5. ;

    6. ;

    7. ;

    8. ;

    9. ;

    10. .

18. Перейти от д.н.ф. функции к ее к.н.ф.:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;