Алгебра логики. Логические функции.?

Question

[Ali Aliev]

Всё в выражении бы ничего, но не понял почему появились две общие инверсии в конце выражения. Пытаясь сделать самостоятельно, я получил выражение без этих двух палочек на всё выражение.

Как вот тут вот:

При замене !x1 и !x3 получаются через плюс: !(x1+x1).
А не как по сути правильно через умножение: !(x1*x1)

Answer 1

[Rsa97]

Всё просто. Поскольку у нас есть только схема ИЛИ-НЕ, а в формуле стоит просто ИЛИ, мы заменяем ИЛИ на НЕ(ИЛИ-НЕ).

Comments

[Ali Aliev]

Можно ведь было закончить на одном элементе ИЛИ-НЕ в конце? Их два, почему?

[Rsa97]

Ali Aliev, Потому что один элемент даст инверсное значение. ИЛИ-НЕ = НЕ(ИЛИ).
Нам надо ИЛИ, поэтому мы делаем НЕ(НЕ(ИЛИ)) или ИЛИ-НЕ от ИЛИ-НЕ.

[Ali Aliev]

Rsa97, всё равно не понял, почему одного не достаточно.

[Ali Aliev]

Rsa97, правильно ведь, раз даст инверсное значение. Так как требуется это по задаче. Только на элементах 2ИЛИ-НЕ схему

[Rsa97]

Ali Aliev, !(!x1 + x2) + !(!x1 + !x3)
Видите плюсик в середине? Это ИЛИ. Теперь подумайте, как его выразить, имея только схемы ИЛИ-НЕ.

[Ali Aliev]

Rsa97, ну как я понял ещё одной инверсией. А их там две. Две палочки на всё выражение если наглядно.

[Rsa97]

Ali Aliev, Чтотзначит "ещё одной", если в необходимом ИЛИ нет ни одной инверсии?
Первая "палочка" - это первая схема ИЛИ-НЕ, после неё получаем инверсное значение, вторая "палочка" - это вторая схема ИЛИ-НЕ, которая, с учётом соединённых входов, работает как просто НЕ.

[Rsa97]

Ali Aliev,
x V y ≡ (x ⊽ y) ⊽ (x ⊽ y)

[Ali Aliev]

Rsa97, вот как-то так для меня всё выглядит. И поэтому не понимаю смысл двух "палочек".

[Rsa97]

Ali Aliev, Неправильно оно у вас выглядит. !(x + y) = !x * !y
Упростим ситуацию. Обозначение ИЛИ - V, ИЛИ-НЕ - ⊽.
Теперь выразите x V y, используя только ⊽.

[Ali Aliev]

Rsa97, честно, только начинаю изучать схемотехнику. Подобрал книгу, в ней не столь подробно рассматриваются шаги.
Вот вы написали !(x + y) = !x * !y к чему? Вроде по этой формуле и делал всё и это получил, но получил без тех инверсий.
Не понял что делать тут:
Теперь выразите x V y, используя только ⊽.

[Rsa97]

Ali Aliev,

Вроде по этой формуле и делал всё и это получил, но получил без тех инверсий.

Нет, у вас !(x + y) = !x + !y, а это в принципе неверно.

Не понял что делать тут:

Запишите формулу для вычисления ИЛИ используя только операцию ИЛИ-НЕ.

[Ali Aliev]

Rsa97, "Нет, у вас !(x + y) = !x + !y, а это в принципе неверно."
Эти формулы применяются для конъюнкций в этом выражении по отдельности. Чтоб в выражении получить только дизъюнкции. Всё вроде верно

[Ali Aliev]

Rsa97, вот шаги моего решения:
Закон инверсии: !x * !y = !(x+y)
Преобразование этой формулы как я понял делается, чтоб подходило под имеющееся выражение? Тогда:
x - обозначаю как !x
y - как !y
Получается:
!!x * !!y = !(!x+!y) -> x*y = !(!x+!y)
Подстановка:
x - это x1
y - это !x2
x - это x1
y - это x3
Получается:
x1 * !x2+x1 * x3 = !(!x1 + x2) + !(!x1+!x3)
Так как элементы И заменяем на 2ИЛИ-НЕ, то есть имеется два входа, записываем !x1 и !x3 так:
!(!(x1+x1)+x2) + !(!(x1 + x1) + !(x3 + x3))
Составляю схему.

[Ali Aliev]

Rsa97, "Запишите формулу для вычисления ИЛИ используя только операцию ИЛИ-НЕ."
Как?(

[Rsa97]

Ali Aliev, На вашем скане вы преобразовали !(!x1 + !x1) + x2) => (x1 + x1) + !x2.
А правильным преобразованием будет !(!x1 + !x1) + x2) = (x1 + x1) * !x2.

Как?(

А как сумеете.

[Ali Aliev]

Rsa97, "На вашем скане вы преобразовали !(!x1 + !x1) + x2) => (x1 + x1) + !x2.
А правильным преобразованием будет !(!x1 + !x1) + x2) = (x1 + x1) * !x2. "
И про какое именно вы фото?

[Ali Aliev]

Rsa97,
Rsa97, "На вашем скане вы преобразовали !(!x1 + !x1) + x2) => (x1 + x1) + !x2.
А правильным преобразованием будет !(!x1 + !x1) + x2) = (x1 + x1) * !x2. "
А как получилось умножение?

