Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.82
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
#1

Алгоритм приведения к КНФ/ДНФ - C++

24.03.2011, 11:30. Просмотров 4546. Ответов 6
Метки нет (Все метки)

Что-то я запарился, никак придумать не могу...

Допустим имеется у нас формула

x&y|z
Дерево разбора строится как.

Код
 
               &
           x       |
               y         z
С построением такого дерева проблем нету... Но вот как программно это привести к КНФ или в ДНФ?
Прошу совета по поводу алгоритма. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2011, 11:30     Алгоритм приведения к КНФ/ДНФ
Посмотрите здесь:

Стили приведения типов - C++
Строка 38: что за странное объявление? Обычно аргументы заключаются в скобки. Строка 39: что за static_cast и последующий <Complex>? Как...

Приведения типа классов - C++
#include <iostream> class Number2; class Number { public: int i; Number(int ii = 0) : i(ii) {} Number(const...

Неявные приведения в операциях - C++
В умной книжке написано, что в арифметических выражениях все операнды приводятся к одному типу, если это возможно, пример: int a = 5;...

Отличие способов приведения - C++
Есть ли отличия между (int) и static_cast<int>?

Оператор приведения и его объявление - C++
Всем привет! Прошу помощи в разъяснении теории: Есть класс А и B, в классе B есть оператор приведения к А, а в классе А...

Невозможность приведения к стандартному типу - C++
Не могу привести к стандартному типу объект класса. Вот код: class Casting { private: double X; public: Casting() :...

Отличие static_cast от приведения в стиле С - C++
Собственно вопрос в заголовке. Говорят что Static_cast безопасней чем приведение типа в стиле С, но в чем опасность последнего?...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.03.2011, 13:29     Алгоритм приведения к КНФ/ДНФ #2
Сначала надо вычислить значение формулы на всех возможных наборах переменных (т.е. построить таблицу истинности формулы). Затем:

1. Для КНФ:
Находим строку таблицы истинности, где формула ложна (равна нулю). Берём все переменные в этой строке и делаем их логическую сумму (дизъюнкт), причём, если переменная ложна, то она входит в дизъюнкт как есть, а если истинна - то входит в дизъюнкт с отрицанием. Строим такие дизъюнкты из всех наборах переменных (строках таблицы), где формула ложна. Затем строим конъюнкцию полученных дизъюнктов - вот вам и КНФ.
2. Для ДНФ:
Здесь всё наоборот. Т.е. мы строим ТИ, выбираем все единичные строки, строим конъюнкты всех входящих в эти строки переменных, причём если переменная истинна, она входит в конъюнкт как есть, а если ложна - входит в него с отрицанием, и затем строим дизъюнкцию всех полученных элементарных конъюнктов. ДНФ готова.
Фух, вроде ничего не напутал...
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
24.03.2011, 13:40  [ТС]     Алгоритм приведения к КНФ/ДНФ #3
silent_1991, И для программной реализации другого метода, я так понимаю нету?
Т.е. аналогично нужно будет делать через таблицы истины и посылать значение каждой строки в дерево (расписывать по переменным), ну или как-то так, сейчас сформулировать затрудняюсь?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.03.2011, 13:47     Алгоритм приведения к КНФ/ДНФ #4
ForEveR, да, полагаю, это наиболее тупой и простой, но в то же время наиболее эффективный (в плане реализации) метод. Есть ещё аналитический метод, который в принципе можно запрограммировать, но я бы с ним возиться не стал, поскольку приведённый алгоритм вполне сносный. Конечно, он может долго работать на большом наборе переменных...
И да, если результат нужно получить в виде дерева, то сразу можно посчитать, сколько строк таблицы нулевые (ненулевые), в корень записывать &, затем в левого ребёнка &, в правого & и т.д., пока счётчик соответствующих (нулевых / ненулевых) строк не обнулится, ну а потом в каждого из полученных детей начинаем впихивать || в количестве переменных, входящих в формулу, а затем в листы сами эти переменные или их отрицания. Надеюсь, понятно)) Ну да вы и без меня, я думаю, поняли, что делать)))
onlwork
1 / 1 / 0
Регистрация: 10.11.2013
Сообщений: 53
22.11.2013, 00:00     Алгоритм приведения к КНФ/ДНФ #5
Цитата Сообщение от silent_1991 Посмотреть сообщение
Сначала надо вычислить значение формулы на всех возможных наборах переменных (т.е. построить таблицу истинности формулы). Затем:

