ВАРИАНТ 13
.DOCМинистерство образования и науки Российской Федерации
ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (ОмГТУ)
Кафедра «Автоматизированные системы обработки информации и управления»
Расчетно-графическая работа по дисциплине
«Математическая логика и теория алгоритмов»
ВАРИАНТ 13
Принял:
преподаватель А.В. Адельшин
подпись, дата
Выполнила:
студентка гр. АС-223 В.Е.Кузнецова
подпись, дата
Омск 2004
Задание
1. Построить таблицу истинности формулы:
2. Найти СКНФ и СДНФ следующей формулы:
3. Привести формулу к предваренной нормальной форме:
4. Определить, имеет ли место выводимость Г ├ Ф, где
5. Дан внешний алфавит А={0,1}, где 0 – символ пустой ячейки. Построить
машину Тьюринга, которая реализует следующую функцию:
1. Построить таблицу истинности формулы:
Пусть:
Тогда таблица истинности формулы представлена на таблице 1:
|
A |
B |
C |
|
F1 |
F2 |
F3 |
F4 |
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Таблица 1
2. Найти СКНФ и СДНФ следующей формулы:
Найдем СКНФ и СДНФ с помощью таблицы истинности данной формулы
Пусть:
Тогда таблица истинности
формулы представлена на таблице 2:
|
A |
B |
C |
|
|
F1 |
F2 |
F3 |
F4 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
Таблица 2
СДНФ: ABC ABC ABC ABC;
СКНФ: (A B C) (A B C) (A B C) (A B C).
3. Привести формулу к предваренной нормальной форме:
4. Определить, имеет ли место выводимость Г ├ Ф, где
Определим это с помощью таблицы истинности для формулы, полученной из данной выводимости:
|
A |
B |
C |
D |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Таблица 3
Где:
Так как F≠1, то выводимость не имеет место.
5. Дан внешний алфавит А={0,1}, где 0 – символ пустой ячейки. Построить машину Тьюринга, которая реализует следующую функцию:
Алгоритм работает, когда машина начинает работать в состоянии q0 и стоит при этом на позиции правее числа. Числом считается последовательность «1», не разделенных пустыми ячейками.
|
|
q0 |
q1 |
q2 |
|
0 |
0q0Л |
0q0Л |
1q0Л |
|
1 |
0q1Л |
0q2Л |
0q1Л |
Таблица 4 – Машина Тьюринга
Проверим работу алгоритма на примерах.
1. Пусть задано число 3: «01110».
(01110)q0 -> (01110)q0 -> (01100)q1 -> (01000)q2 -> (00000)q1 -> (00000)q1 – стоп.
2. Пусть задано число 2: «0110».
(0110)q0 -> (0110)q0 -> (0100)q1 -> (0000)q2 -> (1000)q2 – стоп.