Практическая работа №2.

Ход работы.

Задана формула: F = y ∼ z → (y z → x̅) ∨ x y z̄ =

Расставим скобки в заданной формуле .
Есть общепринятый порядок выполнения операций при вычислении значений произвольной формулы на каком-либо наборе аргументов. Операции выполняются в следующем порядке:

1) отрицание;

2) конъюнкция;

3) дизюнкция;

4) импликация;

5) эквиваленция и суммирование по модулю 2.

Скобки могут менять порядок исполнения операций, но часто их ставят просто для удобства чтения формул.

В данном случае скобки меняют порядок исполнения операций.
Расставим остальные скобки в соответствии с обычным порядком исполнения, то есть просто для удобства чтения формулы: .

В дальнейшем будем пользоваться записью: , то есть мы будем пользоваться этой последней формулой, имея в виду, что вначале исполняется операция отрицания, затем операция конъюнкции, затем операции в соответствии с расставленными скобками.

1. 
   Составляем таблицу истинности формулы
   

№ набора
0	000	0	1	1	1	0
1	001	0	1	1	1	0
2	010	0	1	1	1	1
3	011	0	1	1	1	1
4	100	0	1	1	1	0
5	101	0	1	1	1	0
6	110	1	1	1	1	1
7	111	0	0	0	0	0
№ операции		2	3	4	5	6

---

Для операции №1 (отрицание) не выделено отдельных столбцов, чтобы не загромождать таблицу.

2. 
   По таблице истинности формулы строим её матрицу Грея, отмечая наборы, на которых .
   

3. 
   Получим ДНФ формулы разложением по переменным.
   

Имеем формулу

Раскладываем по переменной , т. к. она встречается в формуле чаще других:


Подсчитываем и .

;


При подсчёте функции мы воспользовались свойством эквивалентности: для любой формулы .
Теперь записываем: .

Получили: .
Раскладываем по переменной (но можно и по переменной ).



Получили:
Раскладываем по переменной .



Получили:
Получили СДНФ функции

.
Строим матрицу Грэя*.

---

*Знаки «+» на рисунке обозначают дизъюнкцию соответствующих конъюнкций и совмещение матриц Грея этих конъюнкций.
Мы могли прекратить разложение функции после разложения по переменной , т.к. после этого разложения мы уже получили сокращённую ДНФ функции .

4. 
   Получим ДНФ подстановкой кратчайших ДНФ элементарных функций, входящих в формулу .
   

Имеем: .
Сначала заменяем импликацию, используя тождество , где и любые формулы, затем сужаем область действия отрицаний. Затем приводим в скобке подобные.
Получаем:




Записываем формулу кратчайшей ДНФ: .
Получаем: .
Получили ДНФ функции : .
Строим матрицу Грея.

5. 
   Построим сокращённую ДНФ по матрице Грея.
   

Под сокращённой ДНФ обычно понимают ДНФ, в которой нет склеек и поглощений.
Выбираем интервалы, которые покрывают все клетки матрицы Грея, на которых
Матрицу Грея берём из пункта 2).


Получили сокращённую ДНФ: .
Перейдём от сокращённой ДНФ к совершенной ДНФ (СДНФ).
Для этого домножаем конъюнкции, всходящие в сокращённую ДНФ, на единичные множители вида

---

, где литерал, которого нет в данной конъюнкции, раскрываем скобки, приводим подобные.
Получаем совершенную ДНФ (СДНФ):
СДНФ мы уже получили ранее в пункте 3).
Полученные в пунктах 3) и 5) СДНФ совпадают с точностью до порядка слагаемых и сомножителей.
Поэтому матрицу Грея для полученной СДНФ мы в этом пункте можем не строить.

6. 
   Найдём минимальную ДНФ функции с помощью матрицы Грея.
   

Имеем матрицу Грея (пункт 2)).


Объединяем соседние ячейки, содержащие единицы, в области Si.

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

1. Область должна быть прямоугольной.

2. Область должна содержать 2^k ячеек, где k=0, 1, 2, … .

3. Область должна быть как можно больше.

4. Областей должно быть как можно меньше.

5. Области могут перекрываться.

6. Области в сумме должны покрывать все единицы.

7. Покрытие единиц областями не обязательно является однозначным.
Прим. На данной карте Карно соседними являются также ячейки правого и левого столбцов.
Получаем 2 области.


Записываем конъюнкции переменных или их отрицаний, соответствующих выделенным областям.

Переменная, меняющая своё значение в выделенной области, в конъюнкцию не включается.

Если переменная в выделенной области равна единице, она входит в конъюнкцию без отрицания.

Ð

---

Смотрите также файлы

• Группа Специальность 18. 02. 06.pptx

• Реферат по дисциплине Философия Тема Философия понимания игр Студент группы апм22.docx

• Орындаан Мектепке дейін оу мен трбиелеу мамандыыны 1 курс студенті Курманова Жанара Максотовна Тексерген Хасанова А. Ж.docx

• Отчет По Курсовой работе По дисциплине Базы данных Тема Фотоаппараты.docx

• 1. Машинноаппаратурная схема приготовления паштета из печени.doc