Процесс получения новых знаний, выр-х выск-ми из других знаний, также выр-х высказ-ми, назся рассуждениями (умозаключениями). Исходные знания (выск-я) наз-ся посылками (гипотезами), получаемые знания – заключения (следствия).
1. правило заключения Ponens
2. правило отрицания Tollens
3. правило утверждения-отрицания Ponenda-Tollens
или 
4. правило отрицания-утверждения Tollen-Pollens
5. правило трансзитивности
6. правило противоречия
7. правило контрапозиции
8. правило сложной контрапозиции
9. правило сечения
10. правило импортации
11. правило экспортации
12. правило дилемм
30. Алгебра логики (АЛ).
Под алгеброй будем понимать какое-либо
мн-во с заданными на нем операциями, т.е.
А={M;
1,…, n), где
М – несущее множество
i – сигнатура
алгебры
В АЛ заданным мн-м будем считать мн-во {0,1}, а заданными операциями: их 8.
Лог-е ф-и в АЛ м.б. записаны в префиксной и инфиксной форме
Префиксная: (х1,х2),
где :
Инфиксная (х1х2)
31 Булева алгебра.
В ДМ знач-е имеют конечные ф-и. Ф-я наз-ся конечной, если она представляет собой отображение одного конечного мн-ва в другое.
Важным классом конечных ф-й явл-ся булевы ф-и.
Булевы ф-и – произвольное отображение
вида f:{0,1}n 
{0,1}
Наборы знач-й пер-х или n-компонентные кортежи есть мн-во {0,1}n (обл. опр-я БФ)
Вектор знач-й БФ – упорядоченный набор всех знач-й ф-и f (обл. значений функции)
БФ м.б. задана 2 способами:
1) таблицей
2) формулой
Базовыми БФ будем считать констатнты 0 и 1 и операции (8), с помощью к-х можно получать др. ф-лы
Сущ-т наборы ф-й, с помощью к-х можно получить любые др. ф-и, ткие наборы наз-ся функционально-полными или базисами.
1) стандартный базис (мн-во F={
,
})
2) базис Жегалкина (мн-во {
}
Любую ф-лу, записанную над базисом Жегалкина наз-т полиномом Жегалкина.
Любая ф-ла х или 
над стандартным базисом – литерал
Элементарной конъюнкцией или конъюнктом наз-ся конъюнкция литералов.
Элем-й дизъюнкцией (дизъюнкт) –диз-я литералов.
32. СДНФ
Дизъюнкцией конъюнктов наз-ся дизъюнктивная нормальная форма (ДНФ)
Любая БФ, отличная от константы представима в виде ДНФ и КНФ.
Приведение к КНФ и ДНФ можно осущ-ть 2 сп:
1) с помощью таблиц
2) с помощью эквивалентных преобразований
Алгоритм
1) получить в таблице вектор знач-й БФ
2) выписать конституенты единицы
3) записать соот-е конъюнкты, в к-х 1 = пер-е, а 0 –инверсии пер-х
4)соединить полученные конъюнкты дизъюнкциями
^^ v ^^
СДНФ наз-ся дизъюнкция некоторых конституент единицы, среди к-х нет одинаковых
33. CКНФ
Конъюнкцией дизъюнктов наз-ся конъюктивная нормальная форма (КНФ)
Любая БФ, отличная от константы представима в виде ДНФ и КНФ.
Приведение к КНФ и ДНФ можно осущ-ть 2 сп:
1) с помощью таблиц
2) с помощью эквивалентных преобразований
Алгоритм
1) получить в таблице вектор знач-й БФ
2) выписать конституенты нуля
3) записать соот-е дизъюнкты, в к-х 0 = пер-е, а 1 –инверсии пер-х
4)соединить полученные конъюнкты конъюнкциями
(v v) ^(v v)
СКНФ наз-ся конъюнкция некоторых конституент нуля, среди к-х нет одинаковых
34. Эквивалентные преобразования
Эквив-е преоб-я – преоб-я, использ-е эквивалентные соотн-я и правила замены. Эквив-е преобр-я явл-ся мощным ср-м доказ-ва эквивалентности формул.
1.Правило подстановки формулы F вместо переменной х. При подстановке ф-kf вместо пре-й х все вхождения пер-й х в исходное соотн-е д.б. одновременно заменены ф-й F. Правило применяется к эквивал-м соот-м для получения эк-х соот-й.
Правило замены подформул. Если какая-либо ф-ла F, описываюшая ф-ю f, содержит F1 в качестве подформулы, то замена F1 на эквивал-ю F2 (F1=F2) не изменит ф-и f; полученная при такой замене ф-ла F’ эквив-на исходной F. Правило замены подформул позволяет, используя известные эквив-е соотн-я, получать ф-лы, эквив-е данной, в частности, упрощать формулы.
Соотношения:
(*=или 
)
Ассоциативность конъюнкции и дизъюнкции:
x1*(x2*x3)=(x1*x2)*x3=x1*x2*x3 4.14
Коммутативность
x1*x2=x2* x1 4.15
Дистрибутивность К отн-но Д
x1 (x2x3)=x1x2 x1x3 4.16
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.