 |
Преобразуем эту формулу, используя соответствующие эквивалентности
|
|
|
|
U º 
º
º 
.
Изобразим схему, соответствующую заключительной формуле
Контрольные вопросы и задания
1. Построить таблицу истинности для формулы:
a) (P ® Ø(Q Ù P)) ® (P Ú R);
b) (P ® (Q ® R)) ® ((P ® Q) ® (P ® R));
c) (P Ù (Q Ú ØP)) Ù ((ØQ ® P) Ú Q);
d) ((A®B)Ù(B®С))®(A®С);
e) (P ® Q) Ú (P®(Q Ù P));
f) ((A ® ØB) ® C) Ú ØA;
g) Ø(A Ù ØB) ® (B Ú C);
h) (C ® (Ø(A Ú C) ® A)) ~ B.
2. С помощью таблиц истинности показать эквивалентность формул:
a) A ® B º (ØA) Ú B;
b) Ø(A Ù B) º (ØA) Ú (ØB);
c) Ø(A Ú B) º (ØA)Ù (ØB);
d) A Ù (B Ú C) º ((A Ù B) Ú (A Ù C);
e) A Ú (B Ù C) º (A Ú B) Ù (A Ú C).
3.Доказать формулы обобщённого склеивания:
a) 
;
b) 
;
c) 
;
d) 
.
4. Доказать эквивалентность формул:
a) (A Ù B) Ú (
Ù B) Ú ( Ù 
) º A ® B;
b) (AÚ B) Ù (A Ú C) Ù (B Ú D) Ù (C Ú D) º (A Ù D) Ú (B Ù C);
c) A Ù (A Ú C) Ù (B Ú C) º (A Ù B) Ú (A Ù C);
d) (AÚ B) Ù (B Ú C) Ù (C Ú A) º (A Ù B) Ú (B Ù C) Ú (C Ù A);
e) (AÚ B) Ù (B Ú C) Ù (C Ú D) º (A Ù C) Ú (B Ù C) Ú (B Ù D);
f) (AÚ B Ú C) Ù (B Ú C Ú D) Ù (C Ú D Ú A) º
º (A Ù B) Ú (A Ù D) Ú (B Ù D)Ú C;
g) (A Ù B) Ú ((A Ú B) Ù (Ø A Ú ØB)) º A Ú B;
h) ( Ù B Ù C) Ú (C Ù Ù ) Ú (B Ù C) º C Ù (A ® B);
i) (A Ù D) Ú (C Ù D) Ú (A Ù B) Ú (C Ù B) º (A Ú C) Ù (D Ú B);
j) A ® (C ® P) º (A Ù C) ® P.
5. Упростить формулы:
a) 
Ú (A Ù (A ® B));
b) (A ® ) Ù (B ® C);
c) A Ù (
® (A Ú B));
d) (B ® A) Ù (A ~ B);
e) 
Ú (A ® );
f) 
;
g) (A ® B) Ù (B ® C)) ® (C ® A);
h) ( Ù B Ù C) Ú (A Ù Ù C)Ú (A Ù B Ù 
) Ú (A Ù B Ù C).
6. Доказать тождественную истинность формул:
|
|
|
a) (P ® R) ® ((Q ® R) ® ((P Ú Q) ® R));
b) (Q ® R) ® ((P Ú Q) ® (P Ú R));
c) (P ® Q) ® ((P ® (Q ® R)) ® (P ® R));
d) (P ® Q) ® ((Q ® R) ® (P ® R));
e) (P ® Q) ® ((P ® ØQ) ® ØP);
f) (ØQ ® ØP) ® ((ØQ ® P) ® Q).
7. Являются ли следующие формулы тождественно ложными:
a) ((A ® B) Ù B) ®A;
b) Ø(A ® B) ~ Ø(A Ù ØB);
c) Ø(A ® B) ® ((B ® C) ® (A ® C)).
8. Построить формулу U такую, чтобы данная формула была тождественно истиной:
a) ((U Ù Q) ® ØR) ® ((R ® ØQ) ® U);
b) ((R ® (ØQ Ù R)) ® U) ® (U Ù (R ® Q) Ù R).
9. Являются ли эквивалентными условия выхода в операторах цикла:
a) while ((i<n) && (a[i]<>x) && (! marked[i]));
b) while (!((i>=n) | | (a[i]=x) | | (marked[i]));
c) while (!(!(i<n) | | (a[i]<>x) && marked[i])).
10. Упростить схемы:
а)
b)
c)
d)
Нормальные формы
Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами.
Алгоритм построения совершенных нормальных форм.
1. Преобразовать формулу к приведенному виду (см. п.1).
2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности операций конъюнкции и дизъюнкции.
3. Если нормальная форма не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13.
Задание 2.1. Построить совершенные нормальные формы формулы 
.
Решение. Преобразуем формулу к приведенному виду и затем упростим ее.
º 
º 
º 
º 
Полученная формула является КН- и ДН-формой. Обе построенные нормальные формы не являются совершенными. Приведем их к совершенному виду, используя законы склеивания 13.
º 
– СКН-форма.
º 
º
º 
Ú 
Ú
Ú 
Ú 
º
º Ú Ú 
– СДН-форма.
С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы. Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.
|
|
|
Задание 2.2. Найти интерпретации, на которых формула Ø((A Ù B) ® A) Ú (A Ù (B Ú С)) принимает значения 1 и 0.
Решение.
1. Упростим формулу и построим её нормальные формы.
Ø((A ÙB)®A) Ú (A Ù (B Ú С)) ºØ(Ø(A Ù B) Ú A) Ú (A Ù (B Ú С)) º º (A Ù B Ù ) Ú (A Ù (B Ú С)) º 0 Ú (A Ù (B Ú С)) º A Ù (B Ú С) º º (A Ù B) Ú (A Ù C)
2. Построим совершенные нормальные формы.
СКНФ строим из КНФ A Ù (B Ú С).
A Ù (B Ú С) º 
º
º 
º 
СДНФ – из ДНФ (A Ù B) Ú (A Ù C).
(A Ù B) Ú (A Ù C) º 
3. По совершенным нормальным формам определим значения высказывательных переменных, на которых формула истинна и ложна. Для нахождения интерпретаций истинности формулы используем СДНФ, наборы значений переменных запишем в таблицу, порядок их записи соответствует порядку полных элементарных конъюнкций в СДНФ.
| A | B | C |
Аналогично по СКНФ найдем интерпретации, на которых формула ложна.
| A | B | C |
Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение формулы, заданной таблицей истинности. Нули формулы определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам формулы можно построить ее СДН-форму.
Например, формула F переменных X1, X2, X3, заданная таблицей истинности
| x1 | x2 | x3 | f | g | h |
Таблица 1.
имеет следующие совершенные нормальные формы:
F 
– СКН-фор-ма;
F 
– СДН-форма.
|
|
|
Упростив любую из этих формул, можно получить простейшую формулу, реализующую данную функцию.
Контрольные вопросы и задания
1. Преобразовать формулы к дизъюнктивной и конъюнктивной нормальным формам:
a) ((A ® B) ® (C ® ØA)) ® (ØB ® ØC);
b) ((((A ® B) ® ØA) ® ØB) ® ØC) ® C;
c) (A ® (B ® C)) ® ((A ® ØC) ® (A ® ØB)).
2. Привести к СДНФ и СКНФ формулы:
a) (ØA ® ØB) ® ((B Ù С) ® (A Ù С));
b) ((А ® B) ®ØA) ® (A ® (B Ù A))
c) Ø((A Ù B) ® ØA) Ù Ø((A Ù B) ® ØB).
3. По данному набору значений переменных построить элементарную конъюнкцию, истинную только для этого набора значений переменных.
4. По данному набору значений переменных построить элементарную дизъюнкцию, ложную только для этого набора значений переменных.
5. Построить СКНФ и СДНФ, эквивалентные данной формуле, и найти интерпретации, на которых формула истинна и ложна:
a) (С ® A) ® (Ø(B Ú С) ® A);
b) Ø((A Ù B) ® A) Ú (A Ù (B Ú С));
c) Ø(A Ù (B Ú С)) ® ((A Ù B) Ú С).
6. Для формул G и H, заданных таблицей 1, найти СКН - и СДН – формы и простейшие формулы, реализующие эти функции.
7. Построить формулу от трёх переменных, которая истинна в том и только в том случае, когда ровно две переменные ложны.
8. Построить формулу от трёх переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.
9. По СКНФ формулы U построить:
a) СДНФ двойственной формулы U*;
b) СКНФ формулы ØU;
c) СДНФ формулы ØU.
10. По СДНФ формулы U и СДНФ формулы B построить:
a) СКНФ и СДНФ формулы (U Ú B);
b) СКНФ и СДНФ формулы (U Ù B);
c) СКНФ и СДНФ формулы (U ® B).
Полные системы операций
Система операций å называется полной, если любая логическая операция может быть представлена формулой над å.
Так как всякая формула может быть представлена приведенной формулой, то система å0 = {Ù, Ú, 
} - полна.
Система å сводится к å*, обозначается å®å*, если все операции системы å* представимы формулами над системой å. Если å* полна, то и å полна.
Последнее утверждение даёт один из способов доказательства полноты системы операций – сведение её к известной полной системе, например к å0. То есть полной будет система å, через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.
|
|
|
Задание 3.1. Доказать полноту системы å1 = {Ù, Å}.
Решение. Сведем систему å1 к полной системе å0.
.
Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все возможные упрощения, то получится формула, имеющая вид суммы произведений, то есть полинома по mod 2. Такая формула называется полиномом Жегалкина для данной функции. Линейной называется функция, полином Жегалкина которой линеен.
Задание 3.2. Представить формулу (x 1 Ú x 2)(
Ú x 1 x 3) в виде полинома Жегалкина.
Решение.
(x 1 Ú x 2)×(
Ú x 1 x 3) = (x 1 x 2 Å x 1 Å x 2)×(x 1 
x 3 Å x 1 x 3 Å ) =
= x 1 x 2 x 3 Å x 1 x 3 Å x 1 x 3 Å x 1 Å x 1 x 2 x 3 = x 1 x 3 Å x 1 x 3 Å x 1 =
= x 1 (x 2 Å 1) x 3 Å x 1 x 3 Å x 1 (x 2 Å 1) = x 1 x 2 x 3 Å x 1 x 3 Å x 1 x 3 Å x 1 x 2 Å
Å x 1 = x 1 x 2 x 3 Å x 1 x 2 Å x 1
Полученный полином не является линейным и имеет степень 3.
Сводимость к полной системе операций является необходимым условием полноты системы операций. Необходимое и достаточное условие полноты формулирует теорема Поста в терминах булевых функций.
Задание 3.3. Доказать полноту системы å0, используя необходимое и достаточное условие полноты.
Решение. Рассмотрим соответствующую å0 систему булевых функций F0 = { f1, f2, f3 }, где f1(x) = Ø x, f2(x 1, x 2) = x 1 Ù x 2, f3(x1, x2) = x 1 Ú x 2. Покажем, что в F0 есть хотя бы одна функция (не обязательно одна и та же), не принадлежащая каждому из замкнутых классов.
1. Класс функций, сохраняющих 0.
f1(0) = 1, f1ÏT0.
2. Класс функций, сохраняющих 1.
f1(1) = 0, f1ÏT1.
3. Класс самодвойственных функций.
f1*(x) = Ø(Ø 
) = Ø x = f1(x). Таким образом, f1 ÎT*.
f2*(x 1, x 2) = x 1 Ú x 2 ¹ f2(x 1, x 2), т.е. f2 ÏT*.
4. Класс монотонных функций.
Так как f1(0) = 1, а f1(1) = 0, то $ a=0 < b=1, такие что f1(a) > f1(b). Следовательно, f1ÏT£.
5. Класс линейных функций.
f1(x) = Ø x = x Å 1, т.е. f1 – линейна.
f2(x 1, x 2) = x 1 Ù x 2 = x 1× x 2, а значит f2ÏTL.
Следовательно, в силу теоремы Поста система å0 полна.
Задание 3.4. Является ли система операций å ={®, Ú} полной?
Решение. Также как и в предыдущей задаче воспользуемся теоремой Поста. Рассмотрим соответствующую å систему булевых функций F = { f1, f2}, где f1(x 1, x 2) = x 1® x 2, f2(x 1, x 2) = x 1 Ú x 2.
1. Класс функций, сохраняющих 0.
f1(0, 0) = 1, f1ÏT0.
2. Класс функций, сохраняющих 1.
f1(1, 1) = 1, f2(1, 1) = 1. Следовательно, f1 ÎT1 и f2 ÎT1, в системе нет булевой функции, не сохраняющей 1, и поэтому она неполна.
Контрольные вопросы и задания
|
|
|
1. Доказать полноту систем операций сведением системы к å0.
а) å1 = { Ù, Ø}; b) å2 = { Ú, Ø};
c) å3 = { | }; d) å4 = {¯ };
e) å5 = {®, Ø}; f) å6 = {Å, Ú}.
2. Представить формулу в виде полинома Жегалкина:
a) x 1 
Ú 
x 3; b) x 1 x 2 Ú 
;
c) 
; d) 
.
3. Доказать полноту систем операций задания 1, используя необходимое и достаточное условие полноты.
4. Доказать неполноту систем операций:
а) å1 = { Ù, Ú, ®}; б) å2 = {Ø};
в) å3 = { Ù,Ú,®,~}.
5. Покажите, что система функций F = { f1, f2}, f1(x 1, x 2) = = x 1~ x 2, f2(x 1, x 2) = x 1 Å x 2 не является полной. Укажите все способы сделать эту систему полной добавлением одной не более чем двухместной функции.
Выводимость
Пусть задано множество формул от высказывательных переменных 
(
), 
(),..., 
(). (1)
Это множество формул назовем системой посылок.
Определение. Формула 
(
) называется выводимой из системы формул (1) в алгебре высказываний, что обозначается 
,.., ú- 
, тогда и только тогда, когда формула
(2)
является ТИ-высказыванием.
Непосредственное доказательство выводимости формулы по определению сводится к уже известной задаче доказательства тождественной истинности формулы (2) (см. п. 1). Помимо этого способа существует эквивалентное необходимое и достаточное условие выводимости формулы: вхождение всех полных элементарных дизъюнкций формулы в СКН-форму формулы
. (3)
На основе этого условия сформулируем алгоритм доказательства выводимости формулы.
1. Из системы посылок (1) строится конъюнкция (3).
2. Находим СКН-форму от высказывательных переменных для формулы (3).
3. Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).
Задание 4.1. Доказать выводимость 
ú- 
.
Решение.
1. Обозначим 
= X, = 
. Строим их конъюнкцию 
.
2. Найдем СКН-форму 
эквивалентную этой конъюнкции.
V
3. Получим СКН-форму для формулы B 
.
Так как обе дизъюнкции входят в СКН-форму 
, то выводимость доказана.
Задание 4.2. Найти все формулы, выводимые из системы посылок задания 4.1.
Решение. Построим различные комбинации полных элементарных дизъюнкций 
формулы .
1. 
2. 
3. 
4. 
5. 
6. 
7. 
Как легко видеть, при построении всех СКН-форм, выводимых из данной системы посылок, мы получили, как частный случай, формулу 
.
Контрольные вопросы и задания
Показать выводимость формул в алгебре высказываний, используя определение выводимости (1 – 6).
1. X ® Y, Y ® Z ú- X ® Z
2. X ® (Y ® Z) ú- Y ® (X ® Z)
3. X ® Y, Y ® Z, X ú- Z
4. X ® Y, 
ú- 
5. X ® (Y ® Z), X ® Y, X ú- Z
6. X, ú- 
Доказать выводимость формул в алгебре высказываний, используя СКН-формы (7 – 15).
7. Z ® Y ú- ® 
8. (A Ù B) ® C ú- A ® (B ® C)
9. A ® B ú- (B ® C) ® (A ® C)
10. U ® B ú- (G Ù U) ® (G Ù B)
11. U ® B ú- (G Ú U) ® (G Ú B)
12. A ú- B ® (A Ù B )
13. 
ú- 
14. 
ú- 
15. 
ú- 
Построить множество формул, выводимых из данной системы посылок (16 – 19).
16. 
17. 
18. 
19. 
|
|
|
