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

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

а) ((A  B)  (C  A))  (B  C);

б) ((((A  B)  A)  B)  C)  C;

в) (A  (B  C))  ((A  C)  (A  B)).

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

а) (  С  С);

б) ((А 

в)    .

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

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

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

а) С С;

б)  )С));

в) С))  С).

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

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

x1	x2	e1		e2
1 1 0 1 1 0 0 0	1 0 1 1 0 1 0 0	1 1 1 0 0 0 0 1	1 0 0 0 1 1 0 1	1 1 1 1 0 0 0 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию 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, то  =0 < =1, такие что f₁() > f₁(). Следовательно, 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, и поэтому она неполна.