Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

3. x₁ x₂ – номер инверсионного набора – 00₂ – 0₁₀, полная дизъюнкция обозначается D₀.

4. – номер инверсионного набора – 101₂ – 5₁₀, полная дизъюнкция обозначается D₅.

Определение.

Полная конъюнкция, принимающая значение 1 только на одном наборе аргументов, соответствующем её индексу, и значение 0 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией единицы.

Определение.

Полная дизъюнкция, принимающая значение 0 только на одном наборе аргументов, соответствующем её индексу, и значение 1 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией нуля.

Замечание.

Значение булевой функции для конкретных значений аргументов удобно обозначить символом  с индексом в виде десятичного числа, соответствующего двоичному набору аргумента, например, f(1,1) = ₃, f(1,0,1) = ₅.

Примеры.

С учётом введённых определений булеву функцию f(x_1, x₂) можно записать {с учетом разложения в СДНФ или СКНФ} в следующем виде:

.

Замечание.

Приведенный пример показывает, каким образом можно перейти от табличного представления булевой функции к её аналитическому представлению. При табличном представлении функции задаются её значения _i для каждого набора аргументов, определяемого индексом i. Так как в силу определения операции конъюнкции имеем 0K_i = 0 и 1K_i = K_i, то для представления функции в виде СДНФ нужно выписать дизъюнкцию всех тех конституэнт единицы K_i, для которых _i = 1. Учитывая также, что 0D_i=D_i и 1D_i=1, СКНФ получается как конъюнкция всех тех конституэнт нуля D_i, для которых значение функции _i равно 0.

48.Законы двойственности.

Определение.

Учитывая определённую симметрию операций  и  в аксиоматике алгебры Буля логических высказываний и операций, операции  и  называются двойственными.

Определение.

Формулы и ^* называются двойственными, если одна получается из другой заменой каждой операции на двойственную.

Примеры.

1. двойственна .

2. двойственна .

3. двойственна .

Замечание.

Как для операций, так и для формул отношение двойственности взаимно, то есть если ^* двойственна , то и, наоборот, двойственна ^*.

Лемма.

Если формулы (X₁, X₂,…, X_n) и ^*(X₁, X₂,…, X_n) двойственны, а X₁, X₂,…, X_n – все входящие в них элементарные высказывания, то (X₁, X₂,…, X_n) равносильна ^* .

Доказательство:

Доказательство непосредственно следует из законов де Моргана.

Следствие из леммы.

Частным случаем леммы являются следующие соотношения:

; (5)

. (6)

Они являются обобщением законов де Моргана и называются законами Клода Шеннона.

Задание.

Доказать законы Клода Шеннона и лемму.

Теорема (закон двойственности).

Если и равносильны, то и двойственные им формулы ^*и ^* также равносильны.

Доказательство:

Пусть (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) – равносильные формулы, а X₁, X₂,…, X_n – входящие в них элементарные высказывания. Тогда, в силу леммы, ^*(X₁, X₂,…, X_n) равносильна , а ^*(X₁, X₂,…, X_n) равносильна .

Из равносильности формул (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) следует равносильность формул и , так как в силу определения равносильности (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) принимают одинаковые значения при любых значениях переменных X₁, X₂,…, X_n, а, следовательно, и при значениях . Следовательно, формулы и также равносильны, далее, в силу леммы формула ^*(X₁, X₂,…, X_n) равносильна формуле , а формула ^*(X₁, X₂,…, X_n) равносильна формуле . Следовательно, формулы ^*(X₁, X₂,…, X_n) и ^*(X₁, X₂,…, X_n) равносильны между собой, что и требовалось доказать.

Замечание.

1. Если, применяя к формуле дистрибутивные преобразования на основании первого дистрибутивного закона мы получим формулу , то переход от двойственной формулы ^* к двойственной формуле ^* осуществляется дистрибутивными преобразованиями на основании второго дистрибутивного закона.

2. Переход от ^*к ^*называется преобразованием, двойственным преобразованию, переводящему в .

Теорема. (Формулы разложения Клода Шеннона.)

Для любой булевой функции f(x_1, x₂,…, x_n) имеют место следующие разложения по переменным x_1, x₂,…, x_k {1 k  n}:

f(x_1, x₂,…, x_n) = , (7)

где 1) 1 k  n;

2) дизъюнкция берётся по всем наборам (a₁, a₂,…, a_k), {a_i{0,1}}, .

Это разложение называется дизъюнктивным разложением булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k {1 k  n}.

,(8)

где 1) 1 k  n;

2) конъюнкция берётся по всем наборам (a₁, a₂,…, a_k), {a_i{0,1}},

Это разложение называется конъюнктивным разложением булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k , {1 k  n}.

Оба соотношения (7) и (8) также называются формулами разложения Клода Шеннона.

Доказательство:

При k = 1 формулы (7) и (8) имеют следующий вид:

; (9) . (10)

Докажем формулу (9).

При x₁ = 1 имеем:

– равенство очевидно.

При x₁ = 0 имеем:

– равенство очевидно.

Таким, образом доказана справедливость соотношения (9). Подобным образом можно разложить функцию по другой переменной, например по x₂. Тогда для формулы (9) это разложение имеет вид:

. (11)

Подставляя, где записано разложение по x₁, значение x₂=1 и затем x₂=0, легко убедится в справедливости и соотношения (11). Если продолжить процесс разложения по остальным переменным (до k включительно (1 k  n)), то получим соотношение (7). Аналогично доказывается формула (8). Теорема доказана.

Замечания.

1. При k = n дизъюнктивное разложение булевой функции {формула (7)} имеет вид:

……………………………….. (12)

а конъюнктивное разложение {формула (8)} имеет вид:

………………………………………. (13)

2. Из полученных соотношений видно, что дизъюнктивное разложение булевой функции при k = n { см. формулу (12)} есть не что иное, как совершенная дизъюнктивная нормальная форма {см. формулу (3)}, а конъюнктивное разложение булевой функции при k = n {см. формулу (13)} есть совершенная конъюнктивная нормальная форма {см. формулу (4)}. Таким образом, СДНФ и СКНФ являются частными случаями равенств (7) и (8), являющихся соответственно дизъюнктивным и конъюнктивным разложениями булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k , {1 k  n}.

49.Основные свойства булевых функций.

Замечание.

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

Таблица 5.04

1. Элементы теории доказательств.

50.Естественная дедукция.

Логические заключения, которые используют люди в своих рассуждениях, определяются рядом элементарных правил, сформулированных ещё Аристоте­лем. Формализация этих правил приводит к различным формальным системам для логических языков.

Определение.

Фор­мальная система для языка логики предикатов первого порядка, называется естественной дедукцией (natural deduction).

Определение.

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

Характеристики

Список файлов лекций