Булева алгебра (стр. 2 )

Конъюнкция

Операция конъюнкции в дискретной математике соответствует союзу "И ".

Пусть х - "Я студент", у - "Я учусь в ЮТИ ТПУ ", тогда ху соответствует высказывание «Я студент И я учусь в ЮТИ ТПУ». Если «Я студент» истинное высказывание, то х=1 Если «Я учусь в ЮТИ ТПУ» истинное высказывание, тоу=1 А теперь получим результат нашего высказывания

«Я не студент (х =0) и я не учусь в ЮТИ ТПУ (у-0)». Результатом будет явная ложь - 0,

«Я не студент (х =0) и я учусь в ЮТИ ТПУ (у=1)». Результатом будет также ложь - 0.

«Я студент (х=1) и я не учусь в ЮТИ ТПУ (у=0)». Результатом будет также ложь - 0.

«Я студент {х =1) и я учусь в ЮТИ ТПУ (y=1)». Это истина - 1.

Дизъюнкция

Операция дизъюнкция в дискретной математике соответствует союзу ИЛИ. Пусть х - "У моего дяди есть собака".

у - " У моего дяди есть кошка",

тогда xy соответствует высказывание

«У моего дяди есть собака ИЛИ кошка».

Импликация

Операция импликация х→y в дискретной математике соответствует связке ЕСЛИ ТО.

Пусть х-«У меня есть билет» x=1,

y- "Меня не оштрафуют" y=1,

тогда х→у соответствует высказывание;

«Если у меня есть билет, то меня не оштрафуют».

Это высказывание будет ложно лишь в том случае, когда у тебя есть билет, а тебя все-таки оштрафовали. Ты вправе возмутиться таким беззаконием. Это несправедливо! Да несправедливо, именно по этой причине, в таблице импликации в строке, где х-1, а у-0 значение функции также равно нулю. Допустим, что ты будешь не против проехать зайцем, не покупая билет и при этом если тебя не оштрафуют. Поэтому высказывание "Если у меня нет билета, то меня не оштрафуют" считается истинным.

Х1		Х2		→
о	«У меня нет билета»	0	"Меня оштрафуют"	1	"Если у меня нет меня оштрафуют
0	«У меня нет билета»	1	"Меня не оштрафуют"	1	"Если у меня нет меня не оштрафуют
1	«У меня есть билет»	0	"Меня оштрафуют"	0	"Если у меня ее меня оштрафуют
1	«У меня есть билет»	1	"Меня не оштрафуют"	1	"Если у меня есть меня не оштрафуют

Функция эквивалентности x1~x2 в дискретной математике соответствует смысловой связке тогда и только тогда или если : если.

Пусть х — "Я выучил все билеты",

у-" Я точно сдам экзамен на 5",

тогда х~у соответствует высказывание

«Я точно сдам экзамен если и только если я выучу все билеты».

Другими словами, эквивалентность подразумевает под равенство.

Функция -сумма по модулю два x1x2 в дискретной математике соответствует связке либо... либо.

Пусть х - "Эта фигура квадрат",

у - " Эта фигура окружность",

тогда ху соответствует высказывание

«Эта фигура либо, либо окружность»,

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

Функция штрих Шеффера x1 /х2 это отрицание конъюнкции

Пусть х - "Я студент ",

у - "Я учусь в ЮТИ ТПУ ".

Тогда х / y соответствует высказывание

«неверно, что я студент и учусь в ЮТИ ТПУ».

Функция стрелка Пирса X1↙x2,- это отрицание дизъюнкции

Пусть х - "У моего дяди есть собака",

у - " У моего дяди есть кошка",

тогда х ↙ y соответствует высказывание «неверно, что у моего дяди есть собака или кошка».

Упражнение №1:

Пусть х-«Идет дождь», у-«Дует ветер». Запишите в виде формулы следующие высказывания:

1.  Если идет дождь, то дует ветер;

2.  Если дует ветер, то идет дождь;

3.  Ветер дует тогда и только тогда, когда идет дождь;

4.  Если дует ветер, то дождя нет;

5.  Неверно, что ветер дует тогда и только тогда. когда пет
дождя;

6.  Неверно, что дует ветер или вдет дождь;

7.  Неверно, что дует ветер и идет дождь.

Упражнение №2:

Пусть х-«Идет дождь», у-«Дует ветер», z-«Светит солнце».Запишите словами следующие высказывания представленные формулами:

Например, (ху)→

Словами запишется так:

«Если идет дождь и дует ветер, то солнце не светит».

1.  ;

2.  ;

3.  ;

4.  .

Упражнение №3:

Запишите в виде формул, заменив союзы на значки логические операций:

Например: (если с то r) и (если r то с) и не (s или y).

ответ .

1.  если с, то не (r или s) ;

2.  если r или s, то не c;

3.  у тогда и только тогда, когда r или с;

4.  если r то с, и если с то у;

5.  y и (с или г);

Задание булевых функций с помощью таблицы истинности

Любую булеву функцию можно задать помощью таблицы истинности. Для этого необходимо указать значение функции на всех наборах.

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

Например, из конъюнкции и дизъюнкции, используя скобки можем построить функцию (x v y) (хyy) xy.

Запомните! Операция конъюнкции сильнее всех остальных опер если нет скобок, то ее выполняем самой первой.

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

Построение таблицы истинности покажем на примере(табл. 3).

Пусть . Функция зависит от двух аргументов, следовательно в таблице истинности будет 22=4 строк.

Таблица 3. Пример

x y	(xy)
0 0	0
0 1	1
1 0	0
1 1	0

Перепишем нашу формулу, подставив вместо х и у их значения из первой строки. Тогда получим: (00) . Первой будет выполняться операция в скобках, то есть дизъюнкция, ищем по таблице истинности (№4) значение дизъюнкции на наборе 00, оно равно (00)=0. Чему равен ноль с инверсией? Ответ 0=1. А инверсия единицы? =0 . Теперь мы должны найтив таблице истинности (табл. №4) значение конъюнкции на наборе 01. Оно равно (01)=0. Записываем получений ноль в строке 00, в столбец значений функций.

Проделываем аналогичные действия для второй строки:

(0 l) = 1/\1=1;

для третьей строки: (1 0) =1/\0= 0;

для четвертой строки: (1 1) = 1 /\0=0.

Есть другой способ построения таблиц истинности. Рассмотрим еще один пример в котором функция зависит от трех аргументов (следовательно будет 23=8 строк). Таблица 6 построена для функции f(x1,x2,x3)=(x1→x3) (x2/x1) . Мы разобьем всю формулу на подформулы, соответственно разобьем таблицу на дополнительные столбцы. Пронумеруем их в порядке выполнения операций. Пятый столбец будет результирующим.

В первом столбце работаем с первой и третьей переменной и используем таблицу истинности для импликации.

Во втором столбце работаем с первой и второй переменной и используем таблицу истинности для функции штрих Шеффера.

Третий столбец особенный. Мы применяем операцию дизъюнкции к переменным х1 и х2. а затем должны записать инверсию (или отрицание) результата. Например, на наборе 110 мы получим (10) это равно 1 и теперь берем инверсию и получаем 0.

В четвертом столбце мы выполняем операцию конъюнкции между значениями из первого и второго столбца. Таким образом, в первой строке получим l/\1=1.

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

Таблица 4. Для функции f(x1,x2,x3)=(x1→x3) (x2/x1)

	1	4	2	5	3
x1 x2 x3			(x2/x1)
0 0 0	1	1	1	1	1
0 0 1	1	1	1	1	1
0 1 0	1	1	1	1	0
0 1 1	1	1	1	1	0
1 0 0	0	0	1	0	0
1 0 1	1	1	1	1	0
1 1 0	0	0	0	0	0
1 1 1	1	0	0	0	0

