Минимизиция булевых функций

[SANeK]

Найти минимальную ДНФ
нужна помощь в решении контрольной работы по Дискретки.
при решении задания нужно найти минимальную ДНФ
я нашел СКНФ и СДНФ (тоже надо было)
СДНФ: $\overline{x_1}$ $\overline{x_2}$ $\overline{x_3}$ $\vee $\overline{x_1}$ $\overline{x_2}$ $x_3$ $ $\vee $\overline{x_1}$ $x_2$ $\overline{x_3}$ $ $\vee $x_1$ $\overline{x_2}$ $\overline{x_3}$ $ $\vee $x_1$ $\overline{x_2}$ $x_3$ $

как мне теперь найти сокращенную ДНФ?
желательно с объяснениями, в интернете искал, но что то никак не могу понять как и что делается

буду рад если дадите ссылки на подробную литературу по этой теме

[Профессор Снэйп]

А что значит "минимальная"? Наиболее короткая что ли?

[SANeK]

вроди да,
просто в плане написано найти минимальную

[juna]

http://www.sceptic-ratio.narod.ru/ma/dm1-2b.htm
Например, для нахождения минимальной в базисе ДНФ от трех переменных хорошо подходят карты Карно.

[SANeK]

че то ниче с ними вообще не понятно
объясните хотябы как склеиваются ?

[juna]

Должно получиться:
$\bar x_2\vee\bar x_3\bar x_1$
Сейчас, увы, нет времени подробно объяснять

[SANeK]

это в принципи дней несколько терпит так что буду очень признателе если объясните
спасибо за ответ

[mvb13]

Диаграмма Карно
1.Нужно записать таблицу истинности для данной функции

2.Значения при которых функция равна 1 заносятся в таблицу (для ДНФ, для КНФ записываются 0 )

3.Нужно произвести склеивание (можно склеивать по 2 ,4 ,8,... элементов) 1, которые находятся рядом либо по углам.
Для склеивания двух элементов $\bar{x_1}\bar{x_2}\bar{x_3}$ и $\bar{x_1}{x_2}\bar{x_3}$ сначала работаем с первой строкой (столбцы 2 ,3) В них находятся значения 00 01 .Первые цифры совпадают 0 0 значит остается x1(с отрицанием если бы совпали 1 x1 был бы без отрицания). Вторые цифры 0 1 различны поэтому переменная x2 исчезает.
Теперь работаем с первым столбцом (вторая строка) x3 нельзя склеить, поэтому он остается (с отрицанием)
Получается $\bar{x_1}\bar{x_3}$
Анаогично склеиваются 4 элемента

В результате $\bar{x_1}\bar{x_3}\vee \bar{x_2}$

[SANeK]

mvb13, огромное спасибо вам за помощь, очень признателен

и еще один вопрос:
Является ли полной система булевых функций, состоящая из конъюнкции, константы и эквивалентности?

вот такое задание, что тут нада сделать и вообще о чем идет речь?

[Brukvalub]

Советую Вам прочесть первые три-четыре лекции О.Б.Лупанова (а еще лучше - все!), скачав их, например, отсюда: http://www.vilenin.narod.ru/ (см. 2-й семестр) , тогда все станет ясно.

[Профессор Снэйп]

Brukvalub писал(а):

Советую Вам прочесть первые три-четыре лекции О.Б.Лупанова (а еще лучше - все!), скачав их, например, отсюда: http://www.vilenin.narod.ru/ (см. 2-й семестр) , тогда все станет ясно.

Там, между прочим, экзешники. Не знаю, кто как, а я не такой дурень, чтоб на своём компутере непонятно чей экзешник открывать

[Brukvalub]

Это экзешники - разархиваторы. Я их раньше открывал - происходит формирование Вордовского документа. Но Ваши сомнения мне понятны.

Добавлено спустя 34 минуты 46 секунд:

Раз не нравятся исполняемые файлы, то читаем те же лекции здесь: http://dmvn.mexmat.net/logic.php Большего сделать я не в силах

[juna]

SANeK писал(а):

Является ли полной система булевых функций, состоящая из конъюнкции, константы и эквивалентности?

Используйте критерий Поста.

[kwirk]

1) Построить сокращенную ДНФ функции f, используя геметрическую интерпретацию ее области определения.
$f(x_1, x_2, x_3, x_4)= (1010111111 000001)$

2) Найти минимальную ДНФ функции f методом минимизирующих карт
$f(x_1, x_2, x_3)=xyz \vee xy'z' \vee xyz' \vee xy'z$

p.s. значок x' - это x с черточкой (извините пока не разобралсь как грамотно здесь писать)

1-й как я поняла надо рисовать карту карно, только не поняла как с ней работать

// 8.05.09 близкие темы соединены. / GAA

[luitzen]

kwirk писал(а):

1-й как я поняла надо рисовать карту карно, только не поняла как с ней работать

А я так понял, что карту Карно надо рисовать во втором задании, а в первом — сколькитомерный куб.
Или что у вас называется геометрической интерпретацией области определения?