Дискретная математика (стр. 6 )

a + 0 = a a × 1 = a

a + 1 = 1 a × 0 = 0

a + b = b + a ab = ba коммутативный

(переместительный) закон

(a + b) + c = a + (b + c) (ab)c = a(bc) ассоциативный

(сочетательный) закон

a(b + c) = ab + ac a + bc = (a + b)(a + c) дистрибутивный

(распределительный) закон

a + a = a aa = a идемпотентность

a + ab = a (a + b)a = a поглощение

склеивание

Правила де Моргана:

, для нескольких переменных

, для нескольких переменных

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

7.3. Правила преобразования некоторых логических функций

a + b = a Å b Å ab

`a = a Å 1

a Å b = a`b +`ab

a Å 0 = a

a Å a = 0

a½b = 

ab = 

a ® b =`a + b

a « b = ab +`a`b

Пример 1. Упростить выражение

= (x2 +`x3) + (x1x2 + x2 ×`x3) + x1 =

= (x2 + x1x2) + (`x3 + x2 ×`x3) + x1 = x2(1 + x1) +`x3(1 + x2) + x1 =

= x2 × 1 +`x3 × 1 + x1 = = x2 +`x3 + x1

Пример 2. Доказать справедливость соотношения

((`a ® (c Å b)) × (`b ® (a × d)) × (d ® (b Å c)) × (a Å c)) ® a = 1

((`a ® (c Å b)) × (`b ® (a × d)) × (d ® (b Å c)) × (a Å c)) ® a = 

= ((a + (c Å b)) × (b + ad) × (`d + (b Å c)) × (a ×`c + `ac)) ® a =

= ((a + (c Å b)) × (`d + (b Å c)) × (b + ad) × (a ×`c + `ac)) ® a =

= ((a ×`d + (c Å b)) × (ab ×`c +`abc + a ×`cd)) ® a =

= ((a ×`d + b ×`c +`bc) × (ab ×`c +`abc + a ×`cd)) ® a =

= (ab ×`c ×`d + ab ×`c + ab ×`cd) ® a = ab ×`c × (`d + 1 + d) ® a =

= (ab ×`c × 1) ® a = ab ×`c ® a =   =`

=a +`b + c + a = 1 +`b + c = 1

Контрольные вопросы

1. Сколько наборов можно образовать из

а) 3-х входных переменных;

2. Определить количество различных логических функций

а) 3-х аргументов;

3. Пусть p и q обозначают следующие высказывания:

p: Я совершу путешествие на Марс.

q: У меня есть деньги.

Запишите в символической форме такое высказывание: «У меня нет денег и я не совершу путешествие на Марс.»

4. Пусть p, q и r обозначают следующие высказывания:

p: Эта игра очень трудна.

q: Я играю в шахматы.

r: Игра в шахматы требует времени.

Интерпретируйте следующее выражение как обычное высказывание: (p Ú r) Ù q.

5. Определить значения функции f(x1, x2, x3) = x3 + (x1 Å (`x1 × x2)) на наборе данных (0, 1, 1).

8. Минимизация логических функций

8.1. Минимизация с помощью карт Карно

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

Составим карты Карно для функций двух, трех и четырех аргументов.

Пусть задана логическая функция двух аргументов:

Пусть функция трех аргументов задана таблицей:

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