Лекции Математическая логика (стр. 5 )

Пример.

Важны места в функции, а именно 1-ое и 3-е.

Схема реализации функции: номера мест – номера входов в схему. Две леммы позволяют получить все булевы операции с помощью нелинейных, немонотонных, и констант 0 и 1. Это ещё не полнота в сильном смысле.

Лекция № 4.

ТЕОРЕМЫ О ПОЛНОТЕ (продолжение).

Определение 1.

Система функций называется функционально полной в слабом смысле, если любая БФ может быть представлена , т. е. может быть представлена суперпозицией констант 0, 1 и функций из .

Теорема 1.

О функциональной полноте в слабом смысле.

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

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

Пусть содержит немонотонную и нелинейную функцию. Тогда по лемме 1 получаем отрицание, а из леммы 2 получаем необходимые дизъюнкции и конъюнкции.3

Пример.

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

Нелинейная и немонотонная функция.

Утверждение 1.

Класс самодвойственных функций является замкнутым.

4Пусть и самодвойственны.

Подставим в вместо :

, т. е. g тоже замкнута.3

Теорема 2.

Поста (в сильном смысле).

Для того чтобы система была функционально полной в сильном смысле необходимо и достаточно, чтобы она содержала:

1.  Функцию, не сохраняющую ноль.

2.  Функцию, не сохраняющую единицу.

3.  Нелинейную функцию.

4.  Немонотонную функцию.

5.  Самодвойственную функцию.

4 Следует из замкнутости всех пяти классов.

Если не самодвойственна, то подстановкой и можно получить константу:

Тогда функция .

а)  Пусть теперь не сохраняет 0, а не сохраняет 1. не самодвойственна.

есть 1. по определению.

б)  Если , то , так как по определению и .

Тогда из подстановкой и получаем , являющуюся константой.

Используя ещё раз получаем другую константу.

Таким образом .

Этого достаточно для получения константы 0 и 1.

Таким образом, используя получение 0 и 1 и теорему о слабой полноте, получили теорему о сильной полноте. 3

Лекция № 5.

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ БУЛЕВЫХ ФУНКЦИЙ.

Определение 1.

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

Определение 2.

ДНФ называется минимальной, если она содержит наименьшее количество букв по сравнению со всеми другими ДНФ, эквивалентными исходной. Обозначим её МДНФ.

Будем считать набор аргументов точками n-мерного пространства. Тогда функцией будет n-мерный куб.

Определение 3.

Интервалом k-ого ранга будем называть подмножество вершин n-мерного куба, соответствующей конъюнкции k-ого ранга.

Интервал большего ранга покрывает интервал меньшего ранга.

Пример.

Определение 4.

Интервал I называется максимальным, если не существует и , где – множество наборов значений аргументов, на которых функция равна 1.

Определение 5.

ДНФ, полученная покрытием множества максимальными интервалами, называется сокращенной ДНФ (СокДНФ).

Метод минимизации Куайн-Мак-Класки.

1.  Нахождение первичных импликант. Все неотмеченные (не склеенные) мини термы называются первичными импликантами.

2.  Построение таблицы и её разметка.

3.  Нахождение существенных импликант, т. е. которые покрывают исходный мини терм (в столбце 1 галочка).

4.  Вычеркивание лишних столбцов. Если 2 столбца имеют галочки в одних строках, то 1 их них можно вычеркнуть.

5.  Вычеркивание лишних строк, если есть пустые строки.

Пример.

Смотри лабораторную работу.

Модификация Мак-Класки.

Мак-Класки решил вместо x писать двоичный код и разбивать на группы по числу единиц.

Лекция № 6.

МЕТОД БЛЕКА-ПОРЕЦКОГО.

Лемма 1.

Пусть , где . Тогда .

4

Если

Если 3

Пример.

После получения первичных импликант применяем метод Мак-Класки со второго шага (таблица).

Метод минимизации в базисе .

Лемма 2.

– выражение, описывающее n-местную над n операндами.

Если , то эквивалентно , т. е.

– произвольный терм.

4

3