2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 15:28 
Аватара пользователя


07/01/14
119
Добрый день.

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

$\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\\
$

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 15:47 


15/11/15
1124
А что означают плюсы?

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 15:52 
Заслуженный участник
Аватара пользователя


11/03/08
10207
Москва
Главное, куда ушло c?
Первое выражение от c зависит, второе нет.

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 16:19 


14/01/11
3144
Евгений Машеров в сообщении #1501986 писал(а):
Первое выражение от c зависит, второе нет.

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 17:16 
Заслуженный участник


27/04/09
28128
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 --

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 17:49 
Заслуженный участник
Аватара пользователя


18/09/14
5485
Kosat в сообщении #1501982 писал(а):
но $\neg a$ не хочет уходить

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

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

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:07 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Что значит "прийти из ... к ..."? А просто сравнить две таблицы истинности нельзя?

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:22 


15/11/15
1124
geomath в сообщении #1502030 писал(а):
Что значит "прийти из ... к ..."? А просто сравнить две таблицы истинности нельзя?

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:26 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:30 


15/11/15
1124
Mihr в сообщении #1502034 писал(а):
Без всяких таблиц истинности

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:37 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Не знаю, как заставить ВольфрамАльфу выдать промежуточные преобразования, а не сразу результат?

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:38 
Заслуженный участник
Аватара пользователя


18/09/14
5485
gevaraweb в сообщении #1502035 писал(а):
Но потом же они все равно вводятся?

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:44 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Mihr в сообщении #1502038 писал(а):
И потом, использование таблиц истинности удобно лишь для формул с малым числом переменных.
Компьютер построит вам и сравнит любые.

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:49 


21/05/16
4292
Аделаида
Kosat в сообщении #1501982 писал(а):
но $\neg a$ не хочет уходить

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

 Профиль  
                  
 
 Re: Как в Булевой алгебре совершить один переход
Сообщение20.01.2021, 18:52 
Аватара пользователя


11/12/16
14746
уездный город Н
arseniiv в сообщении #1502018 писал(а):
обычно плюс это xor,

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group