- •Висловлювання і операції над ними. Класифікація формул алгебри висловлювань. Основні тавтології алгебри висловлювань. Логічна рівносильність в алгебрі висловлювань
- •2. Подання формул алгебри висловлювань у вигляді досконалої нормальної диз’юнктивної або кон’юнктивні форми.
- •3.Булеві функції від n аргументів. Вираження булевих функцій через кон’юнкцію, диз’юнкцію і заперечення.
- •4. Системи булевих функцій. Спеціальні класи булевих функцій.
-
Висловлювання і операції над ними. Класифікація формул алгебри висловлювань. Основні тавтології алгебри висловлювань. Логічна рівносильність в алгебрі висловлювань
Висловлювання та операції над висловлюванням.
Висловлювання позначають латинськими буквами. Висловлювання можуть приймати два значення (істинність та хибність): або , де λ - функція істинності, яка вказує логічне значення висловлювання.
Операції над висловлюваннями:
Заперечення висловлювання А називається висловлювання, яке приймає значення істинність, якщо А хибне, і прийматиме значення хибність, якщо А істинне. Позначається .
Диз’юнкцією двох висловлювань А і В називається висловлювання, яке приймає значення хибність в тому випадку, коли висловлювання А і В одночасно хибні і приймає значення істинність в інших випадках. Позначається .
Кон’юнкцією двох висловлювань А і В називається висловлювання, яке приймає значення істинність тільки в тому випадку, коли А і В одночасно істинні, в інших випадках приймає значення хибність. Позначається .
Імплікація двох висловлювань А і В називається висловлювання, яке приймає значення істинність у всіх випадках, крім того коли перше висловлювання істинне а друге висловлювання хибне. Позначається .
Еквіваленцією двох висловлювань А і В називається висловлювання, яке приймає значення істинність, коли обидва висловлювання або істинні, або хибні одночасно і прийматиме значення хибність в інших випадках. Позначається .
Пріоритет операцій визначається в наступній послідовності:
Класифікація формул алгебра висловлювань.
Всі формули алгебри висловлювань можна поділити на такі типи: виконувані, тотожно істинні або тавтології, спростовуючі, тотожньо хибні або суперечності.
Формула F(x1,x2,...,xn) називається виконуваною, якщо існує такий набір значень α1, α2, ..., αn при підстановці яких у формулу замість x1, x2, ..., xn наша формула перетвориться у тотожне висловлювання.
Приклад: – не є виконуваною.
|
||
1 |
0 |
0 |
0 |
1 |
0 |
Формула F(x1,x2,...,xn) називається тавтологією або тотожно істинною, якщо при будь-яких наборах α1, α2, ..., αn формула перетвориться у істинне висловлювання. Позначається |=.
Приклад: – тавтологія.
|
||
1 |
0 |
1 |
0 |
1 |
1 |
Формула F(x1,x2,...,xn) називається спростовуючою, якщо існує такий набір значень α1, α2, ..., αn що при підстановці цих значень у формулу ми отримуємо хибне висловлювання.
Формула F(x1,x2,...,xn) називається тотожно хибною або суперечністю, якщо для будь-якого набору α1, α2, ..., αn ми отримуємо хибне висловлювання.
Основні тавтології.
закон виключення третього: ,закон заперечення протиріччя:
закон подвійного заперечення: ,закон контрапозиції:
Властивості диз’юнкції і кон’юнкції
закон ідемпотентності: ,закон комутативності:
закон асоціативності: ,
закон дистрибутивності:
закон поглинання: ,
закон де Моргана:
Властивості імплікації і еквівалентності
1. ,2. ,3. ,4. ,5. ,6. ,7.
8.,9. ,10.
Теорема: Якщо формули є тавтологіями, то формула Н є також тавтологією.
Теорема: Якщо формула F(x) є тавтологією, то після заміни замість змінної х формулою Н отримана формула також буде тавтологією.
Логічна рівносильність.Формули називаються рівносильними, якщо при будь-якому наборі α1, α2, ..., αn, які підставляються замість x1,x2,...,xn значення даних формул співпадають. Позначають .
Теорема: Формули F і H є рівносильними, якщо формула є тавтологією.
Для рівносильності характерні наступні властивості:
1. симетричність
2. рефлексивність
3. транзитивність
2. Диз’юнктивна та кон’юнктивні нормальні форми алгебри висловлювань. . Диз’юнктивні та кон’юнктивні нормальні форми алгебри висловлювань.
Будь-яку формулу алгебри висловлювань можна подати у вигляді логічних зв’язків заперечення, кон’юнкції чи диз’юнкції. Кон’юнктивним одночленом від змінних x1, x2, ..., xn називається кон’юнкція цих змінних та їх заперечень. Приклад:.
Диз’юнктивним одночленом від змінних x1, x2, ..., xn називається диз’юнкція цих змінних та їх заперечень. Приклад: .
Диз’юнктивною нормальною формою називається диз’юнкція кон’юнктивних одночленів.Кон’юнктивною нормальною формою називається кон’юнкція диз’юнктивних одночленів.Будь-яку формулу алгебри висловлювань можна подати у вигляді багатьох диз’юнктивних та кон’юнктивних форм.
Одночлен (диз’юнктивний або кон’юнктивний) називається досконалим, якщо він з пари змінних ( і=1..n) містить тільки одну букву або змінну.
Нормальна (диз’юнктивна або кон’юнктивниа) форма називається досконалою, якщо в неї входять тільки досконалі одночлени від змінних x1,, ..., xn.