Теперь попробуйте построить таблицы истинности сами.

Упражнение №1:

Постройте таблицы истинности для функций.

1. 5. 10.(x↙y)\z

2. 6. 11. (xyxz)yz

3. 7. 12.

4. 8. 9. .

3.  Существенные и фиктивные переменные

Определение: Набором α (альфа) длины n назовём последовательность α1,α2,…,αi , где αi – называется i-ым разрядом и равно 0 или 1.

Например, в наборе α =11010 α1 =1 α2 =1 α3 =0 α4 =1 α5 =0.

Определение: Наборы, которые отличаются значением лишь одного разряда называются соседними.

Определение: Говорят, что функция f(x1,x2,…,xn) существенно зависит от переменной xi, если существует набор значений α1, α2,…, αi-1, αi+1,…, αn для переменных x1,x2,…,xi-1,xi+1,…,xn, такой что f(α1, α2,…, αi-1,0, αi+1,…, αn )f(α1, α2,…, αi-1,1, αi+1,…, αn).

В определении в наборе α намеренно пропущен разряд αi.

Определение: Если функция существенно не зависит от переменной xi, то эта переменная называется фиктивной.

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

x y z	f
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 * 0 1 0 0 * 1 0 1

Рассмотрим это на примере функции f, заданной вектором значений f(x,y,z)=(1,0,1,0,0,1,0,1). Этот вектор записываем по вертикали в столбец значений функции f.

Начнем с переменной х, ищем соседние наборы у которых различие лишь в разряде соответствующем переменной х. Набору 000 соответствует набор 100 (найдите их в таблице истинности, эти наборы помечены звездочками), значение функции этих наборах отличается f(0,0,0)=1, f(1,0,0)=0. Можно сказать, повезло, так как мы сразу нашли наборы, на которых значение функции изменяется с изменением значения переменной х,при условии, что у и z остаются неизменными. Следовательно определению функция f(x,y,z) существенно зависит от переменной х.

Рассмотрим переменную у. Ищем соседние наборы у которых различие лишь в разряде соответствующем переменной у. Набору соответствует набор 010. Значения функции f(0,0,0)= 1 и f(0,1,0)=1 этих наборах совпадают. Мы еще не имеем права делать никаких выводов. Проверяем следующие наборы. Набору 001 соответствует набор 011, значения функции f(0,0,1)=0 и f(0,1,1)=0 совпадают, проверили уже первые четыре набора, движемся дальше. Значение функции f(1,0,0)=0 и f(1,1,0)=0 совпадают. Проверяем последние набора 101 и 111, f(1,0,1)=1 и f(1,1,1)=1. Подведем итог. Мы не нашли ни одной пары соседних наборов по переменной у, таких, что бы значение функции отличалось. Следовательно, переменная у фиктивная.

Аналогичная проверка показывает, что переменная z существенная. Теперь мы можем сократить нашу таблицу следующему правилу.

Вычеркиваем либо все строки, содержащие 1, либо все строки содержащие 0 в столбце соответствующем фиктивной переменной. Вычеркиваем столбец, соответствующий этой переменой.

В результате наша таблица примет вид (в данном примере мы вычеркивали строки, в которых переменная у =0).

Определение. Функции называются равными, если одна из них может бы получена из другой путём добавления или исключения несущественных переменных.

Упражнение №1:

Найдите в предложенных функциях фиктивные переменные и сократите

таблицы истинности.

a)  f(x, y)=(1,0,1,0);

b)  f(x, y)=(1,1,0,0);

c)  f(x, y,z)=(0,1,0,0,0,1,0,0);

d)  f(x, y,z)=(1,1,0,01,1,1,1);

e)  f(x1,x2,x3,x4)=(1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1);

f)  f(x1,x2,x3,x4)=(0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0);

g)  f(x1,x2,x3,x4)=(0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1);

h)  f(x1,x2,x3,x4)=(1,1,1,1,0,1,0,1,0,0,0,0,1,0,1,0).