| 
Математическая логика и теория алгоритмов
Одна практическая работа 500 рублей
Методичка практических работ
Письма присылайте на Почтовый ящик
Практическая работа №1
1. Для приведенных формул логики высказываний построить соответствующие им логические функции в виде таблиц истинности, определить общезначимость, выполнимость (невыполнимость) и число моделей формул.
2. Записать следующие утверждения в виде формул логики высказываний, построить таблицы истинности и определить общезначимость, выполнимость (невыполнимость) и число моделей полученных формул.
А) если Сидоров поедет на автобусе, то его уволят с работ, если автобус опоздает.
Б) необходимое и достаточное условие для жизни растений состоит в наличии питательной почвы, чистого воздуха и солнечного света.
В) Если «Торпедо» или «Динамо» проиграют, а Локомотив выиграет, то Спартак потеряет первое место.
Г) Если рабочие или администрация упорствуют, то забастовка будут урегулирована тогда и только тогда, когда правительство добьется судебного запрещения, но войска не будут посланы на завод.
Д) Если вечером будет туман или снег, то Джон или останется дома, или должен будет взять такси.
Е) Либо рост инфляции эквивалентен снижению уровня жизни, либо рост производства влечет то, что уровень жизни не снижается.
Ж) Если будет идти дождь или снег, то футбольный матч либо не состоится, либо его результат не будет отражать соотношение сил.
З) Если животное млекопитающее и имеет острые зубы и имеет клыки и не есть траву, то это хищник.
3. Преобразовать следующие формулы в КНФ
Практическая работа №2
1. Используя метод резолюций доказать невыполнимость или выполнимость следующих множеств дизъюнктов. Применять произвольный порядок перебора дизъюнктов.
2. Записать формально следующее рассуждение на языке логики высказываний и доказать его справедливость, используя метод резолюций.
а) Посылки: Если идет дождь, то нежарко. Если светит солнце, то жарко. Идет дождь.
Заключение : Нежарко и не светит солнце.
б) Посылки: Экзамен сдан вовремя или сессия продлена. Если сессия продлена, то не сдана курсовая работа или не зачтены лабораторные работы. Курсовая работа сдана. Экзамен вовремя не сдан.
Заключение: Неверно, что если курсовая работа сдана, то лабораторные работы зачтены.
в) Посылки: Если имеет место денежная эмиссия, то растет курс доллара. Если эмиссии нет и инфляция не растет, то курс доллара не растет. Инфляция не растет.
Заключение: Имеет место эмиссия и растет курс доллара или нет эмиссии и курс доллара не растет.
г) Посылки: Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет.
Заключение: Стоимость жизни увеличится.
д) Посылки: Если 2 - простое число, то это наименьшее простое число. Если 2 - наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число.
Заключение: 2 - простое число.
е) Посылки: Джон или переутомился или он болен. Если он переутомился, то он раздражается. Он не раздражается.
Заключение: Джон болен.
ж) Посылки: Если завтра будет холодно, я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен.
Заключение: Я не надену теплое пальто.
з) Посылки: Если исход скачек будет предрешен сговором или в игорных домах будут орудовать шулеры, то доходы от туризма упадут и город пострадает. Если доходы от туризма упадут, полиция будет довольна. Полиция никогда не бывает довольна.
Заключение: Исход скачек не предрешен сговором.
и) Или Сэлли и Боб одного возраста, или Сэлли старше Боба. Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста. Если Сэлли старше Боба, то Боб старше Уолтера.
Заключение: Или Нэнси и Боб не одного возраста, или Боб старше Уолтера.
Практическая работа № 3
1. Определить временную и емкостную сложность алгоритмов решения следующих задач при равномерном и логарифмическом весовых критериях.
а) Вычислить n!
б) В массиве из n целых чисел найти все пары элементов, сумма которых четна и сформировать новый массив из этих сумм.
в) Вычислить nn.
г) Вычислить среднее значение элементов массива из n чисел.
д) Вычислить число размещений A(n,m)= n!/(m!*(n-m)!).
е) Вычислить максимальное значение в массиве чисел.
ж) В множестве из n дизъюнктов найти и исключить все надслучаи.
з) В множестве из n дизъюнктов найти и исключить все тавтологии.
и) В множестве из n дизъюнктов найти и исключить все дизъюнкты с уникальными литералами.
к) В массиве из n целых чисел найти все тройки элементов, в которых сумма двух элементов равна третьему, подсчитать количество таких троек.
л) Упорядочить массив из n целых чисел таким образом, чтобы элементы с четными и нечетными значениями чередовались (пока имеются элементы разной четности).
м) В массиве èç n целых чисел найти все элементы, равные квадрату другого элемента массива и составить массив из этих элементов.
н) В множестве из n дизъюнктов найти и исключить все одинаковые дизъюнкты.
Практическая работа № 4
1. Записать на языке логики предикатов следующие утверждения
а) Для любых трех чисел, если их сумма - четна, то хотя бы одно из этих чисел - четно.
б) Для любых двух чисел, сумма которых - четна, либо оба слагаемых - четны, либо оба - нечетны.
в) Для любых двух чисел, если их сумма - четна, а произведение - нечетно, то оба числа нечетны.
г) Для любых трех чисел, если их произведение - нечетно, то все три числа - нечетны.
д) Ни одна женщина не является одновременно политиком и домашней хозяйкой.
е) Некоторые женщины одновременно являются юристами и членами конгресса.
ж) Каждый второкурсник прочитал хотя бы одну книгу.
з) Кто-то встретил кого-то, а кто-то так никого и не встретил.
и) Каждое простое число, неравное двум, нечетно.
к) Существуют числа, не имеющие общих делителей, кроме единицы.
л) Две прямые, каждая из которых параллельна третьей прямой, параллельны между собой.
м) Судья Джонс не восхищается ни одним жуликом.
н) Если по крайней мере один ученик решил все задачи, то каждую задачу решил по крайней мере один ученик.
о) В Москве живет женщина, имеющая брата в Петербурге, тогда и только тогда, когда в Петербурге живет мужчина, имеющий сестру в Москве.
2. Указать все подформулы, а также области действия квантификаций, свободные и связанные вхождения всех переменных в следующих формулах
Практическая работа № 5
1. Выполнить сколемизацию следующих формул, представленных в предваренной форме
2. Преобразовать следующие формулы в клаузальную форму
3. Записать следующие предложения в виде формул логики предикатов и преобразовать их в клаузальную форму
а) Погода плохая тогда и только тогда, когда неверно, что светит солнце и жарко.
б) Если существуют марсиане и они разумны, тогда существуют марсианские растения, которые съедобны и питательны.
в) Если для любых трех чисел одно из них равно сумме двух других, то существуют два числа, одно из которых является квадратом другого.
г) Любой студент любит логику или философию тогда и только тогда, когда существует преподаватель, который любит и логику и философию.
д) Если некоторые прикладные программы несовместимы с некоторыми операционными системами, то все студенты, занимающиеся программированием, изучают операционные системы.
е) Если для любых двух человек, не являющихся гражданами одной страны, существует третий человек, не являющийся соотечественником первых двух, то эти три человека не могут быть членами одной национальной сборной по футболу.
ж) Для любых трех человек, играющих в одной баскетбольной команде, либо рост каждого из них более двух метров, либо один из них является разыгрывающим.
з) Если не существует интеллектуальных машин и если каждая идеальная машина является интеллектуальной машиной, то идеальная машина не существует.
и) Если каждый обманщик является преступником и всякий, кто подстрекает преступника является преступником, то существует трус, который подстрекает обманщика.
Практическая работа № 6
1. Определить наиболее общий унификатор и соответствующий ему общий пример для следующего множества термов или показать, что множество неунифицируемо.
2. Записать следующее рассуждение на языке логики предикатов и доказать его справедливость, используя метод резолюций.
а) Посылки: Все люди смертны. Сократ человек.
Заключение: Сократ смертен.
б) Посылки: Ни один человек не является четвероногим. Все женщины - люди.
Заключение: Ни одна женщина не является четвероногой.
в) Посылки: Арт - мальчик, у которого нет автомобиля. Джейн любит только мальчиков, имеющих автомобили.
Заключение: Джейн не любит Арта.
г) Посылки: Ни один первокурсник не любит второкурсников. Все живущие в Васюках - второкурсники.
Заключение: Ни один первокурсник не любит никого из живущих в Васюках.
д) Посылки: Ни один республиканец или демократ не является социалистом. Норман Томас - социалист.
е) Посылки: Всякое рациональное число есть действительное число. Существует рациональное число.
ж) Посылки: Все рациональные числа являются действительными числами. Некоторые рациональные числа - целые числа.
Заключение: Некоторые действительные числа - целые числа.
з) Посылки: Все первокурсники встречаются со всеми второкурсниками. Ни один первокурсник не встречается ни с одним студентом предпоследнего курса. Существуют второкурсники.
Заключение: Ни один второкурсник не является студентом предпоследнего курса.
и) Посылки: Для любых объектов x, y и z если x есть часть y и y есть часть z, то x есть часть z. Палец есть часть кисти руки. Кисть руки есть часть руки. Рука есть часть человека.
Заключение: Палец есть часть человека.
| |
