Навигация
Нормальні форми логіки висловлювань
34324
знака
8
таблиц
0
изображений
1.3. Нормальні форми логіки висловлювань.
Літералом називатимемо атом або заперечення атома. Прикладами літералів є р, 
, r. Літерал називають позитивним, якщо він не має знака заперечення, та негативним, якщо він має знак заперечення. Пару літералів {p, 
} називають контрарною парою.
Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f1
f2…fn(n≥1) і всі fi (i=1,2,...,n) різні. Тут кожна з формул f1,f2,…,fn є диз'юнкцією літералів, у якій всі атоми різні.
Приклад 1.17. Нехай p, g та r — атоми. Тоді f=(р
)(g) - формула, записана в кон'юнктивній нормальній формі. У цій формулі f1=(р) та f2=(g), тобто f1 - диз'юнкція літералівp, , , а f2 - диз'юнкція літералів таg.
Кажуть, що формулу f записано у диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд f=f1f2…fn(n≥1) і всі fi (i=1,2,...,n) різні. Тут кожна з формул f1,f2,…,fn є кон'юнкцією літералів, у якій всі атоми різні.
Приклад 1.18. Нехай p, g та r - атоми. Тоді f=(g)(p) - формула, записана у диз'юнктивній нормальній формі. У цій формулі f1=(g) та f2=( p), де f1 - кон'юнкція літералів та g, а f2 - кон'юнкція літералівp, та .
Довільну формулу можна перетворити в одну з нормальних форм застосуванням законів логіки висловлювань. Для побудови нормальних форм необхідно виконати таку послідовність кроків еквівалентних перетворень.
Крок 1. Використати правила f→g=
g та f~g=(f→g)(g→f) (див. параграф 1.2) для усунення логічних зв'язок "→" та "~".
Крок 2. Використати закон подвійного заперечення та закони де Моргана для перенесення знаку заперечення безпосередньо до атомів.
Крок 3. Використати відповідні закони дистрибутивності закони для побудови нормальної форми. Для побудови кон'юнктивної нормальної форми використати закон дистрибутивності для диз'юнкції відносно кон'юнкції (закон 3а з табл. 1.8). Для побудови диз'юнктивної нормальної форми використати закон дистрибутивності для кон'юнкції відносно диз'юнкції (закон 3 б з табл. 1.8).
Приклад 1.19. Побудуємо диз'юнктивну нормальну форму формули ((p)→r)(→s). Наведемо послідовність кроків для побудови ДНФ та застосовані закони.
1. (
r)(
) - усунення логічної зв'язки "→" із заданої формули.
2. ((
)r)() - закон де Моргана 8а до формули з рядка 1.
3. ((g)r)(rs) - закон подвійного заперечення 6 до формули 2.
4. ((g)(rs))(r(rs)) - закон дистрибутивності 3б до формули 3.
5. ((gr)(gs))((rr)(rs)) - закон дистрибутивності 3б до формули 4.
6. (gr)(gs)(rr)(rs) - асоціативний закон 2а до формули 5.
7. (gr)(gs)r(rs) - закон ідемпотентності 7б до формули 6.
Ми одержали ДНФ. Звернемо увагу, що її можна спростити, якщо двічі використати закон поглинання 9б: диз'юнктивний член к поглинає члени (gr) та (rs). Отже, ДНФ заданої формули ((p)→r)(→s) також буде (gs)r. Останні міркування свідчать, що ДНФ певної формули, якщо казати загалом, не єдина.
Приклад 1.20. Побудуємо кон’юнктиву нормальну форму формули (р(g→r))→s. Наведемо послідовність кроків побудови КНФ і застосовані закони та правила.
1. 
- усунення логічної зв'язки "→" із заданої формули.
2. 
s - закон де Моргана 8б до формули 1.
3. ()s - закон де Моргана 8а до формули 2.
4. (g)s - закон подвійного заперечення 6 до формули 3.
5. s(g) - закон комутативності 1а до формули 4.
6. (s)(g) - закон асоціативності 2а до формули 5.
7. (gs)(s) - закон дистрибутивності За до формули 6.
Формула (gs)(s) є КНФ формули (р(g→r))→s.
Розділ ІІ: Логіка предикатів.
Похожие работы
... його функцій і структури, тобто ролі і значення в пізнанні і практичній діяльності, і в той же час з погляду складових його елементів, а також зв'язків і відносин між ними. Це і є власний, специфічний предмет логіки. Тому вона визначається як наука про форми і закони правильного мислення, що веде до істини. Що ж таке логічна культура? Це культура мислення, що виявляється в культурі письмового й ...
... (логіці, етиці і політиці) означає не що інше, як повернення до традиціоналістсько-авторитарного типу цивілізації, на що і претендував тоталітаризм XX в. 3. Загальне і відмінності формальної і діалектичної логіки В четвертій книзі “Метафізики" Арістотель ставив питання: який принцип є таким самоочевидним, що його можна покласти в основу істинної філософії. Таким самоочевидним принципом Арі ...
... , сполучників, префіксів і префіксальних словоформ, розділових знаків, а також за розподілом довжини речення). Крім статистичних методів, у мовознавстві застосовують методи теорії інформації, математичної логіки, теорії ймовірностей і теорії множин. 3. Застосування математичних теорій. Дані теорії інформації використовуються для найекономнішої передачі інформації засобами мови. Кожна ...
... і продукції. Виробничі потужності ТОВ «Брусилівський маслозавод» дозволяють виробляти близько 150 т масла, 30 т глазурованих сирків за рік, переробляючи приблизно 1000 кг молока за день. Основні споживачі продукції ТОВ «Брусилівський маслозавод» - населення Брусилівсьекого району та районів, що знаходяться поруч з Брусилівським, Житомирської області. . Отже, ТОВ «Брусилівський маслозавод» – ...
0 комментариев