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