Форум программистов, компьютерный форум, киберфорум
Наши страницы
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Altec
4 / 4 / 0
Регистрация: 31.01.2013
Сообщений: 19
1

Получить СДНФ

01.02.2013, 17:10. Просмотров 1007. Ответов 4
Метки нет (Все метки)

Доброго времени суток!
Помогите дорешать задачку.
Получить СДНФ для формулы ((X~Y)~Z)(1⊕XY)⊕XZ перейти к СКНФ.
Разделил для удобства формулу на 2 части: ((X~Y)~Z) и (1⊕XY)⊕XZ.
Решаю ((X~Y)~Z) используя равносильность алгебры высказываний A~B≡ABv(AB)' получаю
(XY v (XY)') ~ Z = (XY v (XY)') * Z v (XY v (XY)')' * Z'
далее применяя закон Де Моргана получаю
XYZ v (XY)'Z v ((XY)' * (XY)'') * Z' - тут возникает вопрос какой закон применить, чтобы дорешать?

Решаю (1⊕XY)⊕XZ используя A⊕B≡A(B)'v(A)'B получаю
(XY)' ⊕ XZ = (XY)'(XZ)' v XY XZ = XYZ v ((X)' v (Y)') ((X)' v (Z)') = XYZ v (X)' v (YZ)'
Вопрос какие здесь применяются законы XYZ v ((X)' v (Y)') ((X)' v (Z)') = XYZ v (X)' v (YZ)' ?

Добавлено через 9 часов 2 минуты
Вчера редактор формул не работал
http://www.cyberforum.ru/cgi-bin/latex.cgi?(XY\vee \bar{XY})\sim Z = (XY\vee \bar{XY})Z\vee\bar{(XY\vee \bar{XY})}\bar{Z}= <br />
XYZ\vee \bar{XY}Z\vee (\bar{XY}\bar{\bar{XY}})\bar{Z}

Добавлено через 8 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?(1\oplus XY)\oplus XZ = \bar{XY}\oplus XZ = \bar{XY}\bar{XZ}\vee XY XZ = <br />
XYZ\vee (\bar{X}\vee \bar{Y})(\bar{X}\vee \bar{Z}) = XYZ\vee \bar{X}\vee \bar{YZ}

Добавлено через 1 час 41 минуту
по 2й части, я так понимаю для http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{XY}\bar{XZ} упрощаем до http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{XYZ} т.к. по закону идемпотентности АА=А, так мы избавились от http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{X} далее применяем из равносильности алгебры высказываний дистрибутивный закон A(BC)=(AvB)(AvC) т.е. http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{XYZ}=(\bar{X}\vee \bar{Y})(\bar{X}\vee \bar{Z})
правильный ход мысли?

Добавлено через 5 часов 7 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x\sim y)\sim z применим http://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim B\equiv A\cdot B\vee \bar{A}\cdot \bar{B}
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x\cdot y\vee \bar{x}\cdot \bar{y})\sim z=(x\cdot y\vee \bar{x}\cdot \bar{y})\cdot z\vee \bar{(x\cdot y\vee \bar{x}\cdot \bar{y})}\cdot \bar{z} далее применим Дистрибутивный закон http://www.cyberforum.ru/cgi-bin/latex.cgi?A(B\vee C)\equiv AB\vee AC и закон Де Моргана http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A\vee B}\equiv \bar{A}\cdot \bar{B}
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee (\bar{x\cdot y}\cdot \bar{\bar{x}\cdot \bar{y}})\cdot \bar{z} теперь применим закон двойного отрицания http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{A}}\equiv A и закон Де Моргана http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A\cdot B}\equiv \bar{A}\vee \bar{B}
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee (\bar{x}\vee \bar{y})\cdot (x\vee y)\cdot \bar{z}
расскроем скобки используя закон отрицания http://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot \bar{A}\equiv 0
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee (\bar{x}\cdot y\vee x\cdot \bar{y})\cdot \bar{z} раскрываем скобки законом дистрибутивности и получаем 1ю часть СДНФ
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot \bar{z}\vee x\cdot \bar{y}\cdot \bar{z}

Добавлено через 2 часа 13 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?(1\oplus x\cdot y)\oplus x\cdot y применим http://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus B \equiv (A\cdot \bar{B})\vee (\bar{A}\cdot B) и закон поглощения http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{1}\equiv 0
http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{x\cdot y}\oplus x\cdot z=(\bar{x\cdot y}\cdot \bar{x\cdot z})\vee (\bar{\bar{x\cdot y}}\cdot x\cdot z) применим закон Де Моргана и закон двойного отрицания http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{A}}\equiv A
http://www.cyberforum.ru/cgi-bin/latex.cgi?(\bar{x}\vee \bar{y})\cdot (\bar{x}\vee \bar{z})\vee (x\cdot y\cdot x\cdot z) применим закон дистрибутивности и идемпотентности
http://www.cyberforum.ru/cgi-bin/latex.cgi?(\bar{x}\vee \bar{y})\cdot (\bar{x}\vee \bar{z})\vee (x\cdot y\cdot z)
http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{x}\vee \bar{y}\cdot \bar{z}\vee x\cdot y\cdot z
получили ДНФ

Добавлено через 19 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot \bar{z}\vee x\cdot \bar{y}\cdot \bar{z})\cdot (\bar{x}\vee \bar{y}\cdot \bar{z}\vee x\cdot y\cdot z) используя закон противоречия и идемпотентности раскрываем скобки
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot z\vee  \bar{x}\cdot \bar{y}\cdot z далее
http://www.cyberforum.ru/cgi-bin/latex.cgi?x\cdot y\cdot z\vee \bar{x}\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot z получили СДНФ