1. Для КНФ:
Находим строку таблицы истинности, где формула ложна (равна нулю). Берём все переменные в этой строке и делаем их логическую сумму (дизъюнкт), причём, если переменная ложна, то она входит в дизъюнкт как есть, а если истинна - то входит в дизъюнкт с отрицанием. Строим такие дизъюнкты из всех наборах переменных (строках таблицы), где формула ложна. Затем строим конъюнкцию полученных дизъюнктов - вот вам и КНФ.
2. Для ДНФ:
Здесь всё наоборот. Т.е. мы строим ТИ, выбираем все единичные строки, строим конъюнкты всех входящих в эти строки переменных, причём если переменная истинна, она входит в конъюнкт как есть, а если ложна - входит в него с отрицанием, и затем строим дизъюнкцию всех полученных элементарных конъюнктов. ДНФ готова.
Фух, вроде ничего не напутал...
Извините, но это СКНФ и СДНФ
bio4
2 / 2 / 3
Регистрация: 15.10.2015
Сообщений: 19
04.02.2017, 16:06     Алгоритм приведения к КНФ/ДНФ #6
Цитата Сообщение от onlwork Посмотреть сообщение
Извините, но это СКНФ и СДНФ
да
и я придумал некую реализацию напоминающую метод карт Карно(обычно для програмной реализации используют метод Куайна — Мак-Класки http://www.********************/showthread.php?t=148179)
для нахождения ДНФ по полному списку выходных сигналов содержащего "0","1","Х" (Х-выходы на которых всеравно какой будет сигнал)

1) ишим в списке выходных сигналов первую "1"
2) ищем с кем можно объеденить эту "1" (другая "1" или "Х")
3) если в пункте (2) не найдена другая "1" или "Х", то перейти к пункту(6)
4) находим общие входные сигналы для "1" найденной в пункте (1) и следующей "1" или "Х"
5) если данные общие входные сигналы подходят для выходов содержащих "0", то в общие входные сигналы записываюстя входные сигналы для "1" найденной в пункте (1)
6) в массив ДНФ записываются общие входные сигналы
7) необходимо удалить из массива ДНФ общие входные сигналы, которые могут подходить под шаблон других сигналов массива ДНФ
8) удалить повторяющиеся наборы в массиве ДНФ
9) массив ДНФ уже содержит шаблоны входных сигналов между которыми установив знак объединения(+) выйдет формула ДНФ

вот метод оттображающий основную последовательность выполнения алгоритма(черонвой вариант)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
QString Karno::buildDNF(QString puth)
{
    QString result="";
    QVector<uint32_t> masOutput=Karno::readCSV(puth);//набор выходов
    uint32_t capacity= pow(masOutput.size(),0.5);//число входных сигналов
    QVector<QString> temp_global(0);
    for(int i=0; i<masOutput.size();i++)
    {
        if(masOutput[i]==1)//ищим единицы
        {
            QString temp1=Karno::makeBinOfDec(i,capacity);
            QString global=temp1;
            //с кем можно объединить?
            for(int j=i+1; j<masOutput.size();j++)
            {
                if(masOutput[j]>0)//с единицами или 2
                {
                    QString temp2=Karno::makeBinOfDec(j,capacity);
                    //проверить на возможность объединения
                    //(существуют ли с данным условием не единицы)
                    global=Karno::getGlobal(temp1,temp2);
 
                    //кто еще подходит под єто описание?
                    QVector<uint32_t> masGlobal=Karno::searchGlobal(global,masOutput);
                    if(masGlobal.size()>0)
                    {
                        //есть нули?(global=0)
                        if(Karno::chekNum(masOutput,masGlobal,0))
                        {
                            global=temp1;
                        }
                    }
                }
                temp_global.append(global);//массив который нужно отсеять
            }
            //result+='+'+temp1;
        }
    }
    //отсеиваем обьединения входящие в другие
    QVector<QString> ansver=Karno::separator(temp_global);
    //удаление обьединений с "2" для тех, кто уже обьединен
    ansver=Karno::delExcessJoin(ansver,masOutput);
    foreach(QString str,ansver)
        result+=Karno::convert(str)+"+";
    QString h100=result.left(result.length()-1);
    return h100;
}
и весь класс с файлом для теста
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2017, 16:14     Алгоритм приведения к КНФ/ДНФ
Еще ссылки по теме:

Небезопасность приведения. Не понимаю Прата - C++
О коде, который описан в книге, слегка переправлен мной: #include &lt;iostream&gt; using std::cout; class Grand { public: ...

Перегрузка операторов приведения типов - C++
Доброго времени суток! Возник вопрос по перегрузке оператора преобразования типа const char*. Вот пример: class Integer { public: ...

Двумерный массив - ошибка приведения типов - C++
Приветсвую. Столкнулся с такой проблемой, точнее не с проблемой а с вопросом. допустим: имеется функция Function; void Function( double...

Вызов оператора приведения базового класса - C++
Добрый день. У меня есть иерархия классов. class A: B { ... operator const char* () const; ...

Исправьте ошибку C2664 приведения типов - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;conio.h&gt; using namespace std; void statistics(char...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
bio4
2 / 2 / 3
Регистрация: 15.10.2015
Сообщений: 19
04.02.2017, 16:14     Алгоритм приведения к КНФ/ДНФ #7
Цитата Сообщение от bio4 Посмотреть сообщение
и весь класс с файлом для теста
нечитабельный
Вложения
Тип файла: 7z karno.7z (2.3 Кб, 3 просмотров)
Yandex
Объявления
04.02.2017, 16:14     Алгоритм приведения к КНФ/ДНФ
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru