Вход

Контрольная работа по дисциплине «Математическая логика»

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 267246
Дата создания 09 мая 2015
Страниц 28
Мы сможем обработать ваш заказ (!) 22 апреля в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 410руб.
КУПИТЬ

Описание

Контрольная работа
по дисциплине
«Математическая логика»

Упражнения для практического занятия № 1
Задание 1. Для приведенных формул логики высказываний построить соответствующие им логические функции в виде таблиц истинности, определить общезначимость, выполнимость (невыполнимость) и число моделей формулы:
г) p & (q ˅ ┐p) & ((┐q → p) → q);
Решение.

Задание 2. Записать следующие утверждения в виде формул логики высказываний, построить таблицы истинности и определить обще значимость, выполнимость (невыполнимость) и число моделей полученных формул:
г) Если рабочие или администрация упорствуют, то забастовка будет урегулирована тогда и только тогда, когда правительство добьется судебного запрещения, но войска не будут посланы на завод.
Решение.

Задание 3. Преобразовать следующие формулы в ...

Содержание

Контрольная работа
по дисциплине
«Математическая логика»

Введение

-

Фрагмент работы для ознакомления

За время всех n проходов:i=2nlogi=logn!Во-вторых, работа с промежуточной суммой. Логарифмическая сложность этой операции на шаге i в худшем случае определяется как i*log(Amax).За все проходы имеем:i=1n(i*log⁡(Amax))=(n*n+12)*log⁡(Amax)И деление:log(MAX(s, n))=(n*n+12)*log⁡(Amax)Тогда суммарная временная сложность при логарифмическом критерии есть:logn!+n*n+12*logAmax+log(MAX(s, n))+ (n*n+12)*log⁡(Amax)Окончательно для временной сложности при логарифмическом весовом критерии имеем:O(MAX(logn!,(n*n+12)*log⁡(Amax)))Емкостная сложность при равномерном весовом критерии. Очевидно определяется размером n массива, поэтому есть O(n).Емкостная сложность при логарифмическом весовом критерии. Определяется с одной стороны размером массива и его элементов, а с другой – емкостью счетчика:log(n)+n*log⁡(Amax)Окончательно имеем O(n*log⁡(Amax)).и) В множестве из n дизъюнктов найти и исключить все дизъюнкты с уникальными литералами.Здесь нужно сперва выписать все встречающиеся литералы с общим количеством их включений. Таким образом получим уникальные литералы (с количеством включений, равным единице). Далее следует пройти по всем дизъюнктам, для каждого проверяя, есть ли в нём неуникальный литерал. Если есть – оставляем, если нет – удаляем.Обозначим массив литералов как Аij, где строки – дизъюнкты, в которых данные литералы содержатся. Его размерность – n на m. , Bk c размерностью n*m – массив дизъюнктов, a Cl с такой же размерностью – их частот. Результирующий массив назовём AA. Тогда, используя синтаксис языка Паскаль, можно записать:program NU;procedure put (inp: string)begink:=1; f:=0;while B(k) <> “–“ and f<>1beginif inp=B(k)beginС(k):=С(k)+1;f:=1;endk:=k+1;endif B(k) = “–“ thenbeginB(k) := inp;C(k) := 1;endendbool function isUniq (inp: integer)begink:=1; f:=0;while B(k) <> “–“ and f<>1beginif inp=B(k) and 1=C(k)isUniq:=TrueelseisUniq:=Falsef:=1;k:=k+1;endendbeginfor i:=1 to n*m dobeginB(i):=“–“;С(i):=0;endfor i:=1 to n dofor j:=1 to m doput(A(i,j))ii:=0;for i:=1 to n dobeginf:=0;for j:=1 to m doif isUniq(A(i,j)) thenf:=1;if f=0 then beginii:=ii+1;for j:=1 to m do AA(ii,j)=A(i,j)endendend;Временная сложность при равномерном весовом критерии. Наибольшую вложенность циклов наблюдаем при вызове процедуры put. Следовательно, наиболее значимая часть числа шагов в алгоритме равна:n*m*(n*m)!Таким образом, если принять множество всех литералов во всех дизъюнктах за N (n*m=N), то временная сложность алгоритма при равномерном весовом критерии есть O(N*N!).Временная сложность при логарифмическом весовом критерии. Здесь в основном происходят сравнения строковых величин – литералов, которые имеют одинаковую логарифмическую временную сложность (1). Следовательно, логарифмическая временная сложность всего алгоритма будет равняться равномерной временной сложности n*m*(n*m)! и она есть O(N*N!).Емкостная сложность при равномерном весовом критерии. Очевидно определяется размерами n*m массива, поэтому есть O(N).Емкостная сложность при логарифмическом весовом критерии. Определяется с одной стороны размером задействованных массивов и их элементов (примем за 1), а с другой – емкостями счетчиков:6*N+2*n+m+2Окончательно имеем O(N).Упражнения для практического занятия № 4Задание 1. Записать на языке логики предикатов следующие утверждения:г) Для любых трех чисел, если их произведение – нечетно, то все три числа – нечетны.и) Каждое простое число, неравное двум, нечетно.Решение. г) Для любых трех чисел, если их произведение – нечетно, то все три числа – нечетны.Областью интерпретации является множество чисел (очевидно, целых). Введем трёхместную функциональную и одноместную предикатную формы для обозначения соответственно произведения чисел и чётности:f(x, y, z) – “x * y * z”;P(x) – “x – чётно”.Окончательно, запишем формулу: xyz(┐P(f(x, y, z)) → (┐P(x)&┐P(y)&┐P(z)).и) Каждое простое число, неравное двум, нечетно.Областью интерпретации является множество простых чисел. Введем две одноместные предикатные формы для обозначения соответственно равенства двум и чётности:Р(x) – “x равно двум”;Q(x) – “x – чётно”.Окончательно, запишем формулу: x(┐P(x) → ┐Q(x)).Задание 2. Указать все подформулы, а также области действия квантификаций, свободные и связанные вхождения всех переменных в следующих формулах:г) S(t, w) ˅ xw[(Q(x, w) → P(x)) → R(w)];Решение. Подформулы:S(t, w) Q(x, w)P(x)R(w)Q(x, w) → P(x)(Q(x, w) → P(x)) → R(w)w[(Q(x, w) → P(x)) → R(w)]xw[(Q(x, w) → P(x)) → R(w)]S(t, w) ˅ xw[(Q(x, w) → P(x)) → R(w)];Области действия квантификаций:x: w[(Q(x, w) → P(x)) → R(w)]y: (Q(x, w) → P(x)) → R(w)Свободные вхождения – это все вхождения переменной t и первое вхождение переменной w, а связанные вхождения – это все кроме первого вхождения переменной w и все вхождения переменной x.Упражнения для практического занятия № 5Задание 1. 1. Выполнить сколемизацию следующих формул, представленных в предваренной форме:г) txwy[(P(t, w) & Q(x, y) → S(y)) → R(x)];и) yzux[(┐S(y, x) ˅ Q(u)) → ┐R(z, x, y)];Решение. г) txwy[(P(t, w) & Q(x, y) → S(y)) → R(x)];1. Исключение связок импликации и эквивалентности:txwy[┐(┐(P(t, w) & Q(x, y)) ˅ S(y)) ˅ R(x)]2. Переименование.3. Удаление ненужных квантификаций:4. Сужение области действия отрицаний и снятие двойных отрицаний:txwy[┐((┐P(t, w) ˅ ┐Q(x, y)) ˅ S(y)) ˅ R(x)]txwy[┐(┐P(t, w) ˅ ┐Q(x, y) ˅ S(y)) ˅ R(x)]txwy[(┐┐P(t, w) & ┐┐Q(x, y) & ┐S(y)) ˅ R(x)]txwy[(P(t, w) & Q(x, y) & ┐S(y)) ˅ R(x)]5. Перенос квантификаций в начало формулы.txwy[(P(t, w) & Q(x, y) & ┐S(y)) ˅ R(x)]Получена предваренная форма.Сколемизируем формулу в предваренной форме, полученную в рассмотренном выше примере:txwy[(P(t, w) & Q(x, y) & ┐S(y)) ˅ R(x)]1.Поставим в соответствие каждой -квантифицированной переменной функциональную форму от предшествующих ей в префиксе -квантифицированных переменных:x – f(t);y – g(t, w).2. Подставим в формулу функциональные формы:txwy[(P(t, w) & Q(f(t), g(t, w)) & ┐S(g(t, w))) ˅ R(f(t))]3. Удалим -квантификации:tw[(P(t, w) & Q(f(t), g(t, w)) & ┐S(g(t, w))) ˅ R(f(t))]Получили сколемовскую форму.и) yzux[(┐S(y, x) ˅ Q(u)) → ┐R(z, x, y)];1. Исключение связок импликации и эквивалентности:yzux[┐(┐S(y, x) ˅ Q(u)) ˅ ┐R(z, x, y)]2. Переименование.3. Удаление ненужных квантификаций:4. Сужение области действия отрицаний и снятие двойных отрицаний:yzux[(┐┐S(y, x) & ┐Q(u)) ˅ ┐R(z, x, y)]yzux[(S(y, x) & ┐Q(u)) ˅ ┐R(z, x, y)]5. Перенос квантификаций в начало формулы.yzux[(S(y, x) & ┐Q(u)) ˅ ┐R(z, x, y)]Получена предваренная форма.Сколемизируем формулу в предваренной форме, полученную в рассмотренном выше примере:yzux[(S(y, x) & ┐Q(u)) ˅ ┐R(z, x, y)]1. Поставим в соответствие каждой -квантифицированной переменной функциональную форму от предшествующих ей в префиксе -квантифицированных переменных:z – a;u – f(z).2. Подставим в формулу функциональные формы:yzux[(S(a, x) & ┐Q(f(z))) ˅ ┐R(a, x, y)]3. Удалим -квантификации:yz[┐P(a, y) ˅ Q(f(y, z)) ˅ R(z, x, y)]Получили сколемовскую форму.Задание 2. 2. Преобразовать следующие формулы в клаузальную форму:г) R(t, w) ˅ ┐xw[┐(P(w) ˅ S(x)) → ┐Q(w)];Решение. 1. Исключение связок импликации и эквивалентности:R(t, w) ˅ ┐xw[┐┐(P(w) ˅ S(x)) ˅ ┐Q(w)]2. Переименование.R(t, w) ˅ ┐xu[┐┐(P(u) ˅ S(x)) ˅ ┐Q(u)]3. Удаление ненужных квантификаций:4. Сужение области действия отрицаний и снятие двойных отрицаний:R(t, w) ˅ ┐xu[P(u) ˅ S(x) ˅ ┐Q(u)]R(t, w) ˅ xu(┐[P(u) ˅ S(x) ˅ ┐Q(u)])R(t, w) ˅ xu[┐P(u) & ┐S(x) & ┐┐Q(u)]R(t, w) ˅ xu[┐P(u) & ┐S(x) & Q(u)]5. Перенос квантификаций в начало формулы.xu(R(t, w) ˅ [┐P(u) & ┐S(x) & Q(u)])Получена предваренная форма.Предваренная форма в общем случае может содержать свободные переменные. Однако, при анализе выполнимости достаточно оперировать только замкнутыми формулами, т.е. формулами не содержащими свободных переменных. Действительно, если A – формула, содержащая свободные переменные x0, ..., xn, которая (после переименования) не содержит ни одного связанного вхождения этих переменных, то замкнутая формула x1... xnA выполнима тогда и только тогда, когда выполнима формула A. Например, наша формула xz((R(y) & Q(x)) ˅ P(z, x, y)] после преобразования в замкнутую форму примет вид: yxz((R(y) & Q(x)) ˅ P(z, x, y)].Сколемизируем формулу в предваренной форме, полученную в рассмотренном выше примере:twxu(R(t, w) ˅ [┐P(u) & ┐S(x) & Q(u)])1. Поставим в соответствие каждой -квантифицированной переменной функциональную форму от предшествующих ей в префиксе -квантифицированных переменных:t – a;w – b;u – f(x).2. Подставим в формулу функциональные формы:twxu(R(a, b) ˅ [┐P(f(x)) & ┐S(x) & Q(f(x))])3. Удалим -квантификации:x(R(a, b) ˅ [┐P(f(x)) & ┐S(x) & Q(f(x))])Получили сколемовскую форму.Клаузальная форма – это сколемовская форма, матрица которой является КНФ. Преобразование матрицы в КНФ выполняется так же, как и в логике предикатов. Для нашего примера после применения правил дистрибутивности получим следующую клаузальную форму:x[(R(a, b) ˅ ┐P(f(x))) & (R(a, b) ˅ ┐S(x)) & (R(a, b) ˅ Q(f(x)))]Задание 3. 3. Записать следующие предложения в виде формул логики предикатов и преобразовать их в клаузальную форму:г) Любой студент любит логику или философию тогда и только тогда, когда существует преподаватель, который любит и логику и философию.и) Если каждый обманщик является преступником и всякий, кто подстрекает преступника является преступником, то существует трус, который подстрекает обманщика. Решение. г) Любой студент любит логику или философию тогда и только тогда, когда существует преподаватель, который любит и логику и философию.P(х) – «любить логику»;Q(t) – «любить философию»;хy[(P(х)˅Q(x))↔(P(y)&Q(y))]1. Исключение связок импликации и эквивалентности:хy[{(P(х)˅Q(x))→(P(y)&Q(y))} & {(P(y)&Q(y))→(P(х)˅Q(x))}]хy[{┐(P(х)˅Q(x))˅(P(y)&Q(y))} & {┐(P(y)&Q(y))˅(P(х)˅Q(x))}]2. Переименование.3. Удаление ненужных квантификаций:4. Сужение области действия отрицаний и снятие двойных отрицаний:хy[{(┐P(х)&┐Q(x))˅(P(y)&Q(y))} & {(┐P(y)˅┐Q(y))˅(P(х)˅Q(x))}]хy[{(┐P(х)&┐Q(x))˅(P(y)&Q(y))} & {┐P(y)˅┐Q(y)˅P(х)˅Q(x)}]5. Перенос квантификаций в начало формулы.хy[{(┐P(х)&┐Q(x))˅(P(y)&Q(y))} & {┐P(y)˅┐Q(y)˅P(х)˅Q(x)}]Получена предваренная форма. Она здесь также есть и сколемовской.Сколемизируем формулу в предваренной форме, полученную в рассмотренном выше примере:хy[{(┐P(х)&┐Q(x))˅(P(y)&Q(y))} & {┐P(y)˅┐Q(y)˅P(х)˅Q(x)}]1. Поставим в соответствие каждой -квантифицированной переменной функциональную форму от предшествующих ей в префиксе -квантифицированных переменных:y – f(x).2. Подставим в формулу функциональные формы:хy[{(┐P(х)&┐Q(x))˅(P(f(x))&Q(f(x)))} & {┐P(f(x))˅┐Q(f(x))˅P(х)˅Q(x)}]3. Удалим -квантификации:х[{(┐P(х)&┐Q(x))˅(P(f(x))&Q(f(x)))} & {┐P(f(x))˅┐Q(f(x))˅P(х)˅Q(x)}]Получили сколемовскую форму.Клаузальная форма – это сколемовская форма, матрица которой является КНФ. Преобразование матрицы в КНФ выполняется так же, как и в логике предикатов.

