Муниципальное образовательное учреждение высшего профессионального образования
Южно-Уральский профессиональный институт
Факультет управления и информационных технологий
Кафедра информатики и вычислительной техники
Контрольная работа
по дисциплине «Математическая логия и теория алгоритмов»
Студент
гр. ВМз-01-08, факультет УиИТ
____________________ М.О.Белозерова
«__»___________2009
Преподаватель
___________________ С.А. Рудаков
к.п.н. «__»___________2009
Челябинск
2009
1. Задание по логике высказываний
Ниже приведены по три клаузы в одном варианте. Каждую клаузу необходимо доказать следующими методами: резолюций и с помощью таблиц истинности.
a. А, В v С => А & В; С
b. B v С, (А -> В) -> (С -> А) => А
c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D
Докажем с помощью метода резолюций истинность следующей клаузы:
a. А, В v С => А & В; С
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
A, В v C, -B v -C, -A => 0
P1 P2 P3 P4
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
№ п/п Выводы Почему 1. 0 Р2, Р3 2. 0 P1, P4 3. 0 1, 2
Докажем с помощью метода резолюций истинность следующей клаузы:
B v С, (А -> В) -> (С -> А) => А
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
В v С, A v -B v -C, -A => 0
P1 P2 P3
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
№ п/п Выводы Почему 1. А Р1, Р2 2. 0 P3, 1
Докажем с помощью метода резолюций истинность следующей клаузы:
c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С;
А & В & D
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
А v В v С, -В v -D v А, -С v –В v А, -А v -В v С, -D v A v В, P1 P2 P3 P4 P5 D v -А v В,
- С v В v D, A v С v D,
-С v -А v В, -А, -В, -С v -А, -В, -D =>0 P6 P7 P8 P9 P10 P11 P12 P13 P14
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
№ п/п Выводы Почему 1. C v -D P4,P5 2. A v -C P2,P7 3. B v C P6,P8 4. -A v -D P12,1 5. -C v -A P9,P11 6. -C 2,5 7. B 3,6 8. -A v -D P10,4 9. -A v -D P14,8 10. 0 P1,P3 11. 0 P13,7 12. 0 9,10 13. 0 11,12
Докажем с помощью таблиц истинности следующую клаузу:
А, В v С => А, В v С
P1 P2 C1 C2
Докажем с помощью таблиц истинности следующую клаузу:
B v С, (А -> В) -> (С -> А) => А
P1 P2 C1
Теперь составим таблицу истинности (табл. 1.1) , в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р.
n А B C P1 P2 P C1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 2 0 1 0 1 1 1 0 3 0 1 1 1 0 0 0 4 1 0 0 0 1 0 1 5 1 0 1 1 1 1 1 6 1 1 0 1 1 1 1 7 1 1 1 1 1 1 1
Клауза считается ложной, т.к. единицы следствия (С1) не накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины не образуют подмножество единиц следствия.
Докажем с помощью таблиц истинности следующую клаузу:
А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
P1 P2 P3 P4 P5
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D
Р6 Р7 Р8 Р9 С1 C2 C3 C4 C5
Теперь составим таблицу истинности (табл. ............
