Xreferat.com » Рефераты по математике » Математическая логика

Математическая логика

Математическая логика с функциями Математическая логикаЇ:


Математическая логика.


2.5.2 Функция Вебба (Пирса)


Математическая логика


Аксиомы: Математическая логика.

Коммутативность: Математическая логика.

Формулы преобразования функций Математическая логика Ї через ↓:


Математическая логика.


2.5.3 Функция импликации


Математическая логика


Аксиомы: Математическая логика.

Импликация обладает свойством коммутативности в виде:

Математическая логика;

ассоциативность не выполняется.

Формулы преобразования функций Математическая логика Ї через →:


Математическая логика.


2.5.4 Функция Шеффера


Математическая логика


Аксиомы: Математическая логика.

Свойство коммутативности верно только для двух переменных:


Математическая логика


ассоциативность не выполняется.

Формулы преобразования:


Математическая логика

3. Системы функций алгебры логики


3.1 Функциональная полнота


Алгебра над множеством логических функций с двумя бинарными операциями Математическая логика и Математическая логика называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:


Математическая логика


а также соотношения булевой алгебры, относящиеся только к конъюнкции и константам (с конъюнкцией).

Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:


Математическая логика

Математическая логика


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

Полином вида: Математическая логика, где Математическая логика есть либо 1, либо переменная, либо конъюнкция различных переменных, Математическая логика при Математическая логика, называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на


Математическая логика

где ki – коэффициенты, принимающие значения 0 или 1: Математическая логика.


3.2 Класс линейных функций (К Л)


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


Математическая логика.


Количество линейных функций равно Математическая логика, где п – число перемен-ных.

Для п = 2 их 8:


Математическая логика


3.3 Класс функций, сохраняющих ноль (К 0)


Если булева функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль: Математическая логика


3.4 Класс функций, сохраняющих единицу (К 1)


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


3.5 Класс монотонных функций (К м)


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


3.6 Класс самодвойственных функций (К с)


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


Математическая логика


Например, конъюнкция и дизъюнкция двойственны друг другу, отрицание двойственно самому себе.

Функция, совпадающая со своей двойственной, называется самодвойственной.

Самодвойственная функция на противоположных наборах Математическая логика и Математическая логика принимает противоположные значения. Противоположными являются наборы, сумма десятичных эквивалентов которых равна 2n – 1, где п – количество переменных, от которых зависит функция.

Распределение булевых функций двух переменных по классам


Функция К л К 0 К 1 К м К с
f 0 * *
*
f 1
* * *
f 2
*


f 3 * * * * *
f 4
*


f 5 * * * * *
f 6 * *


f 7
* * *
f 8 - - - - -
f 9 *
*

f 10 *


*
f 11

*

f 12 *


*
f 13

*

f 14 - - - - -
f 15 *
* *

3.7 Принцип двойственности


Если в формуле алгебры логики F заменить знаки всех логических функций на знаки двойственных функций, то получится двойственная формула F *, реализующая функцию, двойственную той, которая реализуется формулой F. При этом, если формулы равны F 1 = F 2, то верно равенство двойственных формул Математическая логика, которое называется двойственным предыдущему. Например, равенства, являющиеся двойственными друг другу:


Математическая логика и Математическая логика;

Математическая логика и Математическая логика;

Математическая логика и Математическая логика;

Математическая логика и Математическая логика;

Математическая логика и Математическая логика.


3.8 Полнота функций алгебры логики


Суперпозицией функций Математическая логика называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных, а формулой называется выражение, описывающее эту суперпозицию.

Например, суперпозицию функций f1, f2, f3 можно задать формулой


Математическая логика.


Если f1 обозначает дизъюнкцию, f2 – конъюнкцию, а f3 – сложение по mod 2, то последняя формула примет вид:


Математическая логика.


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

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

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


3.9 Теорема Поста – Яблонского (критерий функциональной полноты)


Для того, чтобы система ФАЛ Математическая логика была полной необходимо и достаточно, чтобы она содержала функцию:

1) не сохраняющую ноль;

2) не сохраняющую единицу;

3) нелинейную;

4) немонотонную;

5) несамодвойственную.

Примерами функционально полных систем являются, например, системы:


Математическая логика.


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

Полная система ФАЛ называется базисом,если теряется полнота Ф при удалении хотя бы одной функции системы.

К базису относятся системы функций:

базис 1: Математическая логика;

базис 2: Математическая логика;

базис 3: Математическая логика;

базис 4: функция Шеффера: x1 | x2;

базис 5: функция Пирса (Вебба): x1 ↓ x2.

Базис 1 – избыточный, базисы 4 и 5 – минимальные (удаление хотя бы одной функции превращает систему ФАЛ в неполную).

При исследовании полноты систем функций удобно пользоваться таблицей, которую называют критериальной. Эта таблица имеет пять столбцов, каждый из которых соответствует одному из пяти классов, а строки таблицы соответствуют функциям исследуемой системы. На пересечении строки таблицы, соответствующей функции f, и столбца, соответствующего классу К, ставится знак плюс, если функция Математическая логика, и минус, если Математическая логика. Система функций полна тогда и только тогда, когда в каждом столбце содержится хотя бы один знак минус.

Пример.

Является ли система булевых функций Математическая логика Математическая логикаполной? Если является, то выписать все возможные базисы.

Рассмотрим функцию Математическая логика.

1. Исследуем ее принадлежность к классу К0:


Математическая логика.


