- •Минобрнауки россии
- •Содержание
- •Тема 1.1.5 Совершенные нормальные формы формул логики высказываний
- •Тема 2.1.4 Перевод выражений логики предикатов в клаузальную форму.
- •Тема 4.1Вычислительная сложность алгоритмов
- •Тема 3.4. Машины Тьюринга.
- •3. Методические указания по подготовке к текущей аттестации
Тема 1.1.5 Совершенные нормальные формы формул логики высказываний
Общая трудоемкость 7 часа, из них 2 часа – аудиторные занятия, 5 ч - самостоятельные занятия.
На аудиторных занятиях студенты изучают преобразование формул логики высказываний к совершенному виду, учатся записывать совершенные формулы по заданной таблице истинности. В ходе самостоятельной работы студенты тренируются в решении задач на построение совершенных формул логики высказываний по таблице истинности, проектируют схему цифрового устройства по полученной совершенной нормальной форме, отличающуюся минимумом. минимальным числом логических элементов [1] параграф 13.
Задачи для самоконтроля по теме 1.1.5
Задан алгоритм функционирования некоторого комбинационного цифрового устройства в виде связи между входными и выходными сигналами. Эта связь представлена таблицей истинности (задан последний столбец таблицы истинности, первые три столбца значений переменных имеют стандартный вид
X |
y |
z |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
Спроектируйте схему этого цифрового устройства, отличающуюся минимумом. минимальным числом логических элементов.
№ варианта |
F(X,Y,Z) | |||||||
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
7 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
8 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
9 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
10 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
11 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
12 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
13 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
14 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
15 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
16 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
17 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
18 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
19 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
20 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
21 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
22 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
23 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
24 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
25 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
26 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
27 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
28 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
29 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
30 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |