Автор: Пользователь скрыл имя, 18 Января 2012 в 16:09, контрольная работа
1.1 Для приведенных формул логики высказываний построить соответствующие им логические функции в виде таблиц истинности, определить общезначимость, выполнимость (невыполнимость) и число моделей формулы:
г) x & (y Ú Øx) & ((Øy ® x) ® y);
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}
Решение:
Рассмотрим вывод невыполнимости с использованием стратегии предпочтения одночленам. В начале выпишем и пронумеруем дизъюнкты исходного множества:
Справедливость утверждения доказана.
Рассмотрим теперь вывод с использованием линейной стратегии:
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)}
Информация о работе Контрольная работа по "Математическая логика и теория алгоритмов"