Контрольная работа по "Математическая логика и теория алгоритмов"
1.1 Для приведенных формул логики высказываний построить соответствующие им логические функции в виде таблиц истинности, определить общезначимость, выполнимость (невыполнимость) и число моделей формулы:
г) x & (y Ú Øx) & ((Øy ® x) ® y);
Решение
Построим таблицу истинности, вычисляя сначала значения подформул:
| x | y | z | Øx | yÚØx | x&(yÚØx) | Øy | Øy®x | (Øy®x)®y | x & (yÚØx)&((Øy®x)®y) |
| T | T | T | F | T | T | F | T | T | T |
| T | T | F | F | T | T | F | T | T | T |
| T | F | T | F | F | F | T | T | F | F |
| T | F | F | F | F | F | T | T | F | F |
| F | T | T | T | T | F | F | T | T | F |
| F | T | F | T | T | F | F | T | T | F |
| F | F | T | T | T | F | T | F | T | F |
| F | F | F | T | T | F | T | F | T | F |
Данная
формула выполнима, так как она
принимает значение T. Есть 2 интерпретации,
при которых формула принимает значение
T, значит, она имеет 2 модели. Формула не
является общезначимой, так как она принимает
значение F при некоторых интерпретациях.
1.2. Записать следующие утверждения в виде формул логики высказываний, построить таблицы истинности и определить общезначимость, выполнимость (невыполнимость) и число моделей полученных формул:
г) Если рабочие или администрация упорствуют, то забастовка будет урегулирована тогда и только тогда, когда правительство добьется судебного запрещения, но войска не будут посланы на завод.
Решение:
Обозначим все встретившиеся элементарные высказывания пропозициональными переменными:
p – «рабочие упорствуют»;
q – «администрация упорствует»;
r – «забастовка будет урегулирована»;
t – «правительство добьется судебного запрещения»;
s – «войска будут посланы на завод».
Тогда формула запишется в следующем виде:
(p Ú q) ® (r ↔ (t & s)). Построим таблицу истинности, вычисляя сначала значения подформул:
| p | q | r | t | s | p Ú q | t & s | r ↔ (t & s) | (p Ú q) ® (r ↔ (t & s)) |
| T | T | T | T | T | T | T | T | T |
| T | T | T | T | F | T | F | F | F |
| T | T | T | F | T | T | F | F | F |
| T | T | T | F | F | T | F | F | F |
| T | T | F | T | T | T | T | F | F |
| T | T | F | T | F | T | F | T | T |
| T | T | F | F | T | T | F | T | T |
| T | T | F | F | F | T | F | T | T |
| T | F | T | T | T | T | T | T | T |
| T | F | T | T | F | T | F | F | F |
| T | F | T | F | T | T | F | F | F |
| T | F | T | F | F | T | F | F | F |
| T | F | F | T | T | T | T | F | F |
| T | F | F | T | F | T | F | T | T |
| T | F | F | F | T | T | F | T | T |
| T | F | F | F | F | T | F | T | T |
| F | T | T | T | T | T | T | T | T |
| F | T | T | T | F | T | F | F | F |
| F | T | T | F | T | T | F | F | F |
| F | T | T | F | F | T | F | F | F |
| F | T | F | T | T | T | T | F | F |
| F | T | F | T | F | T | F | T | T |
| F | T | F | F | T | T | F | T | T |
| F | T | F | F | F | T | F | T | T |
| F | F | T | T | T | F | T | T | T |
| F | F | T | T | F | F | F | F | T |
| F | F | T | F | T | F | F | F | T |
| F | F | T | F | F | F | F | F | T |
| F | F | F | T | T | F | T | F | T |
| F | F | F | T | F | F | F | T | T |
| F | F | F | F | T | F | F | T | T |
| F | F | F | F | F | F | F | T | T |
Данная
формула выполнима, так как она
принимает значение T. Есть 20 интерпретаций,
при которых формула принимает значение
T, значит, она имеет 20 моделей. Формула
не является общезначимой, так как она
принимает значение F при некоторых интерпретациях.
1.3
. Преобразовать следующие
д) Ø(z Ú y Ú Øx) ® Ø(t ® Øs)
Решение:
Выполним преобразования в соответствии с алгоритмом.
- Исключение связки эквивалентности, импликации:
Ø (z Ú y Ú Øx) ® Ø (t ® Øs)= ØØ( z Ú y Ú Øx) Ú Ø (t ® Øs)= ØØ( z Ú y Ú Øx) Ú Ø (Øt Ú Øs);
- Сужение области действия отрицаний и снятие двойных отрицаний:
ØØ( z Ú y Ú Øx) Ú Ø (Øt Ú Øs) = (z Ú y Ú Øx) Ú (ØØt & ØØs)= z Ú y Ú Øx Ú (t & s);
- Применение дистрибутивности, исключение тавтологий:
z Ú y Ú Øx Ú (t & s) = (z Ú y Ú Øx Ú t) & (z Ú y Ú Øx Ú s).
2.1. Используя метод резолюций доказать невыполнимость (или выполнимость) следующих множеств дизъюнктов. Применять произвольный порядок перебора дизъюнктов, а также, по указанию преподавателя, одну из следующих стратегий: предпочтение одночленам, линейную, насыщение уровня.
б) {(y Ú z), (y Ú Øz), (z Ú Øy), Øz}
Решение:
Рассмотрим вывод невыполнимости с использованием стратегии предпочтения одночленам. В начале выпишем и пронумеруем дизъюнкты исходного множества:
- y Ú z;
- y Ú Øz;
- z Ú Øy;
- Øz;
- y (4, 1);
- z (5, 3);
- F (6, 4)
Справедливость утверждения доказана.
Рассмотрим теперь вывод с использованием линейной стратегии:
5) y (1, 2);
6) z (5, 3);
7) F (6, 4)
Справедливость утверждения доказана.
2.2 Записать формально следующее рассуждение на языке логики высказываний и доказать его справедливость, используя метод резолюций.
б) Посылки: Экзамен сдан вовремя или сессия продлена. Если сессия продлена, то не сдана курсовая работа или не зачтены лабораторные работы. Курсовая работа сдана. Экзамен вовремя не сдан.
Заключение: Неверно, что если курсовая работа сдана, то лабораторные работы зачтены.
Решение:
- Введем символические обозначения элементарных высказываний:
p – «экзамен сдан вовремя»;
q – «сессия продлена»;
r – «сдана курсовая работа»;
s – «зачтены лабораторные работы».
Запишем данное утверждение формально в виде логического следования:
y Ú Øz
{(p Ú q); (q ® (Ør Ú Øs)); r; Øp}╞ Ø(r ® s).
- Добавим отрицание целевого утверждения к множеству посылок:
{(p Ú q); (q ® (Ør Ú Øs)); r; Øp; ØØ(r ® s)}
- Преобразуем все формулы в КНФ:
(q ® (Ør Ú Øs)) = (Øq Ú Ør Ú Øs);
ØØ(r ® s) = (Ør Ú s).
Получим
следующее множество
{(p Ú q); (Øq Ú Ør Ú Øs); r; Øp; (Ør Ú s)}
- Рассмотрим вывод с использованием линейной стратегии. В начале выпишем и пронумеруем дизъюнкты исходного множества:
- p Ú q;
- Øq Ú Ør Ú Øs;
- r;
- Øp;
- Ør Ú s;
- p Ú Ør Ú Øs (1, 2);
- p Ú Øs (3, 6);
- Øs (4, 7);
- s (3, 5);
- F (8, 9).
Справедливость утверждения доказана.
4.1 Записать на языке логики предикатов следующие утверждения:
м) Судья Джонс не восхищается ни одним жуликом.
Решение:
Областью интерпретации является множество людей. Введем одноместные предикатные формы для обозначения судей и жуликов и двухместнуую предикатную для обозначения восхощения:
P(x) – “ x – судья”;
Q(x) – “x – жулик”;
R(x, y) – “x восхищается у”;
d – “Джонс”.
Окончательно
запишем формулу: P(d) & "xØ(Q(x) & R(d, x)).
4.2 Указать все подформулы, а также области действия квантификаций, свободные и связанные вхождения всех переменных в следующих формулах:
г) S(t, w) Ú $x"w[(Y(x, w) ® X(x)) ® Z(w)]
Решение:
- Перечислим все подформулы:
S(t, w);
$x"w[(Y(x, w) ® X(x)) ® Z(w)];
"w[(Y(x, w) ® X(x)) ® Z(w)];
(Y(x, w) ® X(x)) ® Z(w);
Y(x, w) ® X(x);
Y(x, w); X(x); Z(w).
- Области действия квантификаций:
$x – (Y(x, w) ® X(x)) ® Z(w);
"w – (Y(x, w) ® X(x)) ® Z(w).
- Вхождения переменных:
Переменная
x имеет только 3 связанных вхождения в
квантификаторе $x и предикатах Y(x, w)
и X(x) и не имеет свободных. Переменная
w имеет только три связанных вхождения
в квантификаторе "w и предикатах Y(x, w)
и Z(w) и одно свободное в предикате S(t, w).
Переменная t имеет только одно свободное
вхождение в предикате S(t, w).
5.1 Выполнить сколемизацию следующих формул, представленных в предваренной форме:
б) "v"w"t$z[(Z(w, t) Ú S(z)) « (X(v) & ØS(w))]
Решение:
- Поставим каждой $-квантифицированной переменной функциональную форму от предшествующих ей в префиксе "-квантифицированных переменных:
z – f(v, w, t).
- Подставим в формулу функциональные формы:
"v"w"t$z[(Z(w, t) Ú S(f(v, w, t))) « (X(v) & ØS(w))]
- Удалим $-квантификацию:
"v"w"t[(Z(w, t) Ú S(f(v, w, t))) « (X(v) & ØS(w))]
Получили
Сколемовскую форму.
5.2 Преобразовать следующие формулы в клаузальную форму:
г) Z(t, w) Ú Ø$x"w[Ø(X(w) Ú S(x)) ® ØY(w)]
Решение:
Сначала получим предваренную форму:
- Исключим связки импликации и эквивалентности:
Z(t, w) Ú Ø$x"w[ØØ(X(w) Ú S(x)) Ú ØY(w)]
- Переименование и удаление ненужных квантификаций:
Z(t, w) Ú Ø$x"u[ØØ(X(u) Ú S(x)) Ú ØY(u)]
- Сужение области действия отрицаний и снятие двойных отрицаний:
Z(t, w) Ú "x$u[ØX(u) & ØS(x) & Y(u)]
- Перенос квантификаций в начало формулы:
"x$u (Z(t, w) Ú [ØX(u) & ØS(x) & Y(u)])
Получена предваренная форма. Получим из нее скорлемовскую форму:
- Поставим каждой $-квантифицированной переменной функциональную форму от предшествующих ей в префиксе "-квантифицированных переменных:
u = f(x)
- Подставим в формулу функциональные формы и удалим $-квантификацию:
"x(Z(t, w) Ú [ØX(f(x)) & ØS(x) & Y(f(x))])
Получили Сколемовскую форму.
- Приведем к КНФ:
"x((Z(t, w) Ú ØX(f(x))) & (Z(t, w) Ú ØS(x)) & (Z(t, w) ÚY(f(x))))
Поскольку все переменные связаны "- квантификациями, префикс может быть опущен.
Имеем множество дизъюнктов (каузальную форму):
{Z(t, w) Ú ØX(f(x));
Z(t, w) Ú ØS(x);
Z(t, w) ÚY(f(x))}
5.3. Записать следующие предложения в виде формул логики предикатов и преобразовать их в клаузальную форму:
в) Если для любых трех чисел одно из них равно сумме двух других, то существуют два числа, одно из которых является квадратом другого.
Решение:
- Запишем формулу.
Областью интерпретации является множество действительных чисел. Введем двухместную функциональную форму для обозначения суммы чисел, одноместную функциональную форму для обозначения возведения числа в квадрат и двухместную предикатную для обозначения равенства:
f(x, y) – “x + y”;
g(x) – “x2”
P(x, y) – “ x = y”.
Окончательно запишем формулу:
"x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) ®$x$yP(g(x), y).
- Исключим связки импликации и эквивалентности:
Ø"x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) Ú $x$yP(g(x), y))
- Переименование и удаление ненужных квантификаций:
Ø"x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) Ú $u$vP(g(u), v))
- Сужение области действия отрицаний и снятие двойных отрицаний:
$x$y$z (ØP(f(x, y), z) & ØP(f(x, z), y) & ØP(f(y, z), x)) Ú $u$vP(g(u), v))
- Перенос квантификаций в начало формулы:
- Контрольная работа по «Математическая статистика»
- Контрольная работа по "Математическая статистика"
- Контрольная работа по "Математическая статистика"
- Контрольная работа по "Математическая статистика"
- Контрольная работа по « Математические задачи электроэнергетики »
- Контрольная работа по «Математические методы в иследовании экономике»
- Контрольная работа по «Математические методы в психологии»
- Контрольная работа по "Математике и информатике"
- Контрольная работа по "Математике и информатике"
- Контрольная работа по "Математике и информатике"
- Контрольная работа по "Математики"
- Контрольная работа по "Математики"
- Контрольная работа по "Математики"
- Контрольная работа по математики 1 курса БГУИР
