Автор работы: Пользователь скрыл имя, 20 Мая 2012 в 18:03, реферат
Из истории мы знаем о том, как более тысячи лет назад наши предки сильно страдали от беспорядка в своей жизни, от неумения «владеть собой». Тогда они обращались за помощью к варягам: «Земля наша велика и обильна, а порядка в ней нет. Приходите княжить и владеть нами.» (Нестор. Повесть временных лет.)
Сегодня наша жизнь снова как будто являет собой пример очевидного беспорядка, от которого страдают очень многие.
Между тем всем и давно известно, что порядок в действиях, поступках, в жизни отдельного человека и общества есть внешнее выражение внутреннего порядка в умах, мыслях людей. Вопросы о порядке в мыслях, о структуре, формах и законах правильного мышления рассматриваются логикой. Поэтому знакомство с основами логики представляется жизненно важным делом для каждого человека.
_
1. А В = А +В
2. А В = А &В
3. А В = В А правило контрапозиции
4. А + В = А & В правила де Моргана
5. А & В = А + В
6. А & B = B & A правила коммутативности
7. A +B = B +A
8. A +(A & B) = A правила поглощения
9. A &(A +B) = A
10. A & (B +C) = (A & B) +(A & C) правила дистрибутивности
11. A +(B & C) = (A +B) &(A +C)
12. (A +B) &(C +D) = A & C +A & D +B &C +B & D правило раскрытия скобок
=
13. А = А правило двойного отрицания
14. А +A = A правила равносильности (идемпотентности)
15. A & A = A
16. A +( B +C) = (A +B) +C правила ассоциативности
17. A & ( B & C) = (A & B ) &C
18. A + A = 1
19. A & A = 0
20. A +1 = 1
21. A + 0 = A
22. A & 1 = A
23. A & 0 = 0
24. A &A & B = 0
25. A + A +B = 1
26. (А &A) +B = B
27. (A + A) &B = B
28. (A +B) &( A +B) =B
29. (A B)= (A +B) &( B +A)
30. (A +C) &( B + C)= (A +C) &(B + C) &(A +B)
31. (A +C) & C=(A +C) & C & A
32. C &(B + C) = С & (B + C) & B
Всем формулы логики высказываний делятся на три класса:
1. тождественно истинные формулы
2. тождественно ложные
3. те. которые при одних значениях входящих в них переменных истинны, а при других - ложны.
В 1 и 3 случаях формулы являются выполнимыми, т.е. истинными хотя бы при одном наборе истинностных значений входящих в них переменных.
Используя возможность замены одних символических выражений высказываний на другие, но тождественные исходным, можно, например, для любой формулы определить является ли она тождественно истинной формулой, т.е. законом логики, или тождественно ложной, или выполнимой при определенном сочетании истинностных значений переменных. Для этой цели применяется процедура приведения формулы логики высказываний к конъюнктивной нормальной форме (сокращенно КНФ).
КНФ - конъюнкция дизъюнкций переменных или их отрицание, т.е. кратная конъюнкция, конъюнктивные члены которой - это кратные дизъюнкции, в которых каждый из дизъюнктов есть какая-нибудь переменная или отрицание переменной. Например, формулы
(А + B + C) &(B + C) & (A +C); A & (A +B) &(B +C) & C &(A +B +C)
находятся в КНФ. Во второй формуле конъюнктивные члены А и С - «вырожденные» дизъюнкции с одним дизъюнктом.
Приведение любой формулы к КНФ предполагает следующие требования:
1. Все подформулы вида А B заменить на (А V В) ^ ( А V В)
2. Все подформулы вида А B заменить, согласно правилу 29, на формулы
_ _
( А +B) & (B +A)
3. Все подформулы вида В C заменить, согласно правилу 1, на В +C или, на В&С, cогласно правилу 2.
4. Все отрицания, стоящие над сложными подформулами, опускаются до подформул, образовавшихся после первого шага формулы (по правилам де Моргана).
5.Устаняются все двойные отрицания над формулами, согласно правилу 13.
6.Раскрываются все скобки по правилу дистрибутивности дизъюнкции относительно конъюнкции - при приведении к КНФ, или дистрибутивности конъюнкции относительно дизъюнкции - при приведении к дизъюнктивной нормальной форме (сокращенно ДНФ).
Если в элементарной дизъюнкции содержится хотя бы одна пара дизъюнктов, один из которых есть некоторая переменная, а другой ее отрицание, то это будет тождественно истинная дизъюнкция.
Формула логики высказываний в КНФ тождественно истинна, если каждый из ее конъюнктивных членов т.е. каждая элементарная дизъюнкция, содержит хотя бы одну переменную со знаком отрицания и без него. Поэтому о тождественной истинности формулы можно судить по ее виду в КНФ.
Пусть дана формула (А& ( А В)) В
По правилу 1 избавляемся от импликаций (А&(А +B)) +В
В большой скобке применяем правило 5 (правило де Моргана)
_ _
(А +(А +B)) +В
В маленькой скобке применяем снова правило 5
_ _
(А +(А & B)) +В
В большой скобке применяем правило 11 (правило дистрибутивности)
_ _ _
((A + A) & (A + B)) + B
По правилу 16 (правило ассоциативности дизъюнкции) к каждому из конъюнктов в большой скобке присоединяем через знак «+» остающуюся В
_ _ _
(A + A + B) & (A + B + B)
В полученной КНФ каждый из двух конъюнктов содержит переменную со знаком отрицания и без него, следовательно, это тождественно истинная формула.
Если в результате приведения к КНФ выяснится, что имеющаяся формула оказалась не тождественно истинной, то нужно проверить на тождественную истинность ее отрицание. Если отрицание данной формулы окажется тождественно истинной формулой, то значит сама исходная формула является тождественно ложной. Если же отрицание данной формулы окажется не тождественно истинным, то, значит, исходная формула при одних значениях переменных истинна, а при других ложна.
ЗАДАНИЕ 23. Путем приведения данной формулы логики высказываний к КНФ выяснить, является ли она тождественно истинной или тождественно ложной.
Вариант: _
1. (A + C) ((B & C) A)
_
2. (AA) (B(A + C))
3. (AC) (B(B + C))
4. ((A+ B) & (AC) & ( BC)) C
5. A((AB) B)
6. ((AB) & (CD)) ((AC) (B & D))
7. (AB) ((A& C) (A&C))
8. ((AB) + (AC)) (A(A + C))
9. A(B(A&B))
_ _
10. ((AB) &(BC) &(CA)) + A
Совершенная конъюнктивная нормальная форма
(сокращенно СКНФ)
Каждая не тождественно истинная формула имеет одну КНФ, которая называется совершенной. СКНФ - это КНФ, обладающая следующими свойствами:
a) в ней нет двух одинаковых конъюнктов (т.е. получающихся один из другого при замене по правилу 7);
b) ни один конъюнкт (т.е. элементарная дизъюнкция) не содержит двух одинаковых дизъюнктов;
c) ни один конъюнкт не содержит переменной с отрицанием и без него;
d) в каждом конъюнкте имеются все, содержащиеся в данной формуле, переменные.
Для приведения любой формулы логики высказываний к СКНФ необходимо:
1. Сначала привести формулу к КНФ.
2. Требование а)выполняют посредством правила 15, устранением всех повторений, т.е. любой конъюнкт остается в формуле только на одном месте и вычеркивается из остальных.
3. Требование b) выполняют посредством правила 14, устранением всех повторений в каждом конъюнкте, т.е. в каждой из элементарных дизъюнкций.
4. Требование с) выполняют посредством правила 22, устранением из формулы тех конъюнктов, которые являются тождественно истинными элементарными дизъюнкциями.
5. Требование d) выполняется приписыванием ко всем конъюнктам, в которых отсутствует какая либо из имеющихся в формуле переменных, знака дизъюнкции и, вслед за ним тождественно ложной конъюнкции этой переменной и ее отрицания
( Х &X).
Дизъюнктивное присоединение к любой формуле ложной формулы, согласно правилу 21, не изменяет условий ее истинности. Затем применяем правило 11. Эту процедуру повторять до тех пор, пока не выполним требование d).
Пример приведения к СКНФ:
Сначала приводим к КНФ: _ = =
Полученную КНФ преобразуем в СКНФ:
Согласно требованию с) вычеркиваем первый конъюнкт, а в третьем, согласно требованию b) устраняем повторения. Получаем формулу (В + C + A) & (C +A)
Но во втором конъюнкте нет В. Поэтому присоединяем сюда знаком дизъюнкции (B & B).
Получаем формулу
(B + C + A) & ( C + A + (B & B))
По правилу дистрибутивности 11 получаем:
(B + C + A) & (C + A + B) & (C + A + B)
Устраняем появившиеся повторения конъюнктов и получаем СКНФ:
( B + C + A) & ( C + A + B)
Приведением формулы к СКНФ можно решать задачу отыскания всех логических следствий из данных формул. Для этого все данные формулы связываем знаком конъюнкции «&» и для возникшей таким образом формулы находим ее СКНФ. Каждый конъюнктивный член СКНФ, а также любая конъюнкция любого числа этих членов является следствием из данных формул. Затем, используя правил 28 и другие, можно получить более простую форму записи этих следствий.
Пусть даны две формулы: А и А В
Связываем их знаком конъюнкции A & (AB)
Находим СКНФ получившейся формулы
A & (AB) = A & (A + B) = ( A + (B & B)) & (A + B) = (A + B) & (A + B) &(A + B)
Полученная СКНФ позволяет увидеть все следствия данных формул в СКНФ.
Этими следствиями будут:
1. A + B
2. A + B
3. A + B
4. (A + B) & (A + B)
5. (A + B) & (A + B)
6. (A + B) & (A + B)
7. (A + B) & (A + B) & (A + B)
Применяя правило упрощения 28 к следствию 4, получаем следствие - А, которое есть одна из данных формул. В обзор всех следствий будут входить и сами данные формулы.
Из следствия 5 посредством правила 28 получаем следствие - В;
Из следствия 6 посредством правила 29 получаем следствие - A B;
Следствие 7 дает следствие - А & В.
ЗАДАНИЕ 24. Упростить данную формулу посредством приведения ее к СКНФ, или найти все следствия из предложенного набора посылок.
Варианты:
1. ((А + В)&(ВС )) + ((В А)&(В + С))
2. ((А & В) (В + С )) & ((В&А) (ВС))
3. В + С; В А ; ВС
4. ((А + В) (A + С )) & ((В + C) (A + В))
5. A B; ВС; С А
6. ((А В) & (C & A) & (B C)) + A
7. (A & B) C; В; С
8. ( А В) +(B + C)
9. А В; A C; A & (BC)
10. (((АВ) В) + B) + ( A & C)
Сокращенная конъюнктивная нормальная форма
(сокращенно КНФ)
Сокращенная конъюнктивная форма позволяет найти все простые следствия из конъюнкции данных формул. Следствие называют простым если оно есть не содержащая повторений и не тождественно истинная элементарная дизъюнкция, которая, будучи логическим следствием из конъюнкции данных формул, не поглощается никаким более сильным следствием такого же вида, т.е. после отбрасывания какого-нибудь из ее членов перестает быть следствием из данных формул. Иногда более сильное следствие поглощает слабые. Так, при тождественной истинности формул вида AB, считают, что А сильнее чем В.
Сокращенная КНФ некоторой формулы есть конъюнкция всех ее простых следствий.
Она обладает следующими свойствами:
a) ни в одном конъюнкте ни одна переменная не повторяется;
b) нет таких пар конъюнктивных членов, что всякий дизъюнкт из одного имеется в другом;
c) для всяких двух конъюнктивных членов, из которых один содержит некоторую переменную, а другой ее отрицание (при условии, что другой переменной, для которой это же имеет место, в данной паре конъюнктов нет), имеется в этой же КНФ конъюнктивный член, равный дизъюнкции остальных дизъюнктов этих двух конъюнктивных членов.
Для получения обзора всех простых следствий из данных посылок необходимо:
1. Привести конъюнкцию посылок к КНФ.
2. Из всех одинаковых конъюнктов оставить только один и в элементарных дизъюнкциях устранить все повторения.
3. На основании правил 20 и 22 устранить все конъюнкты, которые содержат хотя бы одну переменную одновременно с отрицанием и без него.
4. Если из двух конъюнктов один содержит некую переменную, а другой - ее отрицание, то согласно правилу 30 добавить к формуле новый конъюнкт, равный дизъюнкции остальных дизъюнктов этих двух конъюнктивных членов. Например, если два конъюнкта имеют вид:
A + C и B + C, то добавляется новый конъюнкт A + В.
А на основании правила 31 - (A + C) & C = (A + C) & C & A и правила 32 - C& (B + C)=C & (B + C) & B, которые являются частными случаями правила 30, при наличии конъюнктов вида С и В + C или же вида А + С и С мы в первом случае приписываем новый конъюнкт В, а во втором - А.
5. Если имеется возможность, применяем правило 9, т.е. если есть конъюнкты вида А и A + В, то дизъюнкция A + В вычеркивается.
6. Если необходимо, то применяем правило 15, устраняя повторения конъюнктов.
В результате применения пунктов 1-6 получим сокращенную КНФ (силлогиcтический многочлен), содержащую все простые следствия из данных посылок.
Пример. Даны посылки A B, A + C, B & C.
Найти все простые следствия из этих посылок:
(A B) & (A + C) & (B & C),
(A + B) & (A + C) & ( B + C),
(A + B) & ( A + C) & (B + C) & (B + C) & (A + B) & B,
(A + C) & B.
Это значит, что при данных посылках формула А + С истинна, а В - ложна.
ЗАДАНИЕ 25. Найти все простые следствия из данного набора посылок путем приведения к сокращенной КНФ конъюнкции этих посылок.
Вариант:
1. (A & B) C, (A + C) (B + D)
2. (A + B) (D + C), D(C & B)
3. A(B & C), (A & D) B, (A&C) E
4. A + B, B + C, A & C
5. AB, AC, B + C
6. AC, CB, AC
7. (A + B) & C, A C, B C
8. AB, C + D, A (D & C)
9. AB, D + E, B C, C D, E(A&D)
10. C(A & B), A(B & C), (B & C) A