Пояснительная записка к курсовой работе по информатике. Здесь мы проектировали логическую схему.
Содержание:
Абстрактный синтез логической функции: 3
Построение СДНФ, СКНФ логической функции. 4
Минимизация логической функции- 4
Минимизация методом Квайна — Мак-Класски- 6
Построение минимальной логической функции в заданном базисе- 7
Структурный синтез функциональных схем— 8
Реализация базиса в заданной элементной базе- 8
Построение в базисе «или-не»- 9
Построение в базисе «и-или-не»- 10
Выбор варианта функциональной схемы для реализации- 12
Текст программы, выполняющей задание: 13
Текст программы, выполняющей минимизацию методом Квайна-Мак-Класски: 13
Список использованной литературы: 21
Задание на курсовую работу:
Автоматический диспетчер взлёта и посадки.
- Две взлётно-посадочные полосы.
- АД даёт разрешение на взлёт/посадку на конкретную полосу.
- ПУНКТЫ 3, 4, 5 ИЗ ЗАД. 9:
3.3 Случай, когда к аэропорту подлетает одновременно более 3-х самолётов, считаем невозможным.
3.4 Если к аэропорту подлетело несколько самолётов, то предпочтение отдаётся самолёту с меньшим порядковым номером.
3.5 АД выдаёт подлетевшему самолёту одну из следующих команд:
— садиться немедленно
— сделать один круг над аэропортом
— сделать два круга над аэропортом.
- Команды АД для взлёта:
— взлетать
— ждать.
Абстрактный синтез логической функции:
Вычислим количество возможных вариантов входных данных для АД. К аэропорту могут подлететь одновременно только не более трёх самолётов, При обработке одного самолёта возможно 2 варианта: он хочет сесть и он хочет взлететь. Если обрабатываются два самолёта то для каждого из вариантов одного самолёта возможно два варианта для второго, то есть возможных 2*2=4 варианта. Соответственно для случая с тремя самолётами существует 2*2*2=8 вариантов. Добавим вариант, когда самолётов нет и в сумме получим 2+4+8+1=15 вариантов. Попробуем определить, сколько переменных должно быть
23=8 значит трех переменных не хватит
24=16 значит нужно 4 переменных
Теперь узнаем, сколько будет выходных функций. АД может выделить первую полосу, если обрабатывается один самолёт. Если обрабатывается два самолёта, то возможно несколько ситуаций: первому – первую полосу, второму – вторую (если они оба садятся или взлетают одновременно), первому – вторую полосу, второму – первую (если первый садится, второй — взлетает). Рассуждая таким образом, получим:
| Команда первому самолёту | Команда второму самолёту | Команда третьему самолёту |
| первая полоса | — | — |
| первая полоса | вторая полоса | — |
| вторая полоса | первая полоса | — |
| первая полоса | вторая полоса | ждать\ сделать один круг |
| первая полоса | ждать\ сделать один круг | вторая полоса |
| ждать\ сделать один круг | первая полоса | вторая полоса |
| вторая полоса | первая полоса | ждать\ сделать один круг |
| вторая полоса | ждать\ сделать один круг | первая полоса |
Значит необходимо 3 функции (23=8, а в таблице 8 строк). Заметим в случае, если нет самолётов, автоматический диспетчер будет подавать команду аналогичную с первой строкой в таблице. Но так как самолётов нет, то эту команду никто не будет выполнять.
Кодировка выходного сигнала: для первой строки таблицы 000, для 2-й строки соответственно 001 и так далее.
Построим таблицу истинности. В таблице x1, x2, x3, x4 – переменные, f1,f2,f3-функции. Символ «↓» означает, что самолёт хочет сесть, «↑» -самолёт хочет взлететь
| Входной сигнал | Расшифровка входного сигнала | Выходной сигнал | Расшифровка выходного сигнала | |||||||||
| x1 | x2 | x3 | x4 | Первый самолёт | Второй самолёт | Третий самолёт | f1 | f2 | f3 | первому самолёту | второму самолёту | третьему самолёту |
| 0 | 0 | 0 | 0 | — | — | — | 0 | 0 | 0 | I | ||
| 0 | 0 | 0 | 1 | ↓ | — | — | 0 | 0 | 0 | I | ||
| 0 | 0 | 1 | 0 | ↑ | — | — | 0 | 0 | 0 | I | ||
| 0 | 0 | 1 | 1 | ↓ | ↓ | — | 0 | 0 | 1 | I | II | |
| 0 | 1 | 0 | 0 | ↓ | ↑ | — | 0 | 0 | 1 | I | II | |
| 0 | 1 | 0 | 1 | ↑ | ↓ | — | 0 | 1 | 0 | II | I | |
| 0 | 1 | 1 | 0 | ↑ | ↑ | — | 0 | 0 | 1 | I | II | |
| 0 | 1 | 1 | 1 | ↓ | ↓ | ↓ | 0 | 1 | 1 | I | II | ждать |
| 1 | 0 | 0 | 0 | ↓ | ↓ | ↑ | 0 | 1 | 1 | I | II | ждать |
| 1 | 0 | 0 | 1 | ↓ | ↑ | ↓ | 1 | 0 | 0 | I | ждать | II |
| 1 | 0 | 1 | 0 | ↓ | ↑ | ↑ | 0 | 1 | 1 | I | II | ждать |
| 1 | 0 | 1 | 1 | ↑ | ↓ | ↓ | 1 | 0 | 1 | ждать | I | II |
| 1 | 1 | 0 | 0 | ↑ | ↓ | ↑ | 1 | 1 | 0 | II | I | ждать |
| 1 | 1 | 0 | 1 | ↑ | ↑ | ↓ | 1 | 1 | 1 | II | ждать | I |
| 1 | 1 | 1 | 0 | ↑ | ↑ | ↑ | 0 | 1 | 1 | I | II | ждать |
| 1 | 1 | 1 | 1 | — | — | — | — | — | — | — | — | — |
Построение СДНФ, СКНФ логической функции.
Построим СДНФ логических функций:
F1=x1^¬x2^¬x3^x4٧x1 ٨¬x2 ٨ x3 ٨ x4 ٧ x1 ٨ x2 ٨ ¬ x3 ٨ x4 ٧ x1 ٨ x2 ٨ x3 ٨ x4
F2= ¬ x1 ٨ x2 ٨ x3 ٨ x4 ٧ ¬ x1 ٨ x2 ٨ x3 ٨ x4 ٧ x1 ٨ ¬ x2 ٨ ¬x3 ٨ ¬ x4 ٧ x1 ٨ ¬ x2^ ٨ x3^ ٨ ¬ x4٧ x1^ x2^ ¬ x3^ ¬ x4٧ x1^ x2^ ¬ x3^ x4٧ x1^ x2^ x3^ ¬ x4
F3= ¬ x1^ ¬ x2^ x3^ x4٧ ¬ x1^ x2^ ¬ x3^ ¬ x4٧ ¬ x1^ x2^ x3^ ¬ x4٧ ¬ x1^ x2^ x3^ x4٧ x1^ ¬ x2^ ¬ x3^ ¬ x4٧ x1^ ¬ x2^ x3^ ¬ x4٧ x1^ ¬ x2^ x3^ x4٧ x1^ x2^ ¬ x3^ x4٧ x1^ x2^ x3^ ¬ x4
Теперь построим СКНФ логических функций:
F1= (x1٧ x2٧ x3٧ x4)^ (x1٧ x2٧ x3٧ ¬x4)^ (x1٧ x2٧ ¬x3٧ x4)^ (x1٧ x2٧ ¬x3٧ ¬x4)^ (x1٧ ¬x2٧ x3٧ x4)^ (x1٧ ¬x2٧ x3٧ ¬x4)^ (x1٧ ¬x2٧ ¬x3٧ x4)^ (x1٧ ¬x2٧ ¬x3٧ ¬x4)^ (¬x1٧ x2٧ x3٧ x4)^ (¬x1٧ x2٧ ¬x3٧ x4)^ (¬x1٧ ¬x2٧ ¬x3٧ ¬x4)
F2= (x1٧ x2٧ x3٧ x4)^ (x1٧ x2٧ x3٧ ¬x4)^ (x1٧ x2٧ ¬x3٧ x4)^ (x1٧ x2٧ ¬x3٧ ¬x4)^ (x1٧ ¬x2٧ x3٧ x4)^ (x1٧ ¬x2٧ ¬x3٧ x4)^ (¬x1٧ x2٧ x3٧ ¬x4)^ (¬x1٧ x2٧ ¬x3٧ ¬x4)
F3= (x1٧ x2٧ x3٧ x4)^ (x1٧ x2٧ x3٧ ¬x4)^ (x1٧ x2٧ ¬x3٧ x4)^ (x1٧ ¬x2٧ x3٧ ¬x4)^ (¬x1٧ x2٧ x3٧ ¬x4)^ (¬x1٧ ¬x2٧ x3٧ x4)
Минимизация логической функции
Минимизация методом Карно
Минимизируем первую функцию.
На рисунках объединённые для МДНФ значения обведены зелёным цветом, а для МКНФ — синим.
Принципы минимизации переключательных функций по картам Карно.
Любая пара смежных клеток карты Карно — соседних по вертикали или по горизонтали, либо симметрично расположенных по вертикали или горизонтали – соответствует паре двоичных наборов значений переменных, различающихся значением лишь одной переменной, то есть различных в одном разряде.
Поскольку любой клетке карты n переменных можно поставить в соответствие элементарную конъюнкцию n-го ранга, то паре смежных клеток можно поставить в соответствие ЭК (n-1)-го ранга. При этом в ЭК (n-1)-го ранга будет отсутствовать переменная, значение которой различно в соответствующих наборах.
Рассуждая по индукции, назовём областью смежных клеток совокупность из 2k клеток (k∈{0,…,n}), каждая из которых имеет k смежных с ней клеток из этой области. Смежной области можно поставить в соответствие ЭК по следующему правилу:
Правило покрытия 1. Любой смежной области из 2k клеток можно поставить в соответствие («покрыть») элементарную конъюнкцию (n-k)-го ранга, состоящую из переменных в прямом или инверсном виде, которые имеют постоянное значение во всех двоичных наборах, соответствующих клеткам области. Если «покрытая» область полностью расположена в строках (столбцах), в которой переменная принимает значение 1, то в ЭК эта переменная включается в прямом виде. Если «покрытая» область полностью расположена в строках (столбцах), в которых переменная принимает значение 0, то в ЭК эта переменная включается в инверсном виде. Если «покрытая» область лежит в строках (столбцах), в половине из которых переменная принимает значение 1, а в другой – 0 то эта переменная включается в ЭК, поскольку по ней производится «склеивание» в результате покрытия области..
«Покрытая» область на карте обводится контуром.
Цель минимизации формулы по карте Карно – «покрыть» все клетки, содержащие единицы, наименьшим числом контуров.
МДНФ:
F1=x1^x2^¬x3٧x1^x4
СКНФ:
F1x1^(¬x3٧x4)^ (x2٧x4)
МДНФ:
F2=x1^¬x4٧x2^x4
МКНФ:
F2=(x1٧x4)^( x2٧¬x4)
МДНФ:
F3 = ¬x1^x2^¬x4٧x1^¬x2^¬x4٧x1^x2^x4٧ x3^x4٧x1^x3
МКНФ:
F3 = (x1٧x2٧x4)^ (¬x1٧¬x2٧x3٧x4)^ (x2٧x3٧¬x4)^ (x1٧x3٧¬x4)
Минимизация методом Квайна — Мак-Класски
Метод минимизации переключательной функции, предложенный Квайном и усовершенствованный Мак-Класски, состоит из двух этапов:
- Получение всех простых импликант
- Поиск МДНФ по импликационной таблице покрытий
Первый этап метода основан на последовательном применении закона «склеивания».с целью понижения их ранга и поиска всех простых импликант.
Первый этап завершается, когда невозможно произвести ни одного «склеивания». Результатом первого этапа является множество «несклеенных» (неотмеченных) кубов, которым соответствуют простые импликанты.
Второй этап заключается в построении МДНФ по импликационной таблице покрытия.
Если y1 и y2 – импликанты функции, то импликанта y1 покрывает импликанту y2, если y2 является импликантой y1, то есть на всех наборах, на которых y2 обращается в единицу, покрывающая импликанта y1 обращается в 1. Нетрудно видеть, что y1 поглощает y2: y1٧y2=y1
Для минимизации методом Квайна-Мак-Класски была составлена программа на PASCALE, текст которой приведён в приложении.
С помощью этой программы был получен следующий результат:
МДНФ:
F1=x1^x2^¬x3٧x1^x4
СКНФ:
F1=x1^(¬x3٧x4)^ (x2٧x4)
МДНФ:
F2=x1^¬x4٧x2^x4
МКНФ:
F2=(x1٧x4)^( x2٧¬x4)
МДНФ:
F3 = ¬x1^x2^¬x4٧x1^¬x2^¬x4٧x1^x2^x4٧ x3^x4٧x2^x3
МКНФ:
F3 = (x1٧x2٧x4)^ (¬x1٧¬x2٧x3٧x4)^ (x2٧x3٧¬x4)^ (x1٧x3٧¬x4)
Построение МПНФ логических функций. Для построения МПНФ произведём в МДНФ следующие замены:
¬x=x+1
x٧y=x^y+x+y
F1=x1^x2^¬x3٧x1^x4=x1^x2^¬x3^x4+x1^x2^¬x3+x1^x4
= x1^x2^(x3+1)^x4+x1^x2^(x3+1)+x1^x4
=x1^x2^x3^x4+x1^x2^x4+x1^x2^x3+x1^x2+x1*x4
F2=x1^¬x4^x2^x4+x1^¬x4+x2^x4
= 0+x1^¬x4+x2^x4 (*Свойства ¬*)
=0+x1^(x4+1)+x2^x4
=0+x1^x4+x1+x2^x4
F3 = ¬x1^x2^¬x4٧x1^¬x2^¬x4٧x1^x2^x4٧ x3^x4٧x2^x3
=(¬x1^x2^¬x4 ^x1^¬x2^¬x4+¬x1^x2^¬x4 +x1^¬x2^¬x4) ٧x1^x2^x4٧ x3^x4٧x2^x3
=(0+¬x1^x2^¬x4 +x1^¬x2^¬x4) ٧x1^x2^x4٧ x3^x4٧x2^x3 (*Свойства ¬*)
=(0+¬x1^x2^¬x4 +x1^¬x2^¬x4) ٧( x1^x4٧x2^x3+x1^x2^x4+ x3^x4٧x2^x3)
=(0+¬x1^x2^¬x4 +x1^¬x2^¬x4)^ ( x1^x4٧x2^x3+x1^x2^x4+ x3^x4٧x2^x3) +(0+¬x1^x2^¬x4 +x1^¬x2^¬x4)+( x1^x4٧x2^x3+x1^x2^x4+ x3^x4٧x2^x3)
=(0+¬x1^x2^¬x4 +x1^¬x2^¬x4)^ ( x1^x4٧x2^x3+x1^x2^x4+ x3^x4٧x2^x3) +0+¬x1^x2^¬x4 +x1^¬x2^¬x4+ x1^x4٧x2^x3+x1^x2^x4+ x3^x4٧x2^x3 (*Ассоциативность*)
Построение минимальной логической функции в заданном базисе
МДНФ
МКНФ
Переход в базис «и-не»:
F1=¬ (¬ (x1^x2¬x3٧x1^x4))
= ¬ (¬ (x1^x2^¬x3) ^¬ (x1^x4)) (*Закон де Моргана*)
F2=¬ (¬ (x1^¬x4) ٧x2^x4))
= ¬ (¬ (x1^¬x4) ^¬ (x2^x4)) (*Закон де Моргана*)
F3=¬ (¬ (¬x1^x2^¬x4٧x1^¬x2^¬x4٧x1^x2^x4٧x3^x4٧x1^x3))
= ¬ (¬ (¬x1^x2^¬x4)^ ¬ (x1^¬x2^¬x4)^ ¬ (x1^x2^x4) ^¬ (x3^x4)^ ¬ (x1^x3))(*Закон де Моргана*)
Переход в базис «или-не»:
F1=¬ (¬ (x1^(¬x3٧x4) ^(x2٧x4))
= ¬ (¬x1٧¬ (¬x3٧x4) ٧¬(x2٧x4)) (*Закон де Моргана*)
F2=¬ (¬ (x1٧x4) ^(x2٧¬x4))
= ¬ (¬ (x1٧x4) ٧(x2٧¬x4)) (*Закон де Моргана*)
F3=¬ (¬ (x1٧x2٧x4) ^(¬x1٧¬x2٧x3٧x4) ^(x2٧x3٧¬x4) ^(x1٧x3٧¬x4))
= ¬ (¬ (x1٧x2٧x4) ٧¬ (¬x1٧¬x2٧x3٧x4) ٧¬ (x2٧x3٧¬x4) ٧¬ (x1٧x3٧¬x4)) (*Закон де Моргана*)
Переход в базис «и-или-не»:
F1=¬ ((x1^(x3٧x4) ^(x2٧x4))
= ¬ (¬x1٧¬ (¬x3٧x4) ٧¬ (x2٧x4)) (*Закон де Моргана*)
= ¬ (¬x1٧(x3^¬x4) ٧(¬x2^¬x4)) (*Закон де Моргана*)
F2=¬ (¬ ((x1٧x4) ^(x2٧¬x4)
= ¬ (¬ (x1٧x4) ٧¬(x2٧¬x4)) (*Закон де Моргана*)
= ¬ ((x1^x4) ٧(x2^¬x4)) (*Закон де Моргана*)
F3=¬ (¬ ((x1٧x2٧x4) ^(¬x1٧¬x2٧x3٧x4) ^(x2٧x3٧¬x4) ^(x1٧x3٧¬x4)))
= ¬ (¬ (x1٧x2٧x4) ٧¬ (¬x1٧¬x2٧x3٧x4) ٧¬ (x2٧x3٧¬x4) ٧¬ (x1٧x3٧¬x4)) (*Закон де Моргана*)
= ¬ ((¬x1^¬x2^¬x4) ٧(x1^x2^¬x3^¬x4) ٧(¬x2^¬x3^x4) ٧(¬x1^¬x3^x4)) (*Закон де Моргана*)
Структурный синтез функциональных схем
Реализация базиса в заданной элементной базе
Построение в базисе «и-не»
Для построения функций в базисе «и-не» подходит, например, элемент К155ЛА10, изображённый на рисунке. Для построения функций при помощи К155ЛА10 необходимо преобразовать функции.
Преобразования:
F1= ¬ (¬ (x1^x2^¬x3) ^¬ (x1^x4))
=¬ (¬ (x1^x2^¬x3) ^¬ ((x1^ x1)^x4)) (*идемпотентность*)
=¬ (¬ (x1^x2^¬x3) ^¬ (x1^x4^ x1)) (*ассоциативность*)
F2= ¬ (¬ (x1^¬x4) ^¬ (x2^x4))
= ¬ (¬ ((x1^ x1)^ ¬x4) ^¬ (( x2^ x2^)x4)) (*идемпотентность*)
= ¬ (¬ (x1^ ¬x4^ x1) ^¬ ( x2 ^x4^ x2)) (*ассоциативность*)
F3= ¬ (¬ (¬x1^x2^¬x4) ^⌐(x1^⌐x2^⌐x4) ^⌐(x1^x2^x4) ^⌐(x3^x4) ^⌐(x1^x3))
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4) ^¬ (x3^x4) ^¬ (x1^x3)) (*Закон двойного отрицания*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4)) ٧ ¬ (¬(x3^x4) ^¬ (x1^x3))) (*Закон де Моргана*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))) ^ ¬ (¬ (¬(x3^x4) ^¬ (x1^x3)))) (*Закон де Моргана*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))) ^ ¬ (¬ (¬ ((x3^x3)^x4) ^¬ (x1^(x3^x3))))) (*Идемпотентность*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))) ^ ¬ (¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3)))) (*Ассоциативность*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))^ ¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4)))) ^ ¬ (¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3))^ ¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3)))) (*Идемпотентность*)
= ¬ (¬ (¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))^ ¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4))^ ¬ (¬ (¬x1^x2^¬x4) ^¬ (x1^¬x2^¬x4) ^¬ (x1^x2^x4)))) ^ ¬ (¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3))^ ¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3))^ ¬ (¬ (x3^x4^x3) ^¬ (x1^x3^x3))))
(*Идемпотентность*)
Полученные функции можно реализовать с помощью элемента К155ЛА1. Схема:
Построение в базисе «или-не»
Для построения функций в базисе «или-не» подходит элемент КР1561ЛЕ6.
Для построения функции при помощи КР1561ЛЕ6 необходимо провести преобразования функций.
Преобразования:
F1= ¬ (¬x1٧¬ (¬x3٧x4) ٧¬(x2٧x4))
=¬ (¬(x1٧x1)٧¬ (¬x3٧x4٧x4) ٧¬(x2٧x4٧x4)) (*Идемпотентность*)
=¬ (¬(x1٧x1٧x1)٧¬ (¬x3٧x4٧x4٧x4) ٧¬(x2٧x4٧x4٧x4)) (*Идемпотентность*)
=¬ (¬(x1٧x1٧x1٧x1)٧¬ (¬x3٧x4٧x4٧x4) ٧¬(x2٧x4٧x4٧x4)) (*Идемпотентность*)
F2= ¬ (¬ (x1٧x4) ٧(x2٧¬x4))
= ¬ (¬ (x1٧x4٧x4) ٧( x2٧x2٧¬x4)) (*Идемпотентность*)
= ¬ (¬ (x1٧x4٧x4٧x4) ٧( x2٧x2٧x2٧¬x4)) (*Идемпотентность*)
F3= ¬ (¬ (x1٧x2٧x4) ٧¬ (¬x1٧¬x2٧x3٧x4) ٧¬ (x2٧x3٧¬x4) ٧¬ (x1٧x3٧¬x4))
= ¬ (¬ (x1٧x2٧x4٧x4) ٧¬ (¬x1٧¬x2٧x3٧x4) ٧¬ (x2٧x3٧ x3٧¬x4) ٧¬ (x1٧x3٧¬x4٧¬x4)) (*Идемпотентность*)
= ¬ (¬ (x1٧x2٧x4٧x4) ٧¬ (¬x1٧¬x2٧x3٧x4) ٧¬ (x2٧x3 ٧¬x4٧ x3) ٧¬ (x1٧x3٧¬x4٧¬x4)) (*Ассоциативность*)
По этим функциям можно построить схему:
Построение в базисе «и-или-не»
Для построения функции в базисе «и-или-не» подходит элемент К555ЛР4.
Для построения схемы при помощи К555ЛР4 необходимо сделать преобразования:
F1= ¬ (¬x1٧(x3^¬x4) ٧(¬x2^¬x4))
= ¬ ((¬x1^¬x1)٧(x3^(¬x4^¬x4)) ٧(¬x2^¬x4^¬x4)) (*Идемпотентность*)
= ¬ (((¬x1^¬x1)^ (¬x1^¬x1))٧(x3^¬x4^¬x4^¬x4) ٧(¬x2^¬x4^¬x4¬x4)) (*Идемпотентность*)
= ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4) ٧(¬x2^¬x4^¬x4¬x4)) (*Идемпотентность*)
= ¬ (((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ٧(¬x2^¬x4^¬x4¬x4)) (*Ассоциативность*)
= ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ^¬(¬x2^¬x4^¬x4¬x4) (*Закон де Моргана*)
= ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ^¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4)) (*Идемпотентность*)
= ¬(¬(¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ^¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4)))) (*Закон двойного отрицания*)
= ¬(¬(¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4))) ٧¬(¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4))))
(*Закон де Моргана*)
= ¬(¬(¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4))^ ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ^ ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4)) ^ ¬ ((¬x1^¬x1^ ¬x1^¬x1)٧(x3^¬x4^¬x4^¬x4))) ٧¬(¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4))^ ¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4)) ^ ¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4)) ^ ¬((¬x2^¬x4^¬x4¬x4) ٧(¬x2^¬x4^¬x4¬x4)))) (*Идемпотентность*)
F2= ¬ ((x1^x4) ٧(x2^¬x4))
= ¬ ((x1^(x4^x4)) ٧(x2^(¬x4^¬x4))) (*Идемпотентность*)
= ¬ ((x1^x4^x4) ٧(x2^¬x4^¬x4)) (*Ассоциативность*)
= ¬ ((x1^x4^(x4^x4)) ٧(x2^¬x4^(¬x4^¬x4))) (*Идемпотентность*)
= ¬ ((x1^x4^x4^x4) ٧(x2^¬x4^¬x4^¬x4)) (*Ассоциативность*)
F3= ¬ ((¬x1^¬x2^¬x4) ٧(x1^x2^¬x3^¬x4) ٧(¬x2^¬x3^x4) ٧(¬x1^¬x3^x4))
= ¬ ((¬x1^¬x2^(¬x4^¬x4)) ٧(x1^x2^¬x3^¬x4) ٧(¬x2^¬x3^(x4^x4)) ٧(¬x1^¬x3^(x4^x4))) (*Идемпотентность*)
= ¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4) ٧(¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)) (*Ассоциативность*)
= ¬ (((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4)) ٧((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4))) (*Ассоциативность*)
= ¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4))^ ¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)) (*Закон де Моргана*)
= ¬ (¬ (¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4))^ ¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)))) (*Закон двойного отрицания*)
= ¬ (¬ (¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4))) ٧ ¬(¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4))) (*Закон де Моргана*)
= ¬ (¬ (¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4)) ^¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4)) ^¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4)) ^¬ ((¬x1^¬x2^¬x4^¬x4) ٧(x1^x2^¬x3^¬x4))) ٧ ¬(¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)) ^¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)) ^¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)) ^¬ ((¬x2^¬x3^x4^x4) ٧(¬x1^¬x3^x4^x4)))) (*Идемпотентность*)
По этим функциям была построена схема:
Выбор варианта функциональной схемы для реализации
Для выбора схемы для реализации воспользуемся коэффициентом использования.. Формула для вычисления коэффициента использования:
Рассчитаем коэффициент использования для схемы в на элементах К155ЛА1:
K=36/54=0,(6)
Рассчитаем коэффициент использования для схемы на элементах КР1561ЛЕ6:
K=31/48=0,6458(3)
Рассчитаем коэффициент использования для схемы на элементах К555ЛР4:
K=28 /56=0,5
Так как коэффициент использования у схемы на элементах КР1561ЛЕ6 наибольший, то нужно реализовывать схему на элементах КР1561ЛЕ6.
Приложение
По схеме, выбранной для реализации, была составлена программа на PASCALE.
Текст программы, выполняющей задание:
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
Program automatic_dispetcher; var F1,F2,a:byte; n,m:word; x:array [1..4] of byte; c:char; F:array[1..9] of byte; O:array[1..9] of char; Procedure Element( x1,x2,x3,x4:byte; var F1:byte); Begin if (x1=1) or (x2=1) or (x3=1) or (x4=1) then f1:=0 else f1:=1; End; Function No(x:byte):byte; begin No:=1-x; end; Procedure Options; var p:byte; c:char; s:string; begin Writeln('Если вы хотите изменять вывод поуровнево, то введите "L", а если вы '); Writeln('хотите изменять вывод для каждого прохода через элемент, то введите "E".'); Readln(c); Case (c) of 'L','l': begin Writeln('Выберите:'); Writeln('1 - не выводить промежуточные значения'); Writeln('2 - выводить значения после прохода первого уровня'); Readln(c); case c of '1': begin for n:=1 to 9 do o[n]:='n'; end; '2': begin For n:=1 to 9 do o[n]:='y'; end; else begin Writeln('Ошибка ввода. Изменение настроек прерывается.'); exit; end; end; {case} end; 'E','e': begin Writeln('Выберите: '); Writeln('1 - изменить вывод для прохода через каждый элемент.'); Writeln('2 - изменить вывод для прохода через определённые элементы.'); Readln(c); for n:=1 to 9 do begin Write('Выводить ',n,'-й элемент (y/n)(текущее значение)',o[n],'?'); Readln(o[n]);end; end; end; end; {case} {end;} Procedure PrintLine; var n:byte; begin For n:=1 to 80 do write(chr(205)); end; Procedure Print(o:char;z:byte;f:byte); begin if o='y' then writeln('После прохода через ',z,'-й элемент значение = ',f); end; begin PrintLine; element(0,0,no(0),no(0),f[1]); Writeln(f[1]); Writeln('Автоматический диспетчер.'); Writeln('Программа создана Урвановым Фёдором Владиславовичем в 2005 году.'); Writeln('Введите "o", для изменения настроек, "s" для запуска.'); Readln(c); while (c<>'e') and (c<>'E') do begin if (c='o') or (c='O') then Options; For n:=1 to 4 do begin Write('Введите ',n,'-ю переменную: '); Readln(x[n]); end; Element(x[1],x[1],x[1],x[1],f[1]); print(o[1],1,f[1]); element(no(x[3]),x[4],x[4],x[4],f[2]); print(o[2],2,f[2]); Element(x[2],x[4],x[4],x[4],f[3]); print(o[3],3,f[3]); Element(x[1],x[4],x[4],x[4],f[4]); print(o[4],4,f[4]); Element(x[2],x[2],x[2],No(x[4]),f[5]); print(o[5],5,f[5]); Element(x[1],x[3],no(x[4]),no(x[4]),f[6]); print(o[6],6,f[6]); Element(x[1],x[2],x[4],x[4],f[7]); print(o[7],7,f[7]); Element(No(x[1]),No(x[2]),x[3],x[4],f[8]); print(o[8],8,f[8]); Element(x[2],x[3],No(x[4]),x[3],f[9]); print(o[9],9,f[9]); Element(f[1],f[2],f[2],f[3],f[1]); { print(o[10],10,f[2]); } Element(f[4],f[5],f[5],f[5],f[2]); { print(o[11],11,f[4]);} Element(f[6],f[7],f[8],f[9],f[3]); { print(o[12],12,f[3]);} Writeln('Результат:'); For n:=1 to 3 do begin Writeln('F',n,' =',f[n]); end; WRITEln('Введите команду "e" - выход, "r" - перезапуск программы, "o" - изменить'); Write('настройки. ');readln(c); PrintLine; end; end. |
Текст программы, выполняющей минимизацию методом Квайна-Мак-Класски:
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 |
Program KvainMakklasski; type symb=string[1]; PTlIST=^Tlist; TLIST=record Value:string; Next:PTLIST; end; var F:PTLIst; CountX:Word; change:longint; Foutput:Text; Bout:byte; Function Comb(var n:word):LongInt; Var m,r:longint; Begin If n>0 then r:=2 else r:=0; For m:=2 to n do r:=r*2 ; Comb:=r; end; Procedure Initialize(var f:PTList); var n:word; P,Last:PTlist; s:string; Begin If ParamCount>0 then s:=Paramstr(1)+'.txt' else s:='con'; Assign(INPUT,s);reset(INPUT); if ParamCount>1 then begin s:=ParamStr(2)+'.txt';bout:=0;end else begin s:='con';bout:=1;end; Assign(FOutput,s);Rewrite(FOutput); p:=f;Last:=nil; for n:=1 to comb(CountX) do Begin New(p); If Last=nil then begin F:=p; last:=p;end else Begin Last^.Next:=P;Last:=p; end; end; end; Procedure INPUTFunctionValue(Var F:PTList;CountX:Word); Var n:Longint; P,Last:PTlist; NoError:byte; s:string; Begin P:=f; n:=0; p:=f; Last:=nil; Writeln(Comb(CountX)); s:=''; While (s<>'/exit') do begin New(p); If Last=nil then begin F:=p; last:=p;end else Begin Last^.Next:=P;end; n:=n+1; Writeln('/exit-конец ввода.'); Writeln('Введите ',n,'-ую импликанту: '); Readln(INPUT,s); If s='/exit' then begin Last^.Next:=nil; dispose(p); break; end; p^.Value:=s; If (Length(P^.Value)<>CountX) and (P^.Value<>'/exit') then NoError:=0 else begin NoError:=1;p^.Value:=s;end; Last:=p; end; end; Procedure DelElement(var p1,p2,lastp2:ptlist); var n:byte; begin For n:=1 to CountX do begin if (p1^.Value[n]<>p2^.Value[n]) then if (p1^.Value[n]<>'z') then exit; end; if lastp2<>nil then begin if (p2^.Next<>nil) and (F<>p2) then lastP2^.next:=p2^.Next else begin if (p2^.Next=nil) and ( p2<>f) then begin LastP2^.Next:=nil; end else if (p2^.Next =nil) and (p2=f) then halt; end; end else begin if (p2^.Next<>nil) and (p2=f) then begin f:=p2^.next; end; end; end; Procedure Print_LIst(F:PTLIST); Var p:PTlist; n:Word; Begin p:=F;n:=1; While (p<>nil) do begin If bout=1 then Write(n:6,'-я импликанта: '); Writeln (FOutput,p^.Value,chr(13)); P:=p^.Next; N:=n+1; end; end; Procedure Minim(var f:ptlist); {минимизация функции} var p1,p2,lastP2,buf:PTList; k1,k2,n,m,k,razl,razl2:byte; Procedure DelEl(var p,lp:ptlist); begin if (lp=nil) and (p^.Next<>nil) then f:=p^.Next; if (p^.Next=nil) and (lp=nil) then halt; if (lp<>nil) and (p^.Next=nil) then begin lp^.Next:=nil; end; if (lp<>nil) and (p^.Next<>nil) then lp^.Next:=p^.Next; dispose(p); end; Function ProvSush(k1,k2:byte;s1,s2:symb):boolean; var p,lp:ptlist; n,r,t:byte; begin p:=f;lp:=nil; While (p<>nil) do begin if (((p^.value[k1]=s1) or (p^.value[k1]='z')) and ((p^.Value[k2]=s2)or (p^.value[k2]='z'))) then begin r:=1; t:=0; For n:=1 to CountX do begin if (n<>k1) and (n<>k2) then begin if (p^.Value[n]<>p1^.Value[n]) then begin t:=t+1; if (p^.Value[n]<>'z') then r:=0; end; { (p^.Value[n]<>p1^.Value[n])} end; { (n<>k1) and (n<>k2)} end; {form:=1 to countx} if r=1 then begin ProvSush:=true; if t=0 then Delel(p,lp); exit; end; end; lp:=p; p:=p^.next; end; end; begin p1:=f;P2:=f; Lastp2:=nil;change:=1;{Присваивание начальных значений} While (change<>0) do begin p1:=f; change:=0; While (p1<>nil) do begin p2:=f; LastP2:=nil; While (p2<>nil) do begin razl:=0; razl2:=0; For k:=1 to CountX do begin if (p1^.Value[k]<>p2^.Value[k]) then begin razl2:=razl2+1; if (p2^.Value[k]<>'z') then begin razl:=razl+1; end; end; end; if (razl=1) then begin For k:=1 to CountX do begin if (p1^.Value[k]<>p2^.Value[k]) and (p2^.Value[k]<>'z') then begin if (p1^.value[k]<>'z') then begin p1^.Value[k]:='z'; change:=change+1; DelElement(p1,p2,lastp2); Writeln(FOutput,'Вывод импликант: ',chr(13)); Print_List(F); break; end; {else begin DelElement(p1,p2,lastp2); Writeln(FOutput,'Вывод импликант: ',chr(13)); Print_List(F); break; end; } end; end; { For k:=1 to CountX do} end;{if razl=1} If (razl2=2) then begin k1:=0;k2:=0; For k1:=1 to CountX do begin For k2:=1 to CountX do begin case p1^.Value[k1] of '0': begin if ((p2^.Value[k1]='z') and (p1^.Value[k2]='z') and (p2^.Value[k2]='1') and (ProvSush(k1,k2,'1','0')=true)) or ((p2^.Value[k1]='z') and (p1^.Value[k2]='z') and (p2^.Value[k2]='0') and (ProvSush(k1,k2,'1','1')=true)) then begin p1^.Value[k1]:='z'; DelElement(p1,p2,lastp2); Writeln(FOutput,'Вывод импликант: ',chr(13)); Print_List(F); change:=change+1; Break; end; end; '1': begin if ((p2^.Value[k1]='z') and (p1^.Value[k2]='z') and (p2^.Value[k2]='0') and (ProvSush(k1,k2,'0','1')=true)) or ((p2^.Value[k1]='z') and (p1^.Value[k2]='z') and (p2^.Value[k2]='1') and (ProvSush(k1,k2,'0','0')=true)) then begin p1^.Value[k1]:='z'; DelElement(p1,p2,lastp2); Writeln(FOutput,'Вывод импликант: ',chr(13)); Print_List(F); change:=change+1; Break; end end; 'z': begin if ((p2^.Value[k1]='0') and (p1^.Value[k2]='1') and (p2^.value[k2]='z') and (ProvSush(k1,k2,'1','0')=true)) or ((p2^.Value[k1]='0') and (p1^.Value[k2]='0') and (p2^.value[k2]='z') and (ProvSush(k1,k2,'1','1')=true)) or {begin p1^.Value[k2]:='z'; write('case');DelElement(p2); Break;end} ((p2^.Value[k1]='1') and (p1^.Value[k2]='0') and (p2^.Value[k2]='z') and (ProvSush(k1,k2,'0','1')=true)) or ((p2^.Value[k1]='1') and (p1^.Value[k2]='1') and (p2^.Value[k2]='z') and (ProvSush(k1,k2,'0','0')=true)) then begin p1^.Value[k2]:='z'; DelElement(p1,p2,lastp2); Writeln(FOutput,'Вывод импликант: ',chr(13)); Print_List(F); change:=change+1; Break;end; end; end;{case}; end; { For k2:=1 to CountX do} end; end; {if razl2=2} lastp2:=p2; if p2^.Next<>nil then p2:=p2^.next else break; end; if p1^.Next<>nil then p1:=p1^.Next else break; end; end;{change<>0} end; Procedure Write_Start_Text; begin Writeln('Минимизация логической функции методом Квайна - Мак-Класски.'); Writeln('Программа создана Урвановым Фёдором Владиславовичем в 2005 году.'); Writeln('При вводе импликант СДНФ на выходе получится МДНФ, при вводе импликант '); writeln('СКНФ на выходе получится МКНФ.'); Writeln('При вводе импликант СДНФ переменные импликант нужно вводить в прямом виде.'); Writeln('При вводе импликант СКНФ переменные импликант нужно вводить в инверсном виде.'); Writeln('Вы можете запустить программу с параметрами. Первый параметр - файл где'); Writeln('находятся исходные данные. Второй параметр - файл, куда программа запишет'); Writeln('результат. Файл с исходными данными должен иметь следующие данные:'); Writeln('1) - количество переменных в функции. (На отдельной строке)'); Writeln('2) - импликанты на которых функция принимает нужное значение. Каждая импликанта'); Writeln('должна быть на отдельной строке.'); Writeln('3) - последняя строка: "/exit".'); end; begin Initialize(F); Writeln; Write_Start_Text; Write('Введите количество переменных в функции> ');readln(INPUT,countX); Writeln('1-переменная в импликанте в прямом виде, 0-переменная в инверсном виде,'); Writeln('"z"-переменная принимает любое значение (1 или 0).'); Writeln('Введите импликаты в которых функция принимает нужное значение.'); writeln('Нажимайте "ВВОД" после ввода каждой импликанты.'); INPUTFunctionValue(F,CountX); Minim(f); Writeln(Foutput,'Окончательный результат:',chr(13)); Print_List(F); Write(FOutput,'Программа завершила свою работу. '); Write('Нажмите "Ввод" для выхода'); Readln(INPUT); Close(INPUT); Close(Foutput); end. |
Вывод:
По заданию была составлена функция, которая затем была реализована. Из трёх схем в различных базисах была выбрана схема с наилучшим коэффициентом использования оборудования. По выбранной схеме была составлена программа на Turbo Pascal-е 7.0. По результатам работы этой программы была составлена временная диаграмма схемы:
Сравнивая эту диаграмму с таблицей истинности реализуемой функции, сделаем вывод, что схема была построена верно.
Список использованной литературы:
- Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М; Новосибирск: НГТУ, 2003. – 280 с. – (Серия «Высшее образование»).
- Власов В. В., Крайников А. В., Чепайкин В. Л Вычислительные машины и системы: Арифметические и логические основы построения ЭВМ: Текст лекций. Чебоксары: Изд-во Чуваш. ун-та, 1991. 96 с.
- Юшин А. М. Цифровые микросхемы для электронных устройств: Справ. для ПТУ. – М.: Высш шк., 1993. – 176 с.:ил.
- Пухальский — Новосильцева «Цифровые устройства: учебное пособие для ВТУЗов СПб: Политехника:1996 г. -885 с.