lec2
.pdf
Законы поглощения
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Закон поглощения логического сложения
F1 ^ (F1 _ F2) = F1
Закон поглощения логического умножения
F1 _ (F1 ^ F2) = F1
Красоткина О.В.
Закон снятия двойного отрицания
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Закон дополнения
F1 = F1
Красоткина О.В.
Свойства констант
Красоткина
О.В.
Законы |
|
|
|
|
|
|
|
Ложь 0 |
|
||||||
алгебры |
|
||||||
логики |
|
|
|
|
|
|
|
|
1 _ |
|
|
|
|||
Равносильность |
F |
0 |
= F |
1 |
|||
ность |
|||||||
и эквивалент- |
|
|
|
||||
формул |
F1 |
^ |
0 |
= 0 |
|
||
|
|
|
|
|
|||
Основные |
|
|
|
|
|
||
законы |
|
|
|
|
|
|
|
алгебры |
|
|
|
|
|
|
|
логики |
Истина 1 |
|
|||||
Задание на |
|
||||||
дом |
F1 _ |
1 |
= 1 |
|
|||
Нормальные |
|
||||||
формы |
|
||||||
формул |
F1 ^ |
1 |
= F1 |
||||
Дизъюнктивная |
|||||||
|
|
|
|
||||
и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Красоткина О.В.
Пример доказательства справедливости закона поглощения с помощью таблиц истинности
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Закон поглощения логического сложения
F1 ^ (F1 _ F2) = F1
|
F1 |
F2 |
F1 _ F2 |
F1 ^ (F1 _ F2) |
|
|
|
|
|
|
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
Красоткина О.В.
Задaние
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
С помощью таблиц истинности доказать законы алгебры логики
Задание выполняется на листочках (листочки подписать)
Сдать 25.02.14 на лекции
Красоткина О.В.
Пример использования законов алгебры логики
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Дано суждение:
или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В).
Кто точно поступил в унивеситет?
Красоткина О.В.
Дизъюнктивная нормальная форма (ДНФ)
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Определение
ДНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде дизъюнкции элементарных конъюнкций, построенных на пропозициональных переменных. K1 _ K2 _ :::Kn, где
Ki = F1 ^ F2 ^ :::: ^ Fmi , i = 1; :::; n
В элементарной коньюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности (F1 ^ F1) = F1 . В ДНФ нет двух одинаковых элементарных коньюнкций, т.к. по закону идемпотентности (F1 _ F1) = F1 . Если одна из элементарных коньюнкций содержит F и F , то элементарную конъюнкцию следует удалить, т. к.
(F1 ^ F1) = 0 .
Красоткина О.В.
Конъюнктивная нормальная форма (ДНФ)
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Определение
КНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных. D1 ^ D2 ^ ::: ^ Dn, где
Di = F1 _ F2 _ :::: _ Fmi , i = 1; :::; n
В элементарной дизъюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности (F1 _ F1) = F1. В КНФ нет двух одинаковых элементарных дизъюнкций, т.к. по закону идемпотентности (F1 ^ F1) = F1. Если одна из элементарных
дизъюнкций содержит F и F , то элементарную коньюнкцию следует удалить, т. к. (F1 _ F1) = 1 .
Красоткина О.В.
Алгоритм перехода к нормальной форме
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Устранить логические связки импликации и эквивалентности по правилам:
F1 ! F 2 = F1 _ F2,
F1 $ F 2 = (F1 ! F 2)^(F2 ! F 1) = (F1 _F2)^(F2 _F1). 
Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:
(F1 ^ F2) = F1 _ F2 , (F1 _ F2) = F1 ^ F2 , F1 = F1 . 
Применить закон дистрибутивности:
для КНФ: F1 _ (F2 ^ F3) = (F1 _ F2) ^ (F1 _ F3) для ДНФ: F1 ^ (F2 _ F3) = (F1 ^ F2) _ (F1 ^ F3).
Красоткина О.В.
Совершенные нормальные формы
Красоткина
О.В.
Законы
алгебры
логики
Равносильность и эквивалентность формул
Основные
законы
алгебры
логики
Задание на дом
Нормальные
формы
формул
Дизъюнктивная и конъюнктивная нормальные формы
Совершенные
нормальные
формы
Определение
Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нор-мальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ)
Красоткина О.В.