lec2

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Законы алгебры логики. Нормальные формы формул алгебры логики

к.ф.-м.н., доцент Красоткина О.В.

Тульский государственный университет

Математическая логика и теория алгоритмов Лекция 2 Тула, 2014

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

1Законы алгебры логики

Равносильность и эквивалентность формул

Основные законы алгебры логики

Задание на дом

2Нормальные формы формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные нормальные формы

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Определение

Две формулы F1 и F2 называются равносильными, если они имеют одинаковое значение 0 или 1 при одинаковых наборах пропозициональных переменных, включаемых в F1 и F2, т.е.F1 = F2 . Если две формулы равносильны, то они эквивалентны, т.е. (F1 $ F2)

Следствие

Если формула F имеет вхождением подформулу Fi , для которой существует эквивалентная подформула Fj , т.е. (F1 $ F2), то возможна подстановка всюду в формулу F вместо формулы Fi подформулу Fj без нарушения истинности формулы F .

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Коммутативность дизъюнкции

F1 _ F2 = F2 _ F1

Коммутативность конъюнкции

F1 ^ F2 = F2 ^ F1

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Ассоциативность дизъюнкции

F1 _ (F2 _ F3) = (F1 _ F2) _ F3

Ассоциативность конъюнкции

F1 ^ (F2 ^ F3) = (F1 ^ F2) ^ F3

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Распределительный закон логического сложения

F1 ^ (F2 _ F3) = (F1 ^ F2) _ (F1 ^ F3)

Распределительный закон логического умножения (чудо-закон)

F1 _ (F2 ^ F3) = (F1 _ F2) ^ (F1 _ F3)

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Логическое умножение

(F1 ^ F2) = F1 _ F2

Логическое сложение

(F1 _ F2) = F1 ^ F2

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Логический закон, позволяющий исключить повторение одного и того же высказывания

Логическое умножение

(F1 ^ F1) = F1

Логическое сложение

(F1 _ F1) = F1

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Лат. tertium non datum, то есть третьего не дано - закон классической логики, состоящий в том, что из двух высказываний - F1 или не F1 одно обязательно является истинным, то есть два суждения, одно из которых является отрицанием другого, не могут быть одновременно ложными.

(F1 _ F1) = 1

Красоткина О.В.

Красоткина

О.В.

Законы

алгебры

логики

Равносильность и эквивалентность формул

Основные

законы

алгебры

логики

Задание на дом

Нормальные

формы

формул

Дизъюнктивная и конъюнктивная нормальные формы

Совершенные

нормальные

формы

Закон непротиворечия (закон противоречия) - закон логики, который гласит, что два несовместимых (противоречащих) суждения не могут быть одновременно истинными. По крайней мере, одно из них ложно.

(F1 ^ F1) = 0

Красоткина О.В.