СДНФ и СКНФ

[long3101]

Всем привет.
Завтра экзамен по мат.логике.
Более-менее разобрался, но не могу понять как построить СДНФ и СКНФ... Помогите понять...

Знаю, что точно будет в одном из заданий это. Нужно будет решить.

Я так понимаю дана будет ф-ция какая-то в задании?
Не могли бы вы пример привести. Я бы попробовал решить, а вы сказали, где ошибки. Мне просто проще так разобраться.


Спасибо.

[Nemiroff]

$$\overline{(x\vee \overline{y})} \rightarrow ((\overline{x}\oplus \overline{z})\vee(y\equiv \overline{zx}))$$

[Nimza]

(Оффтоп)

Даже в википедии написано, как строить

Вот ещё c этими функциями попробуйте.
1. Медиана (функция голосования): $xy \vee xz \vee yz$.
2. Счётчик чётности от переменных $x_1,\ldots,x_n$: $x_1 \oplus ... \oplus x_n$.

[long3101]

я правильно понял, что $\oplus$ это конъюнкция?

просто в здешних символах не очень разобрался пока :)

[Nemiroff]

Конъюнкция не обозначается - там же есть $zx$ - вот между ними конъюнкция.
$\oplus$ - даже не знаю, как называется. "Исключающее или", что ли. Короче, это $\mathtext{xor}$

-- Вс янв 29, 2012 21:53:09 --

А, вот: http://ru.wikipedia.org/wiki/%D0%A1%D0% ... BB%D1%8E_2

[long3101]

может для начала по проще что-то? :)
ограничивая, конъюнкцией, дизъюнкцией, отрицанием и импликацией?

[Nemiroff]

Вам Nimza предложил(а) пример. Решайте.

-- Вс янв 29, 2012 22:05:55 --

Хотя вообще-то можете и сами преобразовать.
$a \oplus b = a \overline b \vee \overline a b$.
$a \equiv b = ab \vee \overline a \overline b$

[long3101]

$xy \vee xz \vee yz$

Насколько я понял, сначала упрощаем.

$x (y \vee z) \vee yz$

верно тут? если да, то как дальше? если нет, то где ошибка?

[Nimza]

Способов много. Универсальный такой (на примере функции $x \vee x\overline{y}$):
1. Находите набор переменных, над которым записана формула (здесь $x,y$).
2. Находите множество $N_f$ единиц функции $f$. Здесь это наборы $(1,1), (1,0)$.
3. Каждому набору сопоставляете элементарную конъюнкцию. Здесь это $xy$ и $x\overline{y}$.
4. Берёте дизъюнкцию элементарных конъюнкций. Получаете $xy \vee x \overline{y}$.

В случае выше можно было поступить легче, пользуясь правилом введения однородности ($1 = x \vee \overline{x}$).

[long3101]

Можете подробнее объяснить 2-4 шаги?

как я понял, во 2ом мы находим множество через таблицу истинности

х у f
0 0 0
0 1 0
1 0 1
1 1 1

но почему именно единиц, а не нулей?

Дальше. пункт 3. Как я понял будет зависеть от наборов. Т.е. у нас 1,1 и 1,0. Поэтому это ху и $x \overline{y}$. Если был, скажем, набор 0,0, то элементарная конъюнкция была бы $\overline{x} \overline{y}$

По пункту 4. Берем дизъюнкцию т.к. находим СДНФ ?

И, соответственно, если бы искали СКНФ, то было бы наоборот?

[Nimza]

Всё так. В случае с СКНФ надо рассматривать множество нулей, а аналогичный алгоритм легко можете записать сами.

long3101 в сообщении #532874 писал(а):

но почему именно единиц, а не нулей?

Потому что СДНФ состоит из элементарных конъюнкций, на которых функция обращается в 1.

[long3101]

Т.е. для СКНФ всё так же, но после таблицы берем 0,0 и 0,1.
соответственно $\overline{x} \overline{y}$ и $\overline{x} y$

дальше берем конъюнкцию и всё.
получаем СКНФ $\overline{x} \overline{y} \overline{x} y$

так?

[Nimza]

Нет. Вы определение СКНФ читали? Она представляет собой конъюнкцию скобок, а в скобках стоят дизъюнкции. Например, набору $(0,0)$ будет соответствовать $\overline{x} \vee \overline{y}$.

[long3101]

спасибо! :)

экзамен сдал. на отлично

[Sonic86]

Nemiroff в сообщении #532835 писал(а):

$\oplus$ - даже не знаю, как называется. "Исключающее или", что ли. Короче, это $\mathtext{xor}$

Можно называть сложением по модулю 2.