Как в Булевой алгебре совершить один переход

[Kosat]

Добрый день.

Как в Булевой алгебре прийти из

$\neg b + \neg ab + \neg ac$

к

$\neg a+\neg b $

?

Я пытался с конца, но $\neg a$ не хочет уходить:

$\\~b + \neg a + \neg ac + \neg ab\\ \neg b + (\neg a + \neg a\neg c) + \neg ac + \neg ab\\ \neg b + \neg a + \neg ac + \neg a\neg c + \neg ab\\ \neg b + \neg a + (\neg ac + \neg a\neg c) + \neg ab\\ \neg b + \neg a + \neg a(c + \neg c) + \neg ab\\ \neg b + \neg a + \neg a⋅1 + \neg ab\\ \neg b + \neg a + \neg a + \neg ab\\ \neg b + (\neg a + \neg a) + \neg ab\\ \neg b + \neg a + \neg ab\\ \neg b + (\neg a + \neg a\neg b) + \neg ab\\ \neg b + \neg a + \neg ab + \neg a\neg b\\ \neg b + \neg a + (\neg ab + \neg a\neg b)\\ \neg b + \neg a + \neg a(b + \neg b)\\ \neg b + \neg a + \neg a⋅1\\ \neg b + \neg a + \neg a\\ \neg b + (\neg a + \neg a)\\ \neg b + \neg a\\ \neg a + \neg b\\ $

[gevaraweb]

А что означают плюсы?

[Евгений Машеров]

Главное, куда ушло c?
Первое выражение от c зависит, второе нет.

[Sender]

Евгений Машеров в сообщении #1501986 писал(а):

Первое выражение от c зависит, второе нет.

Это обманчивое впечатление.

[arseniiv]

gevaraweb в сообщении #1501985 писал(а):

А что означают плюсы?

Видимо, дизъюнкцию, потому что иначе выражения не тождественны (плохой, плохой выбор — обычно плюс это xor, которое с конъюнкцией превращает булеву алгебру в настоящее кольцо; а дизъюнкция с конъюнкцией дают только полукольцо).

Kosat в сообщении #1501982 писал(а):

Как в Булевой алгебре прийти из

$\neg b + \neg ab + \neg ac$

к

$\neg a+\neg b $

?

Один из простых механических способов — это записать их эквивалентность

$$A\leftrightarrow B := (\neg A\vee B)\wedge (\neg B\vee A) = A\wedge B \vee \neg A\wedge\neg B$$

и упростить её до тождественной истины. Если получается что-то кроме, значит $A$ и $B$ не тождественны.

-- Ср янв 20, 2021 19:24:29 --

Ещё механический способ: привести оба выражения к одной и той же нормальной форме (СДНФ например) и сравнить результаты.

[Mihr]

Kosat в сообщении #1501982 писал(а):

но $\neg a$ не хочет уходить

А закон идемпотентности на что?

А вообще, сложно Вы решаете. Я бы сделал так:
1) пользуясь законом дистрибутивности, разлагаем на "множители" дизъюнкцию первых двух "слагаемых"
2) один из множителей оказывается равным единице - опускаем его
3) используем закон поглощения.

Это всё. Можно отправляться пить чай.

[geomath]

Что значит "прийти из ... к ..."? А просто сравнить две таблицы истинности нельзя?

[gevaraweb]

geomath в сообщении #1502030 писал(а):

Что значит "прийти из ... к ..."? А просто сравнить две таблицы истинности нельзя?

Видимо, "Используя равносильные преобразования". Можно и через таблицы истинности, но тут скорее спрашивается первый способ, предложенный Mihr. Он же и более быстрый.

[Mihr]

Ну, вообще-то, булева алгебра задаётся набором аксиом. Без всяких таблиц истинности. Так что подход у ТС правильный. Просто не самый рациональный.

[gevaraweb]

Mihr в сообщении #1502034 писал(а):

Без всяких таблиц истинности

Но потом же они все равно вводятся? Так что можно использовать.

[geomath]

Не знаю, как заставить ВольфрамАльфу выдать промежуточные преобразования, а не сразу результат?

https://www.wolframalpha.com/input/?i=simplify+~b+%7C%7C+~a%26b+%7C%7C+~a%26c

[Mihr]

gevaraweb в сообщении #1502035 писал(а):

Но потом же они все равно вводятся?

Это если интерпретировать булеву алгебру как алгебру логики. В остальных случаях - нет.
И потом, использование таблиц истинности удобно лишь для формул с малым числом переменных. В общем случае ими пользоваться не слишком-то удобно. Так что использование аксиом булевой алгебры должно быть предпочтительно, по-моему.

[geomath]

Mihr в сообщении #1502038 писал(а):

И потом, использование таблиц истинности удобно лишь для формул с малым числом переменных.

Компьютер построит вам и сравнит любые.

[kotenok gav]

Kosat в сообщении #1501982 писал(а):

но $\neg a$ не хочет уходить

А чему равно $\neg a+\neg a$?

[EUgeneUS]

arseniiv в сообщении #1502018 писал(а):

обычно плюс это xor,

Насколько понимаю, обычно xor это $\oplus$