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

Высказывание – это утверждение, принимающее одно из двух значений: 1 («истинно») и 0 («ложно»). Элементарными высказываниями или переменными – это высказывания, значения которых не зависят от значений каких-либо высказываний. Высказывания обозначаются прописными латинскими буквами (с индексом или без), например: A, B, …, X, X₁, X₂, …, X_n.

Определим логические операции для высказываний A и B, которые позволяют из данных высказываний получать новые.

1. Логическое отрицание (читается «не A»): .

2. Конъюнкция (логическое умножение) («A и B»): AB.

3. Дизъюнкция (логическая сумма) («A или B или оба»): A+B.

4. Импликация (следование) («A влечет B», «если A, то B»): A®B.

5. Эквивалентность («A эквивалентно B») A~B.

Таблица истинности приведенных выше логических операций имеет вид

A	B		AB	A+B	A®B	A~B

Порядок выполнения логических операций следующий:

1) выбирается последовательно слева направо каждый раз из присутствующих логических операций в первую очередь операция эквивалентность, во вторую – импликация, в третью – дизъюнкция, в четвертую – конъюнкция и в пятую – отрицание;

2) выбранной операции придается наибольшая область действия.

Другими словами операция отрицания связывает сильнее, чем эквивалентность.

Пример 1.1. Правильно расставить скобки в выражении:

Q ® P + ® R × .

Решение. В соответствии с вышеизложенным порядком выполнения операций скобки следует расставить так:

Q ® ((P + ) ® (R × )).

Две формулы A и B называются равносильными, если их значения совпадают при любых значениях, входящих в них переменных. Для любых X, Y и Z справедливы следующие равносильные формулы.

Снятие двойного отрицания (отрицание отрицания):

=X. (1.1)

Коммутативность:

XY=YX. (1.2)

X+Y=Y+X. (1.3)

Ассоциативность:

(XY)Z=X(YZ). (1.4)

(X+Y)+Z=X+(Y+Z). (1.5)

Дистрибутивность:

X(Y+Z)=XY+XZ. (1.6)

X+YZ=(X+Y)(X+Z). (1.7)

Законы де Моргана:

. (1.8)

. (1.9)

Идемпотентность:

X+X=X. (1.10)

X×X=X. (1.11)

Свойства констант:

X×1=X. (1.12)

X×0=0. (1.13)

X+1=1. (1.14)

X+0=X. (1.15)

Закон «исключения третьего»:

X+ =1. (1.16)

Закон противоречия:

X× =0. (1.17)

Преобразование импликации:

X®Y= +Y. (1.18)

Преобразование эквивалентности:

X~Y=XY+ =( +Y)(X+ ). (1.19)

Элементарные поглощения:

X+XY=X. (1.20)

X+ Y=X+Y. (1.21)

X(X+Y)=X. (1.22)

X( +Y)=XY. (1.23)

Элементарным дизъюнктом (конъюнктом) называется дизъюнкция (конъюнкция) переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнктов.

Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнктов.

Пример 1.2. Построить КНФ и ДНФ формулы

Q ® ((P + ) ® (R × )).

Решение. С помощью равносильных формул и элементарных поглощений получаем:

Q ® ((P + ) ® (R × )) = + ( + R × ) =

= + R + R = + R.

ДНФ: + R;

КНФ: ( + )( + R).

Формула A находится в совершенной конъюнктивной (дизъюнктивной) нормальной форме (СКНФ и СДНФ соответственно), если выполняются следующие условия:

1) формула A находится в КНФ (ДНФ);

2) любая переменная X или ее отрицание в формуле A имеет в любом конъюнктивном (дизъюнктивном) члене ровно одно вхождение;

3) все конъюнктивные (дизъюнктивные) члены в A различны.

Пример 1.3. Построить СКНФ и СДНФ формул из примера 1.2.

Решение. С помощью полученной ДНФ построим СДНФ. Для этого домножим каждый дизъюнкт на дизъюнкцию недостающей переменной и ее отрицания:

+ R = (P + )(R + ) + (Q + ) R.

Раскроем скобки и сократим одинаковые дизъюнкты:

PR + P + R + + Q R + R =

= PR + P + R + + Q R.

СДНФ: Q R + PR + P + R + .

Аналогично СДНФ построим СКНФ с помощью КНФ. Для этого добавим к каждому конъюнкту конъюнкцию недостающей переменной и ее отрицания:

( + )( +R) = ( + + R )( + P + R).

Используем равносильную формулу (1.7) и сокращаем одинаковые конъюнкты:

( + + R)( + + )( + P + R) ( + + R) =

= ( + P + R)( + + R)( + + ).

СКНФ: ( + P + R)( + + R)( + + ).

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

Пример 1.4. Является ли следующее рассуждение истинным:

«Если в стране инфляция, то промышленный рост отсутствует. Или если промышленный рост отсутствует, то сокращается безработица».

Решение. Выделим элементарные высказывания:

