Задачи и упражнения по функциям алгебры логики 1 страница

Теорема о полной в Рk системе функций

Cистема функций { max (x ₁, x ₂), min (x ₁, x ₂), 0, 1,..., k –1, J ₀(x), J ₁(x),..., J_{k -1}(x)} является полной в Р_k и любая функция f (x ₁,..., x_n) Î P_k выражается формулой над этой системой следующим образом:

.

Эта формула есть своеобразный аналог СДНФ.

Доказательство. Покажем справедливость этой формулы на любом произвольном наборе (a ₁,..., a_n). Слева имеем f (a ₁,..., a_n). Справа имеем .

Если для какого-нибудь j из {1, 2,..., n } i_j ¹ a_j, то (a_j) = 0 и min [ J (a ₁), (a ₂), …, (a_n), f (i ₁,.., i_n)] = 0. Рассмотрим набор (i ₁,..., i_n), где i ₁ = a ₁, i ₂ = a ₂,..., i_n = a_n, тогда J (a ₁) = k –1, J (a ₂) = k –1,.., J (a_n) = k –1 и min [ J (a ₁),..., J (a_n) f (a ₁, …, a_n).] = min [(k –1),..., (k –1), f (a ₁, …, a_n).] = f (a ₁, …, a_n), но тогда Так как набор (a ₁,..., a_n) произвольный и равенство на нем справедливо, то формула верна. В этой формуле использованы функции J_i (x), (i = 0,..., k –1), min (x ₁ x ₂), max (x ₁ x ₂) и константы 0,..., k –1, так как функция f (i ₁,..., i_n) есть число из {0, 1,..., k –1}.

При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

1. – коммутативность связки *, где символ * является общим обозначением для связок &, Ú, Å, ~, |, ¯.

2. – ассоциативность связки *, где *– общее обозначение для связок &,Ú,Å,~.

3. Дистрибутивность

а) – дистрибутивность конъюнкции относительно дизъюнкции;

б) – дистрибутивность дизъюнкции относительно конъюнкции;

в) – дистрибутивность конъюнкции относительно сложения по mod 2.

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

в) ; г) ; д) ;

8. а) ;

б) ; в) ;

9. а) ; б) .

1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :

1) , ;

2) ,

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы: 2), 6), 9), 10) – эквивалентны; 3), 7) – не эквивалентны.

2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) .

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

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

4) ;

9)

4. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g двойственной к функции f:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , ;

11) , ;

12) , .

Ответы: 4) , . Значит, g не двойственна к f. 6) – не является; 8),9),11) – является.

5. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции f, и убедитесь в том, что полученная формула эквивалентна формуле V:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

1)

2) ; 5) ; 10) .

6. Указать все фиктивные переменные у функции f:

1)

2)

3)

4)

5)

6)

Ответы:1)две фиктивные переменные; 3)одна фиктивная переменная; 5)фиктивные переменные x ₁ и x ₃.

7. Показать, что x ₁ – фиктивная переменная у функции f (реализовав для этой цели функцию f формулой, не содержащей явно переменную x ₁):

1) ;

2) ;

3) ;

4) 5) 6) 7)

8) 9) 10)

Ответы: 4),8),10) 9)

8. Выяснить, можно ли из функции f, отождествляя и переименовывая в ней переменные, получить функцию g:

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) , ;

8) , ;

9) , ;

10) , .

Ответы: 1),2),5),7),8),9),10)можно. 3),4),6)нельзя.

9. Представить в СДНФ следующие функции:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2) ; 4) , 7)

10. Представить в СКНФ следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1) ; 2) ; 6) ; 8)

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

:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

4)

10)

12. Используя эквивалентные преобразования, построить КНФ функции

:

1)

2) ;

3)

4)

5)

6)

7)

Ответы:

1)

3)

6)

13. Применяя преобразования вида и построить из заданной ДНФ функции ее совершенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

14. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

1)

5)

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

1)

2)

3)

4)

5)

6)

7)

Ответы:

3)

6)

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

Дата добавления: 2014-12-27