2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Дискретная математика. Построение СКНФ, СДНФ
Сообщение20.03.2007, 19:13 


20/03/07
8
Помогите построить СКНФ. позарез нужно.

Помогите понять как это решается.
Я таблицу построил а чё из неё писать не пойму.
а завтра здавать нужно или педсовет по задолжностям.


P.S |- я поставил как знак «НЕ»,
X\wedge(|Y\vee Z)\vee Y\wedge(Z\vee |X)

 Профиль  
                  
 
 
Сообщение20.03.2007, 20:18 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Если таблицу истинности составили, то все тривиально. Алгоритм такой:
1. Берете итоговый столбец этой таблицы и выбираете строчки, в которых в этом столбце стоят нули. (1, 2, 7)
2. Для каждой из таких строк в дизъюнкт включаете все переменные с отрицанием, если они в этой строке равны 1 и без него, если равны нулю.
3. Все полученные дизъюнкты связываете конъюнкцией и СКНФ готова.
P.S. для контроля таблица истинности следующая:
$\\0000\\0010\\0101\\0111\\1001\\1011\\1100\\1111$
(последний столбец - итог, пропозиционные переменные идут в порядке $XYZ$)

 Профиль  
                  
 
 
Сообщение20.03.2007, 20:30 


20/03/07
8
а попонятнее можно? Я просто не понимаю как куда и что подставлять. Я даже с методичкой дискретку не понимаю. А тут ещё в другом задании надо семантические таблицы строить.(короче урок этот для меня тёмный лес)

 Профиль  
                  
 
 
Сообщение20.03.2007, 20:32 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
В каком месте конкретно непонятно?

 Профиль  
                  
 
 
Сообщение20.03.2007, 20:41 


20/03/07
8
вообще непонятно.
я незнаю как её после записывать.
Например в методичке записана формула:
x\vee y\wedge(x\vee |y)
после таблицы
000
010
101
111

у них получается что скнф =
(x\vee y)\wedge(x\vee |y)

c какого фига там взялся (x\vee y) не понимаю.
мне показалось что из начального примера перенесли скобки подставив.
а окозалось они это вычислили откудато, а вот откуда я так и не понял.

 Профиль  
                  
 
 
Сообщение20.03.2007, 21:01 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Для данной таблицы итоговый столбец
$\\0\\0\\1\\1$
Согласно алгоритму (п.1) берем строки, в которых в итоговом столбце стоят нули, т.е.
$\\000\\010$
по п.2 для строки $00$ (исключил нуль итогового столбца) ,берем с отрицанием только те переменные, которые равны 1 - здесь таких нет, поэтому все берем без отрицания и связываем дизъюнкцией, т.е. $x\vee y$
для строки $01$ - вторую переменную нужно взять с отрицанием, т.е. $x\vee \overline y$, а дальше все связываем конъюнкцией $(x\vee y)\wedge (x \vee \overline y)$

 Профиль  
                  
 
 
Сообщение20.03.2007, 21:06 


20/03/07
8
можно это пронимать что мой пример решается так?

(x\vee y\vee z)\wedge (x\vee y\vee |z)\wedge (|x\vee |y\vee z)

 Профиль  
                  
 
 
Сообщение20.03.2007, 21:09 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Да, это правильно.

 Профиль  
                  
 
 
Сообщение20.03.2007, 21:13 


20/03/07
8
Супер.
Спасибо что помог.

 Профиль  
                  
 
 Проверьте СДНФ и СКНФ булевой функции (диск. математика)
Сообщение05.05.2009, 20:37 


04/04/08
481
Москва
Найти СДНФ и СКНФ булевой функции $$f(x_1,x_2,x_3)$$.
Функция задана указанием номеров наборов значений переменных на которых она равна нулю. Наборы нумеруются числами от 0 (набор (0,0,0)) до 7 (набор (1,1,1)).
$$f :1,3,6$$

Решение:

$$1_{(10)}=001_{(2)}$$
$$3_{(10)}=011_{(2)}$$
$$6_{(10)}=110_{(2)}$$

Таблица истинности:
$$x_1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 $$
$$x_2 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 $$
$$x_3 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 $$
$$f | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1$$

$$N_f=\{000,010,100,101,111\}$$
СДНФ: $$\bar x_1\bar x_2\bar x_3\vee \bar x_1 x_2\bar x_3\vee x_1\bar x_2\bar x_3\vee x_1\bar x_2 x_3\vee x_1 x_2 x_3$$

$$N_f=\{001,011,110\}$$
СКНФ: $$(x_1\vee x_2\vee \bar x_3)\&(x_1\vee \bar x_2\vee \bar x_3)\&(\bar x_1\vee \bar x_2\vee x_3)$$

 Профиль  
                  
 
 
Сообщение06.05.2009, 10:36 
Заслуженный участник


12/07/07
4466
У меня получились такие же ответы.


Тема "Проверьте СДНФ и СКНФ..." соединена с близкой темой "Помогите построить СКНФ...".

 Профиль  
                  
 
 
Сообщение06.05.2009, 11:03 
Заслуженный участник


18/03/07
1068
juna писал(а):
в дизъюнкт включаете все переменные с отрицанием

Объявляю holywar :).

Имхо, тут лучше говорить «элементарная дизъюнкция». Ибо под «дизъюнктами» есть соблазн понимать то, что объединяется через дизъюнкцию, а не результат этого объединения. Те гражданcкие, которые говорят «хорновский дизъюнкт» вместо «хорновской дизъюнкции», должны быть расстреляны в первую очередь :).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group