Логіка висловлювань

Муніципальне освітній заклад вищої професійної освіти
Південно-Уральський професійний інститут
Факультет управління та інформаційних технологій
Кафедра інформатики та обчислювальної техніки

Контрольна робота

з дисципліни «Математична логія і теорія алгоритмів"
Студент
гр. ВМЗ-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
Праворуч від кожного нового диз'юнктів будемо писати номери використовуються диз'юнктів, отримаємо:

Доведемо за допомогою методу резолюцій істинність наступного клауз:
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
Тепер складемо таблицю істинності (табл. 1.3), в якій під Р розуміється узагальнена причина, тобто кон'юнкція всіх Р.

n	А	B	C	D	P1	P2	Р3	Р4	Р5	P6	P7	P8	P9	P	C1	C2	C3	C4	C5
0	0	0	0	0	1	1	1	1	1	1	1	0	1	0	0	0	0	0	0
1	0	0	0	1	1	1	1	1	0	1	1	1	1	0	0	0	0	0	1
2	0	0	1	0	1	1	1	1	1	1	0	1	1	0	0	0	0	0	0
3	0	0	1	1	1	1	1	1	0	1	1	1	1	0	0	0	0	0	1
4	0	1	0	0	1	1	1	1	1	1	1	0	1	0	0	1	0	1	0
5	0	1	0	1	1	0	1	1	1	1	1	1	1	0	0	1	1	1	1
6	0	1	1	0	1	1	0	1	1	1	1	1	1	0	0	1	1	1	0
7	0	1	1	1	1	0	0	1	1	1	1	1	1	0	0	1	1	1	1
8	1	0	0	0	0	1	1	1	1	1	1	1	1	0	1	0	1	0	0
9	1	0	0	1	0	1	1	1	1	0	1	1	1	0	1	0	1	0	1
10	1	0	1	0	1	1	1	1	1	1	0	1	0	0	1	0	1	0	0
11	1	0	1	1	1	1	1	1	1	0	1	1	0	0	1	0	1	0	1
12	1	1	0	0	1	1	1	0	1	1	1	1	1	0	1	1	1	1	0
13	1	1	0	1	1	1	1	0	1	1	1	1	1	0	1	1	1	1	1
14	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0
15	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

