Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение. Контрольная работа по математической логике
|
|
Контрольная работа по математической логике
Задание №1
a) Постройте таблицe истинности пропозициональной формулы X.
b) Является ли формула X тавтологией?
c) Найти совершенно дизъюнктивную нормальную форму формулы X.
d) Найти совершенно конъюнктивную нормальную форму формулы X.
| Варианты | X |
| (A Þ Ø (B Ú C))Û (Ø (A Þ B)Ú Ø (A Þ C)) | |
| (Ø (P Ú Q)Þ R)Û (Ø (P Þ Q)Ú Ø (P Þ R)) | |
| (A Ú Ø (B Þ C))Û (Ø (A Ú B)Þ Ø (A Ú C)) | |
| (Ø (P Þ Q)Ú R)Û (Ø (P Ú Q)Þ Ø (P Ú R)) | |
| Ø (S Þ (T Ú U))Û (Ø (S Þ T)Ú Ø (S Þ U)) | |
| (A Þ Ø (B Ú C))Û (Ø (A Þ B)Ù Ø (A Þ C)) | |
| (Ø (P Ú Q)Þ R)Û (Ø (P Þ Q)Ù Ø (P Þ R)) | |
| (A Ú Ø (B Þ C))Û (Ø (A Ù B)Þ Ø (A Ù C)) | |
| (Ø (P Þ Q)Ú R)Û (Ø (P Ù Q)Þ Ø (P Ù R)) | |
| Ø (S Þ (T Ú U))Û (Ø (S Þ T)Ù Ø (S Þ U)) | |
| (A Þ Ø (B Ù C))Û (Ø (A Þ B)Ù Ø (A Þ C)) | |
| (Ø (P Ù Q)Þ R)Û (Ø (P Þ Q)Ù Ø (P Þ R)) | |
| (A Ù Ø (B Þ C))Û (Ø (A Ù B)Þ Ø (A Ù C)) | |
| (Ø (P Þ Q)Ù R)Û (Ø (P Ù Q)Þ Ø (P Ù R)) | |
| Ø (S Þ (T Ù U))Û (Ø (S Þ T)Ù Ø (S Þ U)) | |
| (A Þ Ø (B Ù C))Û (Ø (A Þ B)Ú Ø (A Þ C)) | |
| (Ø (P Ù Q)Þ R)Û (Ø (P Þ Q)Ú Ø (P Þ R)) | |
| (A Ù Ø (B Þ C))Û (Ø (A Ú B)Þ Ø (A Ú C)) | |
| (Ø (P Þ Q)Ù R)Û (Ø (P Ú Q)Þ Ø (P Ú R)) | |
| Ø (S Þ (T Ù U))Û (Ø (S Þ T)Ú Ø (S Þ U)) |
Вариант 0. X =Ø ((S Þ T)Ù U)Û (Ø (S Þ U)Ú Ø (T Þ U)).
Решение.
a) Обозначим формулу Ø ((S Þ T)Ù U) через Y.
Обозначим формулу Ø (S Þ U)Ú Ø (T Þ U) через Z.
Построим полную таблицу истинности формулы X = Y Û Z:
| S | T | U | S Þ T | (S Þ T)Ù U | Y | S Þ U | Ø (S Þ U) | T Þ U | Ø (T Þ U) | Z | X |
b) Формула X не является тавтологией: X =0 например, при S = T = U =0.
c) Для переменной p и истинностного значения a определим:
pa = p, если a =1, и, pa =Ø p, если a =0.
Пусть f (p 1, …, pn) – функция истинности, определяемая таблицей истинности для формулы X. Тогда СДНФ формулы X находим по формуле:
X = Ú { p 1 a 1Ù …Ù pnan | a 1, …, an Î {1, 0}, f (a 1, …, an)=1}.
(Формула X равна дизъюнкции конъюнкций вида p 1 a 1Ù …Ù pnan для истинностных значений a 1, …, an таких, что f (a 1, …, an)=1).
Ответ:
X =(S Ù T Ù U)Ú (S Ù T Ù Ø U)Ú (S Ù Ø T Ù Ø U)Ú (Ø S Ù T Ù U)Ú (Ø S Ù T Ù Ø U)Ú (Ø S Ù Ø T Ù U).
d) Для переменной p и истинностного значения a определим:
p Ø a =Ø p, если a =1, и, p Ø a = p, если a =0.
Пусть f (p 1, …, pn) – функция истинности, определяемая таблицей истинности для формулы X. Тогда СКНФ формулы X находим по формуле:
X = Ù { p 1Ø a 1Ù …Ù pn Ø an | a 1, …, an Î {1, 0}, f (a 1, …, an)=0}.
Ответ:
X =(Ø S Ú T Ú Ø U)Ù (S Ú T Ú U).
(Формула X равна конъюнкции дизъюнкций вида p 1Ø a 1Ù …Ù pn Ø an для истинностных значений a 1, …, an таких, что f (a 1, …, an)=0).