Методические рекомендации по изучению дисциплины (стр. 6 )

б) ;

.

Формула А над В называется тождественно истинной 9тождественно ложной), если - функция тождественно равная 1 (0).

Пример1.6.2 Доказать, что формула

является тождественно истинной.

Упражнение 1.6.6 Доказать, что данные формулы являются тождественно ложными:

а) ;

б) .

1.7 Нормальные формы.

Пусть и . Положим

Формула , ; называется конъюнкцией (дизъюнкцией) над множеством переменных . Число t называется рангом конъюнкции (дизъюнкции). Отметим, что никаких ограничений на вхождения переменных и их отрицаний в конъюнкции (дизъюнкции) над не накладывается: любая переменная из (а также её отрицание) может иметь любое конечное число вхождений; при этом всякая переменная может входить в конъюнкцию (дизъюнкцию) одновременно со своим отрицанием.

Пример 1.7.1

а) ; ; ; ; - конъюнкции над множеством переменных рангов 8; 3; 1; 3; 2 соответственно;

б) ; ; ; - дизъюнкции над множеством переменных рангов 7; 3; 2; 1 соответственно.

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

Пример 1.7.2

а) ; ; ; ; - элементарные конъюнкции над множеством переменных рангов 4; 3; 2; 3; 1 соответственно;

б) ; ; ; ; - элементарные дизъюнкции над множеством переменных рангов 3; 5; 3; 2; 1 соответственно.

Упражнение 1.7.1 Найти число различных конъюнкций (дизъюнкций) ранга t над множеством переменных .

Дизъюнктивной нормальной формой (Д. Н.Ф.) над множеством переменных называется формула

,

где - произвольная конъюнкция над .

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

Пример 1.7.3

а) - Д. Н.Ф. над ;

б) - К. Н.Ф. над .

Упражнение 1.7.2 Доказать, что:

а) Д. Н.Ф. над тождественно ложна тогда и только тогда, когда каждая конъюнкция, входящая в D (в качестве логического слагаемого), содержит некоторую переменную из вместе с её отрицанием (в качестве логических сомножителей);

б) К. Н.Ф. над тождественно истинна тогда и только тогда, когда каждая дизъюнкция, входящая в К (в качестве логического сомножителя), содержит некоторую переменную из вместе с её отрицанием в качестве логических слагаемых.

Д. Н.Ф. D над называется приведённой, если:

а) всякая конъюнкция, входящая в D, является элементарной;

б) конъюнкции, входящие в D попарно различны;

в) в каждой конъюнкции, входящей в D, переменные (как логические сомножители) расположены в порядке возрастания номеров.

Аналогично, К. Н.Ф. К над называется приведённой, если:

а) всякая дизъюнкция, входящая в К, является элементарной;

б) дизъюнкции, входящие в К попарно различны;

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

Пример1.7.4

а) - приведённая Д. Н.Ф. над ;

б) - приведённая К. Н.Ф. над .

Упражнение 1.7.3 Доказать, что число различных приведённых Д. Н.Ф. над множеством переменных равно .

Упражнение 1.7.4 Доказать, что для всякой формулы А над В существует равносильная ей а) Д. Н.Ф.; б) К. Н.Ф.

Упражнение 1.7.5 Доказать, что для всякой алгебры логики существует представление в виде:

а)

;

б) ,

где , .

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

Пример 1.7.5

а) - С. Д.Н. Ф. над ;

б)- С. К.Н. Ф. над .

Набору поставим в соответствие элементарную конъюнкцию ранга n, где

, .

Нетрудно заметить, что указанное соответствие будет биективным.

Упражнение 1.7.6 Доказать, что элементарная конъюнкция принимает значение 1, на наборе и значение 0 на любом наборе , отличном от .

Пример 1.7.6 Найдём наборы , на которых С. Д.Н. Ф. А принимает значение 1, где

.

Согласно упражнения 1.7.6 для этого нужно выписать наборы соответствующие элементарным конъюнкциям, входящим в А:

; ; ; ; .

На остальных 11 наборах С. Д.Н. Ф А принимает значение 0.

Упражнение 1.7.7 Доказать, что для всякой, отличной от константы 0, функции алгебры логики существует представление в виде:

.

Упражнение 1.7.6 и 1.7.7 дают следующий способ построения С. Д.Н. Ф., представляющей функцию :

1) находим табличное задание функции ;

2)  отмечаем те наборы , для которых ;

3)  по каждому отмеченному набору строим соответствующую элементарную конъюнкцию ранга n;

4)  берём логическую сумму (дизъюнкцию), полученных в пункте 3) элементарных конъюнкций.

Пример 1.7.7 Д.Н. Ф. представляющую функцию f от переменных , если f принимает значение 1, когда значение 1 принимает не менее двух переменных.

Исходя из определения функции f, получаем её табличное задание:

0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Справа к этой таблице добавили столбец, в котором выписаны элементарные конъюнкции ранга 3, соответствующие наборам, на которых функция f принимает значения 1. В результате получаем:

.

Упражнение 1.7.8 Н. Ф., представляющую функцию f :

а) ;

б) .

Набору поставим в соответствие элементарную дизъюнкцию ранга n, где

, .

Нетрудно заметить, что указанное соответствие будет биективным.

Упражнение 1.7.9 Доказать, что элементарная дизъюнкция принимает значение 0, на наборе и значение 1 на любом наборе , отличном от .

Пример 1.7.8 Найдём наборы ., на которых С. К.Н. Ф. А принимает значение 0, где

Согласно упражнения 1.7.9 выписываем наборы, соответствующие элементарным дизъюнкциям, входящим в А: ; ; ; ; .

На остальных наборах С. К.Н. Ф. принимает значение 1.

Упражнение 1.7.10 Доказать, что для всякой, отличной от константы 1, функции алгебры логики существует представление в виде:

.

Упражнение 1.7.9 и 1.7.10 дают следующий способ построения С. К.Н. Ф., представляющей функцию :

1) находим табличное задание функции ;

2)  отмечаем те наборы , для которых ;

3)  по каждому отмеченному набору строим соответствующую элементарную дизъюнкцию ранга n;

4)  берём логическое произведение (конъюнкцию), полученных в пункте 3) элементарных дизъюнкций.

Пример 1.7.8 К.Н. Ф. представляющую функцию . Перейдём к табличному заданию функции .

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Справа к таблице добавлен столбец, в котором выписаны элементарные дизъюнкции ранга 3, соответствующие наборам, на которых функция f принимает значения 0. В результате получаем: