Преобразуем эту формулу, используя соответствующие эквивалентности

U º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º

º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru .

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Изобразим схему, соответствующую заключительной формуле

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Варианты заданий.

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.Доказать формулы обобщённого склеивания:

а) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ;

b) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ;

c) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ;

d) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru .

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

a) (A Ù B) Ú ( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù B) Ú ( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) º 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) ( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù B Ù C) Ú (C Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) Ú (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 ® B) Ù A Ù B;

b) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú (A Ù (A ® B));

c) (A ® Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) Ù (B ® C);

d) A Ù ( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ® (A Ú B));

e) (B ® A) Ù (A ~ B);

f) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú (A ® Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru );

g) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ;

h) (A ® B) Ù (B ® C)) ® (C ® A);

i) ( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù B Ù C) Ú (A Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ù C )Ú ( A Ù B Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) Ú (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 ® B) Ù B) ®A; б) ØA ® (A Ú B);

в) Ø(A ® B) ~ (ØA ÚB); г) Ø(A ® B) ~ Ø(A Ù ØB);

д) Ø(A ® B) ® ((B ® C) ® (A ® C)).

8. Построить формулу U такую, чтобы данная формула была тождественно истиной:

а) (((U Ù Q) ® ØR) ® ((R ® ØQ) ® U));

б) (((R ® (ØQ Ù R)) ® U) ® (U Ù (R ® Q) Ù R)).

9. Являются ли эквивалентными условия выхода в операторах цикла:

а) while (i<n)and(a[i]<>x)and(not marked[i]);

б) while not((i>=n)or(a[i]=x)or(marked[i]));

в) until not((i<n)or(a[i]<>x))or(marked[i]).

10. Упростить схемы:

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru а)

b)

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru c)

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru d)

11. Составить релейно-контактные схемы для функций, считая, X ® Y ~ ØX Ú Y :

а) (X ® Y) Ù (Y ®Z); б) ((X ® Y) Ù(Y ®Z))®(X ® Z);

в) (X ® Y) ® (ØX Ù (Y Ú Z)); г) (X ® (Y ®Z)) ® (Y ® ØX).

Нормальные формы

Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами.

Алгоритм построения совершенных нормальных форм.

1. Преобразовать формулу к приведенному виду (см. п.1.).

2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности операций конъюнкции и дизъюнкции.

3. Если нормальная форма не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13.

Задание. Построить совершенные нормальные формы формулы Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru .

Решение. Преобразуем формулу к приведенному виду и затем упростим ее.

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Полученная формула является КН- и ДН-формой. Обе построенные нормальные формы не являются совершенными. Приведем их к совершенному виду, используя законы склеивания 13.

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru – СКН-форма.

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú

Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º

º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru – СДН-форма.

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы. Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.

Задание. Найти интерпретации, на которых формула Ø((A Ù B) ® A) Ú (A Ù (B Ú С)) принимает значения 1 и 0.

Решение.

1. Упростим формулу и построим её нормальные формы.

Ø((A ÙB)®A) Ú (A Ù (B Ú С)) ºØ(Ø(A Ù B) Ú A) Ú (A Ù (B Ú С)) º º (A Ù B Ù Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) Ú (A Ù (B Ú С)) º 0 Ú (A Ù (B Ú С)) º A Ù (B Ú С) º º (A Ù B) Ú (A Ù C)

2. Построим совершенные нормальные формы.

СКНФ строим из КНФ A Ù (B Ú С).

A Ù (B Ú С) º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º

º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

СДНФ – из ДНФ (A Ù B) Ú (A Ù C).

(A Ù B) Ú (A Ù C) º Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

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

A B C

Аналогично по СКНФ найдем интерпретации, на которых формула ложна.

A B C

Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.

Например, функция f переменных x1, x2, x3, заданная в таблице

x1 x2 x3 f g h

Таблица 1.

имеет следующие совершенные нормальные формы:

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru - СКН-форма;

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru - СДН-форма.

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

Варианты заданий

1. Преобразовать формулы к дизъюнктивной и конъюнктивной нормальным формам:

а) ((A ® B) ® (C ® ØA)) ® (ØB ® ØC);

б) ((((A ® B) ® ØA) ® ØB) ® ØC) ® C;

в) (A ® (B ® C)) ® ((A ® ØC) ® (A ® ØB)).

2. Привести к СДНФ и СКНФ формулы:

а) (ØA ® ØB) ® ((B Ù С) ® (A Ù С ));

б) ((А ® B) ®ØA) ® (A ® (B Ù A))

в) Ø((A Ù B) ® ØA) Ù Ø((A Ù B) ® ØB).

3. По данному набору значений переменных построить элементарную конъюнкцию, истинную только для этого набора значений переменных.

4. По данному набору значений переменных построить элементарную дизъюнкцию, ложную только для этого набора значений переменных.

5. Построить СКНФ и СДНФ, эквивалентные данной формуле, и найти интерпретации, на которых формула истинна и ложна:

