Консультация № 180429
24.10.2010, 02:40
64.43 руб.
24.10.2010, 07:31
0 1 1
Помогите, пожалуйста найти СКНФ и СДНФ
(x'-> y')->(y& z)->(x & z)
(где ' -отрицание)
двумя способами:
1)преобразованиями
2) с помощью таблицы истинности

Обсуждение

давно
Посетитель
7438
7205
24.10.2010, 04:29
общий
это ответ
Здравствуйте, sveta11115!
Сначала преобразуем, сведем импликации только к дизъюнкции, конъюнкции и отрицанию,
используем тождество a ⇒ b ≡ ¬a ∨ b, законы де Моргана и законы поглощения:
(¬x ⇒ ¬y) ⇒ (y ∧ z) ⇒ (x ∧ z) ≡
(x ∨ ¬y) ⇒ (y ∧ z) ⇒ (x ∧ z) ≡
(¬(x ∨ ¬y) ∨ (y ∧ z)) ⇒ (x ∧ z) ≡
¬(¬(x ∨ ¬y) ∨ (y ∧ z)) ∨ (x ∧ z) ≡
¬((¬x ∧ y) ∨ (y ∧ z)) ∨ (x ∧ z) ≡
((x ∨ ¬y) ∧ (¬y ∨ ¬z)) ∨ (x ∧ z) ≡
(x ∧ ¬y) ∨ (x ∧ ¬z) ∨ ¬y ∨ (¬y ∧ ¬z) ∨ (x ∧ z) ≡ x ∨ ¬y (1)

СКНФ = x ∨ ¬y ≡ (x ∨ ¬y) ∨ (z ∧ ¬z) ≡ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z)

Построим таблицу истинности (2)
[table]
[row][col]x[/col][col]y[/col][col]z[/col][col]¬x[/col][col]¬y[/col][col]¬x⇒¬y[/col][col]y∧z[/col][col](¬x⇒¬y)⇒(y∧z)[/col][col](x∧z[/col][col](¬x⇒¬y)⇒(y∧z)⇒(x∧z)[/col][/row]
[row][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]0[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][/row]
[row][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]1[/col][col]1[/col][/row]
[/table]

СКНФ строим из тех строк (3 и 4), где в итоге 0,
причем в дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1:

СКНФ = (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z)

Построение СДНФ продолжим с формулы (1)

СДНФ = x ∨ ¬y ≡ (x ∨ ¬y) ∧ (z ∨ ¬z) ≡ (x ∧ z) ∨ (x ∧ ¬z) ∨ (¬y ∧ z) ∨ (¬y ∧ ¬z) ≡
(((x ∧ z) ∨ (x ∧ ¬z)) ∧ (y ∨ ¬y)) ∨ ((x ∨ ¬x) ∧ ((¬y ∧ z) ∨ (¬y ∧ ¬z))) ≡
(x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z) ≡
(¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ z)

Построим СДНФ по таблице истинности (2)
Рассматриваются значения переменных при которых функция равна 1 (все, кроме 3 и 4).
Если значение переменной равно 0, то в конъюнкцию она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

СДНФ = (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ z)
5
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа