Головна

Обчислення висловлювань і числення предикатів.

Логіка висловлювань - найпростіший розділ математичної логіки,

що лежить в основі всіх інших її розділів. Основними об'єктами рас

смотрения є висловлювання. Під висловом розуміють повество-

Серйозна пропозиція, про яку можна сказати одне з двох: істинно воно

або помилково.

З елементарних висловлювань будуються більш складні висловлювання з

допомогою логічних зв'язок «НЕ», «І», «АБО», «ТОЙ ЖЕ, ЩО»

(«Еквіваленцію»), «З ... БУДЕ ...». («... Тягне ...»,

"... ТОМУ ЩО...".). Ці зв'язки називаються сентенціональнимі. зв'язки

логіки висловлювань представляють функції істинності або функції алгебри логіки. У таб.1.1 представлені логічні зв'язки і їх позначення.

Таблиця 1.1

Визначення 1. Запереченням висловлювання p називається висловлювання p

(Або ?p), яке істинно тільки тоді, коли p помилково.

Приклад. Вислів «Неправда, що йде сніг» є запереченням

висловлювання «йде сніг».

Визначення 2. кон'юнкції висловлювань p і q називається висловлюються

ня, яке істинно тільки тоді, коли p і q істинні., тобто p = 1 і q = 1.

Приклад. Щоб успішно скласти іспит, потрібно мати при собі залікову книжку і

правильно відповісти на питання. Для успішного складання іспиту потрібно виконати

нитка обидва умови. Якщо позначити як p - «мати залікову книжку» і q - «правильно

відповісти на питання », то умовою здачі буде кон'юнкція висловлювань p & q.

Визначення 3. Диз'юнкцією висловлювань p і q називається висловлюються

ня, яке помилково тоді і тільки тоді, коли обидва висловлювання помилкові, т. е. p = 0 і q = 0.

Приклади. (7> 3 або 4 ? 1) = 1; (Або sin2x має період 2?, або v?2 - ра-

циональное число) = 0.

Визначення 4. імплікації висловлювань p і q називається висловлюються

ня, яке помилково тоді і тільки тоді, коли p істинно, q помилково, тобто p = 1 і

q = 0 (з p слід q).

Приклад. Вищенаведений приклад з успішною здачею іспиту можна

записати як p & q > r, де r - «успішно скласти іспит».

Визначення 5. еквіваленцію висловлювань p і q називається вискази-

вання, яке істинно тільки і тільки тоді, коли значення висловлювань p

і q збігаються (p еквівалентно q).

Приклад. «Граф є дводольним тоді і тільки тоді, коли він не

містить циклів непарної довжини ». Якщо p - висловлювання «мати цикли не-

парної довжини », q -« граф двочастковий », то початкова фраза прикладу запишеться

у вигляді q ?? p.

 Мінімізація в класі діз'юнктівних нормальних форм. |  обчислення предикатів


 Логіка висловлювань. |  Визначення булевої функції |  Логічні операції. |  Формули логіки висловлювань |  Равносильность формул. |  Нормальні форми формул, приведення до ДНФ, КНФ. |  Використовуючи закон дистрибутивности, перетворимо формулу так, щоб все диз'юнкції виконувалися раніше, ніж кон'юнкції. |  Алгоритм отримання СДНФ по таблиці істинності. |  Алгоритм отримання СКНФ по таблиці істинності. |  Суперпозиції функцій. Повні системи логічних функцій. |

© 2016-2022  um.co.ua - учбові матеріали та реферати