P – «в стране инфляция»;

Q – «промышленный рост отсутствует»;

R – «безработица сокращается».

Выражения в тексте задания «если …, то», «следовательно» (после точки) соответствуют импликации; «или» – дизъюнкции; «и» и точка в конце предложения (если далее не следует «или») – конъюнкции.

Тогда эти рассуждения можно представить в виде формулы

(P ® Q) + (Q ® R).

Преобразуем формулу с помощью равносильных формул

(P ® Q) + (Q ® R) = ( + Q) + ( + R) = + R + 1 = 1.

Формула имеет значение «истина», а значит рассуждения, соответствующие данной формуле, верны. Если формула принимает значение, отличное от истинного, то верность суждений не доказана.

Упражнения

При выполнении упражнений необходимо приводить формулы к таким КНФ и ДНФ, которые нельзя упростить более с помощью равносильных формул и элементарных поглощений.

а) Доказать эквивалентность с помощью равносильных преобразований или таблицы истинности:

1) A ~ A;

2) (A(A+C)(B+C)) ~ (AB+AC);

3) ((A+B)×(B+C)×(C+D)) ~ (AC+BC+BD);

4) ((AB+C)×(AC+B)×(BC+A)) ~ (AB+AC+BC);

5) ((A+B+C)×(B+C+D)×(C+D+A)) ~ (AB+AD+BD+C).

б) При каких значениях:

переменных X, Y ложна следующая формула:

1) (X+Y)®(( ×Y)+(X× ));

переменных X, Y, Z ложны следующие формулы:

2) ((X®(Y×Z))®( ® ))® ;

3) Y+ Z+X ;

4) ( +Y)( +Z)(X+ );

5) ((X+Y)(Y+Z)(X+Z))®(XYZ);

переменных X, Y, Z, U, V, W ложна следующая формула:

6) XY+XZ+YZ+UV+UW+VW+ .

в) Построить КНФ, ДНФ, СКНФ и СДНФ следующих формул, правильно расставив скобки:

1) A®С× ®B+ ;

2) D+B× ®A×В+ ®C;

3) A× +A× ®A®B;

4) A®(B®C)®A× ;

5) A+B(C®A)®A×B;

6) B×C×(A® )+A® ;

7) A® ×(C+A)® ;

8) ® +B®A+ ®A;

9) С× ®A+ ®C®B;

10) A+C×D® ®D®C;

11) D®B×D®A+C® ;

12) C® + ®C+A® ;

13) D+A×B®C®D®B;

14) A® ®A× +D®C.

г) Представить рассуждения в виде формул логики высказываний и ответить на вопросы.

1) Является ли следующее рассуждение истинным:

«Если (профсоюзы поддержат президента на предстоящих выборах |P), то (он подпишет законопроект о повышении заработной платы ½Q). Если (фермеры окажут президенту поддержку ½R), то (он наложит вето на законопроект ½S). Очевидно, что он не подпишет законопроект или не наложит на него вето. Следовательно, президент потеряет голоса профсоюзов или голоса фермеров».

2) Является ли следующее рассуждение истинным:

«(В бюджете возникнет дефицит |P), если не (повысят пошлины |Q). Или если в бюджете будет дефицит, то (социальные расходы сократятся |R), из чего следует, что если повысят пошлины, то социальные расходы не сократятся».

3) Является ли следующее рассуждение истинным:

«Если (наступит мир |P), то (возникнет депрессия |Q); или при отсутствии депрессии (страна проведет программу перевооружения |R), или при наличии депрессии (осуществит грандиозную социальную программу |S). Но договориться о целях такой грандиозной программы невозможно. Следовательно, если наступит мир и не будет депрессии, то будет осуществляться программа перевооружения».

4) Выяснить, кто из четверых виновен на основе следующих высказываний:

«Если Петров виновен, то виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова, и неверно, что Кулагин виновен, а Сидоров нет».

д) Построить КНФ и ДНФ следующих формул:

1) ®(B+( ®(C+ ))®(A+ ));

2) (( + )®B)×(( ®C)®A)×F;

3) (C®(((D®A)+ )®B))+(( +F)® );

4) F(B®(B(C®(( +A)® )))+ );

5) (D+B)×( +( ®F×A)® );

6) B×( ®A)+((B (F®A))®D);

7) ((C® )®A)+( ®B)+(( ×F)®A);

8) ((B+C)®B)+((( ®D)® )®F);

9) (FB®B)×(( ®(( +A)®F))+ );

10) ®(((A®C)+ B)+( ®D));

11) (A®B)+( ®((C+ )®(A+ )));

12) B×(( ®A)+B×((D ®A)®C));

13) ((A+B)®((C+( ®A))+ ))®B;

14) ((C®((D®A)+ ))®(B+ )×F)®A;

15) ( ®(A®(C+B))× )+( ®F);

16) B+(C®B)+((( ®D)® )®F);

17) ((D+ +C)® )®((A+C)®B);