Следовательно, Математическая логика.

2. Исследуем принадлежность функции к классу К1:


Математическая логика.


Следовательно, Математическая логика.

3. Установим, является ли функция f1 линейной. Используем метод неопределенных коэффициентов. Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:


Математическая логика.


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


Математическая логика, Математическая логика, Математическая логика.


Следовательно, Математическая логика.

Зафиксируем набор 100:


Математическая логика,

Математическая логика,

Математическая логика.

Следовательно, Математическая логика.

Фиксируем набор 010:


Математическая логика,

Математическая логика


Фиксируем набор 001:


Математическая логика

Математическая логика.


Следовательно, функция (по нашему предположению) может быть представлена полиномом первой степени вида:


Математическая логика.


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

4. Исследуем заданную функцию на самодвойственность.

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

Построим таблицу: Математическая логика; вычислим значения функции на оставшихся наборах:


Математическая логика Математическая логика:

(000)

0

(001)

1

(010)

2

(011)

3

(100)

4

(101)

5

(110)

6

(111)

7

0 1 0 1 0 1 1 0

На наборах 0 и 7, 1 и 6 функция принимает одинаковые значения. Следовательно Математическая логика.

5. Проверим принадлежность заданной функции f1 классу монотонных функций. Из таблицы видно: 001< 010, но Математическая логика. Следовательно, функция Математическая логика.

Рассмотрим функцию Математическая логика.

1. Принадлежность функции классу К0:


Математическая логика.


Следовательно, Математическая логика.

2. Принадлежность функции классу К1:


Математическая логика.


Следовательно, Математическая логика.

3. Принадлежность функции классу К л.

Предполагаем, что


Математическая логика.


Фиксируем набор 0000:


Математическая логика,

Математическая логика, Математическая логика.

Фиксируем набор 1000:


Математическая логика,

Математическая логика.


Фиксируем набор 0100:


Математическая логика,

Математическая логика.


Фиксируем набор 0010:


Математическая логика,

Математическая логика.


Фиксируем набор 0001:


Математическая логика.

Математическая логика.


Окончательно получаем


Математическая логика.


Это равенство на других 11 наборах не выполняется. Действительно, для набора 1111 имеем


Математическая логика, Математическая логика, т.е. Математическая логика.

Следовательно, Математическая логика.


4. Принадлежность функции классу самодвойственных функций.

Строим таблицу:


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0

Из таблицы видно, что на наборах 1 и 14, 2 и 13, 7 и 8 функция принимает одинаковые значения. Следовательно, Математическая логика.

5. Принадлежность функции классу монотонных функций.

Из таблицы видно, что 1000>0000, а Математическая логика. Следовательно, Математическая логика.

Строим критериальную таблицу:



К 0 К 1 К л К с К м
f 1 + - - - -
f 2 - - - - -

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


Математическая логикаМатематическая логика


Найдем все возможные базисы. По критериальной таблице составим к.н.ф. К, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве слагаемых символы тех функций, которые не входят в класс, соответствующий столбцу. В данном случае имеем


Математическая логика.

Используя законы и свойства дизъюнкции и конъюнкции, приведем к.н.ф. К к д.н.ф. D, в которой упрощение Математическая логика невозможно. В нашем случае получим


Математическая логика.


По полученной д.н.ф. D выпишем подмножества функций, соответствующие слагаемым д.н.ф. D. Это и будут искомые базисы. В нашем случае имеется два базиса:


Математическая логика.


Минимальная форма представления ФАЛ содержит минимальное количество термов и переменных в термах (т.е. не допускает никаких упрощений).

Пример.


Математическая логика,

Математическая логика - минимальная форма.

4 Способы представления функций алгебры логики


Для булевых функций существуют различные способы представления: таблица истинности, числовой, аналитический.

Пример.

Пусть функция Математическая логика задана таблицей истинности:


№ набора х1 х2 х3

Математическая логика

0 0 0 0 1
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 1
5 1 0 1 0
6 1 1 0 0
7 1 1 1 0

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

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

Запись


Математическая логика


представляет собой аналитическое представление булевой функции.

Можно в выражении функции вместо конъюнкций термов записать соответствующие двоичные наборы. Тогда получим:


Математическая логика.

Булеву функцию можно задать с помощью единичного п – мерного куба (рис. 7).


Математическая логика

Рис. 7


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

На рис. 7 показаны п-мерные кубы для булевых функций: двух переменных (а), трех переменных (б), четырех переменных (в).

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


Математическая логика


примет вид:

Математическая логика

Рис. 8


Часто для изображения булевых функций двух и трех переменных используют прямоугольную систему координат:


Математическая логика


Рис. 9


Изображение булевых функций числа переменных более трех в этом случае невозможен.

В методе минимизации булевых функций Квайна – Мак-Класки используется кубическое представление булевых функций (аналог п-мерных кубов).

Терм максимального ранга принято называть 0-кубом и обозначать К 0. Если два 0-куба из комплекса К 0 различаются только по одной координате, то они образуют куб (отрезок) K 1.

Пример.

Для

Математическая логика Математическая логика.

5. Минимизация булевых функций


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

Любой конъюнктивный терм (элементарная конъюнкция) или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции

Элементарная конъюнкция (конъюнктивный терм), в которой удален один или несколько первичных термов, называется простой импликантой.

Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.


5.1 Метод Квайна


На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:


Математическая логика.


Процедура продолжается до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом. В результате получают некоторое количество простых

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: