Слайд 1Лекции по Дискретной математике
Функционально полные системы.
Лекция 12
Слайд 2Базис логической алгебры
Система логических функций называется функционально полной
(ФПС) или базисом, если через нее формулой может быть выражена
любая логическая функция.
- ФПС в слабом смысле, если любая логическая функция представима в виде суперпозиции функций и констант 0 и 1.
Утверждение: Система является базисом, если через нее выразимы функции ФПС .
Слайд 3Примеры базисов
{,,} – базис Буля
{, , 1} – базис Жегалкина
{,
} – конъюнктивный базис
{, } – дизъюнктивный базис
{, } –
базис Гильберта
{} – базис Пирса
{} – базис Шеффера
Слайд 4Замыкание базиса.
Замыкание ФПС ([ ]) – это множество ПФ, которые
можно получить из композицией.
Теорема: , - некоторые множества ПФ,
тогда
[]
[[]]=[]
[][]
- ФПС [] - ФПС.
Слайд 5Свойства функций базиса Буля
Σ= {,,}
идемпотентность: хх=х, хх=х
коммутативность: ху=ух, ху=ух
ассоциативность:
х(yz)= (хy)z,
х(yz)= (хy)z
поглощение: (xy)x=x, (xy)x=x
дистрибутивность: х(yz)= (хy) (хz),
х(yz)= (хy) (хz)
Слайд 6Свойства функций базиса Буля
Σ= {,,}
Слайд 7Представление ПФ в булевом базисе
х1х2= х1х2
х1х2 = (х1х2) = х1(х2)
х1х2=
(х1х2) = х1(х2)
х1х2 =(х1х2)(х2х1)=
=(х1х2)(х1х2)
х1х2 = (х1х2) =(х1х2)(х2х1)=
=(х1х2)
(х2х1)
Слайд 8Свойства ПФ базиса Жегалкина
Σ={, , 1}
А
B = B A, A B = B
A
А (B C) = (A B) (A C)
А A = 0, А A = A
А 1 = A, А 1 = A
А 0 = A, А 0 = 0
Слайд 9Представление булевых функций
в базисе Жегалкина
A = А 1
А В= (А В)=
=(А 1) (В
1) 1=
=А В АВ
Слайд 10Выражение булевых функций
в минимальных базисах
X Y = (X
Y)
X =X | X
X Y =
(X Y) =
= (XY) (XY)
X Y = (X Y)
X =XX
X Y= (X | Y) =
= (X|Y)|(X|Y)
Слайд 11Замкнутые классы ПФ
Система логических функций называется замкнутым классом, если
любая композиция ее функций является ее же замыканием т.е =[].
Пример:
Σ={f1, f2} , f1=x, f2= x
f1f2=f2 f2f1=f2
f1f1=f1 f2f2=f1
Слайд 12Функции, сохраняющие константы
0={f | f(0,0,…,0)=0}
Пример: дизъюнкция, конъюнкция, т.л.(0)
1={f |
f(1,1,…,1)=1}
Пример:
дизъюнкция, конъюнкция, т.и.(1)
Слайд 13Монотонные функции
= {f | f()f()},
где =(a1…an),
=(b1…bn)
,
= {i aibi}
пример: тождественность аргументу,
дизъюнкция, конъюнкция, константы
Слайд 14Линейные функции
л = {f | f=ixi i},
где
i{0,1}, i{0,1}
представимы в виде полинома Жегалкина первой степени
Слайд 15Теоремы о функциональной полноте
Теорема 1. - ФПС в
слабом смысле, если она содержит хотя бы одну немонотонную или
нелинейную функцию.
Теорема 2 (Теорема Поста). - ФПС тогда и только тогда, когда она содержит хотя бы одну
нелинейную функцию,
немонотонную функцию,
несамодвойственную функцию,
функцию, не сохраняющую констант.
Слайд 16Доказательство теоремы Поста
Необходимость. Пусть есть хотя бы одна из перечисленных
функций, тогда данная система замкнута, т.е. через этот базис невозможно
выразить остальные функции, не входящие в ФПС. Получаем противоречие допущению.
Слайд 17Доказательство теоремы Поста
Достаточность.
![Замыкание базиса.Замыкание ФПС ([ ]) – это множество ПФ, которые можно получить из композицией.Теорема: , -](/img/thumbs/7c07871de670a3e440a9e2cda6a8820a-800x.jpg "Лекции по Дискретной математике Замыкание базиса.Замыкание ФПС ([ ]) – это множество ПФ, которые можно")
