Пример 2. Упростить формулу.

Решение. Подвергнём формулу A равносильным преобразованиям:

Пример 3. Доказать, что формула тождественно истинная.

Решение. Подвергнём формулу A равносильным преобразованиям

Упражнение 1. Доказать равносильность:

1) ;

2) ;

3) ;

4) ;

5) ;

Упражнение 2. Упростить формулу:

1) ;

2) ;

3) ;

4) .

5) ;

6) ;

Упражнение 3. Доказать тождественную истинность или тождественную ложность формул:

;

Упражнение 4. Найдите x, если .

Домашнее задание:

1. Доказать тождественную истинность или тождественную ложность формул:

;

2. Упростить:

а) ;

б) ;

3 Занятие №3

3.1 Функции алгебры логики. Совершенные нормальные формы

Определение 2. Элементарной конъюнкциейn переменных называется конъюнкция переменных или их отрицаний.

Определение 3. Дизъюнктивной нормальной формой (ДНФ) формулы A называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкции.

Определение 4. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы A называется ДНФ A, обладающая свойствами (С).

СДНФ A можно получить двумя способами: а) с помощью таблицы истинности; б) с помощью равносильных преобразований.

Определение 5. Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний.

Определение 6. Конъюнкция нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Определение 7. Совершенной конъюнктивной нормальной формой формулы А (СКНФ А), называется КНФ А, удовлетворяющая четырем свойствам:

1) все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные;

2) все элементарные дизъюнкции, входящие в КНФ А, различны;

3) каждая элементарная дизъюнкция, входящая в КНФ А, содержит переменную один раз;

4) ни одна элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и её отрицание.

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

Пример 1. Найти формулу, определяющую функцию Ф(x,y,z), по заданной таблице истинности:

x	y	z	Ф(x,y,z)
1	1	1	1
1	1	0	0
1	0	1	0
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	1

Решение. Используя правило получения формулы алгебры логики из таблицы истинности для функции Ф(x,y,z), получим:

Упростив эту формулу, получим:

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

Пример 2. Следующую формулу привести к СДНФ, предварительно приведя её равносильными преобразованиями к ДНФ: .

Решение.

Отве т: .

Пример 3. Для формулы из примера 2 найти СДНФ путём составления таблицы истинности.

Решение. Составим таблицу истинности для формулы .

a	b	C	c	b		A
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
1	0	0	0	0	1	1
0	1	1	1	0	0	0
0	1	0	0	0	1	0
0	0	1	0	0	1	0
0	0	0	0	0	1	0

Тогда .

Пример 4. Для формулы из примера 2 найти СКНФ путём равносильных преобразований, предварительно приведя ее к КНФ.

Решение. Из примера 2: . Далее

Ответ: .

Все формулы алгебры логики делятся на три класса: 1) тождественно истинные; 2) тождественно ложные; 3) выполнимые.

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

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

Пример 6. Будет ли формула тождественно истинной, тождественно ложной или выполнимой?

Решение. Приведём пример к какой-либо нормальной форме:

Получение ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и её отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преобразуем данную формулу к КНФ.

Это произведение не является тождественно истинным, так как элементарная сумма не тождественно истинна, следовательно, она выполнима.

Упражнение №1. По таблице истинности найдите формулы, определяющие функции , , и придайте им более простой вид:

	x	y	z

	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун	0	0	1	1	0	0
Смит	0	1	0	0	1	0
Вессон	1	0	0	0	0	1

	Физика	Математика	Информатика	Литература	География
Ирена	0	1	0	0	0
Тимур	0	0	0	0	1
Камилла	1	0	0	0	0
Эльдар	0	0	0	1	0
Залим	0	0	1	0	0