Висловлювання і операції над ними. Класифікація формул алгебри висловлювань. Основні тавтології алгебри висловлювань. Логічна рівносильність в алгебрі висловлювань

Висловлювання позначають латинськими буквами. Висловлювання можуть приймати два значення (істинність та хибність): або , де л - функція істинності, яка вказує логічне значення висловлювання.

Операції над висловлюваннями:

Заперечення висловлювання А називається висловлювання, яке приймає значення істинність, якщо А хибне, і прийматиме значення хибність, якщо А істинне. Позначається .

Диз’юнкцією двох висловлювань А і В називається висловлювання, яке приймає значення хибність в тому випадку, коли висловлювання А і В одночасно хибні і приймає значення істинність в інших випадках. Позначається .

Кон’юнкцією двох висловлювань А і В називається висловлювання, яке приймає значення істинність тільки в тому випадку, коли А і В одночасно істинні, в інших випадках приймає значення хибність. Позначається .

Імплікація двох висловлювань А і В називається висловлювання, яке приймає значення істинність у всіх випадках, крім того коли перше висловлювання хибне а друге висловлювання істинне. Позначається .(false-A=1iB=0)

Еквіваленцією двох висловлювань А і В називається висловлювання, яке приймає значення істинність, коли обидва висловлювання або істинні, або хибні одночасно і прийматиме значення хибність в інших випадках. .

Пріоритет операцій визначається в наступній послідовності:

Класифікація формул алгебра висловлювань.

Всі формули алгебри висловлювань можна поділити на такі типи: виконувані, тотожно істинні або тавтології, спростовуючі, тотожньо хибні або суперечності.

Формула F(x1,x2,...,xn) називається виконуваною, якщо існує такий набір значень б1, б2, ..., бn при підстановці яких у формулу замість x1, x2, ..., xn наша формула перетвориться у тотожне висловлювання.

Приклад: – не є виконуваною. – тавтологія

1 | 0 | 0 | 1 | 0 | 1

0 | 1 | 0 | 0 | 1 | 1

Формула F(x1,x2,...,xn) називається тавтологією або тотожно істинною, якщо при будь-яких наборах б1, б2, ..., бn формула перетвориться у істинне висловлювання. Позначається |=.

Формула 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. транзитивність

Основні рівносильності:

1. 2. 3.

4. 5. 6.

7. 8. 9. 10.

11. 12. 13. 14.

15. 16. 17.

18. 19. 20.

21. 22. 23.

2. Диз’юнктивна та кон’юнктивні нормальні форми алгебри висловлювань. Подання формул алгебри висловлювань досконалими диз’юнктивними та кон’юнктивними нормальними формами

Будь-яку формулу алгебри висловлювань можна подати у вигляді логічних зв’язків заперечення, кон’юнкції чи диз’юнкції.

Кон’юнктивним одночленом від змінних x1, x2, ..., xn називається кон’юнкція цих змінних та їх заперечень. Приклад:.

Диз’юнктивним одночленом від змінних x1, x2, ..., xn називається диз’юнкція цих змінних та їх заперечень. Приклад: .

Диз’юнктивною нормальною формою називається диз’юнкція кон’юнктивних одночленів.

Кон’юнктивною нормальною формою називається кон’юнкція диз’юнктивних одночленів.

Приклад: .

Будь-яку формулу алгебри висловлювань можна подати у вигляді багатьох диз’юнктивних та кон’юнктивних форм.

Одночлен (диз’юнктивний або кон’юнктивний) називається досконалим, якщо він з пари змінних ( і=1..n) містить тільки одну букву або змінну.

Нормальна (диз’юнктивна або кон’юнктивниа) форма називається досконалою, якщо в неї входять тільки досконалі одночлени від змінних x1, x2, ..., xn.

Подання формул алгебри висловлювань у вигляді досконалої нормальної диз’юнктивної або кон’юнктивні форми.

Введемо позначення:

звідси тобто

- це є диз’юнкція все можливих наборів формули , де формула Н залежить від змінних x1, x2, ..., xn, а пробігає всі можливі набори значень 0 та 1.

Лема: Кожну формулу алгебри висловлювань можна подати в наступному вигляді:

Теорема: Кожна формула алгебри висловлювань, яка не є тотожньо хибною, має єдину (з точністю до перестановок кон’юнктивних одночленів) досконалу диз’юнктивну нормальну форму.

Для доведення єдності розкладу у досконалу кон’юнктивну нормальну форму використовуються наступні позначення:

Лема: Будь-яку формулу алгебри висловлювань можна подати у вигляді:

Теорема: Кожна формула алгебри висловлювань, яка не є тавтологією, має єдину (включно до перестановок) досконалу кон’юнктивну нормальну форму.

Доведення аналогічне попередньому.

Булеві функції від n аргументів. Вираження булевих функцій через кон’юнкцію, диз’юнкцію і заперечення.

Булевою функцією від одного аргументу називається функція, яка задана на множині двох елементів і приймає значення цій же множині двох елементів (елементи 0 і 1).

х | f1 | f2 | f3 | f4

0 | 0 | 0 | 1 | 1

1 | 0 | 1 | 0 | 1

0 | >’ | x | <’ | y | v | - | y’ | < | x’ | > | | | 1

x | y | g0 | g1 | g2 | g3 | g4 | g5 | g6 | g7 | g8 | g9 | g10 | g11 | g12 | g013 | g14 | g

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |