СДНФ, СКНФ

Равносильные формулы алгебры логики.

Важнейшие равносильности алгебры логики можно разбить на 3 группы:

1. Основные равносильности:

2. Равносильности выражающие одни логические операции через другие:

3. Равносильности выражающие основные законы алгебры логики:

3. Доказать равносильности:

а) построив таблицы истинности,

б) используя основные равносильности

1) ;

2)

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10)

11)

12)

13)

14)

15)

16) .

4. Используя основные равносильности алгебры логики докажите равносильность формул V и U:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

11) ,

12) ,

13) ,

14)

15)

16)

Пример 1. Пусть функция f (x ₁, x ₂, x ₃) задана таблицей истинности. Запишем ее в виде СДНФ.

x 1	x 2	x 3	f

Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f (x ₁, x ₂, x ₃) = = & x ₂& Ú x ₁& & Ú x ₁& x ₂& x _3.

Пример2. Пусть f (x ₁, x ₂, x ₃) = x ₁ (x ₂ (x ₃ ~ x ₁)). Представим ее в виде КНФ, для этого получим таблицу истинности.

x 1	x 2	x 3	x 3~ x 1	x 2 (x 3~ x 1)	f
0	0	0	1	1	1

Функция равна нулю только на наборе (1, 1, 0), поэтому

f (x ₁ x ₂ x ₃)= Ú Ú x ₃.

Пример3: Следующую формулу привести к СДНФ, предварительно приведя её равносильными преобразованиями к ДНФ: А=

Решение: Пример4: Следующую формулу привести к СКНФ, предварительно приведя её равносильными преобразованиями к КНФ: А= .

Решение:

5. Используя дистрибутивный закон перейти от заданной КНФ формулы А к ДНФ:

1)

2)

3)

4)

5)

6)

7)

6. Используя дистрибутивный закон перейти от заданной ДНФ формулы А к ее КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

7. Привести к ДНФ(СДНФ), КНФ(СКНФ) следующие формулы:

1)

2)

3) ;

4)

5)

6) ;

7) ;

8) ;

9) ;

10)

11) ;

12) ;

13) ;

14) ;

15)

16)

Приложения алгебры логики.

1. Приложения алгебра логики к релейно- контактным схем.

9. Найти функции проводимости следующих схем, если возможно упростить схемы:

Дата добавления: 2015-06-27