139

Глава 4

Логика высказываний

4.1 Основные понятия

Высказывание – это утвердительное (повествовательное) предложение, которое может быть либо истинным, либо ложным, но не тем и другим вместе. “Истина"или

“ложь приписанная некоторому высказыванию, называется истинностным значением высказывания.

Истинностные значения “истина"и “ложь"обозначаются, соответственно, И и Л, T и F (True, False), или 1 и 0. Чаще других мы будем использовать обозначения 1 и 0.

Символы p; q; r и т.д., которые используются для обозначения высказываний называются высказывательными (пропозициональными) переменнымии, атомарными формулами

или атомами.

Примеры 4.1.

1.Земля вертится (фактическая истина: высказывание выражает некоторый факт из физики и астрономии).

2.Если истинно утверждение: когда идет дождь, дорога мокрая, то истинно и следующее утверждение: если дорога сухая, то дождя нет. (“Идет дождь”, “дорога сухая”, “дорога мокрая” – атомарные формулы (атомы), “если – то" – логи-

ческая связка). Истинностное значение всего предложения –

логическая истина. J

Из атомов можно строить соcтавные высказывания – формулы, используя логические связки или логические операции:

Примеры 4.2.

1. Из атомарных высказываний

p : команда выиграла на своем поле q : команда проиграла на чужом поле

r : команда выходит в следующий круг соревнований можно построить составное высказывание

(p ^ (:q)) ! r :

если команда выиграла на своем поле и не проиграла на чужом поле, то она выходит в следующий круг соревнований. 2. Если студент сдал сессию без троек, или если он получил не более одной тройки и за него ходатайствует группа, то он будет получать стипендию (из легенды). J

Определение. Правильно построенная формула (ППФ) или просто формула в логике высказываний определяется следующим образом:

1.Атом – формула (1 и 0 – формулы).

2.Если F – формула, то и (:F ) – формула.

3.Если F и G – формулы, то

(F _ G), (F ^ G), (F ! G), (F $ G) – формулы.

4. Формулы порождаются только конечным числом применений правил 1 – 3.

Логические (пропозициональные) связки упорядочиваются по приоритетам (в порядке убывания):

Пример 4.3.

Найдем все интерпретации формулы (p ^ q) ! r:

Таблица 4.2. Интерпретации формулы (p ^ q) ! r

З а м е ч а н и е. Интерпретация, при которой истинностное значение формулы есть 1, называется моделью этой формулы. I

Пример 4.4. Рассмотрим формулу F : (p ! Общезначимость q) ^ p ! q и найдем все ее интерпретации.

Определение. Формула F общезначима тогда и только тогда, когда она истинна во всех возможных интерпретациях.

Таким образом, формула из примера 4.4 общезначима. Общезначимая формула называется также тавтологией (от греческого tauto – то же самое, logos – слово, мысль, речь, разум).

Формула необщезначима тогда и только тогда, когда она не является общезначимой.

Определение. Формула F противоречива (невыполнима) то-

гда и только тогда, когда она ложна при всех возможных интерпретациях.

Формула непротиворечива (или выполнима) тогда и только тогда, когда она не является противоречивой.

Формулу, которая не является ни общезначимой, ни противоречивой (невыполнимой), называют также нейтральной.

Из этих определений непосредственно следует:

²отрицание общезначимой формулы противоречиво;

²отрицание противоречивой формулы общезначимо.

Примеры 4.5.

1.p _:p – формула общезначима, выполнима и непротиворечива.

2.(p ! q) ^ p ^ :q – формула противоречива, невыполнима и необщезначима.

3.p ^ :p – формула противоречива, невыполнима и необщезначима.

4.p ! :p – формула необщезначима и непротиворечива (нейтральна). J

Если формула F истинна в интерпретации I; то говорят, что I удовлетворяет F; или F выполнена в I.

Если формула F ложна в интерпретации I, то говорят, что I опровергает F; или F опровергается в интерпретации I (отсюда следует, что любая интерпретация опровергает противоречивую формулу).

Если интерпретация I удовлетворяет формуле F , то I называется также моделью F .

Ввиду конечности числа интерпретаций, путем полного перебора всех возможных интерпретаций всегда можно решить, общезначима формула или противоречива (или нейтральна).

Эквивалентность Определение. Две формулы F и G называ-

формул ются эквивалентными (или F эквивалентна G; обозначается F = G) тогда и только

6.a)F _ 1 = 1; b)F ^ 0 = 0;

7.:(:F ) = F (закон отрицания);

8.a):(F _ G) = :F ^ :G; b):(F ^ G) = :F _ :G (законы де Моргана);

9.F $ G = (F ! G) ^ (G ! F );

10.F ! G = :F _ G;

11.a)F _ F = F ; b)F ^ F = F (идемпотентность);

12.a)F _ (F ^ G) = F ; b)F ^ (F _ G) = F (законы поглощения).

Пример 4.7. Доказать эквивалентность формул:

(p _ q) ^ (p _ r) ^ (p _ s) = p _ (q ^ r ^ s).

Применяя к левой части последовательно дистрибутивный закон 3a), а затем ассоциативный закон 2 b), получим

(p _ (q ^ r)) ^ (p _ s) = (p _ (q ^ r) ^ s) = p _ (q ^ r ^ s): J

F_ G _ H и F ^ G ^ H.

Вобщем случае можно писать, не опасаясь двусмысленности

F1 _ F2 _ ¢ ¢ ¢ _ Fn, где F1; : : : ; Fn – формулы.

Такая формула – дизъюнкция формул – истинна, когда хотя бы одна из формул Fi истинна.

Аналогично, можно написать

F1 ^ F2 ^ ¢ ¢ ¢ ^ Fn.

Эта формула – конъюнкция формул – истинна, когда все формулы Fi истинны.

Порядок, в котором Fi встречается в конъюнкции или дизъюнкции, несуществен вследствие коммутативности операций ^ и _.

Определение. Литерал – это атом или отрицание атома. Дизъюнкция литералов вида p _ :q _ ¢ ¢ ¢ _ t называется клозом или дизъюнктом (англ. clause – предложение). Конъюнкция литералов вида :p^q ¢ ¢ ¢^t называется импликантой (конъюнктой, конъюнктом, cube).

Определение. Формула F представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет вид

F = F1 ^ F2 ^ ¢ ¢ ¢ ^ Fn; n > 1,

где каждая из формул Fi есть дизъюнкция литералов (клоз). Определение. Формула F представлена в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет вид

F = F1 _ F2 _ ¢ ¢ ¢ _ Fn; n > 1,

где каждая из формул Fi есть конъюнкция литералов (импликанта).

3. Используя нужное число раз дистрибутивные законы, приводим формулу к нужной форме.

Пример 4.8.

Привести формулу к ДНФ и КНФ: (p ! q) ! r.

(p ! q) ! r = :(:p _ q) _ r = p ^ :q _ r (ДНФ) =