Добавлено через 23 минуты
выпишем недостающие конституенты
http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{f}=\bar{x}\cdot \bar{y}\cdot \bar{z}\vee x\cdot y\cdot \bar{z}\vee x\cdot \bar{y} \cdot \bar{z} \vee x\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot \bar{z}
применим отрицание
http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{f}}=\bar{\bar{x}\cdot \bar{y}\cdot \bar{z}\vee x\cdot y\cdot \bar{z}\vee x\cdot \bar{y} \cdot \bar{z} \vee x\cdot \bar{y}\cdot z\vee \bar{x}\cdot y\cdot \bar{z}}
вот она СКНФ
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x\vee y\vee z)\cdot (\bar{x}\vee \bar{y}\vee z)\cdot (\bar{x}\vee y\vee z)\cdot (\bar{x}\vee y\vee \bar{z})\cdot (x\vee \bar{y}\vee z)
Правильно ли я решил и как можно проверить?!?!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2013, 17:10
Ответы с готовыми решениями:

составить СДНФ

Минимизировать СДНФ
СДНФ f(x,y,z)=\bar{x}\bar{z}\bar{y}V\bar{x}y\bar{z}V\bar{x}yzVx\bar{y}\bar{z}Vx\bar{y}z. Как...

Найти СДНФ
помогите пожалуйста найти СДНФ по формуле ¬(Xv(Y↔¬Z))

СДНФ и СКНФ ФАЛ
Как записать СДНФ и СКНФ ФАЛ, задание в цифровой форме: f(x1...x4)=v(1,4,6,8,10,13,15)

найти СДНФ И СКНФ
Помогите пожалуйста найти СДНФ И СКНФ Для 01111000 01101010 10101000 01000111 01110010

4
Glimpse
9 / 9 / 8
Регистрация: 21.01.2013
Сообщений: 20
02.02.2013, 01:04 2
Чтобы проверить себя, постройте СДНФ данной формулы по таблице истинности.

Добавлено через 22 минуты
http://www.cyberforum.ru/cgi-bin/latex.cgi?f = ((x \sim y) \sim z)(1 \oplus xy) \oplus xz

1. http://www.cyberforum.ru/cgi-bin/latex.cgi?((x \sim y) \sim z)
2. http://www.cyberforum.ru/cgi-bin/latex.cgi?(1 \oplus xy)
3. http://www.cyberforum.ru/cgi-bin/latex.cgi?((x \sim y) \sim z)(1 \oplus xy)
4. http://www.cyberforum.ru/cgi-bin/latex.cgi?((x \sim y) \sim z)(1 \oplus xy) \oplus xz

x y z 1 2 3 4
0 0 0 0 1 0 0
0 0 1 1 1 1 1
0 1 0 1 1 1 1
0 1 1 0 1 0 0
1 0 0 1 1 1 1
1 0 1 0 1 0 1
1 1 0 0 0 0 0
1 1 1 1 0 0 1

У меня получилось, что http://www.cyberforum.ru/cgi-bin/latex.cgi?f = (\bar{x} \wedge \bar{y} \wedge z) \vee (\bar{x} \wedge y \wedge \bar{z}) \vee (x \wedge \bar{y} \wedge \bar{z}) \vee (x \wedge \bar{y} \wedge z) \vee (x \wedge y \wedge z)
1
Altec
4 / 4 / 0
Регистрация: 31.01.2013
Сообщений: 19
02.02.2013, 13:35  [ТС] 3
Цитата Сообщение от Glimpse Посмотреть сообщение
Чтобы проверить себя, постройте СДНФ данной формулы по таблице истинности.
Посоветуйте пожалуйста литературу!
у меня ошибка в том что не перевел ДНФ в СДНФ во второй части формулы, но даже если я перевожу в СДНФ все равно не получается при перемножении обоих частей с ответом который вы написали
0
Glimpse
9 / 9 / 8
Регистрация: 21.01.2013
Сообщений: 20
02.02.2013, 23:54 4
Altec, посмотрите внимательней на порядок действий.

Цитата Сообщение от Altec Посмотреть сообщение
Разделил для удобства формулу на 2 части: ((X~Y)~Z) и (1⊕XY)⊕XZ.
Нельзя разорвать формулу http://www.cyberforum.ru/cgi-bin/latex.cgi?f = ((x \sim  y) \sim z)(1 \oplus xy)\oplus xz на такие части, т.к. конъюнкция по приоритету стоит выше, чем сложение по модулю 2.
1
Altec
4 / 4 / 0
Регистрация: 31.01.2013
Сообщений: 19
03.02.2013, 12:30  [ТС] 5
Цитата Сообщение от Glimpse Посмотреть сообщение
Altec, посмотрите внимательней на порядок действий.
Ура!!! получилось!!! огромное спасибо
0
03.02.2013, 12:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2013, 12:30

проверить сокращение сднф
нужно проверить и исправить ошибки, сокращение сднф. Правило 5.18. Запрещено выкладывать задачи в...

Найти СКНФ и СДНФ
Добрый вечер Помогите пожалуйста найти СКНФ и СДНФ Думал успею разобраться что к чему......

Составление СДНФ и СКНФ
Составить СДНФ и СКНФ для:F=¬((x∨y)→¬z)∧(¬(x∨z)∧¬y)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru