ДМ.9. Замкнутые классы

Содержание

Слайд 2

Замкнутый класс

Система функций Σ называется замкнутым классом, если любая суперпозиция функций системы

Замкнутый класс Система функций Σ называется замкнутым классом, если любая суперпозиция функций
Σ снова принадлежит системе Σ.

Слайд 3

Пример 1

Множество всех конъюнкций K1 – замкнутый класс.

Пример 1 Множество всех конъюнкций K1 – замкнутый класс.

Слайд 4

Пример 2

Множество всех дизъюнкций K2 – замкнутый класс.

Пример 2 Множество всех дизъюнкций K2 – замкнутый класс.

Слайд 5

Пример 3

Множество всех полиномов Жегалкина K3 – замкнутый класс.

Пример 3 Множество всех полиномов Жегалкина K3 – замкнутый класс.

Слайд 6

Замыканием сиcтемы функций Σ называется система [Σ], состоящая из всех функций системы

Замыканием сиcтемы функций Σ называется система [Σ], состоящая из всех функций системы
Σ и всех суперпозиций функций системы Σ.

Замыкание

Слайд 7

Система функций Σ называется функционально полной (ФП), если через суперпозиции функций этой

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

Функционально полные системы

Слайд 8

Если система функций Σ является замкнутым классом,
то есть Σ=K,
тогда она равна своему

Если система функций Σ является замкнутым классом, то есть Σ=K, тогда она
замыканию:

Замечание 1

Слайд 9

Если система функций Σ является функционально полной,
тогда ее замыкание равно всему множеству

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

Замечание 2

Слайд 10

Пусть система - множество булевых операций
(базис Буля).
Σ0 – ФП, так как

Пусть система - множество булевых операций (базис Буля). Σ0 – ФП, так
любая логическая функция может быть выражена Булевой формулой (БФ).

Пример 1

Слайд 11

Система Σ0 является избыточной.

Пример 2

Дизъюнкцию можно выразить через конъюнкцию и

Система Σ0 является избыточной. Пример 2 Дизъюнкцию можно выразить через конъюнкцию и
отрицание:

Конъюнкцию можно выразить через дизъюнкцию и отрицание:

Слайд 12

Откуда:

Продолжение примера 2

Откуда: Продолжение примера 2

Слайд 13

Замечание:

За не избыточность системы приходится платить избыточностью формул.

Замечание: За не избыточность системы приходится платить избыточностью формул.

Слайд 14

Тогда, в системе Σ1 она принимает вид:

Пример 3

Пусть булева формула имеет вид:

Тогда, в системе Σ1 она принимает вид: Пример 3 Пусть булева формула имеет вид:

Слайд 15

Тогда, в системе Σ2 она принимает вид:

Пример 4

Тогда, в системе Σ2 она принимает вид: Пример 4

Слайд 16

Это следует из того, что через штрих Шеффера можно выразить функции ФП

Это следует из того, что через штрих Шеффера можно выразить функции ФП
системы:

Пример 6

Система

- функционально полна.

Слайд 17

Продолжение примера 6

Конъюнкцию выразим по формуле:

Отрицание выразим по формуле:

Продолжение примера 6 Конъюнкцию выразим по формуле: Отрицание выразим по формуле:

Слайд 18

Продолжение примера 6

Убедимся в истинности равенства:

Продолжение примера 6 Убедимся в истинности равенства:

Слайд 19

Это следует из того, что через стрелку Пирса можно выразить функции ФП

Это следует из того, что через стрелку Пирса можно выразить функции ФП
системы:

Пример 7

Система

- функционально полна.

Слайд 20

Продолжение примера 7

Дизъюнкцию выразим по формуле:

Отрицание выразим по формуле:

Продолжение примера 7 Дизъюнкцию выразим по формуле: Отрицание выразим по формуле:

Слайд 21

Продолжение примера 7

Убедимся в истинности равенства:

Продолжение примера 7 Убедимся в истинности равенства:

Слайд 22

то система Σ - функциональна полна.

Теорема 1

Если через функции системы Σ можно

то система Σ - функциональна полна. Теорема 1 Если через функции системы
выразить функции булева базиса ,

Тогда говорят, что система Σ - сводится к системе Σ0:

Слайд 23

Следствие

Следствие

Слайд 24

то система Σ - функциональна полна.

Теорема 2

Если через функции системы Σ можно

то система Σ - функциональна полна. Теорема 2 Если через функции системы
выразить функции некоторой функционально полной системы
,

Слайд 25

Следствие

Таким образом, доказательство функциональной полноты произвольной системы функций можно строить путем сведения

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

Слайд 26

Функциональная полнота в слабом смысле

Система функций Σ называется функционально полной в слабом

Функциональная полнота в слабом смысле Система функций Σ называется функционально полной в
смысле (сФП),

если она будет функционально полной после добавления констант 0 и 1.

Имя файла: ДМ.9.-Замкнутые-классы.pptx
Количество просмотров: 23
Количество скачиваний: 0