2015-03-22
884Вывод: Шекспир был умным человеком.
Представим символьно высказывания:
А – автор литературных произведений, постигший природу человека
В – умный человек
С – автор является истинным поэтом
D – автор способен волновать сердца людей
E – Шекспир
F – автор «Гамлета»
Теперь запишем задание в формальном виде:
1. Все авторы литературных произведений, постигшие природу человека, умные люди.
2. Ни одного автора нельзя считать истинным поэтом, если он не способен волновать сердца людей.
3. Шекспир написал "Гамлета".
4. Ни один автор, не постигший природу человека, не способен волновать сердца людей
5. Только истинный поэт мог написать "Гамлета".
Вывод: Шекспир был умным человеком.
Представим все высказывания в дизъюнктивной форме.
|
|
|
|
 - что и требовалось доказать
|
Задача 2. Сформулировать представленную выше задачу на языке логики предикатов и упростить полученную систему используя теоремы и тождества логики предикатов.
|
|
|
Тождество доказано.
Задача 3. Сконструировать машину Тьюринга (написать соответствующую программу) для решения следующей задачи.
Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q 1собозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Машина Тьюринга для этой программы выглядит тривиально просто — в ней всего одно состояние. Такая машина Тьюринга выполняет следующие действия: стирает самый правый штрих, ищет разделитель (пустую ячейку) и в эту пустую ячейку помещает штрих, тем самым сформирована непрерывная последовательность штрихов длины n + m.
Задача 4. Записать логическую функцию, соответствующую высказыванию:
«Если прогноз показывает, что можно получить крупную прибыль на выпуске новых товаров (A), то при разработке стратегии развития фирме следует сделать упор на маркетинг (B) или сеть распределения (C), а также целесообразно открыть более крупные магазины (D) и расширить торговую сеть (E)».
Задача 5. Записать сложное высказывание «Если гражданин имеет право голоса (A), то ему больше 18 лет (B). Сидорову нет 18 лет, следовательно, он имеет право голоса» логической формулой и минимизировать его, используя карту Карно.
| 
| 
| 
| 
|
|
|
|
|
В нашем случае не меняется переменная , значит 
Задача 6. Каждой пропозициональной форме, содержащей n различных пропозициональных букв, соответствует таблица истинности с 2n строками.
Составить таблицу истинности для следующей формы: ((А & В) V (С)) → (А → В))
|
|
| 
| 
| 
|
| 
| 
|
Задача 7. Составить рекуррентное выражение для вычисления функции f(n) = z2 • х + у (рекурсия проводится по переменной z), представив функции h(х, у, z, m) и g(х, у, z).
Тогда
Задача 8. Представить на языке ГСА (операторные вершины обозначить буквами А1, А2, …, Аn, а логические – буквами α1, α2, …, αm), используя рекомендуемые ГОСТом обозначения, алгоритм решения следующей задачи.
Расположить четыре представленных числа A, B, C и D в порядке «убывания волн» (4, 7, 13, 8 → 13, 7, 8, 4; 5, 11, 8, 12 → 12, 8, 11, 5).
Введем обозначения:
A0 – «начало»
А1 – «x1 = A»
А2 – «x1 = B; x2 = A»
А3 – «x2 = B»
А4 – «x3 = x2; x2 = x1; x1 = C»
А5 – «x3 = x2; x2 = C»
А6 – «x3 = C»
А7 – «x4 = x3; x3 = x2; x2 = x1; x1 = D»
А8 – «x4 = x3; x3 = x2; x2 = D»
А9 – «x4 = x3; x3 = D»
А10 – «x4 = C»
А11 – «x5 = x2; x2 = x3; x3 = x5»
А12 – «конец»
α1 – «B > x1»
α2 – «C > x2»
α3 – «C > x1»
α4 – «D > x3»
α5 – «D > x1»
α6 – «D > x2»
Задача 9. Представленный в предыдущем задании алгоритм перевести с языка ГСА на язык ЛСА (используя обозначения предыдущей задачи).
A0A1α1↑1A2↑2↑↓1A3↓2α2↑3α3↑4A40↑5↓4A50↑6↓3A6↓5↓6α4↑7α5↑8A70↑9↓8α6↑10A8↑11↓10A9↑12↓7A10↓12↓11↓9A11A12
Библиографический список
1. Игошин В.И. Задачи и модели по математической логике и теории алгоритмов. – 2-е изд. – М.: Академия, 2006. – 304 с.
2. Тимофеева, И.Л. Математическая логика: курс лекций: учеб. пособие. – 2-е изд. – М.: КДУ, 2007.
3. Гладкий А.В. Математическая логика и теория алгоритмов. – М.: МЦНМО, 2001.
4. Зюзьков В.М, Шелупанов А.А. Математическая логика и теория алгоритмов: Учебное пособие для вузов. – 2-е изд. – М.: Горячая линия–Телеком, 2007. – 176 с.
5. Игошин В.И. Задачник-практикум по математической логике: уч. пособие. – М.: Академия, 2006.
6. Галиев Ш.И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А.Н. Туполева. 2002. – 270 с.
