ПГНИУ-20.09.22 МЛ Л 4

Тема 2:Логика высказываний

Лекция 4

Функциональная полнота
систем логических функций

С.94-145

С.47-145

Логические функции одной и двух переменных называются элементарными
где В – бинарное множество {0,1}

1. Логические функции одной переменной

Сколько всего функций одной переменной?

2⋅2

n=1

2.Логические функции двух переменных

Сколько всего функций двух переменных?

2⋅2⋅2⋅2

Сколько всего функций n переменных?

3.Суперпозиция и проблема функциональной полноты

Суперпозиция
Подстановка в данную функцию вместо ее переменных других функций.

Проблема функциональной полноты
Каким должен быть минимальный состав элементарных логических функций, чтобы путём суперпозиции получить любую сколь угодно сложную логическую функцию от конечного числа переменных?

Классы ПФ

1) класс функций, сохраняющих константу 0.
В этот класс входят функции, которые на нулевом наборе переменных принимают нулевое значение: f(00...0)=0.

2) класс функций, сохраняющих константу 1.
В этот класс входят функции, которые на единичном наборе переменных принимают единичное значение: f(11...1)=1.

Самодвойственность

Двойственность f и g

Двойственность f и g

Самодвойственность

Линейность

Класс линейных функций.
функция называется линейной, если возможно представление в виде линейного полинома, использующего функцию сложения по модулю 2:
f(x1x2)=с0⊕с1х1⊕с2х2,
где с0,с1,с2 – константы 0, 1.

f(x1x2)=с0⊕с1х1⊕с2х2

Монотонность

Класс монотонных функций.
Монотонная функция на большем сравнимом наборе переменных принимает не меньшие значения. Это удобно проверять на решетках Хассэ.

3.Теорема (критерий) Поста

Пост, Эмиль Леон (1897 – 1954)

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

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

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

ПФ двух переменных
N4-7

ПФ двух переменных
N8-11

ПФ двух переменных
N12-15

Имеются базисы, состоящие из двух функций:

Примеры базисов
Импликативный базис

Примеры базисов
Базис Жегалкина:

Не минимальное множество (не базис) – из трех функций:

Имеются функции, обладающие всеми пятью отмеченными свойствами. Таковы функции↓⎥.
Часто их называют соответственно ИЛИ-НЕ, И-НЕ.
Таким образом, это базисы, состоящие из одной функции.

Т3. МИНИМИЗАЦИЯ ФОРМУЛ ЛОГИКИ ВЫСКАЗЫВАНИЙ

С.118-145

С.62-102

Метод Квайна-Мак-Класки.

Willard Van Orman Quine (1908-2000), McCluskey (1929-2016)

Таблица Квайна

Минимизация по кубу соседних чисел

МИНИМИЗАЦИЯ
ПО
КАРТАМ КАРНО

Maurice Karnaugh (1924) is an American physicist, famous for the Karnaugh mapMaurice Karnaugh (1924) is an American physicist, famous for the Karnaugh map used in Boolean algebra.

Edward W. Veitch (1924 –2013) was an American computer scientist.

Карта Карно для n=3

Карта Карно для n=4

Пример.

Карта Карно для n=5?

Карта Карно для n=6?