Дискретная математика. Построение СКНФ, СДНФ

[stricer]

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

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


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

[juna]

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

[stricer]

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

[juna]

В каком месте конкретно непонятно?

[stricer]

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

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

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

[juna]

Для данной таблицы итоговый столбец
$\\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)$

[stricer]

можно это пронимать что мой пример решается так?

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

[juna]

Да, это правильно.

[stricer]

Супер.
Спасибо что помог.

[rar]

Найти СДНФ и СКНФ булевой функции

$$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)$$

[GAA]

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


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

[luitzen]

juna писал(а):

в дизъюнкт включаете все переменные с отрицанием

Объявляю holywar .

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