[Ali Aliev]

Rsa97, всё, я поплыл, к экспрессивным выражениям это всё! Пойду спрыгну

[Ali Aliev]

Rsa97, Как вот тут вот:

При замене !x1 и !x3 получаются через плюс: !(x1+x1).
А не как по сути правильно через умножение: !(x1*x1)

[Rsa97]

Ali Aliev, Для начала аксиоматика:
x ≡ ¬(¬x)
x ≡ x ∨ x
¬(x ∧ y) ≡ ¬x ∨ ¬y
¬(x ∨ y) ≡ x ⊽ y

Теперь запишем вашу формулу в классической нотации:
y = x₁ ∧ ¬x₂ ∨ x₁ ∧ x₃

Разобьём её на части и выполним преобразование так, чтобы все операции свелись к ИЛИ-НЕ (⊽).
x₁ ∧ ¬x₂ ≡ ¬(¬(x₁ ∧ ¬x₂)) ≡ ¬(¬x₁ ∨ ¬(¬x₂)) ≡ ¬x₁ ⊽ x₂ ≡ ¬(x₁ ∨ x₁) ⊽ x₂
≡ (x₁ ⊽ x₁) ⊽ x₂

x₁ ∧ x₃ ≡ ¬(¬(x₁ ∧ x₃)) ≡ ¬(¬x₁ ∨ ¬x₃) ≡ ¬x₁ ⊽ ¬x₃ ≡ ¬(x₁ ∨ x₁) ⊽ ¬(x₃ ∨ x₃)
≡ (x₁ ⊽ x₁) ⊽ (x₃ ⊽ x₃)

Обозначим первую часть как a, вторую как b. Тогда:
x₁ ∧ ¬x₂ ∨ x₁ ∧ x₃ ≡ a ∨ b ≡ ¬(¬(a ∨ b))

На этом этапе и возникают те самые две черты. Но продолжим преобразование дальше:
¬(¬(a ∨ b)) ≡ ¬(a ⊽ b) ≡ ¬((a ⊽ b) ∨ (a ⊽ b)) ≡ (a ⊽ b) ⊽ (a ⊽ b)

Теперь подставим обратно a и b. Получим:
y = (((x₁ ⊽ x₁) ⊽ x₂) ⊽ ((x₁ ⊽ x₁) ⊽ (x₃ ⊽ x₃))) ⊽ (((x₁ ⊽ x₁) ⊽ x₂) ⊽ ((x₁ ⊽ x₁) ⊽ (x₃ ⊽ x₃)))

Составим алгоритм вычисления, на каждом шаге которого будет только одна операция:
z₁ = x₁ ⊽ x₁
y = ((z₁ ⊽ x₂) ⊽ (z₁ ⊽ (x₃ ⊽ x₃))) ⊽ ((z₁ ⊽ x₂) ⊽ (z₁ ⊽ (x₃ ⊽ x₃)))

z₂ = x₃ ⊽ x₃
y = ((z₁ ⊽ x₂) ⊽ (z₁ ⊽ z₂)) ⊽ ((z₁ ⊽ x₂) ⊽ (z₁ ⊽ z₂))

z₃ = z₁ ⊽ x₂
y = (z₃ ⊽ (z₁ ⊽ z₂)) ⊽ (z₃ ⊽ (z₁ ⊽ z₂))

z₄ = z₁ ⊽ z₂
y = (z₃ ⊽ z₄) ⊽ (z₃ ⊽ z₄)

z₅ = z₃ ⊽ z₄
y = z₅ ⊽ z₅

Каждый шаг алгоритма - один чип ИЛИ-НЕ.

[Ali Aliev]

Rsa97, спасибо большое. Долго, но допёр

Answer 2

[mayton2019]

Там нет общих инверсий. Там каждая инверсия применяется только к части выражения.

Покажи свои преобразования step-by-step и кто-нибудь тебе укажет на ошибку.

Comments

[Ali Aliev]

То же самое получилось, но без этих двух инверсий что на всё выражение

[mayton2019]

Вот первое выражение

x1 * !x2 + x1 * x3 =

показывай шаг за шагом как ты делал

[Ali Aliev]

mayton2019, ну ладно.
Закон инверсии: !x * !y = !(x+y)
Преобразование этой формулы как я понял делается, чтоб подходило под имеющееся выражение? Тогда:
x - обозначаю как !x
y - как !y
Получается:
!!x * !!y = !(!x+!y) -> x*y = !(!x+!y)
Подстановка:
x - это x1
y - это !x2
x - это x1
y - это x3
Получается:
x1 * !x2+x1 * x3 = !(!x1 + x2) + !(!x1+!x3)
Так как элементы И заменяем на 2ИЛИ-НЕ, то есть имеется два входа, записываем !x1 и !x3 так:
!(!(x1+x1)+x2) + !(!(x1 + x1) + !(x3 + x3))
Составляю схему.

[Ali Aliev]

mayton2019, я уже понял благодаря ответу сверху зачем ещё одна инверсия для всего выражения. Но насчёт второй не понимаю

Answer 3

[atereffigies]

Кхм, просто посмотрите симуляцию исходного уравнения и приведённого уровнения к базису ИЛИ-НЕ: https://tinyurl.com/2g8jwdh5
Возможно, это вам поможет понять.