Автор Тема: Найти ДНФ, КНФ, СДНФ и СКНФ булевой функции  (Прочитано 3310 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Natali

  • Пользователь
  • Сообщений: 22
    • Просмотр профиля
а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”).

\(  \large (x \wedge (y \supset ( x \sim z)))' \)
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4946
  • Поблагодарили: 1571 раз(а)
    • Просмотр профиля
Найти ДНФ, КНФ, СДНФ и СКНФ булевой функции
« Ответ #1 : Октябрь 12, 2015, 10:31:32 pm »
Найдём ДНФ с помощью равносильных преобразований. Имеем:

1) так как \(  \large (x \wedge y)'=x' \vee y' \), то \(  \large (x \wedge (y \supset (x \sim z)))'=x' \vee (y \supset ( x \sim z))' \);

2) так как \(  \large x \supset y= x' \vee y \), то \(  \large x' \vee (y \supset ( x \sim z))'=x' \vee (y' \vee ( x \sim z))' \);

3) так как \(  \large (x \wedge y)'=x' \vee y' \), то \(  \large x' \vee (y' \vee ( x \sim z))'=x' \vee (y'' \wedge ( x \sim z)') \);

4) так как \(  \large x''=x \), то \(  \large x' \vee (y'' \wedge ( x \sim z)')=x' \vee (y \wedge ( x \sim z)') \);

5) так как \(  \large x \sim y=(x \supset y) \wedge (y \supset x) \), то \(  \large x' \vee (y \wedge ( x \sim z)')=x' \vee (y \wedge ((x \supset z) \wedge (z \supset x))') \);

6) так как \(  \large (x \wedge y)'=x' \vee y' \), то \(  \large x' \vee (y \wedge ((x \supset z) \wedge (z \supset x))')=x' \vee (y \wedge ((x \supset z)' \vee (z \supset x)')) \);

7) так как \(  \large x \supset y= x' \vee y \), то \(  \large x' \vee (y \wedge ((x \supset z)' \vee (z \supset x)'))=x' \vee (y \wedge ((x' \vee z)' \vee (z' \vee x)')) \);

8) так как \(  \large (x \vee y)'=x' \wedge y' \), то \(  \large x' \vee (y \wedge ((x' \vee z)' \vee (z' \vee x)'))=x' \vee (y \wedge ((x'' \wedge z') \vee (z'' \wedge x'))) \);

9) так как \(  \large x''=x \), то \(  \large x' \vee (y \wedge ((x'' \wedge z') \vee (z'' \wedge x')))=x' \vee (y \wedge ((x \wedge z') \vee (z \wedge x'))) \);

10) так как \(  \large x \wedge (y \vee z) =(x \wedge y) \vee (x \wedge z)  \) и \(  \large x \wedge y = y
\wedge x \), то \(  \large x' \vee (y \wedge ((x \wedge z') \vee (z \wedge x')))=x' \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \).

Итак, \(  \large x' \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \) - ДНФ функции \(  \large (x \wedge (y \supset (x \sim z))' \).

Здесь штрихом обозначено отрицание.

Используя найденную выше ДНФ, найдём СДНФ с помощью равносильных преобразований:

1) так как \(  \large x \wedge 1 = x \), то \(  \large  x' \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)=(x' \wedge 1) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \);

2) так как \(  \large 1= x \vee x' \), то \(  \large (x' \wedge 1) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) =(x' \wedge (y \vee y')) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \);