а) (С ® A) ® (Ø(B Ú С) ® A);

б) Ø((A Ù B) ® A) Ú (A Ù (B Ú С));

в) Ø(A Ù (B Ú С)) ® ((A Ù B) Ú С).

6. Для функций g и h, определённых в таблице 1, найти СКН - и СДН – формы и простейшие формулы, реализующие эти функции.

7. Составить две булевы функции, планирующие 1-разрядный двоичный сумматор по следующей таблице

x1 x2 e1 å e2

где x1 и x2 - одноимённые разряды 1-го и 2-го слагаемых; e1 - единица переноса из младшего разряда; e2 – единица переноса в старший разряд суммы; å - результат суммирования.

8. Построить формулу от трёх переменных, которая истинна в том и только в том случае, когда ровно две переменные ложны.

9. Построить формулу от трёх переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.

10. По СКНФ формулы U построить:

а) СДНФ двойственной формулы U*;

б) СКНФ формулы ØU;

в) СДНФ формулы ØU.

11. По СДНФ формулы U и СДНФ формулы B построить:

а) СКНФ и СДНФ формулы (U Ú B);

б) СКНФ и СДНФ формулы (U Ù B);

в) СКНФ и СДНФ формулы (U ® B).

Полные системы операций

Система операций å называется полной, если любая логическая операция может быть представлена формулой над å.

Так как всякая формула может быть представлена приведенной формулой, то система å0 = {Ù, Ú, Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru } - полна.

Система å сводится к å*, обозначается å®å*, если все операции системы å* представимы формулами над системой å. Если å* полна, то и å полна.

Последнее утверждение даёт один из способов доказательства полноты системы операций – сведение её к известной полной системе, например к å0. То есть полной будет система å, через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.

Задание. Доказать полноту системы å5 = {Ù, Å}.

Решение. Сведем систему å5 к полной системе å0.

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru

Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru .

Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все возможные упрощения, то получится формула, имеющая вид суммы произведений, то есть полинома по mod 2. Такая формула называется полиномом Жегалкина для данной функции. Линейной называется функция, полином Жегалкина которой линеен.

Задание. Представить формулу (x1 Ú x2)( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú x1x3) в виде полинома Жегалкина.

Решение.

(x1 Ú x2)×( Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú x1x3) = ( x1x2 Å x1 Å x2)×( x1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru x3 Å x1x3 Å Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) =

= x1x2x3 Å x1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru x3 Å x1x3 Å x1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Å x1x2x3 = x1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru x3 Å x1x3 Åx1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru = = x1 (x2 Å 1) x3 Å x1 x3 Å x1 (x2 Å 1) = x1x2x3 Å x1x3 Å x1x3 Å x1x2 Å Å x1 = x1 x2 x3 Å x1 x2 Å x1

Полученный полином не является линейным и имеет степень 3.

Сводимость к полной системе операций является необходимым условием полноты системы операций. Необходимое и достаточное условие полноты системы операций формулируется в терминах булевых функций.

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

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

Задание. Доказать полноту системы å0, используя необходимое и достаточное условие полноты.

Решение. Рассмотрим соответствующую å0 систему булевых функций F0 = { f1, f2, f3 }, где f1(x) = Øx , f2(x1, x2) = x1 Ù x2 , f3(x1, x2) = x1 Ú x2 . Покажем, что в F0 есть хотя бы одна функция (не обязательно одна и та же), не принадлежащая каждому из замкнутых классов.

1. Класс функций, сохраняющих 0.

f1(0) = 1, f1ÏT0.

2. Класс функций, сохраняющих 1.

f1(1) = 0, f1ÏT1.

3. Класс самодвойственных функций.

f1*(x) = Ø(Ø Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ) = Øx = f1(x). Таким образом, f1 ÎT*.

f2*(x1, x2) = x1 Ú x2 ¹ f2(x1, x2), т.е. 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(x1, x2) = x1 Ù x2 = x1×x2, а значит f2ÏTL.

Следовательно, в силу теоремы Поста система å0 полна.

Задание. Является ли система операций å ={®, Ú} полной?

Решение. Также как и в предыдущей задаче воспользуемся теоремой Поста. Рассмотрим соответствующую å систему булевых функций F = { f1, f2}, где f1(x1, x2) = x1®x2 , f2(x1, x2) = x1 Ú x2.

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) x1 Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru x3; b) x1 x2 Ú Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ;

c) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru ; d) Преобразуем эту формулу, используя соответствующие эквивалентности - student2.ru .

3. Доказать полноту систем операций задания 1, используя необходимое и достаточное условие полноты.

4. Доказать неполноту систем операций:

а) å1 = {Ù, Ú, ®}; б) å2 = {Ø};

в) å3 = {Ù,Ú,®,~}.

5. Покажите, что система функций F = { f1, f2}, f1(x1, x2) = = x1~x2 , f2(x1, x2) = x1 Å x2 не является полной. Укажите все способы сделать эту систему полной добавлением одной не более чем двухместной функции.

Наши рекомендации