Булевы функции двух переменных

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

	x
	y
название	обозначение	Значения переменных	формула
φ0 нуль (константа)
φ1 конъюнкция	. , &, Λ					x&y
φ2 отрицание	x, , x’
φ3 = x (константа)						x
φ4
φ5 (x, y) = y						y
φ6 сложение по mod2	+, Å, D
φ7 дизъюнкция	Ú					xÚy
φ8 стрелка Пирса	¯
φ9 эквивалентность	~, ≡, ↔					x↔y
φ10 (x, y) =
φ11						y→x
φ12 (x, y) =
φ13 импликация	→, Þ, É					x→y
φ14 штрих Шеффера x│y	½					x│y =
φ15 единица						

Все функции двух переменных являются комбинацией этих основных функций.

Пусть F = {f₁, …, f_m} – множество всех булевых функций.

Формулой над F называется выражение вида ₣ [F] = f(t₁, …, t_L)

где fÎF и t_i либо переменная либо формула над F, тогда множество F называется базисом, f – главной (внешней) формулой (или операцией), t_i - подформулой.

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

Пример 1.F₁= (xLy)V((xL )V( Ly)).

x					xLy	F1

Если сравнить зачения функции и ее аргументов с таблицей основных функций, можно заметить, что F₁ – реализует дизъюнкцию.

Пример 2. F₂= (x₁Lx₂)®x₁

F₂ – реализует константу 1.

Пример 3. F₃= ((x₁Lx₂) + x₁) + x₂

F₃ – реализует дизъюнкцию.

Одна функция может иметь множество реализаций (над данным базисом). Формулы, реализующие одну и ту же функцию, называются равносильными(F₁º F₂)

Равносильные формулы:

1. аÚа = а аÙа = а

2. аÚb = bÚа аÙb = bÙа

3. аÚ (bÚс) = (аÚb) Úс аÙ (bÙс) = (аÙb) Ùс

4. (аÙb) Úа = а (аÚb) Ùа = а

5. аÚ (bÙс) = (аÚb) Ù (аÚс) аÙ (bÚс) = (аÙb) Ú (аÙс)

6. аÚ1 =1 аÙ0 = 0

7. аÚ0 = а аÙ1 = а

8. а = а

9. ( аÙb) = аÚb (аÚb) = аÙв

10. аÚа = 1 аÙа = 0

Все они могут быть проверены построением соответствующих таблиц истинности.

Говорят, что < E₂; Ú, Ù, > булева алгебра.

Формулы ₣₁ и ₣₂ – эквивалентные (₣₁ ~ ₣₂) если при любых значениях переменных значение ₣₁ совпадает со значением ₣₂.

Формула называется выполнимой (опровержимой), если это такой набор значений переменных, при которых эта формула принимает значение истина (ложь).

Формула называется тождественно истинной или тавтологией (тождественно ложной или противоречие), если эта формула принимает значение истина (ложь) при всех наборах значений переменной.

ЗАДАЧИ

1. Максимально упростите выражение, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните ваше упрощенное выражение с исходным:

а)( Ú d) Ù (( Ù c) Ú (a Ù c) Ú ( Ù ) Ú (a Ù )) Ù(bÚ d);

б) (aÚ c) Ù ( Ú ) Ù ( Ú c) Ù ( Ú b) Ù (b Ú c);

в) (aÙ c) Ú ((bÚ ) Ù ( Ú ) Ù (d Ú c) Ù ( Ú d)) Ú (a Ù ).

2.Аналитическим способом, т.е. на основе формул взаимосвязи между логическими операциями , докажите справедливость тождества, затем с помощью диаграмм Эйлера-Венна подтвердите справедливость этого доказательства:

а) ((aïb) ï(a~b)) ï((c+d)®(d-c)=((b®c) ®(a-c))¯((aïd) ï(d® ));

б) ((aÙ )¯(b-c)) Ù((aïd)-(bÙd))=((aïb) ï(a+ ))®((c+d) Ù(d®c));

в) ((a ¯ b) Ú (a + b)) - ((c - d) ¯ (c ~ d))=((c® a) Ù (c® b)) ® ((a ¯ d) Ú (b ¯ d)).