Клаузе вважається дійсною, т.к одиниці слідства (С1) накривають всі одиниці узагальненої причини (Р), тобто одиниці узагальненої причини утворюють підмножину одиниць слідства.
2. Складання легенди по Клаузе
Клаузе 1: А, В v С => А & В; З
Машина їде по Копейськ шосе. На дорозі небезпечно, тому що вона покрита льодом або мокра. Отже, машина їде по шосе або по крижаній дорозі або по мокрій.
Клаузе 2: B v С, (А -> В) -> (С -> А) => А
Студент Іванов знаходився на уроці або в коридорі. На уроці була контрольна робота, Іванов отримав четвертку, то він був на уроці, він був в коридорі, не дивлячись на те, що він отримав четвірку. Це говорить про те, що у студента Іванова є, прагнення добре вчиться.
3. Складання клауз за легендою
Нижче наведена легенда. Запишіть з використанням 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	0	0	0	0	0	1	1	1	1	1	0
1	0	0	0	0	0	0	1	1	1	1	1	1	1
2	0	0	0	0	0	1	0	1	1	1	1	1	1
3	0	0	0	0	0	1	1	1	1	1	1	1	1
4	0	0	0	0	1	0	0	1	1	1	1	1	0
5	0	0	0	0	1	0	1	1	1	1	1	1	0
6	0	0	0	0	1	1	0	1	1	1	1	1	1
7	0	0	0	0	1	1	1	1	1	1	1	1	1
8	0	0	0	1	0	0	0	1	1	0	1	0	0
9	0	0	0	1	0	0	1	1	1	0	1	0	1
10	0	0	0	1	0	1	0	1	1	0	1	0	1
11	0	0	0	1	0	1	1	1	1	0	1	0	1
12	0	0	0	1	1	0	0	1	1	0	1	0	0
13	0	0	0	1	1	0	1	1	1	0	1	0	1
14	0	0	0	1	1	1	0	1	1	1	1	1	1
15	0	0	0	1	1	1	1	1	1	1	1	1	1
16	0	0	1	0	0	0	0	1	1	1	1	1	0
17	0	0	1	0	0	0	1	1	1	1	1	1	1
18	0	0	1	0	0	1	0	1	1	1	1	1	0
19	0	0	1	0	0	1	1	1	1	1	1	1	1
20	0	0	1	0	1	0	0	1	1	1	1	1	0
21	0	0	1	0	1	0	1	1	1	1	1	1	0
22	0	0	1	0	1	1	0	1	1	1	1	1	0
23	0	0	1	0	1	1	1	1	1	1	1	1	0
24	0	0	1	1	0	0	0	1	1	0	1	0	0
25	0	0	1	1	0	0	1	1	1	0	1	0	1
26	0	0	1	1	0	1	0	1	1	0	1	0	0
27	0	0	1	1	0	1	1	1	1	0	1	0	1
28	0	0	1	1	1	0	0	1	1	0	1	0	0
29	0	0	1	1	1	0	1	1	1	0	1	0	0
30	0	0	1	1	1	1	0	1	1	1	1	1	0
31	0	0	1	1	1	1	1	1	1	1	1	1	0
32	0	1	0	0	0	0	1	1	1	1	1	1	1
33	0	1	0	0	0	1	0	1	1	1	0	0	1
34	0	1	0	0	0	1	1	1	1	1	1	1	0
35	0	1	0	0	1	0	0	1	1	1	0	0	0
36	0	1	0	0	1	0	1	1	1	1	1	1	0
37	0	1	0	0	1	1	0	1	1	1	0	0	1
38	0	1	0	0	1	1	1	1	1	1	1	1	1
39	0	1	0	1	0	0	0	1	1	0	0	0	0
40	0	1	0	1	0	0	1	1	1	0	1	1	1
41	0	1	0	1	0	1	0	1	1	0	0	0	1
42	0	1	0	1	0	1	1	1	1	0	1	1	1
43	0	1	0	1	1	0	0	1	1	0	0	0	0
44	0	1	0	1	1	0	1	1	1	0	1	1	0
45	0	1	0	1	1	1	0	1	1	1	0	0	1
46	0	1	0	1	1	1	1	1	1	1	1	1	1
47	0	1	1	0	0	0	0	1	1	1	0	0	0
48	0	1	1	0	0	0	1	1	1	1	1	1	1
49	0	1	1	0	0	1	0	1	1	1	0	0	0
50	0	1	1	0	0	1	1	1	1	1	1	1	1
51	0	1	1	0	1	0	0	1	1	1	0	0	0
52	0	1	1	0	1	0	1	1	1	1	1	1	0
53	0	1	1	0	1	1	0	1	1	1	0	0	0
54	0	1	1	0	1	1	1	1	1	1	1	1	0
55	0	1	1	1	0	0	0	1	1	0	0	0	0
56	0	1	1	1	0	0	1	1	1	0	1	1	1
57	0	1	1	1	0	1	0	1	1	0	0	0	0
58	0	1	1	1	0	1	1	1	1	0	1	1	1
59	0	1	1	1	1	0	0	1	1	0	0	0	0
60	0	1	1	1	1	0	1	1	1	0	1	1	0
61	0	1	1	1	1	1	0	1	1	1	0	0	0
62	0	1	1	1	1	1	1	1	1	1	1	1	0
63	1	0	0	0	0	0	0	0	0	1	1	0	0
64	1	0	0	0	0	0	1	0	0	1	1	0	1
65	1	0	0	0	0	1	0	0	0	1	1	0	1
66	1	0	0	0	0	1	1	0	0	1	1	0	1
67	1	0	0	0	1	0	0	0	0	1	1	0	0
68	1	0	0	0	1	0	1	0	0	1	1	0	0
69	1	0	0	0	1	1	0	0	0	1	1	0	1
70	1	0	0	0	1	1	1	0	0	1	1	0	1
71	1	0	0	1	0	0	0	0	1	0	1	0	0
72	1	0	0	1	0	0	1	0	1	0	1	0	1
73	1	0	0	1	0	1	0	0	1	0	1	0	1
74	1	0	0	1	0	1	1	0	1	0	1	0	1
75	1	0	0	1	1	0	0	0	1	0	1	0	0
76	1	0	0	1	1	0	1	0	1	0	1	0	0
77	1	0	0	1	1	1	0	0	1	1	1	0	1
78	1	0	0	1	1	1	1	0	1	1	1	0	1
79	1	0	1	0	0	0	0	0	1	1	1	0	0
80	1	0	1	0	0	0	1	0	1	1	1	0	1
81	1	0	1	0	0	1	0	0	1	1	1	0	0
82	1	0	1	0	0	1	1	0	1	1	1	0	1
83	1	0	1	0	1	0	0	0	1	1	1	0	0
84	1	0	1	0	1	0	1	0	1	1	1	0	0
85	1	0	1	0	1	1	0	0	1	1	1	0	0
86	1	0	1	0	1	1	1	0	1	1	1	0	0
87	1	0	1	1	0	0	0	0	1	0	1	0	0
88	1	0	1	1	0	0	1	0	1	0	1	0	1
89	1	0	1	1	0	1	0	0	1	0	1	0	0
90	1	0	1	1	0	1	1	0	1	0	1	0	1
91	1	0	1	1	1	0	0	0	1	0	1	0	0
92	1	0	1	1	1	0	1	0	1	0	1	0	0
93	1	0	1	1	1	1	0	0	1	0	1	0	0
94	1	0	1	1	1	1	1	0	1	0	1	0	0
95	1	1	0	0	0	0	0	1	0	1	0	0	0
96	1	1	0	0	0	0	1	1	0	1	1	0	1
97	1	1	0	0	0	1	0	1	0	1	0	0	1
98	1	1	0	0	0	1	1	1	0	1	1	0	1
99	1	1	0	0	1	0	0	1	0	1	0	0	0
100	1	1	0	0	1	0	1	1	0	1	1	0	0
101	1	1	0	0	1	1	0	1	0	1	0	0	1
102	1	1	0	0	1	1	1	1	0	1	1	0	1
103	1	1	0	1	0	0	0	1	1	0	0	0	0
104	1	1	0	1	0	0	1	1	1	0	1	0	1
105	1	1	0	1	0	1	0	1	1	0	0	0	1
106	1	1	0	1	0	1	1	1	1	0	1	0	1
107	1	1	0	1	1	0	0	1	1	0	0	0	0
108	1	1	0	1	1	0	1	1	1	0	1	0	0
109	1	1	0	1	1	1	0	1	1	1	0	0	1
110	1	1	0	1	1	1	1	1	1	1	1	1	1
111	1	1	1	0	0	0	0	1	1	0	0	0	0
112	1	1	1	0	0	0	1	1	1	0	1	0	1
113	1	1	1	0	0	1	0	1	1	0	0	0	0
114	1	1	1	0	0	1	1	1	1	0	1	0	1
115	1	1	1	0	1	0	0	1	1	0	0	0	0
116	1	1	1	0	1	0	1	1	1	0	1	0	0
117	1	1	1	0	1	1	0	1	1	0	0	0	0
118	1	1	1	0	1	1	1	1	1	0	1	0	0
119	1	1	1	1	0	0	0	1	1	1	0	0	0
120	1	1	1	1	0	0	1	1	1	1	1	1	1
121	1	1	1	1	0	1	0	1	1	1	0	0	0
122	1	1	1	1	0	1	1	1	1	1	1	1	1
123	1	1	1	1	1	0	0	1	1	1	0	0	0
124	1	1	1	1	1	0	1	1	1	1	1	1	0
125	1	1	1	1	1	1	0	1	1	1	0	0	0
126	1	1	1	1	1	1	1	1	1	1	1	1	0

З таблиці видно, що чотири одиниці узагальненої посилки (Р) не покриваються одиницями помилкового слідства (-Е); одиниці ж істинного слідства (Е -> (В & D)) цілком накривають одиниці узагальненої посилки.
4. Завдання по логіці предикатів
Встановити істинність логічного виразу свого варіанту шляхом конкретизації.
х y (А (x) -> В (у)) = х A (x) -> x В (х)
Доказ: