4. Построить истинностную таблицу для формулы

^G

Решение. Истинностная таблица для G дана в табл.9.3. Как видим, эта формула ложна при всех интерпретациях, т. е. противоречива.

Таблица 9.3 - Истинностная таблица для

P Q
0 0	1	1	0	0
0 1	1	0	0	0
1 0	0	1	1	0
1 1	1	0	0	0

Контрольные вопросы и задания по теме:

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

2. Высказывания, логические связки, логические парадоксы.

3. Составные высказывания.

4. Истинностные значения и функции.

5. Формулы ЛВ. Интерпретации формул ЛВ. Таблицы истинности формул ЛВ.

6. Общезначимые, противоречивые и выполнимые формулы ЛВ.

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

8. Записать следующие высказывания с помощью формул:

   1. “Данное отношение есть отношение эквивалентности тогда и только тогда, когда оно рефлексивно, симметрично и транзитивно”;

   2. “Если влажность так высока, то либо после полудня, либо вечером будет дождь”.

9. Даны атомарные высказывания: P Ему нужен доктор, Q Ему нужен адвокат, R С ним произошел несчастный случай, S Он болен, U Он ранен. Записать в виде предложений русского языка следующие формулы:

b

10. Для каждой из следующих формул определите, верно ли, что она общезначима, необщезначима, противоречива, непротиворечива или обладает некоторой комбинацией этих свойств:

# Преобразование формул логики высказываний. Получение ДНФ, КНФ,

СДНФ, СКНФ. Способы задания булевых функций

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

Часто бывает необходимо преобразовать формулы логики высказываний из одной формы в другую, особенно в так называемую “нормальную форму”. Это достигается путем эквивалентных преобразований формул. Говорят, что две формулы F и G эквивалентны или, что F эквивалентна G (обозначается F=G), тогда и только тогда, когда истинностные значения F и G совпадают при всех интерпретациях. Для осуществления эквивалентных преобразований произвольных формул логики высказываний используются следующие тождества (законы логики высказываний):

1) A B=(A B)(B A);

2) A B=AB;

3) законы коммутативности:

AB=BA, AB=BA;

4) законы ассоциативности:

(AB)C=A(BC),

(AB)C=A(BC);

5) законы дистрибутивности:

A(BC)=(AB)(AC),

A(BC)=(AB)(AC);

6) законы идемпотентности:

AA=A, AA=A;

7) законы элиминации:

A(АB)=A, A(AB)=A;

8) закон двойного отрицания:

A=A;

9) закон исключенного третьего:

AA=U,

где U какая-либо общезначимая формула;

10) закон противоречия

AA=Л,

11) тождества с константами

AЛ=Л, AЛ=A;

AU=A, AU=U;

12) законы де Моргана

(AB)=AB;

(AB)=AB;

Законы де Моргана обобщаются на случай n атомов:

(A₁A₂...A_n) = A₁A₂...A_n

(A₁A₂...A_n ) = A₁A₂...A_n.

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

Литера есть атом или отрицание атома. Формула F находится в конъюнктивной нормальной форме (КНФ), если она имеет вид: F=F₁F₂...F_n, где каждая из F₁, F₂,..., F_n есть дизъюнкция литер. Формула F находится в дизъюнктивной нормальной форме (ДНФ), если она имеет вид: F=F₁F₂...F_n, где каждая из F₁,F₂,...,F_n есть конъюнкция литер. Всякая формула может быть преобразована в нормальную форму. Это легко достигается использованием законов ЛВ. Процедура преобразования формул в нормальные формы описывается следующим алгоритмом:

Шаг 1. Используем законы:

F G=(F G)(G F),

F G=FG;

чтобы устранить (элиминировать) логические связки , .

Шаг 2. Несколько раз используем закон F=F и законы де Моргана:

(FG)=FG,

(FG)=FG,

чтобы перенести знак отрицания непосредственно к атомам. Шаг 3. Несколько раз используем дистрибутивные законы:

F(GH)=(FG)(FH),

F(GH)=(FG)(FH)

и другие законы, чтобы получить нормальную форму.

Наряду с задачей перехода от формулы высказывания к его таблице истинности зачастую требуется выполнить обратное: по заданной таблице истинности записать формулу которая передавала бы то же соответствие. Для этого используется совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Конституента 1  это конъюнкция, в которой по одному разу присутствуют литеры всех атомов, имеющихся в формуле. Свойства конституенты 1: 1) конституента 1 равна единице при единственной интерпретации, при которой и исходная формула также принимает единичное значение; 2) конъюнкция любого числа конституент 1 от одних и тех же переменных равна нулю. Конституента 0  это дизъюнкция, в которую входят по одному разу литеры всех атомов, имеющихся в формуле. Свойства конституенты 0: 1) конституента 0 принимает нулевое значение при единственной интерпретации, при которой и исходная формула также равна нулю; 2) дизъюнкция любого числа конституент 0 равна 1.

СДНФ формулы G  это дизъюнкция всех ее конституент 1. СКНФ формулы G  это конъюнкция всех ее конституент нуля. Обозначим через , где запись атома, взятого с отрицанием, либо без него, то есть: при 1 =A¹=A; при 0 =A⁰= A. Справедливо следующее правило записи СДНФ по таблице истинности:

1) для каждой интерпретации, где формула равна единице, выписываем соответствующую конституенту единицы. В качестве показателей при атомах берем истинные значения атомов в данной интерпретации; 2) объединяем полученные значения конституенты единиц дизъюнкцией. Получаем СДНФ. Желательно выписывать конституенты 1 в порядке возрастания номеров соответствующих им интерпретаций.

Правило записи СКНФ по таблице истинности формулируется аналогично. Однако, на первом шаге, при формировании конституент в качестве показателей при атомах берут отрицания истинных значений атомов в соответствующей интерпретации.

Введенные ранее шесть таблиц истинности, полученные в результате использования логических связок можно рассматривать как одноместные и двухместные функции особого вида. В них аргументы и значения могут принимать одно из двух возможных значений, обозначаемых 0 или 1. Такие функции называются логическими или булевыми.

Функция вида f(x₁,x₂,...,x_n)=y, где x₁,x₂,...,x_n,у называется n-местной булевой функцией. Всего существует 4 одноместных булевых функций вида f_i(x):

X	f0(x)	f1(x)	f2(x)	f3(x)
0 1	0 0	0 1	1 0	1 1

f₀(x)=0, f₁(x)=x, f₂(x)= , f₃(x)=1.

Всего существует 16 двухместных булевых функций вида _i(x,y):

x y	0	1	2	3	4	5	6	7
0 0 0 1 1 0 1 1	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1
x y	8	9	10	11	12	13	14	15
0 0 0 1 1 0 1 1	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

Наиболее известные булевы функции двух переменных:

₁(x,y)=xy=x*y=xy=x&y;

₆(x,y)=x y  сложение по mod 2 или функция неравнозначности;

₇(x,y)=ху  дизъюнкция;

₈(x,y)=х у=  стрелка Пирса или отрицание дизъюнкции;

₉(x,y)=x y  эквиваленция или функция равнозначности;

₁₃(x,y)=х у=х у  импликация;

₁₄(x,y)=х|y=  штрих Шеффера или отрицание конъюнкции;

Формула любого сложного высказывания может быть проинтерпретирована как булева функция, принимающая значение 1 на тех наборах значений аргументов (атомов в формуле ЛВ), при которых данное высказывание истинно, и принимающая значение 0 на тех наборах значений аргументов, на которых данное высказывание ложно. Любую булеву функцию можно задать таблицей истинности или с помощью СДНФ, СКНФ. Для булевых функций справедливы описанные выше тождества (законы алгебры логики) и правила перехода от таблиц истинности к СДНФ (СКНФ) и наоборот.

Рассмотрим примеры решения типичных упражнений и задач:

1. Получить ДНФ для формулы P(Q) R.

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

Шаг 1. Избавляемся от операции импликации:

P(Q) R=(P(Q))R;

Шаг 2. Используя законы де Моргана, приближаем все отрицания непостредственно к атомам:

(P(Q))R=(P( Q))R;

Шаг 3. Используем дистрибутивный закон, раскрываем скобки, используем закон двойного отрицания, приводим подобные члены, получаем ДНФ:

(P(Q))R=(PQ)R.

2. Получить КНФ для формулы (P(QR)) S.

Решение. Применяем тот же алгоритм.

Шаг 1. (P(QR)) S=(P(QR))S;

Шаг 2. (P(QR))S=(P(QR))S;

Шаг 3.(P(QR))S=((PQ)(PR))S=(PQS)(PRS).

3. Представить данную формулу в СКНФ: (PQ) R.

Решение. (PQ) R=(PQ)R=PQR=

=(PR)(QR)=(PQR)(PQR)

(PQR)(PQR)=

=(PQR)(PQR)(PQR).

4. По данной таблице истинности записать СДНФ и СКНФ формулы высказывания.

A B C	F(A,B,C)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 1 0 1 0 1 0

Решение. Используем правило получения ДНФ по таблице истинности:

Шаг 1. Выписываем все конституенты 1 для каждой интерпретации, где F=1. В качестве показателей при атомах берем истинные значения атомов в данной интерпретации. Получаем следующие конституенты 1:

A⁰B¹C⁰=ABC, A¹B⁰C⁰=ABC, A¹B¹C⁰=ABC

Шаг 2. Соединяя полученные конституенты 1 дизъюнкциями, получаем СДНФ:

ABC)(ABC)(ABC)=F.

Теперь получим представление той же формулы ЛВ в виде СКНФ:

Шаг 1. Выписываем все конституентны 0 для каждой интерпретации, где F=0. В качестве показателей при атомах берем отрицания значений атомов в данной интерпретации. Получаем следующие конституенты 0:

=A¹B¹C¹=ABC,

=A¹B¹C⁰=ABC,

=A¹B⁰C⁰=ABC,

=A⁰B¹C⁰=ABC,

Шаг 2. Соединяя полученные конституенты 0 конъюнкциями, получаем СКНФ: (ABC)(ABC)(ABC)(ABC).