3) так как \(  \large x \wedge (y \vee z)=(x \wedge y) \vee (x \wedge z)  \), то \(  \large (x' \wedge (y \vee y')) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) =(x' \wedge y ) \vee( x' \wedge y' ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \);

4) так как  \(  \large x \wedge 1 = x \), то \(  \large (x' \wedge y ) \vee( x' \wedge y' ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)=(x' \wedge y \wedge 1 ) \vee( x' \wedge y' \wedge 1 ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \);

5) так как \(  \large 1=x \vee x' \), то \(  \large (x' \wedge y \wedge 1 ) \vee( x' \wedge y' \wedge 1 ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)= \\ =(x' \wedge y \wedge (z \vee z') ) \vee( x' \wedge y' \wedge (z \vee z') ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \)

6) так как \(  \large x \wedge (y \vee z)=(x \wedge y) \vee (x \wedge z)  \), то \(  \large (x' \wedge y \wedge (z \vee z') ) \vee( x' \wedge y' \wedge (z \vee z') ) \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)= \\ =(x' \wedge y \wedge z) \vee (x' \wedge y \wedge z')  \vee ( x' \wedge y' \wedge z) \vee (x' \wedge y' \wedge z')  \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z) \)

7) так как \(  \large x \vee x =x \), то \(  \large (x' \wedge y \wedge z) \vee (x' \wedge y \wedge z')  \vee ( x' \wedge y' \wedge z) \vee (x' \wedge y' \wedge z')  \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)= \\ =(x' \wedge y \wedge z) \vee (x' \wedge y \wedge z')  \vee ( x' \wedge y' \wedge z) \vee (x' \wedge y' \wedge z')  \vee (x \wedge y \wedge z') \)

Итак, \(  \large (x' \wedge y \wedge z) \vee (x' \wedge y \wedge z')  \vee ( x' \wedge y' \wedge z) \vee (x' \wedge y' \wedge z')  \vee (x \wedge y \wedge z')  \) - СДНФ функции \(  \large (x \wedge (y \supset (x \sim z)))' \).

Используя определения булевых функций, составим таблицу значений для булевой функции \(  \large (x \wedge (y \supset (x \sim z)))' \) и найдём СДНФ, а также СКНФ.
Чтобы найти СДНФ (СКНФ) по таблице значений булевой функции, нужно:
1) выбрать все те наборы значений переменных, на которых функция принимает значение 1 (0);
2) для каждого такого набора выписать совершенный конъюнктивный (дизъюнктивный) одночлен, принимающий значений 1 (0) на этом наборе и только на нём;
3) полученные совершенные конъюнктивные (дизъюнктивные) одночлены соединить знаками дизъюнкции (конъюнкции).

Итак, имеем:

1) \(  \large (x' \wedge y' \wedge z') \vee (x' \wedge y' \wedge z) \vee (x' \wedge y \wedge z') \vee (x' \wedge y \wedge z) \vee (x \wedge y \wedge z') \) - СДНФ;

2) \(  \large (x' \vee y \vee z) \wedge (x' \vee y \vee z') \wedge (x' \vee y' \vee z')  \) - CКНФ.

Найдём КНФ, зная, что \(  \large (x \wedge ( y \supset (x \sim z)))'=x' \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)  \) (это было доказано при отыскании ДНФ). Имеем:

1) так как \(  \large x \vee (y \wedge z) =(x \vee y) \wedge (x \vee z) \), \(  \large x' \vee x=1 \), \(  \large 1 \wedge x= x \), то \(  \large x' \vee (x \wedge y \wedge z') \vee (x' \wedge y \wedge z)=((x' \vee x) \wedge ( x' \vee y) \wedge (x' \vee z')) \vee  (x' \wedge y \wedge z)= \) \(  \large =(1 \wedge ( x' \vee y) \wedge (x' \vee z')) \vee (x' \wedge y \wedge z)=( ( x' \vee y) \wedge (x' \vee z')) \vee (x' \wedge y \wedge z) \)

2) так как \(  \large x \vee (y \wedge z)=(x \vee y) \wedge (x \vee z)  \), \(  \large x \vee x=x \), \(  \large x' \vee x =1 \), \(  \large x \wedge 1=x \), то \(  \large ( ( x' \vee y) \wedge (x' \vee z')) \vee (x' \wedge y \wedge z)=(x' \vee y \vee x') \wedge (x' \vee y \vee y) \wedge (x' \vee y \vee z) \wedge \\ \wedge (x' \vee z' \vee x') \wedge (x' \vee z' \vee y) \wedge (x' \vee z' \vee z)= \) \(  \large =(x' \vee y) \wedge (x' \vee y \vee z) \wedge (x' \vee z') \wedge (x' \vee z' \vee y) \)

3) так как \(  \large x \wedge (x \vee y)=x \), то \(  \large (x' \vee y) \wedge (x' \vee y \vee z) \wedge (x' \vee z') \wedge (x' \vee z' \vee y)=(x' \vee y) \wedge (x' \vee z') \)

Итак, \(  \large (x' \vee y) \wedge (x' \vee z') \) - КНФ функции \(  \large (x \wedge ( y \supset (x \sim z)))' \).

Зная КНФ, будем искать СКНФ, используя равносильные преобразования. Имеем:

1) так как \(  \large x \vee 1=x \), \(  \large 1=x' \wedge  x \), то \(  \large (x' \vee y) \wedge (x' \vee z')=(x' \vee y \vee 1) \wedge (x' \vee 1 \vee  z')= (x' \vee y \vee (z \wedge z')) \wedge (x' \vee (y \wedge y') \vee  z') \);

2) так как \(  \large x \vee (y \wedge z)=(x \vee y) \wedge (x \vee z) \), \(  \large x \wedge x=x \), то \(  \large (x' \vee y \vee (z \wedge z')) \wedge (x' \vee (y \wedge y') \vee  z')=(x' \vee y \vee z) \wedge (x' \vee y \vee z') \wedge (x' \vee y \vee z') \wedge (x' \vee y' \vee z')= \) \(  \large =(x' \vee y \vee z) \wedge (x' \vee y \vee z') \wedge (x' \vee y' \vee z') \)

Итак, \(  \large (x' \vee y \vee z) \wedge (x' \vee y \vee z') \wedge (x' \vee y' \vee z') \) - СКНФ функции \(  \large (x \wedge (y \supset (x \sim z)))' \).
 
Сказали спасибо: kakao, programmizd, dota2

Оффлайн Natali

  • Пользователь
  • Сообщений: 22
    • Просмотр профиля
Найти ДНФ, КНФ, СДНФ и СКНФ булевой функции
« Ответ #2 : Октябрь 13, 2015, 03:30:11 pm »
Спасибо огромное! :) :) :)