Исчисление высказываний и исчисление предикатов

Логика высказываний – самый простой раздел математической логики,

лежащий в основе всех остальных ее разделов. Основными объектами рас-

смотрения являются высказывания. Под высказыванием понимают повество-

вательное предложение, о котором можно сказать одно из двух: истинно оно

или ложно.

Из элементарных высказываний строятся более сложные высказывания с

помощью логических связок «НЕ», «И», «ИЛИ», «ТО ЖЕ, ЧТО»

(«ЭКВИВАЛЕНЦИЯ»), «ИЗ … СЛЕДУЕТ…». («… ВЛЕЧЁТ…»,

«…ПОТОМУ, ЧТО…».). Эти связки называются сентенциональными. Связки

логики высказываний представляют функции истинности или функции алгебры логики. В таб.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π, или √⎯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.