Список литературы

1. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 368 с.
2. Бочаров В.А., Маркин В.И. «Основы логики: Учебник для вузов». – М.: Инфра-М, 2002.
3. Войшвенко Е.К., Дегтярев М.Г. «Логика: Учебник для вузов». – М.: Владос-пресс, 2001.
4. Германова А.Д. «Логика: Словарь и задачник: Учебное пособие для студентов вузов». – М.: Владос-пресс, 1998.
5. Гуц А.К. Математическая лоrика и теория алrоритмов. – Омск: Издательство Наследие. Диалог-Сибирь, 2003. – 108 с.
6. Иванов Е.А. «Логика: Учебник для юридических вузов». – М.: Бек, 1996.
7. Ивин А.А. «Логика. Учебник для гуманитарных факультетов». – М.: Фаир-пресс, 1999.
8. Логика. Учебное пособие для студентов вузов. – Ростов-на-Дону. Изд. «Феникс», 1996.
9. Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. – М.: ФАЗИС, 1996.
10. Марков А. А. Элементы математической логики. – М.: Изд-во МГУ, 1984.
11. Светлов В.А. Логика: Учебник. – М.: Логос, 2012.
12. Свободная онлайн-энциклопедия Википедия [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/
13. Сковиков А.К. Логика: учебник и практикум. Серия: Бакалавр. Базовый курс. – М.: Юрайт, 2014.
14. Судоплатов С.В., Овчинникова Б.В. Математическая логика и теория алгоритмов: Учебник – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004. – 224 с. – (Высшее образование).
15. В.А. Успенский, А.Л. Семёнов Теория алгоритмов: основные открытия и приложения – М., Наука, 1987, 288 c.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00484
© Рефератбанк, 2002 - 2024