|
Содержание работы или список заданий
|
База заданий
I. Логика и исчисление высказываний
1. Записать высказывания в виде формул логики высказываний.
1.1. Сегодня мы пойдем в кино или поедем кататься на лыжах.
1.2. Если будет хорошая погода, то мы пойдем гулять.
1.3. Если х=5 и у=3, то х>y.
1.4. Людоед голоден только тогда, когда он давно не ел.
1.5. Иванов сдал экзамен и получил 5 неравнозначно тому, что Иванов сдал экзамен и получил 5
1.6. Если он бегает по лужайке и у него длинные уши, то он или заяц или осел
2. Построить таблицы истинности для формул
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.
2.9.
2.10.
3. Доказать, что формулы являются тавтологиями
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
4. Доказать полноту (неполноту) систем булевых функций
4.1. {?, ~}
4.2. {|}
4.3. {?}
4.4. {?,&}
4.5. {?,?}
4.6. {?,?}
4.7. {?,0}
4.8. {?,?,1}
4.9. {&, ?,?}
4.10. {?, ?}
4.11. {?, ~}
4.12. {~, ?}
5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
5.7.
5.8.
5.9.
5.10.
6. Получить СКНФ, а затем перейти к СДНФ
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.
6.7.
6.8.
6.9.
6.10.
6.11.
6.12.
7. Получить МДНФ для формул
7.1.
7.2.
7.3.
7.4.
7.5.
7.6.
7.7.
7.8.
II. Логика и исчисление предикатов
1. Записать на языке предикатов
1.1. все студенты учатся;
1.2. некоторые студенты отличники;
1.3. Детям до 16 лет и роботам входить запрещено;
1.4. всем детям до 16 лет и роботам надлежит получить справки;
1.5. для любого числа можно найти большее число;
1.6. x+y=z;
1.7. каждый студент выполнил, по крайней мере, одну лабораторную работу.
1.8. всякий предмет обладает свойством А;
1.9. нечто обладает свойством В;
1.10. если студент отлично учится, не имеет нарушений и занимается общественной работой, то он получает повышенную стипендию;
1.11. не всегда из того, что x лучше y, а y лучше z следует, что x лучше z;
1.12. каждое рациональное число есть действительное число;
1.13. некоторые действительные числа являются рациональными;
1.14. «Все счастливые семьи похожи друг на друга, каждая несчастливая семья несчастлива по-своему»
1.15. всякое N, делящееся на 12 делится на 2, 4 и 6.
2. Получить множество дизъюнктов.
2.1. ?x?y, z, v(R(x, y, z, v)&L(y, z))
2.2. ?x, y, z (P(x)&Q(x, y)??R(z))
2.3. ?x, y, z (P(x)??Q(x, y)?R(z)?M(y))
2.4. ?x P(x)&?x Q(x)? ?x(R(x)?P(x))
2.5. ?x P(x) ? ?x R(x)
2.6. ?x(?y P(x, y)??z(Q(x, z)?R(z)))
2.7. (?x P(x) ? ?y Q(y))&(?x, y R(x, y)??y L(y))
2.8. ?x P(x) ??y R(y)
III. Автоматическое доказательство теорем
1. Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
1.1. А1: Все, что обладает свойством P, имеет свойство R.
А2: Все, что обладает свойством R, имеет свойство Q.
Вопрос: Существует ли нечто, что не обладает свойством P или обладает свойством Q?
1.2. А1: Если х есть часть у и у есть часть z, то х есть часть z.
А2: Палец есть часть руки.
А3: Кисть есть часть руки.
Вопрос: Частью кого является рука?
1.3. А1: Кто ходит в гости по утрам, тот поступает мудро.
А2: Если у кого угодно есть воздушный шарик, тот поступает мудро.
А3: У Пяточка есть воздушный шарик.
Вопрос: Кто поступает мудро?
1.4. А1: Если робот обработал деталь, то ее забирает штабелер.
А2: Если деталь поступила на обработку, то ее обработает робот.
А3: Если человеку нужна деталь, то она поступит на обработку.
А4: Человеку нужна втулка.
Вопрос: Что заберет штабелер.
1.5. А1: Если пассажир сел в самолет, на который ему удалось купить билет, то пассажир думает, что самолет разобьется.
А2: Если пассажир не сел ни в какой самолет или самолет не взлетел, то безопасность пассажира гарантируется.
А3: Безопасность пассажира Васи не гарантируется.
Вопрос: Кто думает, что безопасность пассажира Васи не гарантируется.
2. Доказать теорему
2.1. А1:
T:
2.2. A1:
T:
2.3. А1:
Т:
2.4. А1:
Т:
IV. Теория алгоритмов
1. Построить машину Тьюринга, которая:
1.1. Добавляет 1 к числу Р, представленном в двоичной СС.
1.2. Находит первую единицу в числе Р, представленном в двоичной СС.
1.3. Удаляет последнюю единицу в числе Р, представленном в двоичной СС.
1.4. Стирает слово, состоящее из 1 в последовательности, состоящей из 0 и 1.
1.5. В последовательности, состоящей из 0 и 1 заполнить 1 ячейки с 0, расположенные между двумя 1.
1.6. В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево.
1.7. В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево.
1.8. Пусть число записано в виде последовательности 1. Например: 0 – 1, 1 – 11, 2 – 111, 3 – 1111 и т. д. Машина Тьюринга должна складывать эти числа.
2. Доказать, что функции примитивно-рекурсивны:
2.1. f(x)=x+n;
2.2. f(x)=n;
2.3. f(x,y)=x+y;
2.4. f(x,y)=x*y;
2.5. f(x,y)=xy;
2.6. f(x)=x!
3. Построить нормальный алгорифм Маркова, который:
3.1. добавляет две единицы к входному слову, состоящему из последовательности единиц.
3.2. преобразует исходное слово, состоящее из последовательности единиц, в символ Ч, если количество единиц четное и в символ НЧ, если количество единиц нечетное.
3.3. преобразует любое слово в алфавите {x,y,z} в слово zzx.
3.4. меняет порядок букв на обратный для любого трехбуквенного слова в алфавите {a,b,c}.
№ варианта 4
I. Логика и исчисление высказываний 1.4, 2.7, 2.8, 3.4, 4.4, 5.4, 6.4, 7.4
II. Логика и исчисление предикатов 1.4, 1.12, 2.3
III. Автоматическое доказательство теорем 1.4, 2.1, 2.4
IV. Теория алгоритмов 1.4, 2.4, 3.4
|