lec2
.pdfКрасоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Законы алгебры логики. Нормальные формы формул алгебры логики
к.ф.-м.н., доцент Красоткина О.В.
Тульский государственный университет
Математическая логика и теория алгоритмов Лекция 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
Красоткина О.В.