Реферат по дисциплине Дискретная математика на тему Функционально полные базисы булевых функций. Пять важнейших замкнутых класса T0, T1, S, L, M. Теорема Поста о функциональной полноте
![]()
|
Поста.T0 , T1 , S, L, Mназываются классами Теорема 6.1 (критерий Поста). Система Fбулевых функций является полной тогда и только тогда, когда Fцеликом не содержится ни в одном из классов Поста. В таблице приведены свойства, которыми обладают элементарные булевы функции (символ + отмечает свойство, которым обладает данная функция). Свойства элементарных булевых функций.
Используя теорему Поста и вышеприведенную таблицу можно строить базисы из элементарных функций по следующему правилу: выбрав любую элементарную булеву функцию и дополнив ее при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. Через функции этого базиса можно выразить все другие булевы функции. 1 1 2 2 2 2 Пример. Запишите функцию f x1 x x3 в базисе ,,. 1 2 3 Решение. f x1 x x3 xx x3 xx x3 x1 x2 x3 x2 x3 1 1 2 2 xx x3 xxx x2 x3 xxx x2 x3 . 3 Определение 2.6. Система Fбулевых функций называется замкнутой, если любая формула над Fпредставляет некоторую функцию из F . Фундаментальным свойством каждого класса Поста является его замкнутость (в смысле определения 2.6). 1 2 Чтобы исследовать полноту конкретной системы F f, f,..., f n булевых функций, используют критериальную таблицу:
Строки таблицы соответствуют функциям исследуемой системы, а столбцы – классам Поста. Знак + означает, что функция не принадлежит соответствующему классу Поста. Пусть, например, F ,,0. На основании таблицы свойств элементарных булевых функций заполненная критериальная таблица имеет вид:
Как видно из таблицы, система Fцеликом не содержится ни в одном из классов Поста (ни в одном столбце нет всех знаков «–»). Согласно теореме система функций является полной. Исследуем на полноту систему, которая содержит булевы функции, не являющиеся элементарными. Пусть, например, F f, f, где f xx, f x x. 1 2 1 1 2 2 1 2 Проверим, какими свойствами обладают данные функции: Сохранимость константы 0. 1 f00 0 0 0 1 0, т.е. fсохраняет константу 0; 1 2 f00 0 0 11 1, т.е. f2 не сохраняет константу 0. Сохранимость константы 1. 1 f11 1 1 1 0 0, т.е. fне сохраняет константу 1; 1 2 f11 1 1 0 0 1, т.е. fсохраняет константу 1. 2 Самодвойственность. ![]() , т.е. fне самодвойственная. ![]() 1 2 1 2 1 1 2 1 1 2 2 fx , x x x2 x1 x2 x1 x2 x1 x2 ; fx , x x x2 x1 x2 и 1 1 2 2 2 1 1 2 fx, x fx, x , т.е. f2 не самодвойственная. 1 2 2 Линейность. f1 и f2 не являются линейными. Объяснение этому будет дано далее . |