Функционально замкнутые классы булевых функций. Замкнутые классы T0 , T1.

Класс (множество) булевых функций функционально замкнут, если вместе с функциями он содержит все их суперпозиции. Класс всех булевых функций замкнут. Класс функций от одной переменной замкнут. Класс булевых функций от двух переменных не замкнут, так как если взять две функции от двух переменных f = x ~ y и g = t & p, то их четыре суперпозиции: (t & p) ~ y, x ~ (t & p), (x ~ y) & p и t & (x ~ y) будут зависеть от трёх переменных.

Класс T - это класс функций, хранящих ноль. Функция принадлежит T , если во всех нулях она равна нулю. Например, из 16 функций от двух переменных функции: f0, …, f7 принадлежат T , так как при x = 0 и y = 0 эти функции имеют значение ноль. Тогда как функции: f8, …, f15 не принадлежат T , так как при x = 0 и y = 0 эти функции имеют значение единица.

Класс T - это класс функций, хранящих единицу. Функция принадлежит T , если во всех единицах она равна единице. Например, из 16 функций от двух переменных восемь функций с нечётными номерами: f1, f3,…, f13, f15 принадлежат T , так как при x = 1 и y = 1 эти функции имеют значение единица. Тогда как восемь функций с чётными номерами: f0, f2, …, f12, f14 не принадлежат T , так как при x = 1 и y = 1 эти функции имеют значение ноль.

 

Теорема Поста, её необходимость. Таблица Поста.

Теорема Поста: для того, чтобы система булевых функций F = {F1, …, Fm} была полной, необходимо и достаточно, чтобы для каждого из классов T , T , S, L и M нашлась функция Fj из системы F, не принадлежащая этому классу.

Доказательство необходимости: Классы T , T , S, L и M попарно различны и не совпадают с классом всех булевых функций. Если бы все функции системы F принадлежали какому-либо из этих классов, то в силу замкнутости этого класса система F не была бы полной. Необходимость теоремы доказана.

Функция	T	T	S	L	M
	+	+	-	-	+
	+	+	-	-	+
	-	-	+	+	-

 

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

T

+

+

+

+

+

+

+

+

-

-

-

-

-

-

-

-

T

-

+

-

+

-

+

-

+

-

+

-

+

-

+

-

+

S

-

-

-

+

-

+

-

-

-

-

+

-

+

-

-

-

L

+

-

-

+

-

+

+

-

-

+

+

-

+

-

-

+

M

+

+

-

+

-

+

-

+

-

-

-

-

-

-

-

+

 

Независимая система функций и базис функционально замкнутого класса.

Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система { , } независима, так как T , T , L, L. Для определения независимости функций надо найти два класса из пяти такие (можно по таблице Поста), что одна функция принадлежит первому классу и не принадлежит второму, а вторая функция наоборот принадлежит второму классу и не принадлежит первому. Система { , , } зависима, смотри выше законы Моргана.

Независимая система функций называется базисом функционально замкнутого класса, если всякая функция из этого класса есть суперпозиция функций из этой системы. Системы функций {&, } и { , } – базисы класса всех булевых функций.

Система функций {~, 0} – базис класса L. Это независимая система функций, так как 0 принадлежит классу M, а ~ не принадлежит классу M, 0 не принадлежит классу T , а ~ принадлежит классу T . Каждая линейная функция выражается суперпозициями функций + и , поскольку x = x + 1. Но эти функции в свою очередь выражаются через 0 и ~: x = x ~ 0, x + y = (x ~ y).

 

Минимизация ДНФ. Метод минимизирующих карт.

Минимизация проводится в классе ДНФ методом минимизирующих карт. Функция должна быть задана её таблицей истинности или её СДНФ. Минимизирующая карта имеет 2 строк, где n – число переменных функции, и на (2 - 1) столбцов. Например, для n = 3:

x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z
x	y	z	x y	x z	y z	x y z

Использование карты основано на следующем: если какая-то конъюнкция последнего столбца карты не входит в СДНФ функции, то все конъюнкции этой строки не входят ни в одну ДНФ функции. Если бы какая-то конъюнкция строки вошла в ДНФ функции, то при получении из этой ДНФ СДНФ эту конъюнкцию расщепили бы по недостающим в ней переменным и получили бы конъюнкцию последнего столбца.

 

Аксиоматические теории. Определения и свойства исчисления высказываний.

Исчисление высказываний – это пример аксиоматической теории. ИВ определяется следующим образом:

1. Алфавит ИВ – это высказывательные переменные, скобки: (,) и логические символы и . Любой набор символов алфавита ИВ (даже бессмысленный) – это выражение ИВ.

2. Имеется подмножество выражений, называемое формулами ИВ. Формулы ИВ: а) все высказывательные переменные – это формулы; б) если A и B формулы, то A и A B тоже формулы. Формулы ИВ – это подмножество формул логики высказываний, содержащих только логические символы и .

3. Выделено некоторое подмножество формул, называемое аксиомами ИВ. Каковы бы не были формулы A, B и C, следующие формулы являются аксиомами ИВ:

A1. A (B A);

A2. (A (B C)) ((A B) (A C));

A3. ( B A) (( B A) B).

Выражения A1 – A3 называются схемами аксиом, поскольку каждое из них порождает бесконечное множество аксиом ИВ. Например, формула X (Y X) есть аксиома, полученная по схеме A1, а формула ( A A) (( A A) A) – аксиома ИВ, полученная по схеме A3.

4. Имеется правило вывода ИВ, позволяющее из предыдущих формул вывода получать последующие. Выводом в ИВ называется всякая последовательность формул ИВ (шагов вывода) такая, что любая формула есть либо аксиома или теорема ИВ, либо получена из предыдущих формул вывода с помощью правила вывода ИВ.

Формула T называется теоремой ИВ, если существует вывод, в которой эта формула является последней. Этот вывод называется выводом теоремы T ИВ: T. Слева от символа аксиомы ИВ, теоремы ИВ и то, что получено из них по правилу вывода ИВ, не записывается.

Правило вывода m.p.(modus ponens): если в выводе есть две формулы вида А В и А, то после них в выводе можно писать формулу В. Считается, что формула В получена по правилу m.p. из формул А и А В. Правило записывается так: или А, А В В. Порядок формул А и А В в выводе не важен (A может встретиться в выводе раньше А В, а может и позже), но формулу B нельзя писать раньше, чем А и А В появятся в выводе.

Все аксиомы ИВ – это тавтологии, что можно проверить по их таблице истинности. По правилу m.p. из тавтологий можно получить только тавтологии.