Консультации Портала - Консультация #196468

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 196468

27.09.2019, 11:41

0.00 руб.

1 1 1

Образование

Здравствуйте! У меня возникли сложности с таким вопросом:

Упростить выражение функции f(x1, x2, x3) и привести к виду, содержащему только конъюнкцию, дизъюнкцию и отрицание.

Прикрепленные файлы:

03cf5cdb00a80802016465a5d2235d1cc3e962dd.jpeg

скачать (13.00 кБ)

Обсуждение

давно

Гордиенко Андрей Владимирович

Мастер-Эксперт
17387
18345

29.09.2019, 16:40

общий

это ответ

Здравствуйте, sasha181999_9!

Из-за особенностей используемого мной редактора формул сложение по модулю 2 обозначено символом +, отрицание -- символом [$172$]. Для решения задачи воспользуемся тем, что x+y[$8801$][$172$](x[$8596$]y), x|y[$8801$][$172$](x[$8743$]y), x[$8595$]y[$8801$][$172$](x[$8744$]y) [1, с. 22 -- 23]. Тогда

x₁+(([$172$]x₁[$8595$]x₂)|(x₂[$8595$][$172$]x₃))[$8801$]

[$8801$]x₁+[$172$](([$172$]x₁[$8595$]x₂)[$8743$](x₂[$8595$][$172$]x_3))[$8801$]

(воспользуемся тем, что [$172$](x[$8743$]y)[$8801$][$172$]x[$8744$][$172$]y [1, с. 23])

[$8801$]x₁+([$172$]([$172$]x₁[$8595$]x₂)[$8744$][$172$](x₂[$8595$][$172$]x₃))[$8801$]

(воспользуемся тем, что [$172$](x[$8595$]y)[$8801$][$172$]([$172$](x[$8744$]y))[$8801$]x[$8744$]y [1, с. 22 -- 23])

[$8801$]x₁+(([$172$]x₁[$8744$]x₂)[$8744$](x₂[$8744$][$172$]x₃))[$8801$]

(воспользуемся ассоциативностью дизъюнкции и тем, что x[$8744$]x[$8801$]x [1, с. 23 -- 24])

[$8801$]x₁+([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃)[$8801$]

[$8801$][$172$](x₁[$8596$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃))[$8801$]

(воспользуемся тем, что x[$8596$]y[$8801$](x[$8743$]y)[$8744$]([$172$]x[$8743$][$172$]y) [1, с. 25])

[$8801$][$172$]((x₁[$8743$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃))[$8744$]([$172$]x₁[$8743$][$172$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃)))[$8801$]

(воспользуемся тем, что [$172$](x[$8744$]y)[$8801$][$172$]x[$8743$][$172$]y [1, с. 23])

[$8801$][$172$](x₁[$8743$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃))[$8743$][$172$]([$172$]x₁[$8743$][$172$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃))[$8801$]

(воспользуемся тем, что [$172$](x[$8743$]y)[$8801$][$172$]x[$8744$][$172$]y, [$172$][$172$]x[$8801$]x)

[$8801$]([$172$]x₁[$8744$][$172$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃)) [$8743$] (x₁[$8744$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃))[$8801$]

(воспользуемся ассоциативностью дизъюнкции и тем, что x[$8744$][$172$]x[$8801$][$172$]x[$8744$]x[$8801$]1, 1[$8744$]x[$8801$]x[$8744$]1[$8801$]1, 1[$8743$]x[$8801$]x[$8743$]1[$8801$]x [1, с. 23 -- 24])

[$8801$][$172$]x₁[$8744$][$172$]([$172$]x₁[$8744$]x₂[$8744$][$172$]x₃)[$8801$]

(воспользуемся ассоциативностью дизъюнкции и тем, что [$172$](x[$8744$]y)[$8801$][$172$]x[$8743$][$172$]y, [$172$][$172$]x[$8801$]x)

[$8801$][$172$]x₁[$8744$]([$172$]([$172$]x₁[$8744$]x₂)[$8743$]x₃)[$8801$]

(воспользуемся тем, что [$172$](x[$8744$]y)[$8801$][$172$]x[$8743$][$172$]y, [$172$][$172$]x[$8801$]x)

[$8801$][$172$]x₁[$8744$]((x₁[$8743$][$172$]x₂)[$8743$]x₃)[$8801$]

(воспользуемся дистрибутивностью дизъюнкции)

[$8801$]([$172$]x₁[$8744$](x₁[$8743$][$172$]x₂))[$8743$]([$172$]x₁[$8744$]x₃)[$8801$]

(воспользуемся дистрибутивностью конъюнкции [1, с. 23])

[$8801$]([$172$]x₁[$8744$]x₁)[$8743$]([$172$]x₁[$8744$][$172$]x₂)[$8743$]([$172$]x₁[$8744$]x₃)[$8801$]

(воспользуемся тем, что [$172$]x[$8744$]x[$8801$]1, 1[$8743$]x[$8801$]x)

[$8801$]([$172$]x₁[$8744$][$172$]x₂)[$8743$]([$172$]x₁[$8744$]x₃)[$8801$]

(воспользуемся дистрибутивностью дизъюнкции)

[$8801$][$172$]x₁[$8744$]([$172$]x₂[$8743$]x₃).

Мы получили, что f(x₁, x₂, x₃)=x₁+(([$172$]x₁[$8595$]x₂)|(x₂[$8595$][$172$]x₃))=[$172$]x₁[$8744$]([$172$]x₂[$8743$]x₃). Для проверки этого ответа составим таблицы истинности для исходного и полученного выражений, обозначив f₁=[$172$]x₁[$8595$]x₂, f₂=x₂[$8595$][$172$]x₃, f₃=f₁|f₂, f=x₁+f₃, g=[$172$]x₁+f₃, f=[$172$]x₁[$8744$]g. Получим следующие результаты:

[table]
[row][col]x₁[/col][col]x₂[/col][col]x₃[/col][col][$172$]x₁[/col][col][$172$]x₃[/col][col]f₁[/col][col]f₂[/col][col]f₃[/col][col]f[/col][/row]
[row][col]0[/col][col]0[/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]0[/col][col]0[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][/row]
[row][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]0[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/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]1[/col][col]0[/col][/row]
[row][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]0[/col][col]1[/col][/row]
[row][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[/table]

[table]
[row][col]x₁[/col][col]x₂[/col][col]x₃[/col][col][$172$]x₁[/col][col][$172$]x₂[/col][col]g[/col][col]f[/col][/row]
[row][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/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]1[/col][/row]
[row][col]0[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]1[/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]0[/col][col]0[/col][/row]
[row][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]

Последние столбцы в обеих таблицах истинности совпадают. Значит, действительно f(x₁, x₂, x₃)=[$172$]x₁[$8744$]([$172$]x₂[$8743$]x₃).

Литература
1. Галушкина Ю. И., Марьямов А. М. Конспект лекций по дискретной математике. -- М.: Айрис-пресс, 2007. -- 176 с.

Об авторе:
Facta loquuntur.

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.