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

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

а) ;

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 ® B) Ù A Ù B;

b) Ú (A Ù (A ® B));

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

d) A Ù ( ® (A Ú B));

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

f) Ú (A ® );

g) ;

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

i) ( Ù 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 ® 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. Упростить схемы:

а)

b)

c)

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.

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

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

º º º º

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

º – СКН-форма.

º º

Ú Ú

Ú Ú º

º Ú Ú – СДН-форма.

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

Задание. Найти интерпретации, на которых формула Ø((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 переменных x₁, x₂, x₃, заданная в таблице

x1	x2	x3	f	g	h

Таблица 1.

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

- СКН-форма;

- СДН-форма.

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

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

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

где x₁ и x₂ - одноимённые разряды 1-го и 2-го слагаемых; e₁ - единица переноса из младшего разряда; e₂ – единица переноса в старший разряд суммы; å - результат суммирования.

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

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

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

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

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

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

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

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

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

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

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

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

Так как всякая формула может быть представлена приведенной формулой, то система å₀ = {Ù, Ú, } - полна.

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

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

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

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

.

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

Задание. Представить формулу (x₁ Ú x₂)( Ú x₁x₃) в виде полинома Жегалкина.

Решение.

(x₁ Ú x₂)×( Ú x₁x₃) = ( x₁x₂ Å x₁ Å x₂)×( x₁ x₃ Å x₁x₃ Å ) =

= x₁x₂x₃ Å x₁ x₃ Å x₁x₃ Å x₁ Å x₁x₂x₃ = x₁ x₃ Å x₁x₃ Åx₁ = = x₁ (x₂ Å 1) x₃ Å x₁ x₃ Å x₁ (x₂ Å 1) = x₁x₂x₃ Å x₁x₃ Å x₁x₃ Å x₁x₂ Å Å x₁ = x₁ x₂ x₃ Å x₁ x₂ Å x₁

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

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

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

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

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

Решение. Рассмотрим соответствующую å₀ систему булевых функций F₀ = { f₁, f₂, f₃ }, где f₁(x) = Øx , f₂(x₁, x₂) = x₁ Ù x₂ , f₃(x₁, x₂) = x₁ Ú x₂ . Покажем, что в F₀ есть хотя бы одна функция (не обязательно одна и та же), не принадлежащая каждому из замкнутых классов.

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

f₁(0) = 1, f₁ÏT₀.

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

f₁(1) = 0, f₁ÏT₁.

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

f₁^*(x) = Ø(Ø ) = Øx = f₁(x). Таким образом, f₁ ÎT^*.

f₂^*(x₁, x₂) = x₁ Ú x₂ ¹ f₂(x₁, x₂), т.е. f₂ ÏT^*.

4. Класс монотонных функций.

Так как f₁(0) = 1, а f₁(1) = 0, то $ a=0 < b=1, такие что f₁(a) > f₁(b). Следовательно, f₁ÏT_£.

5. Класс линейных функций.

f₁(x) = Øx = x Å 1, т.е. f₁ – линейна.

f₂(x₁, x₂) = x₁ Ù x₂ = x₁×x₂, а значит f₂ÏT_L.

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

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

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

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

f₁(0, 0) = 1, f₁ÏT₀.

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

f₁(1, 1) = 1, f₂(1, 1) = 1. Следовательно, f₁ ÎT₁ и f₂ ÎT₁, в системе нет булевой функции, не сохраняющей 1, и поэтому она неполна.

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

1. Доказать полноту систем операций сведение системы к å₀.

а) å₁= { Ù, ^¾}; b) å₂= { Ú, ^¾};

c) å₃ = { | }; d) å₄ = {¯ };

e) å₅ = {®, Ø}; f) å₆ = {Å, Ú}.

2. Представить формулу в виде полинома Жегалкина:

a) x₁ Ú x₃; b) x₁ x₂ Ú ;

c) ; d) .

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

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

а) å₁ = {Ù, Ú, ®}; б) å₂ = {Ø};

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

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