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

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

Упражнения для практического занятия № 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)}]Получили сколемовскую форму.Клаузальная форма – это сколемовская форма, матрица которой является КНФ. Преобразование матрицы в КНФ выполняется так же, как и в логике предикатов.