Практическая работа №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