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

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

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}.

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

Замечание.

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

Таблица 5.04

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

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

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

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

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

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

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

Работы в этом направлении начинал ученик Лукасевича Ясковский, но первую общепринятую систему естественной дедукции в 1935 году предложил в своей диссертации Генцен.

Аксиом в естественной дедукции нет, а правила вывода можно разделить на две группы: пра­вила введения (обозначаются буквой i — «introduce » — слева соответствующий значок отсутствует, справа присутствует), и правила исключения (обозначают­ся буквой е — «eliminate », справа соответствующий значок отсутствует, слева присутствует) для каждого логического значка и квантора .

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

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