Штрих Шеффера

Обозн. x|y (читается «x штрих y). Задается таблицей истинности:

Высказывание А|В озн-т, что А и В несовместны, т.е. не явл-ся истинными одновр-но. Через штрих Шеффера выраж-ся все др.лог.операции:Øx ~ x|x;

xÚy ~ (x|x)|(y|y);

x&y ~ (x|y)|(x|y);

x®y ~ x|(y|y).

x	y	x|y	x|x	y|y
x|x|y|y	x|y|x|y	x|(y|y)

Значит справедлива теорема 7:

Т7 Система булевых ф-ций {|} явл-ся полной.Штрих Шеффера был введен в рассмотрение Г.Шеффером.Cтрелка Пирса (введена за 30 лет до ш.Шеффера).Обозн. x↓y (читается «x стрелка y»). Задается таблицей истинности:

Высказывание А↓В означает «ни А, ни В». Через стрелку Пирса выражаются все другие логические операции:

Øx ~ x↓x;

x&y ~ (x↓x)↓(y↓y);

xÚy ~ (x↓y)↓(x↓y);

x	y	x↓y	x↓x	y↓y
(x↓x)↓(y↓y)	(x↓y)↓(x↓y)	((x↓x)↓y)↓((x↓x)↓y)

((x↓x)↓y)↓((x↓x)↓y) Значит справедлива теорема 8:

Т8 Система булевых функций {¯} является полной

3. Основные равнос-сти алгебры выс-й.Равносильные ф-лы Опр. Две ф-лы алгебры выс--й наз-ся равносильными, если они на одинаковых наборах знач-й своих переем-х принимают одинаковые знач-я истинности. Обозн. F₁~F₂

Читается: ф-ла F₁ равносильна ф-ле F₂.

Например: F₁=x &y; F₂=x y

. Свойства логических операций:(Основные равносильности (АВ))Приведем перечень наиболее важных равносильных ф-л, выражающих св-ва лог.операций, непосредственно усматриваемых из опр-й этих операций или легко устанавливаемых с пом-ю таблиц истинности:

1. -закон двойного отрицания.

2. x&x ~ x-идемпотентность конъюнкции.

3. xÚx ~ x-идемпотентность дизъюнкции.

4. x&y ~ y&x-ком-ть конъюнкции.

5. xÚy ~ yÚx-коммутативность дизъюнкции.

6. (x&y)&z ~ x&(y&z) -ассоциативность конъюнкции. 7. (xÚy) Úz ~ xÚ (yÚz) –ас-ть дизъюнкции.

8. x&(yÚz) ~ (x&y)Ú(x&z) -дистрибутивность конъюнкции относительно дизъюнкции.

9. xÚ(y&z) ~ (xÚy)&(xÚz) -дистрибутивность дизъюнкции относительно конъюнкции

10. x&(yÚx) ~ x-закон поглощения.

11. xÚ(y&x) ~x-закон поглощения.

12. -.закон де Моргана.

13 --закон де Моргана.

14. x«y ~ y«x.

15. x«y ~ (x®y)&(y®x)

16. .

17

18. x&y ~ .

19. xÚy ~

20. ( -закон противоречия).

21. - закон исключенного третьего.

22. x&1 .

23. x .

24. x&0 .

25. x 0 x

Докажем формулу (12):

Равнос-сти м.испол-ть для упрощения ф-л алгебры выск-й.Н-р.

1)

2)

Дизъюнктивные и конъюнктивные нормальные формы. (ДНФ и КНФ).Для кажд.ф-лы ал-ры выс-й м. указать равносильную ей ф-лу, содержащую из лог.связок лишь отрицание, конъюнкцию и дизъюнкцию. Опр. Ф-ла F наз-ся элементарной конъюн-й (дизъюнкцией), если F есть кон-ция (диз-ция) простейших выск-й или их отрицаний, и кажд.простейшее выс-е встречается в ф-ле ровно один раз.

Пр-ры:

Элемент.кон-ция	Элемент.диз-ция
-не явл-ся	-не явл-ся
- не явл-ся	-не явл-ся

Опр. ДНФ (КНФ) наз-ся ф-ла, явл-ся дизъюнкц-й (конъюнкц-й) элем-х конъюнкций (дизъюнкций). Пр-ры: const. º 0 –– ДНФ, x×y – ДНФ,x×yÚ y×zÚx – ДНФ.

Теорема. Всякая, не тождественно лож.ф-ла (АВ) равносильна нек-й ДНФ.Р! 2 способа нахождения ДНФ. Таб-й и аналитический (с помощью равносильностей).Пример. 1) Табличный:

. Составим т-цу истинности:

Рекомендации: выделить те строчки таблицы, в кот.значение ф-лы равно 1;напротив каждой выделенной строки записать конъюнкцию перем-х, входящих в ф- лу;поставить знак отрицания над теми перем-ми, значения кот.на дан.наборе равны 0;составить дизъюнкцию полученных элементарных конъюнкций. Это и есть ДНФ;

Упростить получ.ДНФ с пом-ю основных равносильностей до мин.ДНФ.

ДНФ:

( y (

Аналитический:-избавиться от импликаций с помощью равнос-й;-используя з-ны де Моргана отрицания внести внутрь ф-лы так, чтобы они относились к перем-м, двойныеотрицания удалить; - с помощью дистрибутивного закона получить ДНФ;-упростить ДНФ.

Пример.

~

~ ~ ~ ~

~ ~ ~ – минимальная ДНФ.