Упрощение формул логики до минимальной днф

Упрощение формул логики до минимальной днф

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком "эквивалентно"

Со знаком "следствие"

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн

Тема программы: Нормальные формы для формул алгебры высказываний.

1) Обобщить теоретические знания по теме: «Упрощение формул логики до минимальной ДНФ».

2) Рассмотреть алгоритмы решений заданий теме «Упрощение формул логики до минимальной ДНФ» .

3) Формировать ответственность; самоконтроль, рассудительность.

Время выполнения:2 часа.

Теоретические основы

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Аналогично для КНФ:

Возможность поглощения следует из очевидных равенств

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2 N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

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

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

В общем случае можно сказать, что 2 K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

Читайте также:  Копирование в информатике это

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с функциями большего числа переменных.

Дата добавления: 2018-02-28 ; просмотров: 786 ;

Приведение формул к виду СДНФ бывает необходимо при решении конкретных, содержательных задач. Если, например, в условиях задачи речь идет об элементарных высказываниях А, В, С и если условия задачи записаны в виде формулы, то, приведя эту формулу к виду СДНФ, мы тем самым получим полныйперечень всех тех случаев, при которых условия задачи будут выполнены.

Рассмотрим конкретный пример.

Задача.Известно, что если Андрей и Володя пойдут в кино, то Сережа в кино не пойдет. Известно также, что если Володя не пойдет в кино, то в кино пойдут Андрей и Сережа. Надо узнать, кто при этих условиях может пойти в кино.

Решение.Введем обозначения. Пусть А означает: «Анд­рей пойдет в кино», В означает: «Володя пойдет в кино», С означает: «Сережа пойдет в кино». Условия задачи запишутся следующим образом:

Воспользуемся теперь равносильностью . (Эта равносильность легко устанавливается с помощью таблиц истинности.) На основании этой равносильности условия задачи примут вид: . Так как оба условия задачи должны быть выполнены, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к виду ДНФ:

Условия задачи свелись к формуле , ко­торая должна быть истинной. Но дизъюнкция истинна, если истинным будет хотя бы один из ее членов. Значит, для того, чтобы условия задачи были выполнены, доста­точно, чтобы имел место один из трех случаев:

1. , т. е. в кино может пойти Володя без Андрея.

2. , т. е. в кино могут пойти Андрей с Сережей, но без Володи.

3. , т. е. в кино может пойти Володя без Сережи.

Задача как будто бы решена. Но на самом деле это решение нельзя признать окончательным, так как в первом и третьем случае ответ будет неполным. Чтобы получить полный ответ, нужно ранее полученную ДНФ преобразовать к СДНФ.

Читайте также:  Как ставить среднее тире в ворде

Теперь мы действительно получили полный перечень всех случаев, при которых выполняются условия задачи, к тому же выяснилось, что таких случев не три, а четыре.

Возникает вопрос: зачем нужны преобразова­ния, приводящие исходные формулы к минимальной фор­ме? Зачем нужна минимальная КНФ? Ответ заключается в том, что все это совершенно необходимо при решении задач. Рассмотрим конкретный пример.

Задача.В школе решили организовать секцию атлетиче­ской гимнастики. Надо было разработать правила приема в эту секцию. Ребята внесли ряд предложений:

1. Если ученик не отличник и не здоров, то он не может быть принят.

2. Если ученик является отличником, то не может быть, чтобы он был здоров и его не приняли.

3. Если ученик не принят, то он не отличник.

4. Если ученик не здоров, то он не отличник и не будет принят. Учитель физкультуры сказал, что четыре правила — это слишком много. К тому же формулировки правил должны быть более простыми, более лаконичными. Поэто­му, сказал учитель, возникает следующая задача: надо совокупность всех четырех правил заменить новыми прави­лами — и надо это сделать так, чтобы число новых правил было минимальным, чтобы каждое новое правило было сформулировано кратчайшим образом и чтобы совокуп­ность новых правил была равносильна совокупности че­тырех исходных правил.

Через некоторое время эту задачу действительно уда­лось решить. Какие правила получились?

Решение.Обозначим элементарные высказывания: ученик является отличником — О, ученик здоров — 3, ученик принят — П. Теперь мы можем записать исход­ные правила в символической форме. Полученные фор­мулы мы сразу же упростим, воспользовавшись равносиль­ностью , законом де Моргана и законом снятия двойного отрицания . Мы получим следующие цепочки равносильностей:

1. ;

2. ;

3. ;

4. .

Так как все четыре условия должны выполняться, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к минимальной дизъюнктивной форме. Мы получим следующий результат: .

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

На самом же деле ответ будет совсем другим. Чтобы понять, в чем тут дело, рассмотрим внимательно получен­ный результат. Формула представляет собой дизъюнкцию, а дизъюнкция истинна тогда и только тогда, когда истинным является хотя бы один из ее компонентов. Может, например, оказаться, что истинно только или только . Когда же учащиеся, получив формулу , считают, что они тем самым получили два правила, т. е. два истинных утверждения, то они совершают грубую ошибку. Ведь из истинности дизъюнкции вовсе не сле­дует, что истинны оба ее компонента. Чтобы найти новые правила приема в спортивную секцию, надо рассуждать совсем по-другому. Начнем с того, что искомые правила должны представлять собой истинные высказывания. Но если высказывания истинны, то истинна и их конъюнк­ция, а если истинна конъюнкция, то истинно и каждое из высказываний в отдельности.

Читайте также:  Как установить драйвер для сетевой карты

Значит, чтобы найти новые правила, достаточно найти конъюнкцию этих правил. Следовательно, мы должны по­лученную ранее формулу преобразовать в конъ­юнкцию. А так как число новых правил должно быть мини­мальным и так как каждое правило должно быть сформу­лировано кратчайшим образом, то искомая конъюнкция должна иметь вид минимальной КНФ.

Чтобы выполнить это преобразование, воспользуемся законом исключенного третье­го и законом поглощения. Мы получим следующую цепочку равносильностей:

=

Таким образом, задача решена. Получилось два правила приема в секцию:

1. Если ученик является отличником, то он будет приняв ;

2. Если ученик принят, то необходимо, чтобы он был| здоров .

Аудиторная самостоятельная работа №11

«Приведение формул алгебры высказываний к КНФ, ДНФ,

СКНФ и СДНФ виду»

Задание №1.

В коробке лежат шары – деревянные и пластмассовые, большие и маленькие, зеленые и красные. Из коробки надо достать шар, соблюдая следующие правила:

1. Шар может быть деревянным только тогда, когда он маленький и зеленый;

2. Если шар маленький, то для того, чтобы он был пластмассовым, достаточно, чтобы он не был зеленым.

3. Если шар маленький и красный, то он деревянный.

Известно, что эти правила сводятся к двум простейшим условиям. Когда же вынули шар, оказалось, что из двух простейших условий выполнено только одно. Кроме того, о вынутом шаре известно, что он либо зеленый, либо большой и деревянный. Какой шар вынули из коробки? (20 баллов)

Задание №2. Приведите формулу к минимальной КНФ:

(10 баллов)

Задание №3. Приведите формулу к минимальной ДНФ:

(10 баллов)

Задание №4. Приведите формулу к минимальной СКНФ:

(10 баллов)

Последнее изменение этой страницы: 2016-12-26; Нарушение авторского права страницы

Ссылка на основную публикацию
Adblock detector